Matroid Closure follows the Closure Operator Properties

Question

I want to show that for a matroid $M=(E,\mathcal{I})$ the closure of $S\subseteq E$ i.e. $$cl(S)=\{x\in E\mid rank(S\cup\{x\})=rank(S)\}$$ actually follows the closure operator properties:

1. $\forall$ $S\subseteq E$, $S\subseteq cl(S)$
2. For $X\subseteq Y\subseteq E$, $cl(X)\subseteq cl(Y)$
3. $\forall$ $S\subseteq E$, $cl(S)=cl(cl(S))$
4. $\forall$ $a,b\in E$ and $\forall$ $S\subseteq E$, if $a\in cl(S\cup \{b\})\setminus cl(S)$ then $b\in cl(S\cup \{a\})\setminus cl(S)$

Now the first property is easy to see that it holds for the matroid closure. I have proved the second property:

Let $e\in cl(X)$. For notational clarity, I will write $S\cup\{e\} $ as $S+e$. We have to show that $e\in cl(Y)$ or $rank(Y+ e)=rank(Y)$. Suppose not. Then $rank(Y+e)>rank(Y)$. Then $I\in\mathcal{I}$ be the independent set such that $rank(Y+e)=|I|$. Since upon adding $e$ to $Y$ rank increased we can say $e\in I$. Now Let $I_x\in\mathcal{I}$ such that $rank(X)=rank(X+e)=|I_x|$ and $e \notin I_x$. Now we can extend $I_x$ by $I$ to get an independent set $I_x^1$ such that $|I_x^1|=|I|$. Now $e\in I_x^1$ since otherwise $I_x^1\subseteq Y$ and then $rank(Y)<|I_x^1|$ which is not possible. So $I_x^1$ is an independent set such that $e\in I_x^1$ and $I_x\subseteq I_x$. Hence the subset $I_x+e$ is an independent set and $I_x+e\subseteq X+e$. So $rank(X+e)>rank(X)$ which is not possible. Hence rank(Y+e)=rank(Y)$

But I am stuck at the 3rd and 4th properties. How do we prove those?

Answer 1

3. For $S \subseteq E$, by 1. you have $cl(S) \subseteq cl(cl(S))$. For the other direction, take any $e \in cl(cl(S))$. We show that $e \in cl(S)$. Suppose not, then $$ rank(cl(S)+e) \geq rank(S+e) > rank(S) = rank(cl(S)), $$ where the first inequality follows from monotonicity, the second one from $e \notin cl(S)$ and the equality can be shown using submodularity of $rank$.

4. Let $a \in cl(S+b) \setminus cl(S)$. Then $rank(S+b+a) = rank(S+b)$ and $rank(S+a) > rank(S)$ (first equality follows from $a \in cl(S+b)$, inequality from $a \notin cl(S)$). We need to show that $rank(S+a) = rank(S+b)$. If not then $rank(S+a) > rank(S) = rank(S+b)$ (first inequality is established above and if $rank(S+a) \neq rank(S+b)$, then the latter cannot be larger as it also only adding one element to $S$). But then $b \in cl(S)$ and hence, $rank(S+b+a) = rank(S+b) = rank(S) < rank(S+a)$, a contradiction, so we have $rank(S+a) = rank(S+b)$ from which the statement follows by concatenating the first two statements that follow from our assumption: $rank(S+b+a) = rank(S+b) = rank(S+a) > rank(S)$, i.e. $rank(S+a) = rank(S+a+b)$ and hence, $b \in cl(S+a)$, and $rank(S+b) > rank(S)$, thus, $b \notin cl(S)$.