Why is this characterization of matroids correct?

Question

Let $E$ be a finite set with a collection of subsets $\mathcal{I}$ which form an independence complex/abstract simplicial complex. (I.e. a non-empty descending family of sets.)

We require an additional condition to characterize the independent sets belonging to a matroid.

Question: Why is this unconventional axiom for the independent sets of a matroid:

• If $D_1, D_2 \not\in \mathcal{I}$, but $D_1 \cap D_2 \in \mathcal{I}$, then for every $e \in E$, $(D_1 \cup D_2) \setminus \{ e \} \not\in \mathcal{I}$.

equivalent to more conventional/common axioms for the independent sets belong to a matroid?

Examples of such more conventional axioms include but are not limited to:

• For every $I_1, I_2 \in \mathcal{I}$, if $|I_1| < |I_2|$, then there exists $x \in I_2 \setminus I_1$ such that $I_1 \cup \{ x \} \in \mathcal{I}$.
• For every $I_1, I_2 \in \mathcal{I}$, if $|I_2| = |I_1| + 1$, then there exists $x \in I_2 \setminus I_1$ such that $I_1 \cup \{ x \} \in \mathcal{I}$.
• For all $E' \subseteq E$, the maximal independent subsets of $E$ are equicardinal (pure subcomplex).

Answer 1

(Older version of the question, formulated dually using spanning and nonspanning sets rather than the more conventional independent and dependent sets)

Let $E$ be a finite set with a collection of subsets $\mathscr{S}$ such that:

1. $ (E \in \mathscr{S}) \iff (\mathscr{S} \not= \emptyset)$. (The equivalence holds if 2. below is true.)
2. If $S_1 \in \mathscr{S}$ and $S_2 \supseteq S_1$, then $S_2 \in \mathscr{S}$.
3. If $\sigma_1, \sigma_2 \not\in \mathscr{S}$, but $\sigma_1 \cup \sigma_2 \in \mathscr{S}$, then for every $x \in E$, $(\sigma_1 \cap \sigma_2) \cup \{ x \} \not\in \mathscr{S}$.

Question: How can we show that this implies the following?

For $S_1, S_2 \in \mathscr{S}$ such that, for a given subset $E' \subseteq E$, $S_1 \supseteq E'$ and $S_2 \supseteq E'$, and for any $X$ such that, for $i = 1,2$, $S_i \supsetneq X \supseteq E' \implies X \not\in \mathscr{S}$, then $|S_1| = |S_2|$.

I.e. "minimal sets in $\mathscr{S}$ are equicardinal". E.g., if $E$ were some finite subset of a vector space, and $\mathscr{S}$ were all subsets of $E$ such that the vectors together span the entire vector space, then this means that all bases of the vector have the same size, i.e. the vector space's dimension is well-defined.

---

Instead of formulating it as a proof by contradiction, I should do proof by contraposition.

Here is the proof that $(\neg S3^1 \implies \neg$ S3) $\iff$ (S3 $\implies S3^1$) when $|S_1 \setminus S_2| = 1$.

If $\neg S3^1$ is true, then there exists $S_1, S_2 \in \mathscr{S}$ such that $|S_2| = |S_1|+1$, and for all $x \in S_2 \setminus S_1$, $S_2 \setminus \{ x \} \not \in \mathscr{S}$. In particular, $S_1 \not\subseteq S_2$, since then $\mathscr{S} \ni S_1 = S_2 \setminus \{x \}$ for some $x \in S_2 \setminus S_1$ (the only such $x$ in fact, given that $|S_2| = |S_1| + 1$). Therefore, $|S_1 \setminus S_2| \ge 1$.

If $|S_1 \setminus S_2| = 1$, then $|S_2 \setminus S_1| = |S_1 \setminus S_2| + 1 = 2$.
(Since $|S_2 \setminus S_1| + |S_1 \cap S_2| = |S_2| = |S_1| + 1 = |S_1 \setminus S_2| + |S_1 \cap S_2| + 1$.)
So $S_2 \setminus S_1 = \{ x_1, x_2 \}$ and $S_2 \setminus \{x_1\} \not\in \mathscr{S}, S_2 \setminus \{x_2\} \not\in \mathscr{S}$, $(S_2 \setminus \{ x_1 \}) \cup (S_2 \setminus \{ x_2 \}) = S_2 \in \mathscr{S}$. But there exists an element in $E$, namely the unique sole/element $y \in S_1 \setminus S_2$, such that $$((S_2 \setminus \{x_1\}) \cap (S_2 \setminus \{ x_2\})) \cup \{ y \} = (S_1 \cap S_2) \cup \{y\} = (S_1 \cap S_2) \cup (S_1 \setminus S_2) = S_1 \in \mathscr{S} \,. $$ Therefore S3 is false, i.e. $\neg$S3 is true, what we wanted to show.

To finish the proof we need to generalize to the case that $|S_1 \setminus S_2| > 1$ or show that we can assume without loss of generality that $|S_1 \setminus S_2| =1$ if $\neg S3^1$ is true. I don't know how to do either.

Original question and work inspiring above question: Let $E$ be a finite set and assume $\mathscr{S}$ is a collection of subsets of $E$ ($\mathscr{S} \subseteq \mathscr{P}(E) = 2^E $) such that:

S1. $E \in \mathscr{S}$.
S2. $S_1 \in \mathscr{S}$ and $S_2 \supseteq S_1$ implies that $S_2 \in \mathscr{S}$ (ascending family).
S3. If $\sigma_1, \sigma_2 \not\in \mathscr{S}$, but $\sigma_1 \cup \sigma_2 \in \mathscr{S}$, then for every $x \in E$, $(\sigma_1 \cap \sigma_2) \cup \{x\} \not\in\mathscr{S}$.

