nyuuzyou/wikis huggingface dataset:
Matroid Base Substitution From Fundamental Circuit

== Theorem ==
Let $M = \struct {S, \mathscr I}$ be a matroid.
Let $B$ be a base of $M$.
Let $y \in S \setminus B$.
Let $\map C {y,B}$ denote the fundamental circuit of $y$ in $B$.
Let $x \in B$.
Then:
:$\paren{B \setminus \set x} \cup \set y$ is a base of $M$ $x \in \map C {y,B}$
That is, $y$ can be substituted for $x$ in $B$ to form another base of $M$ $x \in \map C {y,B}$.
== Proof ==
=== Necessary Condition ===
Let $\paren{B \setminus \set x} \cup \set y$ be a base of $M$.
By definition of the fundamental circuit:
:$\map C {y,B} \subseteq B \cup \set y$
and
:$\map C {y,B}$ is dependent
 $x \notin \map C {y,B}$.
Then:
:$\map C {y,B} \subseteq \paren{B \setminus \set x} \cup \set y$
By matroid axiom $( \text I 2)$:
:$\map C {y,B}$ is independent
This contradicts the fact that:
:$\map C {y,B}$ is dependent
It follows that:
:$x \in \map C {y,B}$ 
=== Sufficient Condition ===
We prove the contrapositive statement.
Let $\paren{B \setminus \set x} \cup \set y$ not be a base of $M$.
We have:
From contrapositive statement of Independent Subset is Base if Cardinality Equals Cardinality of Base:
:$\paren{B \setminus \set x} \cup \set y$ is a dependent subset of $M$
From Dependent Subset Contains a Circuit there exists a circuit $C'$:
:$C' \subseteq \paren{B \setminus \set x} \cup \set y \subseteq B \cup \set y$
From Matroid Base Union External Element has Fundamental Circuit:
:$C' = \map C {y,B}$
Hence:
:$x \notin \map C {y, B}$
From Rule of Transposition we have:
:$x \in \map C {y, B} \implies \paren{B \setminus \set x} \cup \set y$ is a base of $M$
== Sources ==
* Chapter $1.$ $\S 9.$ Circuits, Theorem $1$
Category:Matroid Bases
Category:Matroid Circuits
Matroid Bases Iff Satisfies Formulation 1 of Matroid Base Axiom

== Theorem ==
Let $S$ be a finite set.
Let $\mathscr B$ be a non-empty set of subsets of $S$.
Then $\mathscr B$ is the set of bases of a matroid on $S$ $\mathscr B$ satisfies formulation $1$ of base axiom:
== Proof ==
=== Necessary Condition ===
Let $\mathscr B$ be the set of bases of the matroid on $M = \struct{S, \mathscr I}$
=== Sufficient Condition ===
Let $\mathscr B$ satisfy formulation $1$ of base axiom:
</onlyinclude>
== Sources ==
* Chapter $1.$ $\S 5.$ Properties of independent sets and bases
* Chapter $13$ Matroids $\S 13.2$ Other Matroid Axioms, Theorem $13.9$
Category:Matroid Bases
Category:Matroid Bases Iff Satisfies Formulation 1 of Matroid Base Axiom
Matroid Bases Iff Satisfies Formulation 1 of Matroid Base Axiom/Lemma 1

