A matroid may be defined using a finite ground set $E$ and a closure operator on $E$ which is a map from $2^E\rightarrow 2^E$ written $A\rightarrow \bar{A}$ such that:
- $A\subseteq \bar{A}$
- $\bar{A}=\bar{\bar{A}}$
- If $A\subseteq B$ then $\bar{A}\subseteq \bar{B}$
- If $e\notin \bar{A}$ but $e \in \overline{A+e'}$ then $e' \in \overline{A+e} \hspace{0.5cm} \forall A \in E$
This definition can be found in Lecture Notes on Algebraic Combinatorics [page: 63].
It is also known that a rank function $r$ on $E$ can be defined by the closure operator as follows:
For $A\subseteq E$, $r(A)=\min\{|B|: \bar{B}=\bar{A}\}$ $\hspace{3cm}$ (1)
One of the properties of the rank function is:
If $A\subseteq B$ then $r(A)\leq r(B)$
It is not obvious to me how this property holds from the definition (1).
I want to show that : For $A\subseteq B$, if $C$ and $D$ are sets of minimum cardinalities such that $\bar{C}=\bar{A}$ and $\bar{D}=\bar{B}$ then $|C|\leq |D|$.
My attempt so far has been to use proof by contradiction and make use of property 4 in the definition of the matroid closure operator.
Edit: I guess I have got it.
We know that $\bar{C}\subseteq \bar{D}$. Let $C$ and $D$ are are such that $|C|>|D|$. Let us enumerate $C$ and $D$ as follows:
$C=\{c_1,c_2,...,c_m\}$, $D=\{d_1,d_2,...,d_n\}$,$m>n$
From the way $C$ is defined we must have $c_j\notin \overline{\{c_1,c_2,...,c_{j-1}\}}$ $\hspace{0.5cm}$ (2)
Now for $c_1$ we find the minimal set of elements $\{d_1,d_2,...,d_{a_1}\}$ in $D$ (with renumbering if necessary) such that $c_1 \in \overline{\{d_1,d_2,...,d_{a_1}\}}$ .
For $c_2$ we extend this set to a minimal set $\{d_1,d_2,...,d_{a_1},d_{a_1+1},...,d_{a_2}\}$ such that $c_2\in \overline{\{d_1,d_2,...,d_{a_1},d_{a_1+1},...,d_{a_2}}\}$.
We continue doing the same for $c_j, j>2$ and note that at each step the set must include at least one new element from $D$ (from (2)). Now since $m>n$, we will exhaust all elements of $D$ before we can complete this process for all $c_j$s. Hence we will contradict (2) and therefore the minimality of $C$.