A matroid (A,Σ) is a set A and a collection of subsets Σ such that ∅ ∈ Σ If A ⊆ B ∈ Σ then A ∈ Σ. If A, B ∈ Σ and |A| < |B|, there is some b ∈ B such that A ∪ {b} ∈ Σ.
Dependent: Sets in Σ are called
independent; all other sets are called
dependent
Bases: A maximal set in Σ is called a
basis.
Circuits: A minimal dependent set is
called a circuit
A matroid (A,ℬ) is a set A and a collection of subsets ℬ such that
ℬ ≠ ∅ If U, V ∈ ℬ and u ∈ U \ V then there is some v ∈ V \ U such that (U\{u}) ∪ {v} ∈ ℬ.
A closure operator on a set A is a function ϕ : P(A) → P(A) such that U ⊆ ϕ(U) ϕ2 = ϕ If U ⊆ V then ϕ(U) ⊆ ϕ(V).
A matroid is a closure operator ϕ : P(A) → P(A) such that If x ∈ ϕ(U∪{y}) \ ϕ(U) then y ∈ ϕ(U∪{x}) \ ϕ(U).
Flats: A set such that ϕ(U) = U is called
closed or flat. The set of flats of a
closure operator is denoted 𝒞ϕ
A matroid is a closure operator ϕ : P(A) → P(A) such that
A ∈ 𝒞ϕ If U, V ∈ 𝒞ϕ then U ∩ V ∈ 𝒞ϕ. U ∈ 𝒞ϕ then for each x ∈ Uc there is exactly one Vx ∈ 𝒞ϕ such that x ∈ Vx and U ⊆ Vx, where U is maximal in Vx.
Unions: Flats are almost never closed
under unions
A matroid is a pair (A,ρ) where ρ : P(A) → ℕ ≥ 0 satisfies
ρ(X) ≤ |X| ρ(X∪Y) + ρ(X∩Y) ≤ ρ(X) + ρ(Y) If X ⊆ Y then ρ(X) ≤ ρ(Y)
We call ρ the rank function.
Nullity: We call |X| − ρ(X) the
nullity of X.
The collection of all flats forms a lattice