== Theorem ==
Let $S$ be a finite set.
Let $\mathscr B$ be a non-empty set of subsets of $S$ satisfying formulation $1$ of base axiom:
Let $B_1, B_2 \in \mathscr B$.
Let $U \subseteq B_1$ and $V \subseteq B_2$ such that:
:$\card V < \card U$
Let $B_2 \cap \paren{U \setminus V} = \O$.
Then:
:$\exists B_3 \in \mathscr B$:
::$V \subseteq B_3$
::$\card{B_1 \cap B_3} > \card{B_1 \cap B_2}$
== Proof ==
=== Lemma 2 ===
From Larger Set has Larger Set Difference:
:$(1):\quad \card {V \setminus U} < \card {U \setminus V}$
We have:
and
and
We have:
From the contrapositive statement of Cardinality of Empty Set:
:$\paren{B_2 \setminus B_1} \setminus V \ne \O$
Hence:
:$\exists y \in \paren{B_2 \setminus B_1} \setminus V$
From $(\text B 1)$:
:$\exists z \in B_1 \setminus B_2 : \paren{B_2 \setminus \set y} \cup \set z \in \mathscr B$
Let:
:$B_3 = \paren{B_2 \setminus \set y} \cup \set z$
We have:
:
From Finite Set Formed by Substitution has Larger Intersection:
:$\card{B_1 \cap B_3} = \card{B_1 \cap B_2} + 1$
Hence:
:$\card{B_1 \cap B_3} > \card{B_1 \cap B_2}$
Category:Matroid Bases Iff Satisfies Formulation 1 of Matroid Base Axiom
Matroid Bases Iff Satisfies Formulation 1 of Matroid Base Axiom/Lemma 2

== Theorem ==
Let $S$ be a finite set.
Let $\mathscr B$ be a non-empty set of subsets of $S$.
Let $\mathscr B$ satisfy the formulation $1$ of base axiom:
Then:
:$\forall B_1, B_2 \in \mathscr B : \card{B_1} = \card{B_2}$
where $\card{B_1}$ and $\card{B_2}$ denote the cardinality of the sets $B_1$ and $B_2$ respectively.
== Proof ==
:
:$\exists B_1, B_2 \in \mathscr B : \card{B_1} \ne \card{B_2}$
 and from Max Operation Equals an Operand let:
:$\card{B_1 \cap B_2} = \max \set{\card{C_1 \cap C_2} : C_1, C_2 \in \mathscr B : \card{C_1} \ne \card{C_2}}$
 let:
:$\card{B_1} > \card{B_2}$
From Set Difference of Larger Set with Smaller is Not Empty:
:$\exists x \in B_1 \setminus B_2$
From base axiom $(\text B 1)$:
:$\exists y \in B_2 \setminus B_1 : \paren {B_1 \setminus \set x} \cup \set y \in \mathscr B$
Let $B_3 = \paren {B_1 \setminus \set x} \cup \set y$.
From Finite Set Formed by Substitution has Larger Intersection:
:$\card{B_3 \cap B_2} = \card{B_1 \cap B_2} + 1$
From Finite Set Formed by Substitution has Same Cardinality:
:$\card {B_3} = \card {B_1}$
Hence:
:$\card {B_3} \ne \card {B_2}$
This contradicts the choice of $B_1$ and $B_2$ as:
:$\card{B_1 \cap B_2} = \max \set{\card{C_1 \cap C_2} : C_1, C_2 \in \mathscr B : \card{C_1} \ne \card{C_2}}$
It follows that:
:$\forall B_1, B_2 \in \mathscr B : \card{B_1} = \card{B_2}$
Category:Matroid Bases Iff Satisfies Formulation 1 of Matroid Base Axiom
Matroid Bases Iff Satisfies Formulation 1 of Matroid Base Axiom/Necessary Condition

== Theorem ==
Let $M = \struct {S, \mathscr I}$ be a matroid.
Let $\mathscr B$ be the set of bases of the matroid $M$.
Then $\mathscr B$ satisfies formulation $1$ of base axiom:
== Proof ==
Let $B_1, B_2 \in \mathscr B$.
Let $x \in B_1 \setminus B_2$.
We have:
By matroid axiom $(\text I 3)$:
:$\exists y \in B_2 \setminus \paren{B_1 \setminus \set x} : \paren{ B_1 \setminus \set x} \cup \set y \in \mathscr I$
We have:
Then:
:$\exists y \in B_2 \setminus B_1 : \paren{ B_1 \setminus \set x} \cup \set y \in \mathscr I$
We have:
From Independent Subset is Base if Cardinality Equals Cardinality of Base:
:$\paren { B_1 \setminus \set x} \cup \set y \in \mathscr B$
Since $x$, $B_1$ and $B_2$ were arbitrary then the result follows.
Category:Matroid Bases Iff Satisfies Formulation 1 of Matroid Base Axiom
Matroid Bases Iff Satisfies Formulation 1 of Matroid Base Axiom/Sufficient Condition

