Leigh.Samphier/Sandbox/Matroid satisfies Rank Axioms

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a finite set.

Let $\rho : \powerset S \to \Z$ be a mapping from the power set of $S$ to the integers.


The following are equivalent:

Condition 1

$\rho$ satisfies the rank axioms:

\((R1)\)   $:$   \(\displaystyle \map \rho \O = 0 \)             
\((R2)\)   $:$     \(\displaystyle \forall X \in \powerset S \land y \in S:\) \(\displaystyle \map \rho X \le \map \rho {X \cup \set y} \le \map \rho X + 1 \)             
\((R3)\)   $:$     \(\displaystyle \forall X \in \powerset S \land y, z \in S:\) \(\displaystyle \map \rho {X \cup \set y} = \map \rho {X \cup \set z} = \map \rho X \implies \map \rho {X \cup \set{y,z} } = \map \rho X \)             


Condition 2

$\rho$ satisfies the rank axioms:

\((\text R 1')\)   $:$     \(\displaystyle \forall X \in \powerset S:\) \(\displaystyle 0 \le \map \rho X \le \size X \)             
\((\text R 2')\)   $:$     \(\displaystyle \forall X, Y \in \powerset S:\) \(\displaystyle X \subseteq Y \implies \map \rho X \le \map \rho Y \)             
\((\text R 3')\)   $:$     \(\displaystyle \forall X, Y \in \powerset S:\) \(\displaystyle \map \rho {X \cup Y} + \map \rho {X \cap Y} \le \map \rho X + \map \rho Y \)             


Condition 3

$\rho$ is the rank function of a matroid on $S$

Proof

$\blacksquare$

Sources