Zu einer endlichen Menge ${\displaystyle {}E}$ heißt eine Teilmenge

${\displaystyle {}{\mathcal {M}}\subseteq {\mathfrak {P}}\,(E)\,}$

ein Matroid, wenn folgende Bedingungen erfüllt sind.

1. Es ist ${\displaystyle {}\emptyset \in {\mathcal {M}}}$.
2. Aus ${\displaystyle {}A\in {\mathcal {M}}}$ und ${\displaystyle {}B\subseteq A}$ folgt ${\displaystyle {}B\in {\mathcal {M}}}$.
3. Wenn ${\displaystyle {}A,B\in {\mathcal {M}}}$ mit

   ${\displaystyle {}{\#\left(A\right)}={\#\left(B\right)}+1\,,}$

   so gibt es ein ${\displaystyle {}a\in A\setminus B}$ derart, dass ${\displaystyle {}B\cup \{a\}\in {\mathcal {M}}}$.