== Theorem ==
Let $S$ be a finite set.
Let $\mathscr B$ be a non-empty set of subsets of $S$ satisfying formulation $1$ of base axiom:
Then $\mathscr B$ is the set of bases of a matroid on $S$.
== Proof ==
Let $\mathscr I = \set{X \subseteq S : \exists B \in \mathscr B : X \subseteq B}$
It is to be shown that:
:* $\quad \mathscr I$ satisfies the matroid axioms
and
:* $\quad \mathscr B$ is the set of bases of the matroid $M = \struct{S, \mathscr I}$
From Independence System Induced from Set of Subsets:
:$\mathscr I$ is an independence system
==== Matroid Axiom $(\text I 3)$ ====
Let $U, V \in \mathscr I$ such that:
:$\card V < \card U$
By definition of $\mathscr I$:
:$\exists B_1, B_2 \in \mathscr B : U \subseteq B_1, V \subseteq B_2$
From Max Operation Equals an Operand:
:$\exists B_1, B_2 \in \mathscr B : U \subseteq B_1, V \subseteq B_2 : \card{B_1 \cap B_2} = \max \set{\card{C_1 \cap C_2} : U \subseteq C_1, V \subseteq C_2 \text{ and } C_1, C_2 \in \mathscr B}$
:
:$B_2 \cap \paren{U \setminus V} = \O$
===== Lemma 1 =====
This contradicts the choice of $B_1, B_2$ such that:
:$\card{B_1 \cap B_2} = \max \set{\card{C_1 \cap C_2} : U \subseteq C_1, V \subseteq C_2 \text{ and } C_1, C_2 \in \mathscr B}$
Hence:
:$B_2 \cap \paren{U \setminus V} \ne \O$
Let $x \in B_2 \cap \paren{U \setminus V}$.
From Union of Subsets is Subset:
:$V \cup \set x \subseteq B_2$
By definition of $\mathscr I$:
:$V \cup \set x \in \mathscr I$
It follows that $\mathscr I$ satisfies the matroid axiom $(\text I 3)$ by definition.
This completes the proof that $M = \struct{S, \mathscr I}$ forms a matroid. 
==== $\mathscr B$ is Set of Bases ====
Let $B \in \mathscr B$.
From Set is Subset of Itself:
:$B \in \mathscr I$
Let $U \in \mathscr I$ such that:
:$B \subseteq U$
By definition of $\mathscr I$:
:$\exists B' \in \mathscr B : I \subseteq B'$
From Subset Relation is Transitive:
:$B \subseteq B'$
===== Lemma 2 =====
From Lemma 2:
:$\card B = \card {B'}$
From Cardinality of Proper Subset of Finite Set:
:$B = B'$
By definition of set equality:
:$U = B$
It has been shown that $B$ is a maximal subset of the ordered set $\struct{\mathscr I, \subseteq}$.
It follows that $\mathscr B$ is the set of bases of the matroid $M = \struct{S, I}$ by definition.
Category:Matroid Bases Iff Satisfies Formulation 1 of Matroid Base Axiom
Matroid Bases Iff Satisfies Matroid Base Axiom

== Theorem ==
Let $S$ be a finite set.
Let $\mathscr B$ be a non-empty set of subsets of $S$.
Then $\mathscr B$ is the set of bases of a matroid on $S$ $\mathscr B$ satisfies any one of the base axioms:
In which case, $\mathscr B$ satisfies all of the base axioms.
== Proof ==
Follows immediately from:
:* Matroid Bases Iff Satisfies Formulation 1 of Matroid Base Axiom
:* Equivalence of Definitions of Matroid Base Axioms
== Also see ==
* Definition:Base-Orderable Matroid
* Not All Matroids are Base-Orderable
== Sources ==
* 
* Chapter $1.$ $\S 5.$ Properties of independent sets and bases
* Chapter $11$ Submodular Function and Matroid Union $\S 11.3$ Matroid union and its applications, Exercise $10$
* Chapter $13$ Matroids $\S 13.1$ Independence Systems and Matroids, Definition $13.1$
* 
Category:Matroid Bases
Matroid Bases Satisfy Formulation 4 Base Axiom

== Theorem ==
Let $M = \struct {S, \mathscr I}$ be a matroid.
Let $\mathscr B$ be the set of bases of the matroid $M$.
Then $\mathscr B$ satisfies formulation $4$ of base axiom:
== Proof ==
Let $B_1, B_2 \in \mathscr B$.
Let $x \in B_1 \setminus B_2$.
From Matroid Base Union External Element has Fundamental Circuit:
:there exists a fundamental circuit $\map C {x, B_2}$ of $M$ such that $x \in \map C {x, B_2} \subseteq B_2 \cup \set x$
By definition of set intersection:
:$x \in B_1 \cap \map C {x, B_2}$
From Element of Matroid Base and Circuit has Substitute:
:$\exists y \in \map C {x, B_2} \setminus B_1 : \paren{B_1 \setminus \set x} \cup \set y \in \mathscr B$
We have:
From Matroid Base Substitution From Fundamental Circuit:
:$\paren{B_2 \setminus \set y} \cup \set x \in \mathscr B$
It follows that $\mathscr B$ satisfies formulation $4$ of base axiom:
Category:Matroid Bases
Matroid Bases Satisfy Formulation 7 of Matroid Base Axiom/Lemma 1

== Theorem ==
Let $S$ be a finite set.
Let $\mathscr C$ be a non-empty set of subsets satisfying the circuit axioms.
Let $n \in \N_{>0}$.
Let $C_1, C_2, \ldots, C_n \in \mathscr C$ satisfy:
:$\forall 0 \le k \le n : C_k \nsubseteq \ds \bigcup_{i \ne k} C_i$
Let:
:$A \subseteq S : \size A < n$
Let $r = \size A$.
Then:
:$\ds \exists D_1, \ldots, D_{n - r} \in \mathscr C : \bigcup_{i = 1}^{n - r} D_i \subseteq \paren{\bigcup_{i = 1}^{n} C_i} \setminus A$
== Proof ==
=== Case 1 : $n = 1$ ===
Let $n = 1$.
Hence $\size A = 0$.
From Cardinality of Empty Set:
:$A = \O$
It follows that $C_1$ suffices for $D_1$.
=== Case 2 : $n \ge 2$ ===
Let $n \ge 2$.
This case is proved by Induction of Finite Set.
Let $\map P X$ be the predicate:
:$\ds \exists D_1, \ldots, D_{n - s} \in \mathscr C : \paren{\bigcup_{i = 1}^{n - s} D_i \subseteq \paren{\bigcup_{i = 1}^{n} C_i} \setminus X} \land \paren{\forall 1 \le k \le n - s: D_k \nsubseteq \bigcup_{i = 1, i \ne k}^{n - s} D_i}$
where $s = \size X$.
==== Induction Base case ====
The induction base is $\map P \O$:
:$\ds \exists D_1, \ldots, D_n \in \mathscr C : \paren{\bigcup_{i = 1}^n D_i \subseteq \paren{\bigcup_{i = 1}^{n} C_i} \setminus \O} \land \paren{\forall 1 \le k \le n : D_k \nsubseteq \bigcup_{i = 1, i \ne k}^n D_i}$
From Set Difference with Empty Set is Self:
:$\ds \bigcup_{i = 1}^{n} C_i = \paren{\bigcup_{i = 1}^{n} C_i} \setminus \O$
It follows that $\map P \O$ is true.
==== Induction Hypothesis ====
The induction hypothesis is:
:$\forall A_1 \subseteq A, x \in A : \map P {A_1} \implies \map P {A_1 \cup \set x}$
That is:
:$\forall A_1 \subseteq A, x \in A $: 
:where $s = \size {A_1}$
==== Induction Step ====
Let $A_1 \subseteq A$.
Let $x \in A$.
The induction hypothesis holds if $x \in A_1$.
Let $x \notin A_1$.
Let $s = \size {A_1}$
Let:
:$D_1, \ldots, D_{n - s} \in \mathscr C$:
::* $\quad \ds \bigcup_{i = 1}^{n - s} D_i \subseteq \paren{\bigcup_{i = 1}^{n} C_i} \setminus A_1$
::* $\quad \ds \forall 1 \le k \le n - s: D_k \nsubseteq \bigcup_{i = 1, i \ne k}^{n - s} D_i$
===== Lemma 2 =====
From Cardinality of Proper Subset of Finite Set:
:$s < r < n$
Hence:
:$n - s \ge 2$
With:
:$m := n - s$
:$X := A_1$
:$Y := \bigcup_{i = 1}^{n} C_i$
from Lemma 2:
:$\exists E_1, \ldots, E_{n - s - 1} \in \mathscr C$:
::* $\quad \ds \bigcup_{i = 1}^{n - s - 1} E_i \subseteq \paren{\bigcup_{i = 1}^{n} C_i} \setminus \paren{A_1 \cup \set x}$
::* $\quad \ds \forall 1 \le k \le n - s - 1: E_k \nsubseteq \bigcup_{i = 1, i \ne k}^{n - s -1} E_i$
This proves the induction hypothesis
From Induction of Finite Set:
:$\exists D_1, \ldots, D_{n - r} \in \mathscr C$:
::* $\quad \ds \bigcup_{i = 1}^{n - r} D_i \subseteq \paren{\bigcup_{i = 1}^{n} C_i} \setminus A$
::* $\quad \ds \forall 1 \le k \le n - r: D_k \nsubseteq \bigcup_{i = 1, i \ne k}^{n - r} D_i$
Category:Matroid Bases Satisfy Formulation 7 of Matroid Base Axiom
Matroid Bases Satisfy Formulation 7 of Matroid Base Axiom/Lemma 2

== Theorem ==
Let $S$ be a finite set.
Let $\mathscr C$ be a non-empty set of subsets satisfying the circuit axioms.
Let $m \in \Z: m \ge 2$.
Let $D_1, D_2, \ldots, D_m \in \mathscr C$ satisfy:
:$\ds \forall 0 \le i \le m : D_i \nsubseteq \bigcup_{j = 1, j \ne i}^m D_j$
Let $X, Y \subseteq S$:
:$\ds \bigcup_{i = 1}^m D_i \subseteq Y \setminus X$
Let $x \in S \setminus X$.
Then:
:$\exists E_1, E_2, \ldots, E_{m - 1} \in \mathscr C$:
::* $\quad \ds \forall 0 \le i \le m - 1 : E_i \nsubseteq \bigcup_{j = 1,j \ne i}^{m - 1} E_j$
::* $\quad \ds \bigcup_{i = 1}^{m-1} E_i \subseteq Y \setminus \paren{X \cup \set x}$
== Proof ==
=== Case 1: $x$ is not in any $D_i$ ===
Let:
:$\forall 1 \le i \le m : x \notin D_i$
We have:
Furthermore:
:$\ds \forall 0 \le i \le m - 1 : D_i \nsubseteq \ds \bigcup_{i = 1, j \ne i}^{m - 1} D_j$
Hence $D_1, D_2, \ldots, D_{m - 1}$ suffice as the required $E_1, E_2, \ldots, E_{m - 1}$.
=== Case 2: $x$ is in some $D_i$ ===
Let:
:$\exists 1 \le i \le m : x \in D_i$
, suppose:
:$x \in D_m$
By definition of subset:
:$\ds \forall i = 1, \ldots, m - 1: \exists d_i \in D_i \setminus \paren{\bigcup_{j = 1, j \ne i}^{m - 1} D_j}$
Let $i \in \closedint {1} {m-1}$.
==== Case 2.1: $x \in D_i$ ====
Let:
:$x \in D_i$
By definition of set intersection:
:$x \in D_i \cap D_n$
By circuit axiom $(\text C 4)$:
:$\exists E_i \in \mathscr C$:
::$d_i \in E_i \subseteq \paren{D_i \cup D_m} \setminus \set x$
==== Case 2.2: $x \notin D_i$ ====
Let:
:$x \notin D_i$
Let $E_i = D_i$.
Then:
::$d_i \in E_i = D_i \subseteq \paren{D_i \cup D_m} \setminus \set x$
In both cases:
$\exists E_i \in \mathscr C : d_i \in E_i \subseteq \paren{D_i \cup D_m} \setminus \set x$
Since $i$ was arbitrary, it follows that:
:$(1) \quad \forall i = 1, \ldots, m - 1 : \exists E_i \in \mathscr C : d_i \in E_i \subseteq \paren{D_i \cup D_m} \setminus \set x$
We have:
:
:$\ds \exists i \in \closedint 1 {m-1} : E_i \subseteq \bigcup_{j = 1, j \ne i}^{m - 1} E_j$
We have:
Hence:
:$\ds d_i \in E_i \subseteq \bigcup_{j = 1, j \ne i}^{m - 1} D_j$
This contradicts the choice of $d_i$.
Hence:
:$\ds \forall i = 1, \ldots, m - 1 : E_i \nsubseteq \bigcup_{j = 1, j \ne i}^{m - 1} E_j$
Finally, we have:
The result follows.
In either case, the result follows.
Category:Matroid Bases Satisfy Formulation 7 of Matroid Base Axiom
Matroid Contains No Loops iff Empty Set is Flat

== Theorem ==
Let $M = \struct{S, \mathscr I}$ be a matroid.
Then:
:$M$ contains no loops the empty set is flat.
== Proof ==
Let $\rho: \powerset S \to \Z$ denote the rank function of $M$.
=== Necessary Condition ===
Let $M$ contain no loops.
By definition of a loop:
:$\forall x \in S : \set x \in \mathscr I$
Let $x \in S \setminus \O$.
Then:
It follows that $\O$ is a flat subset by definition.
=== Sufficient Condition ===
Let $\O$ be a flat subset.
Let $x \in S$.
From Set Difference with Empty Set is Self
:$x \in S \setminus \O$
From Element is Loop iff Rank is Zero:
:$x$ is not a loop
It follows that $M$ contains no loops.
== Sources ==
* Chapter $1.$ $\S 4.$ Loops and parallel elements
Category:Matroid Loops
Category:Matroid Flats
Matroid Induced by Affine Independence is Matroid

== Theorem ==
Let $\R^n$ be the $n$-dimensional real Euclidean space.
Let $S = \set {x_1, \dots, x_r}$ be a finite subset of $\R^n$.
Let $\struct {S, \mathscr I}$ be the matroid induced by affine independence on $S$.
That is, $\mathscr I$ is the set of affinely independent subsets of $S$.
Then $\struct{S, \mathscr I}$ is a matroid.
== Proof ==
It needs to be shown that $\mathscr I$ satisfies the matroid axioms $(I1)$, $(I2)$ and $(I3)$.
=== Matroid Axiom $(I1)$ ===
=== Matroid Axiom $(I2)$ ===
=== Matroid Axiom $(I3)$ ===
== Sources ==
* Chapter $1. \, \S 3.$ Examples of Matroids
Category:Matroid Theory
Matroid Induced by Algebraic Independence is Matroid

== Theorem ==
Let $L / K$ be a field extension.
Let $S \subseteq L$ be a finite subset of $L$.
Let $\struct {S, \mathscr I}$ be the matroid induced by algebraic independence over $K$ on $S$.
That is, $\mathscr I$ is the set of algebraically independent subsets of $S$.
Then $\struct {S, \mathscr I}$ is a matroid.
== Proof ==
It needs to be shown that $\mathscr I$ satisfies the matroid axioms $(\text I 1)$, $(\text I 2)$ and $(\text I 3)$.
=== ===
=== Matroid Axiom $(\text I 2)$ ===
=== Matroid Axiom $(\text I 3)$ ===
== Sources ==
* Chapter $1.$ $\S 3.$ Examples of Matroids
Category:Matroid Theory
Matroid Induced by Linear Independence in Abelian Group is Matroid

== Theorem ==
Let $\struct{G, +}$ be a torsion-free Abelian group.
Let $\struct{G, +, \times}$ be the $\Z$-module associated with $G$.
Let $S$ be a finite subset of $G$.
Let $\struct{S, \mathscr I}$ be the matroid induced by linear independence in $G$ on $S$.
That is, $\mathscr I$ is the set of linearly independent subsets of $S$.
Then $\struct{S, \mathscr I}$ is a matroid. 
== Proof ==
It needs to be shown that $\mathscr I$ satisfies the matroid axioms $(I1)$, $(I2)$ and $(I3)$.
=== Matroid Axiom $(I1)$ ===
=== Matroid Axiom $(I2)$ ===
=== Matroid Axiom $(I3)$ ===
== Sources ==
* Chapter $1.$ $\S 3.$ Examples of Matroids
Category:Matroid Theory
Matroid Induced by Linear Independence in Vector Space is Matroid

== Theorem ==
Let $V$ be a vector space.
Let $S$ be a finite subset of $V$.
Let $\struct{S, \mathscr I}$ be the matroid induced on $S$ by linear independence in $V$.
That is, $\mathscr I$ is the set of linearly independent subsets of $S$.
Then $\struct{S, \mathscr I}$ is a matroid.
== Proof ==
It needs to be shown that $\mathscr I$ satisfies the matroid axioms $(I1)$, $(I2)$ and $(I3)$.
=== Matroid Axiom $(I1)$ ===
=== Matroid Axiom $(I2)$ ===
=== Matroid Axiom $(I3)$ ===
== Also see ==
* Matroid Induced by Linear Independence in Abelian Group is Matroid
== Sources ==
* Chapter $1.$ $\S 3.$ Examples of Matroids
Category:Matroid Theory
Matroid Rank Function Iff Matroid Rank Axioms

== 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.
Then:
:$\rho$ is the rank function of a matroid $M = \struct{S, \mathscr I}$.
:
:$\rho$ satisfies the rank axioms
== Proof ==
Follows immediately from:
:* Formulation 1 Rank Axioms Implies Rank Function of Matroid
:* Rank Function of Matroid Satisfies Formulation 1 Rank Axioms
== Sources ==
* Chapter $1.$ $\S 6.$ Properties of the rank function
* Chapter $13$ Matroids $\S 13.2$ Other Matroid Axion, Theorem $13.10$
Category:Matroid Rank Functions
Matroid Unique Circuit Property

== Theorem ==
Let $M = \struct {S, \mathscr I}$ be a matroid.
Let $X \subseteq S$ be an independent subset of $M$.
Let $x \in S$ such that:
:$X \cup \set x$ is a dependent subset of $M$.
Then there exists a unique circuit $C$ such that:
:$x \in C \subseteq X \cup \set x$
=== Corollary ===
== Proof 1 ==
== Proof 2 ==
Category:Matroid Circuits
Category:Matroid Unique Circuit Property
Matroid Unique Circuit Property/Corollary

== Theorem ==
Let $M = \struct {S, \mathscr I}$ be a matroid.
Let $B$ be a base of $M$.
Let $x \in S \setminus B$.
Then there exists a unique circuit $C$ such that:
:$x \in C \subseteq B \cup \set x$
That is, $C$ is the fundamental circuit of $x$ in $B$.
== Proof ==
From Union of Matroid Base with Element of Complement is Dependent:
:$B \cup \set x$ is dependent.
From Matroid Unique Circuit Property there exists a unique circuit $C$ such that:
:$x \in C \subseteq B \cup \set x$
== Sources ==
* Chapter $1.$ $\S 9.$ Circuits
Category:Matroid Unique Circuit Property
Matroid Unique Circuit Property/Proof 1

== Theorem ==
== Proof ==
From Dependent Subset Contains a Circuit:
:there exists a circuit $C$ such that $C \subseteq X \cup \set x$
From Dependent Subset of Independent Set Union Singleton Contains Singleton:
:$x \in C$
 $C'$ is circuit of $M$ such that:
:$C' \ne C$
:$C' \subseteq X \cup \set x$
From Dependent Subset of Independent Set Union Singleton Contains Singleton:
:$x \in C'$
Hence:
:$x \in C \cap C'$
From Circuits of Matroid iff Matroid Circuit Axioms, the set $\mathscr C$ of all circuits satisfies the matroid circuit axiom $(\text C 3)$:
Hence there exists a circuit $C_3$ of $M$:
:$C_3 \subseteq \paren{C \cup C'} \setminus \set x \subseteq X$
This contradicts the independence of $X$.
The result follows.
== Sources ==
* Chapter $1.$ $\S 9.$ Circuits
Category:Matroid Unique Circuit Property
Matroid Unique Circuit Property/Proof 2

== Theorem ==
== Proof ==
From Dependent Subset Contains a Circuit:
:there exists a circuit $C$ such that $C \subseteq X \cup \set x$
From Dependent Subset of Independent Set Union Singleton Contains Singleton:
:$x \in C$
 $C'$ is circuit of $M$ such that:
:$C' \ne C$
:$C' \subseteq X \cup \set x$
From Dependent Subset of Independent Set Union Singleton Contains Singleton:
:$x \in C'$
By the definition of minimal dependent subset:
:$C \nsubseteq C'$
By the definition of a subset:
:$\exists y \in C \setminus C'$
By the definition of minimal dependent subset:
:$C \setminus \set y \in \mathscr I$
From Independent Subset is Contained in Maximal Independent Subset:
:$\exists Y \in \mathscr I : C \setminus \set y \subseteq Y \subseteq X \cup \set x : Y$ is a maximal independent subset of $X \cup \set x$
By assumption:
:$X$ is a maximal independent subset of $X \cup \set x$
By matroid axiom $(\text I 6)$:
:$\card Y = \card X$
As $x \in C'$ and $y \notin C'$ then:
:$x \ne y$
Hence:
:$x \in C \setminus \set y$
By matroid axiom $(\text I 2)$:
:$C \setminus \set y \cup \set y = C \nsubseteq Y$ 
Hence:
:$y \notin Y$
Hence:
:$Y \subseteq \paren {X \cup \set x} \setminus \set y$
From Cardinality of Subset of Finite Set:
:$\card Y \le \card {\paren {X \cup \set x} \setminus \set y}$
We have:
From Cardinality of Proper Subset of Finite Set:
:$Y = \paren {X \cup \set x} \setminus \set y$
Hence:
:$\paren {X \cup \set x} \setminus \set y \in \mathscr I$
As $y \notin C'$ and $C' \subseteq X \cup \set x$ then:
:$C' \subseteq \paren {X \cup \set x} \setminus \set y$
From Superset of Dependent Set is Dependent:
:$\paren {X \cup \set x} \setminus \set y \notin \mathscr I$
This contradicts the previous statement that 
:$\paren {X \cup \set x} \setminus \set y \in \mathscr I$
It follows that $C$ is the unique circuit such that:
:$C \subseteq X \cup \set x$
Category:Matroid Unique Circuit Property
Matroid is Uniquely Defined by Bases

== Theorem == 
Let $M = \struct {S, \mathscr I}$ be a matroid.
Let $\mathscr B$ be the set of bases of the matroid $M$.
Then:
:$M$ is the only matroid on $S$ whose set of bases is $\mathscr B$.
== Proof ==
Let $M^\prime = \struct {S, \mathscr I^\prime}$ whose set of bases is $\mathscr B$.
From Characterization of Matroid Independent Sets in Terms of Bases:
:$\mathscr I^\prime = \set{X \subseteq S : \exists B \in \mathscr B : X \subseteq B}$
Similarly:
:$\mathscr I = \set{X \subseteq S : \exists B \in \mathscr B : X \subseteq B}$
Hence:
:$\mathscr I^\prime = \mathscr I$
and so:
:$M^\prime = M$
Category:Matroid Theory
Category:Matroid Bases