# matroid independence axioms

Hassler Whitney’s definition of a matroid^{} was based upon the idea of independent sets^{} and was given in terms of the following three axioms:

A finite set^{} $E$ along with a collection^{} $\mathcal{I}$ of subsets of $E$ is a matroid if $M=(E,\mathcal{I})$ meets the following criteria:

(I1) $\mathrm{\varnothing}\in \mathcal{I}$;

(I2) If ${I}_{1}\in \mathcal{I}$ and ${I}_{2}\subseteq {I}_{1}$, then ${I}_{2}\in \mathcal{I}$;

(I3) If ${I}_{1},{I}_{2}\in \mathcal{I}$ with $$, then there is some $e\in {I}_{2}$ such that ${I}_{1}\cup \{e\}\in \mathcal{I}$.

The third axiom, (I3), is equivalent^{} to the following alternative axiom:

(I3*) If $S,T\in \mathcal{I}$ and $S,T\subset U\subset E$ and $S$ and $T$ are both maximal subsets of $U$ with the property that they are in $\mathcal{I}$, then $|S|=|T|$.

###### Proof.

Suppose (I3) holds, and that $S$ and $T$ are maximal independent subsets of $A\subseteq E$. Also assume, without loss of generality, that $$. Then there is some $e\in T$ such that $S\cup \{e\}\in \mathcal{I}$, but $S\subset S\cup \{e\}\subseteq A$, contradicting maximality of $S$.

Now suppose that (I3*) holds, and assume that $S,T\in \mathcal{I}$ with $$. Let $A=S\cup T$. Then $S$ cannot be maximal in $A$ by (I3*), so there must be elements ${e}_{i}\in A$ such that $S\cup \{{e}_{i}\}\in \mathcal{I}$ is maximal, and by construction these ${e}_{i}\in T$. So (I3) holds.
∎

Title | matroid independence axioms |
---|---|

Canonical name | MatroidIndependenceAxioms |

Date of creation | 2013-03-22 14:44:05 |

Last modified on | 2013-03-22 14:44:05 |

Owner | sgraves (6614) |

Last modified by | sgraves (6614) |

Numerical id | 6 |

Author | sgraves (6614) |

Entry type | Proof |

Classification | msc 05B35 |

Synonym | matroid independent sets |