Given the first two axioms, the third axioms is supposed to be equivalent to any of the following three equivalent axioms (i.e. I've already shown that these three are equivalent to one another):

$S3^1$. If $S_1, S_2 \in \mathscr{S}$ and $|S_2| = |S_1| + 1$, then there exists a $x \in S_2 \setminus S_1$ such that $S_2 \setminus \{ x \} \in \mathscr{S}$.
$S3^2$. If $S_1, S_2 \in \mathscr{S}$ and $|S_2| > |S_1|$, then there exists a $x \in S_2 \setminus S_1$ such that $S_2 \setminus \{x \} \in \mathscr{S}$.
$S3^3$. Given a fixed subset $E' \subseteq E$, if $S_1, S_2 \in \mathscr{S}$ are such that for $i = 1,2$, $S_i \supsetneq X \supseteq E'$ implies $X \not\in \mathscr{S}$, then $|S_1| = |S_2|$. (minimal spanning sets are equicardinal)

Note: The axiom S3 is the "opposite" of the third axiom for nonspanning sets given in White et al, Theory of Matroids (Encyclopedia of Mathematics and its Applications). In order to (directly) show that nonspanning sets are a "cryptomorphism" of spanning sets, one has to show that S3 implies one of three equivalent forms $S3^1, S3^2, S3^3$ which were given explicitly as axioms for spanning sets. (I.e. as opposed to going indirectly through dependent sets or something like that.)

---

Attempt: Assume that S3 is true, and assume by means of contradiction that $\neg S3^2$ is also true. Then there exist $S_1, S_2 \in \mathscr{S}$, with $|S_2| > |S_1|$, such that for all $x \in S_2 \setminus S_1$, $(S_2 \setminus \{ x \}) \not\in \mathscr{S}$. We have $S_2 = (S_2 \setminus S_1) \cup (S_1 \cap S_2)$, $S_1 = (S_1 \setminus S_2) \cup (S_1 \cap S_2)$. Define $d_1 = |S_1 \setminus S_2|$ and $d_2 = |S_2 \setminus S_1|$. Clearly our assumptions then imply that $d_2 > d_1$ always.

Case 0: $d_1 = 0$. Then $S_1 \subsetneq S_2$, which is a contradiction, because then $$\bigcap\limits_{x \in S_2 \setminus S_1} (S_2 \setminus \{x \}) = S_1 \cap S_2 = S_1 \,,$$ so for all $x \in (S_2 \setminus S_1)$, we have $(S_2 \setminus \{x \}) \supseteq S_1$. But $S_1 \in \mathscr{S}$ and $\mathscr{S}$ is an ascending family, so $(S_2 \setminus \{ x\}) \in \mathscr{S}$ for all $x \in (S_2 \setminus S_1)$.

Case 1: $d_1 = 1$. Then $S_1 \not\subseteq S_2$. Let $\{y\} = (S_1 \setminus S_2)$. Because $d_2 \ge 2 > d_1 = 1$, we can choose any $x_1 \in (S_2 \setminus S_1)$, and conclude that both $(S_2 \setminus \{ x_1 \}) \not \in \mathscr{S}$ and $(S_1 \cap S_2) \cup \{ x_1 \} \not\in \mathscr{S}$ (since $\mathscr{S}$ is an ascending family and $((S_1 \cap S_2) \cup \{x_1 \}) \subseteq (S_2 \setminus \{ x_2 \}) \not\in \mathscr{S}$ for some $x_2 \not= x_1$).

Then by S3, since $(S_2 \setminus \{ x_1 \}) \cup ( (S_1 \cap S_2) \cup \{ x_1 \} ) = S_2 \in \mathscr{S}$, for any $y \in E$, we should have that $$ ((S_2 \setminus \{x_1\})\cap ((S_1 \cap S_2) \cup \{x_1 \} ) ) \cup \{y \} = (S_1 \cap S_2) \cup \{ y \} \not\in \mathscr{S} \,. $$ But when we take $\{ y \} = (S_1 \setminus S_2)$, we have that $(S_1 \cap S_2) \cup \{ y \} = S_1$, which is a contradiction, since by assumption $S_1 \in \mathscr{S}$.

The key idea is that now all that needs to be done to finish is the proof is to find a way to reduce every case for $d_1 > 1$ to the case of $d_1 = 1$ (or $d_1 = 0$). We can do this by induction, i.e. by showing that for every $d_1 > 1$, an analogous set up must also be true for $d_1 - 1$.

Want to show: Given $S_1, S_2 \in \mathscr{S}$ with $|S_2| > |S_1|$, such that for all $x \in (S_2 \setminus S_1)$, $(S_2 \setminus \{ x \} \not\in \mathscr{S}$, and $|S_1 \setminus S_2| = d_1 > 1$, we can always find $S_1^{(1)}, S_2^{(2)} \in \mathscr{S}$ with $|S_2^{(1)}| > |S_1^{(1)}|$, such that for all $x^{(1)} \in (S_2^{(1)} \setminus S_1^{(1)})$, $(S_2^{(1)} \setminus \{ x^{(1)} \})\not\in \mathscr{S}$, and $|S_1^{(1)} \setminus S_2^{(1)}| = d_1 - 1$.

Case (a): There exists a $y \in (S_1 \setminus S_2)$ such that $(S_1 \setminus \{ y \}) \in \mathscr{S}$. Then taking $S_2^{(1)} = S_2$ and $S_1^{(1)} = S_1 \setminus \{y\}$ works, in particular $|S_1^{(1)} \setminus S_2| = |S_1 \setminus S_2| - 1 = d_1 -1$. (This is easy to check.)

Case (b): For all $y \in (S_1 \setminus S_2)$, one has that $(S_1 \setminus \{y \}) \not\in \mathscr{S}$. This implies that for $i = 1,2$, for any set $X\subseteq E$ such that $S_i \supsetneq X \supseteq (S_1 \cap S_2)$, we must have $X \not\in \mathscr{S}$, since $\mathscr{S}$ is an ascending family. (Also any proper subsets of $(S_1 \cap S_2)$ are also not in $\mathscr{S}$ because $\mathscr{S}$ is an ascending family, but I don't think that's relevant.) Anyway, this means that $S_1$ and $S_2$ are both minimal sets in $\mathscr{S}$ containing $(S_1 \cap S_2)$, but they are not equicardinal, i.e. $|S_1| \not= |S_2|$. This means that $\neg S3^3$ is true.

This is where I get stuck and don't know how to continue.

Answer 2

First suppose $E$ and $\mathcal{I}$ satisfy the "conventional" axioms. We'll prove the contrapositive of the "unconventional" axiom. (We take it as given that the "conventional" axioms are equivalent to each other: that seems easy to check, and from the original question it seems to be known and accepted; the question is just about equivalence of the "unconventional" axiom.)

Let $D_1, D_2 \subseteq E$ such that $D_1 \cap D_2 \in \mathcal{I}$. Suppose there exists an $e \in E$ such that $(D_1 \cup D_2) \setminus \{e\} \in \mathcal{I}$. We will prove that $D_1 \in \mathcal{I}$ or $D_2 \in \mathcal{I}$. By the "conventional" axioms we can keep adding elements of $(D_1 \cup D_2) \setminus \{e\}$ to $D_1 \cap D_2$ until we have an independent set $D'$ that (1) is contained in $D_1 \cup D_2$ (since those are the only elements we are adding), (2) contains $D_1 \cap D_2$ (since we start with that), (3) has the same size as $(D_1 \cup D_2) \setminus \{e\}$. This independent set $D' = (D_1 \cup D_2) \setminus \{e'\}$ where $e' \notin D_1 \cap D_2$. Without loss of generality $e' \notin D_1$; then $D_1 \subseteq D' \in \mathcal{I}$, so $D_1 \in \mathcal{I}$.

Now conversely suppose that $E$ and $\mathcal{I}$ satisfy the "unconventional" axiom. We'll prove the "conventional" axioms.

Say $I_1,I_2 \in \mathcal{I}$ with $|I_2| = |I_1|+1$. If $|I_2\setminus I_1| = 1$, then $I_1 \subseteq I_2$; say $x$ is the one element of $I_2 \setminus I_1$; then $I_1 \cup \{x\} = I_2$, so $I_1 \cup \{x\} \in \mathcal{I}$.

Next suppose $|I_2 \setminus I_1| = 2$. Write $I_2 \setminus I_1 = \{x_1,x_2\}$. We also can write $I_1 \setminus I_2 = \{y\}$. Now let $D_1 = I_1 \cup \{x_1\}$ and $D_2 = I_1 \cup \{x_2\}$. We have $D_1 \cap D_2 = I_1 \in \mathcal{I}$, and also $(D_1 \cup D_2) \setminus \{y\} = I_2 \in \mathcal{I}$. By the contrapositive of the "unconventional" axiom, at least one of $D_1$ or $D_2$ is in $\mathcal{I}$. This proves the conclusion of the "conventional" axiom in this case.

Next suppose $|I_2 \setminus I_1| = 3$. Write $I_2 = (I_1 \cap I_2) \cup \{x_1,x_2,x_3\}$ and $I_1 = (I_1 \cap I_2) \cup \{y_1,y_2\}$. ... I'm stuck here.

Answer 3

The following is adapted from Encyclopedia of Mathematics and Its Applications, Vol. 26: Theory of Matroids edited by Neil White, Chapter 2, Axiom Systems, Giorgio Nicoletti and Neil White.

Proof of equivalence of $\mathscr{D}$ and $\mathcal{I}$

$(\implies)$ Claim: If $\mathscr{D}$ satisfies the dependent set axioms, then $opp(\mathscr{D})=: \mathcal{I}$ satisfies the independent set axioms.

Let $\mathscr{D}$ be given such that $\emptyset \not\in \mathscr{D}$, $\mathscr{D}$ is an ascending family, and for all $D_1, D_2 \in \mathscr{D}$, one has that for all $x \in E$, $(D_1 \cup D_2) \setminus \{x\} \in \mathscr{D}$. Define $\mathcal{I} := opp(\mathscr{D})$. Then $\emptyset \in \mathcal{I}$, so $\mathcal{I} \not= \emptyset$. Moreover, since $\mathscr{D}$ is an ascending family, it follows that $\mathcal{I}$ is a descending family. Therefore all that remains to show is that for all $I_1, I_2 \in \mathcal{I}$ such that $|I_1| < |I_2|$, there exists an $x \in I_2 \setminus I_1$ such that $I_1 \cup \{ x \} \in \mathcal{I}$.

Let $I_1, I_2 \in \mathcal{I}$ be given with $|I_1| < |I_2|$. If $I_1 \subsetneq I_2$, i.e. $|I_1 \setminus I_2| =0$, then the desired property is obviously true, since in that case there must exist an $x \in I_2$ such that $I_2 \setminus \{ x\} \supseteq I_1 \implies I_2 \supseteq I_1 \cup \{ x \}$, $I_2 \in \mathcal{I}$, and $\mathcal{I}$ is a descending family.

So assume by means of induction that $\mathbf{I3}$ holds for any $I_1, I_2 \in \mathcal{I}$ whenever $|I_1| < |I_2|$, $|I_1 \setminus I_2| = n$. (The above paragraph was the base case.) Now let $I_1, I_2 \in \mathcal{I}$ be given such that $|I_1| < |I_2|$ and $|I_1 \setminus I_2| = n+1$. Let $y \in I_1 \setminus I_2$ and define $\tilde{I}_1 = I_1 \setminus \{ y \}$. Since $\mathcal{I}$ is a descending family, it follows that $\tilde{I}_1 \in \mathcal{I}$. Moreover, $|\tilde{I}_1| < |I_1| < |I_2|$ and $|\tilde{I}_1 \setminus I_2| = n$, so the induction hypothesis applies.

By iteration beginning with $\tilde{I}_2^{(0)}:= \tilde{I}_1$, we (claim) can get a set $\tilde{I}_2 \in \mathcal{I}$ such that $|\tilde{I}_2| = |I_2|$, $\tilde{I}_1 \cup I_2 \supseteq \tilde{I}_2 \supseteq \tilde{I}_1$. First observe that: $$ I_2 \setminus \tilde{I}_1 = I_2 \cap (I_1 \cap \{ y \}^c)^c = I_2 \cap (I_1^c \cup \{y \}) = I_2 \setminus I_1 \cup \emptyset = I_2 \setminus I_1 \,, $$ since by definition of $I_1 \setminus I_2$, $y \not\in I_2$. Each step of the iteration is an application of $\mathbf{I3}$ justified by the induction hypothesis; thus at each step in order to be able to iterate further we must have that $\tilde{I}^{(m)}_2 \in \mathcal{I}$, $|\tilde{I}^{(m)}_2| < |I_2|$, and $|\tilde{I}^{(m)}_2 \setminus I_2| = n$, and if iteration is possible, the iteration step will add an element from $I_2 \setminus \tilde{I}_2^{(m)}$ to $\tilde{I}_2^{(m)}$ in order to get $\tilde{I}_2^{(m+1)} \in \mathcal{I}$. In particular, since $\tilde{I}_2^{(0)} = \tilde{I}_1 \in \mathcal{I}$, it will follow that for all $m > 0$, $\tilde{I}_2^{(m)} \in \mathcal{I}$ also. Moreover, by the nature of the iteration step, it also follows that for all $m > 0$, $\tilde{I}_2^{(m)} \supsetneq \tilde{I}_2^{(0)} = \tilde{I}_1$, therefore $I_2 \setminus \tilde{I}_2^{(m)} \subseteq I_2 \setminus \tilde{I}_1 = I_2 \setminus I_1$. Thus each iteration step will add an element of $I_2 \setminus I_1$ to $\tilde{I}_2^{(m)} $ to get $\tilde{I}_2^{(m+1)}$, therefore it follows that for all $m$ we have: $$ \tilde{I}_2^{(m)} = \tilde{I}_1 \cup \{ m \text{ elements of }I_2 \setminus I_1 \} = (I_1 \setminus \{y \}) \cup \{ m \text{ elements of }I_2 \setminus I_1 \} \,. $$ Therefore clearly for all $m$, $\tilde{I}_2^{(m)} \supseteq \tilde{I}_1$ as claimed. Moreover, the above also obviously allows us to conclude that for all $m$, $$\tilde{I}_2^{(m)} \subseteq \tilde{I}_1 \cup (I_2 \setminus I_1) = \tilde{I}_1 \cup (I_2 \setminus \tilde{I}_1) = \tilde{I}_1 \cup (\tilde{I}_1 \cap I_2) \cup (I_2 \setminus \tilde{I}_1) = \tilde{I}_1 \cup I_2 \,. $$ From the above we can also conclude that the iteration will terminate exactly when/as soon as the condition $|\tilde{I}_2^{(m)}| < |I_2|$ is no longer satisfied, since it is the only condition whose status can change with $m$. This is equivalent to: $$|\tilde{I}_2^{(m)}| = |I_2| \iff |I_1 \setminus I_2| + |I_1 \cap I_2| - 1 +m = |I_1 \cap I_2| + |I_2 \setminus I_1| $$ $$ \iff |I_1 \setminus I_2| - 1 + m = |I_2 \setminus I_1| \iff (n+1) - 1 + m = |I_2 \setminus I_1| \iff m = |I_2 \setminus I_1| - n \,. $$ Therefore the iteration terminates with a set $\tilde{I}_2 \in \mathcal{I}$ with $|I_2| = |\tilde{I}_2|$, and $$ \tilde{I}_2 = \tilde{I}_2^{(|I_2 \setminus I_1| - n)} = (I_1 \setminus \{ y \}) \cup \{ (|I_2 \setminus I_1| - n) \text{ elements of }I_2 \setminus I_1 \} \,. $$ This is always well defined since $|I_2 \setminus I_1| > |I_1 \setminus I_2| = n+1$. It also gives: $$ \tilde{I}_2 \setminus I_1 = \{ (|I_2 \setminus I_1| -n) \text{ elements of }I_2 \setminus I_1 \} \supseteq \{ 2 \text{ elements of }I_2 \setminus I_1 \} \,, $$ with the subset inclusion following from the fact stated above that: $$ |I_2 \setminus I_1| > n+1 \iff |I_2 \setminus I_1| \ge n+2 \implies |I_2 \setminus I_1| - n \ge 2 \,. $$ Thus there exist at least two distinct $p_1, p_2 \in (\tilde{I}_2 \setminus I_1) \subseteq I_2 \setminus I_1$, $p_1 \not= p_2$. Assume by means of contradiction that both $I_1 \cup \{p_1 \} \in \mathscr{D}$ and $I_1 \cup \{ p_2\} \in \mathscr{D}$. Since $$ (I \cup \{ p_1 \}) \cap (I \cup \{ p_2 \}) = I_1 \in \mathcal{I} \,, $$ it follows from $\mathbf{D3}$ that for any $e \in E$, $$[(I_1 \cup \{ p_1 \}) \cup (I_1 \cup \{ p _2\})] \setminus \{ e \} = (I_1 \cup \{ p_1, p_2 \}) \setminus \{e \} \in \mathscr{D} \,. $$ However, if we take $e = y$, then when substituting this into the above we get $$ \mathscr{D} \ni (I_1 \cup \{ p_1, p_2 \}) \setminus \{ y \} = (I_1 \setminus \{y\}) \cup \{p_1, p_2\} = \tilde{I}_1 \cup \{ p_1, p_2\} \subseteq \tilde{I}_2 \,,$$ which is a contradiction, since $\mathcal{I}$ is a descending family, so $\tilde{I}_2 \in \mathcal{I}$ implies that $ (I_1 \cup \{ p_1, p_2 \}) \setminus \{ y\} \in \mathcal{I}$. Therefore our assumption must have been false, and we have that at least one of $I_1 \cup \{ p_1 \}$ or $I_1 \cup \{ p_2 \}$ is in $\mathcal{I}$. Since $p_1, p_2 \in I_2 \setminus I_1$, it follows that we have proven $\mathbf{I3}$, i.e. the induction hypothesis for $n+1$. Thus, by induction, it follows that $\mathbf{I3}$ holds for all $I_1, I_2 \in \mathcal{I} = opp(\mathscr{D})$, $|I_1| < |I_2|$. $\square$

$(\impliedby)$ Claim: If $\mathcal{I}$ satisfies the independent set axioms, then $opp(\mathcal{I})=: \mathscr{D}$ satisfies the dependent set axioms.

Let $\mathcal{I}$ be given such that $\mathcal{I} \not= \emptyset$, $\mathcal{I}$ is a descending family, and for every $I_1, I_2 \in \mathcal{I}$, we have that there exists an $x \in I_2 \setminus I_1$ such that $I_1 \cup \{x\} \in \mathcal{I}$. Because $\mathcal{I} \not=\emptyset$, there exists at least one $I \in \mathcal{I}, I \subseteq E$. Since $\emptyset \subseteq I$, and $\mathcal{I}$ is a descending family, it follows that $\emptyset \in \mathcal{I}$. Therefore $\emptyset \not\in \mathscr{D}:= opp(\mathcal{I})$. Moreover, since $\mathcal{I}$ is a descending family, $opp(\mathcal{I}) = \mathscr{D}$ is an ascending family. Thus all that remains to show is that for every $D_1, D_2 \in \mathscr{D}$ such that $D_1 \cap D_2 \in \mathcal{I}$, for every $x \in E$, $(D_1 \cup D_2) \setminus \{ x \} \in \mathscr{D}$.

So assume that $D_1, D_2 \in \mathscr{D}$ with $D_1 \cap D_2 \in \mathcal{I}$ are given. If either $D_1 \subseteq D_2$ or $D_2 \subseteq D_1$ then we would have $D_1 \cap D_2 = D_1$ or $D_1 \cap D_2 = D_2$, respectively, which would be a contradiction since $D_1, D_2 \not\in \mathcal{I}$ but $D_1 \cap D_2 \in \mathcal{I}$. Therefore both $D_1 \setminus D_2 \not= \emptyset$ and $D_2 \setminus D_1 \not= \emptyset$. We have as a result that for any $x \not\in D_1 \cap D_2$, that $(D_1 \cup D_2) \setminus \{ x \} \supseteq D_1$ or $(D_1 \cup D_2) \setminus\{ x \} \supseteq D_2$; in either case, because $D_1, D_2 \in \mathscr{D}$, and $\mathscr{D}$ is an ascending family, it follows that $(D_1 \cup D_2) \setminus \{ x \} \in \mathscr{D}$.

So now assume without loss of generality that $x \in D_1 \cap D_2$. Because $D_1 \setminus D_2 \not= \emptyset$ and $D_2 \setminus D_1 \not= \emptyset$, $|D_1 \cup D_2| \ge |D_1 \cap D_2| + 2 \implies |(D_1 \cup D_2) \setminus \{x \}| > |D_1 \cap D_2| $. So assume by means of contradiction that $(D_1 \cup D_2) \setminus \{ x \} \in \mathcal{I}$. Then by the last independent set axiom, there must exist a $y \in [(D_1 \cup D_2) \setminus \{ x\}] \setminus (D_1 \cap D_2) = (D_1 \cup D_2) \setminus (D_1 \cap D_2) = (D_1 \triangle D_2)$ (since by assumption $x \in D_1 \cap D_2$) such that $(D_1 \cap D_2) \cup \{y \} \in \mathcal{I}$. We can iterate this process until we get a set $\tilde{D} \in \mathcal{I}$ such that $(D_1 \cup D_2 )\supseteq \tilde{D} \supseteq D_1 \cap D_2$ and $|\tilde{D}| = |(D_1 \cup D_2) \setminus \{ x \}| = |D_1 \cup D_2| - 1$. Therefore $\tilde{D} \supseteq D_1$ or $\tilde{D} \supseteq D_2$. Because $\mathscr{D}$ is an ascending family, this is a contradiction, since then $D_1 \subseteq \tilde{D}$ or $D_2 \subseteq \tilde{D}$ implies that $\tilde{D} \in \mathscr{D}$, or equivalently it is a contradiction since $\mathcal{I}$ is a descending family, so that $\tilde{D} \in \mathcal{I}$ means that either $D_1 \in \mathcal{I}$ or $D_2 \in \mathcal{I}$, contradicting the hypotheses. Therefore for all $x \in E$, we have that $(D_1 \cup D_2) \setminus \{x \} \in \mathscr{D}$, as we wanted to show.

The conditions of the above iteration are that $|\tilde{D}^{(m)}| < | D_1 \cup D_2| - 1$, $\tilde{D}^{(m)} \in \mathcal{I}$, $$[(D_1 \cup D_2) \setminus \{ x\}] \setminus \tilde{D}^{(m)} \subseteq (D_1 \triangle D_2) \,,$$ and $(D_1 \cup D_2) \supseteq \tilde{D}^{(m)} \supseteq (D_1 \cap D_2)$. The iteration starts with $\tilde{D}^{(0)} = D_1 \cap D_2$ and ends with (claim) $\tilde{D} := \tilde{D}^{(|D_1 \triangle D_2| -1)}$, which equals: $$\tilde{D}^{(|D_1 \triangle D_2| - 1)} = (D_1 \cap D_2) \cup \{ (|D_1 \triangle D_2| - 1) \text{ elements of }D_1 \triangle D_2 \}$$ $$ = (D_1 \cup D_2) \setminus \{ 1 \text{ element of }D_1 \triangle D_2 \} \,. $$ The iteration step consists of adding one new element of $D_1 \triangle D_2$ to $\tilde{D}^{(m)}$ to get $\tilde{D}^{(m+1)} \in \mathcal{I}$, and for every $0 \le m \le |D_1 \triangle D_2| - 1$, we have that $$ \tilde{D}^{(m)} = (D_1 \cap D_2) \cup \{ m \text{ elements of }D_1 \triangle D_2 \} \,. $$ As discussed above, all of these conditions are satisfied in the base case $m = 0$, and the third independent set axiom allows us to prove the induction step holds as long as $|\tilde{D}^{(m)}| < |D_1 \cup D_2| - 1$, i.e. the iteration terminates exactly when/as soon as we reach the first $m \ge 1$ such that $|\tilde{D}^{(m)} |= |D_1 \cup D_2| -1,$ $$ \iff |D_1 \cap D_2| + m = |D_1 \cap D_2| + |D_1 \triangle D_2| -1 \iff m = |D_1 \triangle D_2| - 1 \,, $$ as we had claimed. Since $D_1 \not= D_2$ as a consequence of our assumptions, it must follow that $\tilde{D} \supseteq D_1$ or $\tilde{D} \supseteq D_2$ (due to the alternative way of writing $\tilde{D}$ shown above), thus the proof does go through as had been claimed above. $\square$

Answer 4

Proof of equivalence of $\mathscr{S}$ and $\mathscr{N}$:

$(\implies)$ Claim: If $\mathscr{S}$ satisfies the spanning set axioms, then $opp(\mathscr{S})=: \mathscr{N}$ satisfies the nonspanning set axioms.

Assume $\mathscr{S}$ satisfies the axioms $\mathscr{S} \not= \emptyset$, $\mathscr{S}$ is an ascending family, and for every $S_1, S_2 \in \mathscr{S}$, if $|S_2| > |S_1|$, then there exists an $x \in S_2 \setminus S_1$ such that $S_2 \setminus \{ x \} \in \mathscr{S}$. So now let $\mathscr{N} = opp(\mathscr{S})$, in particular, let $\mathscr{S} = opp(\mathscr{N})$. Since $E \in \mathscr{S}$, $E \not\in \mathscr{N}$, and since $\mathscr{S}$ is an ascending family, $\mathscr{N}$ is a descending family.

So all that remains to show is: For all $N_1, N_2 \in \mathscr{N}$, if $N_1, N_2 \in \mathscr{N}$, but $N_1 \cup N_2 \in \mathscr{S}$, then for all $x \in E$, $(N_1 \cap N_2) \cup \{ x\} \in \mathscr{N}$.

So assume that $N_1, N_2 \in \mathscr{N}$ with $N_1 \cup N_2 \in \mathscr{S}$ are given. If we had either $N_1 \subseteq N_2$ or $N_2 \subseteq N_1$ then we would have $N_1 \cup N_2 = N_2$ or $N_1 \cup N_2 = N_1$ respectively, contradicting our assumption that $N_1 \cup N_2 \not\in \mathscr{N}$. Thus $N_1 \setminus N_2 \not= \emptyset$ and $N_2 \setminus N_1 \not= \emptyset$. Therefore, for every $x \in N_1 \cup N_2 = (N_1 \cap N_2) \cup (N_1 \setminus N_2) \cup (N_2 \setminus N_1)$, we must have that $(N_1 \cap N_2) \cup \{ x \} \subseteq N_1$ or $(N_1 \cap N_2) \cup \{x\} \subseteq N_2$. Since $N_1, N_2 \in \mathscr{N}$ and $\mathscr{N}$ is a descending family, in both cases, i.e. for any $x \in N_1 \cup N_2$, we must have that $(N_1 \cap N_2) \cup \{x\} \in \mathscr{N}$.

So assuming by means of contradiction that $(N_1 \cap N_2) \cup \{ x \} \in \mathscr{S}$ for some $x \in E$, we can assume without loss of generality that $x \not\in N_1 \cup N_2$. Since $|N_1 \setminus N_2| \ge 1$ and $|N_2 \setminus N_1| \ge 1$, we have that $|N_1 \cup N_2| \ge |N_1 \cap N_2| + 2$. Therefore, $|N_1 \cup N_2| > |(N_1 \cap N_2) \cup \{x\}|$, and since both $(N_1 \cup N_2) \in \mathscr{S}$ and $(N_1 \cap N_2) \cup \{ x \} \in \mathscr{S}$, by $\mathbf{S3}$, we have that there exists a $y \in (N_1 \cup N_2) \setminus [ (N_1 \cap N_2) \cup \{x\} ]$ such that $N_1 \cup N_2 \setminus \{ y \} \in \mathscr{S}$. Since $x \not\in N_1 \cup N_2$, $(N_1 \cup N_2) \setminus [ (N_1 \cap N_2) \cup \{ x \} ] = (N_1 \cup N_2 ) \setminus (N_1 \cap N_2) = (N_2 \setminus N_1) \cup (N_1 \setminus N_2) = N_1 \triangle N_2$, so $ y \in N_1 \triangle N_2$. If $|(N_1 \cup N_2) \setminus \{ y \} |> |N_1 \cap N_2| + 1$, we can iterate this process again. After iterating $\mathbf{S3}$ so many times we get a subset of $N_1 \cup N_2$ which is in $\mathscr{S}$ with the same cardinality as $(N_1 \cap N_2) \cup \{ x \}$, therefore which must be of the form $(N_1 \cap N_2) \cup \{ p \}$ for some $p \in N_1 \triangle N_2$ (since in each step of the iteration, the relative complement with respect to $(N_1 \cap N_2) \cup \{x\}$ can not contain points in $N_1 \cap N_2$). However it follows that $(N_1 \cap N_2) \cup \{ p\} \subseteq N_1$ or $(N_1 \cap N_2) \cup \{p \} \subseteq N_2$. In either case we get a contradiction since $\mathscr{S}$ is an ascending family and $\mathscr{N}$ is a descending family, and $N_1, N_2 \in \mathscr{N}$. Therefore $\mathbf{N3}$ holds for $\mathscr{N} = opp(\mathscr{S})$.

The conditions of the above iteration are that $|\tilde{N}^{(m)}| > |N_1 \cap N_2| + 1$, $$\tilde{N}^{(m)} \setminus [(N_1 \cap N_2) \cup \{ x \}] = \tilde{N}^{(m)} \setminus (N_1 \cap N_2) \subseteq N_1 \triangle N_2 \,, $$ and $\tilde{N}^{(m)} \in \mathscr{S}$. The iteration starts with $\tilde{N}^{(0)} = N_1 \cup N_2$ and (claim) ends with: $\tilde{N}^{(|N_1 \triangle N_2| -1)} = (N_1 \cap N_2) \cup \{ p \}$ for some $p \in N_1 \triangle N_2$. Each step consists of the removal of one element of $N_1 \triangle N_2$ from $\tilde{N}^{(m)}$, using $\mathbf{S3}$, to get $\tilde{N}^{(m+1)} \in \mathscr{S}$.

We already showed above that $\tilde{N}^{(0)} = N_1 \cup N_2$ satisfies these conditions. Thus, applying the definition of the iteration step, the following holds when $m = 0$: $$ \tilde{N}^{(m+1)} = (N_1 \cup N_2) \setminus \{ (m+1) \text{ elements of }N_1 \triangle N_2 \} $$ $$= \{ (|N_1 \cap N_2| - (m+1)) \text{ elements of }N_1 \triangle N_2 \} \cup (N_1 \cap N_2) \in \mathscr{S} \,. $$ As a consequence of $\mathbf{S3}$, by induction it will also hold for any $m \ge 1$ satisfying the conditions of the iteration, because $x \not\in (N_1 \cup N_2) \implies (N_1 \cup N_2) \subseteq \{x\}^c$: $$ \tilde{N}^{(m)} \setminus [(N_1 \cap N_2) \cup \{x\}] = [(N_1 \cup N_2) \setminus \{ m \text{ elements of }N_1 \triangle N_2 \}] \setminus [ (N_1 \cap N_2) \cup \{ x \}] $$ $$ = [(N_1 \cup N_2) \cap \{ m \text{ elements of }N_1 \triangle N_2 \}^c \cap (N_1 \cap N_2) ^c] \cap \{x\}^c $$ $$= N^{(m)} \setminus (N_1 \cap N_2) = (N_1 \triangle N_2) \setminus \{ m \text{ elements of }N_1 \triangle N_2 \} \subseteq N_1 \triangle N_2 \,. $$ Thus the only way that the iteration can terminate is if $|N^{(m)}| = |N_1 \cap N_2| +1$, $$ \iff |N_1 \triangle N_2| - m + |N_1 \cap N_2| = |N_1 \cap N_2| + 1 \iff m = |N_1 \triangle N_2| - 1 \,. $$ Therefore the iteration ends with $\tilde{N}^{(|N_1 \triangle N_2| - 1)} $: $$ = [ (N_1 \triangle N_2) \setminus \{ (|N_1 \triangle N_2|- 1) \text{ elements of }N_1 \triangle N_2 \}] \cup (N_1 \cap N_2) $$ $ = \{ 1 \text{ element of }N_1 \triangle N_2 \} \cup (N_1 \cap N_2)$, exactly as had been claimed above. $\square$

$(\impliedby)$ Claim: If $\mathscr{N}$ satisfies the nonspanning set axioms, then $opp(\mathscr{N})=: \mathscr{S}$ satisfies the spanning set axioms.

Let $\mathscr{N}$ be given such that $E \not\in \mathscr{N}$, $\mathscr{N}$ is a descending family, and for all $N_1, N_2 \in \mathscr{N}$, if $N_1 \cup N_2 \not\in \mathscr{N}$, then for all $x \in E$, $(N_1 \cap N_2) \cup \{ x \} \in \mathscr{N}$. Defining $\mathscr{S} := opp(\mathscr{N})$, then clearly $E \in \mathscr{S}$, and $\mathscr{S}$ is an ascending family. So all that remains to show is that for all $S_1, S_2 \in \mathscr{S}$, if $|S_2| > |S_1|$, there exists an $x \in S_2 \setminus S_1$ such that $S_2 \setminus \{x\} \in \mathscr{S}$ (i.e. $\mathbf{S3}$ applies to $opp(\mathscr{N}) = \mathscr{S}$).

If $|S_1 \setminus S_2| = 0$, then $S_1 \subsetneq S_2$, so there exists an $x \in S_2 \setminus S_1$ such that $S_2 \setminus \{x \} \supseteq S_1$, and thus $S_2 \setminus \{ x \} \in \mathscr{S}$ (since $S_1 \in \mathscr{S}$ and $\mathscr{S}$ is an ascending family). So assume by means of induction that $\mathbf{S3}$ holds whenver $|S_1 \setminus S_2| = n$, and let $S_1, S_2 \in \mathscr{S} = opp(\mathscr{N})$ such that $|S_1 \setminus S_2| = n+1$. Therefore $|S_2 \setminus S_1| \ge n+2$.

Let $y \in S_1 \setminus S_2$, and define $\tilde{S}_2 = S_2 \cup \{ y \}$. Since $\mathscr{S}$ is ascending, $\tilde{S}_2 \in \mathscr{S}$. Moreover, clearly $|\tilde{S}_2| > |S_1|$ and $|S_1 \setminus \tilde{S}_2| = n$. As a result of our induction hypothesis, there exists an $x \in \tilde{S}_2 \setminus S_1$ such that $\tilde{S}_2 \setminus \{x\} \in \mathscr{S}$. If $|\tilde{S}_2 \setminus \{x\}| > |S_1|$, we can iterate this process again, until we get a set $\tilde{S}_1 \in \mathscr{S}$ with $|\tilde{S}_1| = |S_1|$ and $\tilde{S}_2 \supseteq \tilde{S}_1 \supseteq (S_1 \cap S_2) \cup \{y\}$. Then $|S_2 \setminus \tilde{S}_1| \ge 2$, since $|S_2 \setminus S_1| \ge n+2$ and $S_2 \setminus \tilde{S}_1 = (S_2 \setminus S_1) \setminus \{ n \text{ elements of } S_2 \setminus S_1 \}$ by construction of $\tilde{S}_1$. Therefore there exist $p_1, p_2 \in S_2 \setminus \tilde{S}_1$ with $p_1 \not= p_2$. Assume by means of contradiction that both $S_2 \setminus \{ p_1 \} \in \mathscr{N}$ and $S_2 \setminus \{ p_2 \} \in \mathscr{N}$. Then since $(S_2 \setminus \{ p_1 \}) \cup (S_2 \setminus \{ p_2 \}) = S_2 \in \mathscr{S}$, we have by $\mathbf{N3}$ that for every $e \in E$, $((S_2 \setminus \{ p_1 \}) \cap (S_2 \setminus \{p_2\})) \cup \{ e \} = (S_2 \setminus \{ p_1, p_2 \} ) \cup \{e\} \in \mathscr{N}$. But $(S_2 \setminus \{p_1, p_2\} ) \supseteq \tilde{S}_1 \setminus \{y \}$, so taking taking $e = y$, we get that both $(S_2 \setminus \{p_1, p_2\} ) \cup \{ y \} \in \mathscr{N} = opp(\mathscr{S})$ and $(S_2 \setminus \{p_1, p_2\} ) \cup \{ y \} \supseteq \tilde{S}_1 \in \mathscr{S} \implies (S_2 \setminus \{p_1, p_2\} ) \cup \{ y \} \in \mathscr{S}$ (since $\mathscr{S}$ is an ascending family), which is (obviously) a contradiction. Therefore at least one of $S_2 \setminus \{ p_1 \}$ or $S_2 \setminus \{ p_2 \}$ is in $\mathscr{S}$, which means that there exists a $p \in S_2 \setminus S_1$ such that $S_2 \setminus \{ p \} \in \mathscr{S}$, proving the induction step. Thus by induction $\textbf{S3}$ holds for all applicable $S_1, S_2 \in opp(\mathscr{N}) = \mathscr{S}$, which is what we wanted to show.

The conditions of the above iteration are the conditions of the induction hypothesis, which are the conditions of $\mathbf{S3}$, $S_1, \tilde{S}_1^{(m)} \in \mathscr{S}$, $|\tilde{S}_1^{(m)}| > |S_1|$, plus the additional restriction that $|S_1 \setminus \tilde{S}_1^{(m)}| = n$. The iteration starts with: $\tilde{S}_1^{(0)} = \tilde{S}_2$ and (claim) ends with: $\tilde{S}_1^{(|S_2 \setminus S_1| - n )} = \tilde{S}_1$. Each iteration step consists of the removal of some element from $\tilde{S}_1^{(m)}\setminus S_1$ from $\tilde{S}^{(m)}_1$ to get, by $\mathbf{S3}$, $\tilde{S}_1^{(m+1)} \in \mathscr{S}$.

When $m = 0$, $\tilde{S}_1^{(0)} = \tilde{S}_2 = S_2 \cup \{ y \}$, $\tilde{S}_2 \in \mathscr{S}$ since $\mathscr{S}$ is ascending, and $|\tilde{S}_2| > |S_1|$ trivially. We also have that $$S_1 \setminus \tilde{S}_2 = (S_1 \setminus S_2) \setminus \{y\} \,, \quad \text{whence} \quad |S_1 \setminus \tilde{S}_2| = |S_1 \setminus S_2| - 1 =(n+1) - 1 =n$$ as required. Moreover, we have that $$\tilde{S}_2 \setminus S_1 = (S_2 \cup \{ y \}) \cap S_1^c = S_2 \cap S_1^c \cup \{ y \} \cap S_1 ^c = S_2 \setminus S_1 \cup \emptyset = S_2 \setminus S_1 \,. $$ Applying the definition of the iteration step, the following holds when $m=0$: $$\tilde{S}_1^{(m+1)} = (S_2 \setminus \{ (m+1)\text{ elements of }S_2 \setminus S_1 \}) \cup \{ y \} \in \mathscr{S} \,. $$ By induction it will also hold for any $m \ge 1$ satisfying the conditions of the iteration. Let's see when the conditions for iterating further are satisfied: $$ S_1 \setminus \tilde{S}_1^{(m)} = S_1 \cap (\tilde{S}_1^{(m)})^c = S_1 \cap ( (S_2 \setminus \{ m\text{ elements of }S_2 \setminus S_1 \} ) \cup \{ y \} )^c $$ $$= S_1 \cap ( (S_2 \cap \{ m\text{ elements of } S_2 \setminus S_1 \}^c )^c \cap \{ y\}^c ) $$ $$ = S_1 \cap ( ( S_2^c \cup \{ m\text{ elements of }S_2 \setminus S_1 \} ) \cap \{ y \}^c) ) $$ $$ = S_1 \cap ( S_2^c \cap \{ y \}^c \cup \{ m\text{ elements of }S_2 \setminus S_1 \} \cap \{ y \}^c ) \,. $$ Since $ y \in S_1 \setminus S_2$ by definition, and $(S_1 \setminus S_2) \cap (S_2 \setminus S_1) = \emptyset$, the above equals: $$ = S_1 \cap ( S_2^c \cap \{ y \}^c \cup \{m \text{ elements of }S_2 \setminus S_1 \} ) = S_1 \cap S_2^c \cap \{ y \}^c \cup S_1 \cap \{m \text{ elements of }S_2 \setminus S_1 \} $$ $$ = (S_1 \cap S_2^c) \cap \{ y \}^c \cup \emptyset = (S_1 \setminus S_2) \setminus \{y \} = S_1 \setminus \tilde{S}_1^{(0)} = S_1 \setminus \tilde{S}_2 \,. $$ Thus $|S_1 \setminus \tilde{S}_1^{(m)}| = |S_1 \setminus \tilde{S}_1^{(0)}| = n$, so the same hypotheses are satisfied as in the base case as long as we have $|\tilde{S}_1^{(m)}| > |S_1|$.

In order to see whether this is true, we first have to look at $\tilde{S}_1^{(m)} \setminus S_1$, since $$ |\tilde{S}_1^{(m)}| - |S_1| = | \tilde{S}_1^{(m)} \cap S_1| + |\tilde{S}_1^{(m)}\setminus S_1| - |\tilde{S}_1^{(m)} \cap S_1| - |S_1 \setminus \tilde{S}_1^{(m)}| $$ $$= |\tilde{S}_1^{(m)} \setminus S_1| - |S_1 \setminus \tilde{S}_1^{(m)}| = |\tilde{S}_1^{(m)} \setminus S_1| - n \,. $$ Therefore we can conclude that: $$ |\tilde{S}_1^{(m)}| > |S_1| \iff | \tilde{S}_1^{(m)} \setminus S_1 | > n $$ Looking at $\tilde{S}_1^{(m)} \setminus S_1$, we find that: $$\tilde{S}_1^{(m)} \setminus S_1= ( (S_2 \setminus \{ m\text{ elements of }S_2 \setminus S_1 \}) \cup \{ y \}) \setminus S_1 = ( ( S_2 \cap \{ m\text{ elements of }S_2\setminus S_1 \}^c ) \cup \{ y\}) \cap S_1 ^c $$ $$ = ( ( S_2 \cap \{ m\text{ elements of }S_2 \setminus S_1 \}^c ) \cap S_1^c) \cup (\{ y \} \cap S_1^c) =(S_2 \setminus S_1) \setminus \{ m\text{ elements of }S_2 \setminus S_1 \} \,. $$ Therefore we can keep on iterating as long as $$ |(S_2 \setminus S_1) \setminus \{ m\text{ elements of }S_2 \setminus S_1 \} | > n \iff |S_2 \setminus S_1| - m >n \iff |S_2 \setminus S_1| > m+n \,. $$ Thus the iteration stops exactly when $$|S_2 \setminus S_1| = m + n \iff m = |S_2 \setminus S_1| - n \iff m = |S_2 \setminus S_1| - (|S_1 \setminus S_2| -1) \iff m = |S_2 \setminus S_1| - |S_1 \setminus S_2| + 1 \,. $$ This means in particular that we have $$ \tilde{S}_1 = S_2 \setminus \{ (|S_2 \setminus S_1| - |S_1 \setminus S_2| + 1)\text{ elements of }S_2 \setminus S_1 \} \cup \{ y \} \,. $$ We can see then that $|\tilde{S}_1| = |S_1|$, since: $$ |\tilde{S}_1 | = |S_2| - ( |S_2 \setminus S_1| - |S_1 \setminus S_2| + 1 ) + 1 = |S_2| - |S_2 \setminus S_1| + |S_1 \setminus S_2| - 1 + 1 = |S_1 \cap S_2| + |S_1 \setminus S_2| = |S_1| \,. $$ We still need to show that $\tilde{S}_2 \supseteq \tilde{S}_1 \supseteq (S_1 \cap S_2) \cup \{y \}$. As a result of the iteration process only removing elements in $S_2 \setminus S_1$, as well as of the definition of $\tilde{S}_2$, this will be true whenever (thus if and only if) $(\tilde{S}_1 \setminus \{ y\}) \supseteq S_1 \cap S_2$.

Now by definition of $\tilde{S}_1$, we have that $$ \tilde{S}_1 \setminus \{ y \} = S_2 \setminus \{ (|S_2 \setminus S_1| - (|S_1 \setminus S_2| - 1))\text{ elements of }S_2 \setminus S_1 \} $$ $$ = ((S_2 \setminus S_1) \setminus \{ (|S_2 \setminus S_1| - (|S_1 \setminus S_2| - 1) )\text{ elements of }S_2 \setminus S_1 \}) \cup (S_1 \cap S_2) $$ $$ = \{ |S_1\setminus S_2| - 1\text{ elements of }S_2 \setminus S_1 \} \cup (S_1 \cap S_2) \,. $$ Observe that the above is always well-defined, since even when $n = 0$, $|S_1 \setminus S_2| = n + 1 \ge 1$, i.e. $|S_1 \setminus S_2| -1 \ge 0$ always. So we have that $\tilde{S}_1 \setminus \{ y \} \supseteq S_1 \cap S_2$. We can also conclude from the above that $$ S_2 \setminus \tilde{S}_1 = \{ (|S_2 \setminus S_1| - (|S_1 \setminus S_2| - 1))\text{ elements of }S_2 \setminus S_1 \}\,. $$ Moreover, $|S_2 \setminus S_1| \ge |S_1 \setminus S_2| + 1$ always, so that we always have $$ |S_2 \setminus S_1| - (|S_1 \setminus S_2| - 1) \ge |S_1 \setminus S_2| + 1 - (|S_1 \setminus S_2| - 1) = 1 +1 = 2 \,. $$ Therefore $|S_2 \setminus \tilde{S}_1| \ge 2$ as claimed as well. $\square$