Matroids

Why

We generalize the notion of linear dependence.

Definition

A matroid is a finite subset algebra satisfying

Any subset of a distinguished set is distinguished.
For two distinguished subsets of nonequal cardinality, there is an element of the base set in the complement of the smaller set in the bigger set whose singleton union with the smaller set is a distinguished set.

We call the distinguished subsets independent subsets and we call the undistinguished subsets the dependent subsets.

Notation

We follow the notation of subset algebras, but use $M$ for the base set, a mnemonic for matroid, and $\mathcal{I} $ for the distinguished sets, a menomic for independent.

Let $(M, \mathcal{I} )$ a matroid. We denote the properties by

$A \in \mathcal{I} \land B \subset A \implies B \in \mathcal{I} $.
$A, B \in \mathcal{I} \land \num{A} < \num{B} \implies \exists x \in M: (A \cup \set{x}) \in \mathcal{I} $