Editing Matroid (section)

=== Independent sets <span class="anchor" id="independent_sets_anchor"></span>===
In terms of independence, a finite matroid <math> M </math> is a pair <math> (E, \mathcal{I})</math>, where <math> E </math> is a [[finite set]] (called the ''ground set'') and <math> \mathcal{I} </math> is a [[family of sets|family]] of [[subset]]s of <math> E </math> (called the ''independent sets'') with the following properties:<ref name=w7-9>{{harvtxt|Welsh|1976|pp=7–9}}, Section&nbsp;1.2, "Axiom Systems for a Matroid".</ref>

* (I1)  The [[empty set]] is independent, i.e., <math> \emptyset \in \mathcal{I}</math>.

* (I2)  Every subset of an independent set is independent, i.e., for each <math> A' \subseteq A \subseteq E</math>, if <math> A \in \mathcal{I} </math> then <math> A' \in \mathcal{I}</math>. This is sometimes called the ''hereditary property'', or the ''downward-closed'' property.

* (I3) If <math>A</math> and <math>B</math> are two independent sets (i.e., each set is independent) and <math>A</math> has more elements than <math> B</math>, then there exists <math> x \in A \setminus B</math> such that <math> B \cup \{ x \} </math> is in <math> \mathcal{I}</math>. This is sometimes called the ''augmentation property'' or the ''independent set exchange property''.

The first two properties define a combinatorial structure known as an [[independence system]] (or [[abstract simplicial complex]]). Actually, assuming (I2), property (I1) is equivalent to the fact that at least one subset of <math>E</math> is independent, i.e., <math>\mathcal{I}\neq\emptyset</math>.