Suppose $M=(E,S)$ is an independence system, meaning
- $S\neq \emptyset$
- $S\subseteq 2^E$
- $\forall A\in S, B\subseteq A: B\in S$
For $A\subseteq E$, $X$ is called a maximally independent subset of $A$ iff
- $X\subseteq A$
- $X\in S$
- $\forall Y\supset X: Y\notin S$.
Suppose $\forall A\subseteq E:$ all maximally independent subsets of $A$ have the same cardinality.
How can one derive from this that $M$ is a matroid? I managed to prove the other direction, but this direction kinda leaves me baffled.
What needs to be shown is that
$\forall A,B\in S: |A|=|B|+1\implies \exists v\in A\setminus B: B\cup\{v\}\in S$.
I really am not sure what to even start with. I guess must choose some subset of $E$ first, in order to use the cardinality property, but no idea which one (maybe $A\cup B$?).
Maybe a proof by contradiciton is easier, but I also have no idea how to continue once setting up the contradictory assumptions.
Any hints or solutions are much appreciated, thank you.
UPDATE:
So, I am not sure if I have the definition of maximally independent subset right. If I change point 3 of the definition to
3'. $\forall A\supseteq Y\supset X: Y\notin S$
I have a proof.
Suppose $\exists A,B\in S$ such that $|A|=|B|+1$ and $\forall v\in A\setminus B: B\cup\{v\}\notin S$.
Then $B$ is a maximally independent subset of $A\cup B$. However, since $|A|\neq|B|$ means that $A$ is not a maximally independent subset of $A\cup B$, there exists $X\in S, X\subseteq A\cup B$ such that $A\subset X$. Let $X^*$ be a maximal such set.
However, that means $|X^*|=|B|$ and $|X^*|>|A|$ and since $|A|=|B|+1$, we get $|X^*|>|X^*|+1$, a contradiction.
Therefore, there don't exist such sets $A,B$, hence $M$ is a matroid. QED
Is that correct?