<p>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.</p>

<p>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. </p>

CC BY-SA 3.0
2013-06-28T17:09:04.947Z
Thanks. And yes, the first conditions are there precisely to ensure non-emptiness.
Austin Buchanan
CC BY-SA 3.0
2013-06-28T04:14:45.017Z
2013-06-28T04:14:45.017Z
Sasho Nikolov
<p>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:</p>

<ol>
<li>$\emptyset \in \mathcal{I}$, and</li>
<li>$I_1 \subset I_2 \in \mathcal{I}$ implies $I_1 \in \mathcal{I}$.</li>
</ol>

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

<ol>
<li>$I \in \mathcal{I}$, and</li>
<li>$I_1 \supset I_2 \in \mathcal{I}$ implies $I_1 \in \mathcal{I}$.</li>
</ol>

<p>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?</p>

CC BY-SA 3.0
2013-06-29T13:58:20.250Z
This is often referred to as the dual system.
Suresh Venkat
CC BY-SA 3.0
2013-06-29T15:55:55.417Z
@SureshVenkat do you have a reference for that?
Austin Buchanan
CC BY-SA 3.0
2013-06-29T19:30:55.257Z
As @SashoNikolov points out, this terminology comes from poset land
Suresh Venkat
<co.combinatorics><independence><set-system>
Dual/complement of independence system
Austin Buchanan
# Dual/complement of independence system

(Asked by: username_0 on 2013-06-28)

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?

**Tags:** co.combinatorics, independence, set-system

> **Comments:**
> **username_1**: This is often referred to as the dual system.  
> **username_0**: @SureshVenkat do you have a reference for that?  
> **username_1**: As @SashoNikolov points out, this terminology comes from poset land  

---

## 1 answers

### Answer by username_2 on 2013-06-28. Score: 5 | Accepted answer

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.

> **Comments:**
> **username_0**: Thanks. And yes, the first conditions are there precisely to ensure non-emptiness.  

---

