# Dual/complement of independence system

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?

• This is often referred to as the dual system. – Suresh Venkat Jun 29 '13 at 13:58
• @SureshVenkat do you have a reference for that? – Austin Buchanan Jun 29 '13 at 15:55
• As @SashoNikolov points out, this terminology comes from poset land – 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.

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