Definition:Independence System

From ProofWiki
Jump to navigation Jump to search

Definition

Let $S$ be a finite set.

Let $\mathscr F$ be a set of subsets of $S$ satisfying the independence system axioms:

\((\text I 1)\)   $:$   \(\ds \O \in \mathscr F \)      
\((\text I 2)\)   $:$     \(\ds \forall X \in \mathscr F: \forall Y \subseteq S:\) \(\ds Y \subseteq X \implies Y \in \mathscr F \)      


The ordered pair $I = \struct {S, \mathscr F}$ is called an independence system on $S$.


Also known as

When the context is obvious, $I = \struct {S, \mathscr F}$ is simply called an independence system.


Sources