An independence system is a pair $(I,\mathcal{I})$ where $I$ is a (usually finite) ground set and $\mathcal{I}$ is a collection of subsets of $I$ such that:

  1. $\emptyset \in \mathcal{I}$, and
  2. $I_1 \subset I_2 \in \mathcal{I}$ implies $I_1 \in \mathcal{I}$.

I am interested a related, dual notion, where we replace conditions 1 and 2 with:

  1. $I \in \mathcal{I}$, and
  2. $I_1 \supset I_2 \in \mathcal{I}$ implies $I_1 \in \mathcal{I}$.

It is clear that the pair $M=(I,\mathcal{I})$ is an independence system if and only if $\overline{M}=(I,\overline{\mathcal{I}})$ obeys the new conditions, where $\overline{\mathcal{I}} = \{ I\setminus I_0 : I_0 \in \mathcal{I} \}$. However, in my application it is much easier to work with the new conditions. Does this have a name?

  • $\begingroup$ This is often referred to as the dual system. $\endgroup$ – Suresh Venkat Jun 29 '13 at 13:58
  • $\begingroup$ @SureshVenkat do you have a reference for that? $\endgroup$ – Austin Buchanan Jun 29 '13 at 15:55
  • $\begingroup$ As @SashoNikolov points out, this terminology comes from poset land $\endgroup$ – Suresh Venkat Jun 29 '13 at 19:30

The usual terms I know from the theory of posets and lattices are downset and upset (or upper set). Also as the empty set is a subset of every set, I think your first condition is vacuous as long as the system is not empty. Same for the first condition in the second definition.

If a downset is closed under joins (in your case set unions), it is called an ideal. If an upset is closed under meets (in your case set intersections), it is called a filter.

  • $\begingroup$ Thanks. And yes, the first conditions are there precisely to ensure non-emptiness. $\endgroup$ – Austin Buchanan Jun 28 '13 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.