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$ Jun 29, 2013 at 13:58
  • $\begingroup$ @SureshVenkat do you have a reference for that? $\endgroup$ Jun 29, 2013 at 15:55
  • $\begingroup$ As @SashoNikolov points out, this terminology comes from poset land $\endgroup$ Jun 29, 2013 at 19:30

1 Answer 1


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$ Jun 28, 2013 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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