avewright/proofwiki-math huggingface dataset:
Theorem: Cantor's Theorem

There is no surjection from a set $S$ to its power set for any set $S$.
That is, $S$ is strictly smaller than its power set.

Proof:
We temporarily introduce the notation:
:<nowiki>$a^n = \begin{cases}
a : & n = 0 \\
\set {a^{n - 1} } : & n > 0
\end{cases}$</nowiki>
where $a \in S$.
Thus $a^n$ consists of a single element $a^{n - 1} \in \map {\PP^{n - 1} } S$.
Let there be a bijection $f: S \to \QQ^n$ where $\QQ^n \subseteq \map {\PP^n} S$.
Then define:
:$\AA^{n - 1} = \set {s^{n - 1} \in \map {\PP^{n - 1} } S: s^{n - 1} \ne \map f s}$
Each $\QQ^{n - 1} \in \QQ^n$ is the image of some element of $S$ under $f$.
Let $\QQ^{n - 1} = \map f x$ for some $x \in S$.
Let $x^{n - 1} \in \QQ^{n - 1} = \map f x$.
Then $x^{n - 1} \notin \AA^{n - 1}$, and so $\AA^{n - 1} \notin \QQ^{n - 1}$.
On the other hand, let $x^{n - 1} \notin \QQ^{n - 1} = \map f x$.
Then $x^{n - 1} \in \AA^{n - 1}$, and so again $ A^{n - 1} \notin \QQ^{n - 1}$.
Thus $\AA^{n - 1} \notin Q^n$.
Therefore $Q^n$ is a proper subset of $\map {\PP^n} S$.
Hence the result.
{{qed}}
Theorem: Cantor's Theorem

There is no surjection from a set $S$ to its power set for any set $S$.
That is, $S$ is strictly smaller than its power set.

Proof:
The proof proceeds by induction.
For all $n \in \N_{> 0}$, let $\map P n$ be the proposition:
:There is no surjection from $S$ onto $\map {\PP^n} S$.
=== Basis for the Induction ===
$\map P 1$ is Cantor's Theorem.
This is our basis for the induction.
=== Induction Hypothesis ===
Now we need to show that, if $\map P k$ is true, where $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.
So this is our induction hypothesis:
:There is no surjection from $S$ onto $\map {\PP^k} S$.
Then we need to show:
:There is no surjection from $S$ onto $\map {\PP^{k + 1} } S$.
=== Induction Step ===
{{:Cantor's Theorem (Strong Version)/Proof 2/Induction Step}}
Theorem: Cantor's Theorem

There is no surjection from a set $S$ to its power set for any set $S$.
That is, $S$ is strictly smaller than its power set.

Proof:
By Power Set is Nonempty, $\powerset {\map {\PP^k} S}$ is non-empty.
By definition: 
:$\map {\PP^{k + 1} } S = \powerset {\map {\PP^k} S}$
Then:
:$\map {\PP^{k + 1} } S \ne \O$
By Law of Excluded Middle, there are two choices:
:$S = \O$
or:
:$S \ne \O$
Suppose that $S = \O$.
By {{Corollary|Image of Empty Set is Empty Set|2}}, there is no surjection from $S$ onto $\map {\PP^{k + 1} } S$.
Suppose that $S \ne \O$.
By the induction hypothesis $\map P k$ is true.
{{AimForCont}} that $f: S \to \map {\PP^{k + 1} } S$ is a surjection.
By Injection from Set to Power Set, there is an injection:
:$g: \map {\PP^k} S \to \powerset {\map {\PP^k} S}$
By Injection has Surjective Left Inverse Mapping, there exists a surjection:
:$h: \powerset {\map {\PP^k} S} \to \map {\PP^k} S$
By definition of $\powerset {\map {\PP^k} S}$, this is a surjection:
:$h: \map {\PP^{k + 1} } S \to \map {\PP^k} S$
By Composite of Surjections is Surjection, we have a surjection:
:$h \circ f: S \to \map {\PP^k} S$
But this contradicts the induction hypothesis.
Thus we conclude that the theorem holds for all $n$.
{{qed}}
Theorem: Cantor's Theorem

There is no surjection from a set $S$ to its power set for any set $S$.
That is, $S$ is strictly smaller than its power set.

Proof:
{{AimForCont}} $S$ is a set with a surjection $f: S \to \powerset S$.
Then:
{{begin-eqn}}
{{eqn | q = \forall x \in S
      | l = \map f x
      | o = \in
      | r = \powerset S
      | c = {{Hypothesis}}
}}
{{eqn | ll= \leadsto
      | q = \forall x \in S
      | l = \map f x
      | o = \subseteq
      | r = S
      | c = {{Defof|Power Set}}
}}
{{end-eqn}}
Now by Law of Excluded Middle, there are two choices for every $x \in S$:
:$x \in \map f x$
:$x \notin \map f x$
Let $T = \set {x \in S: x \notin \map f x}$.
As $f$ is supposed to be a surjection, $\exists a \in S: T = \map f a$.
Thus:
:$a \in \map f a \implies a \notin \map f a$
:$a \notin \map f a \implies a \in \map f a$
This is a contradiction, so the initial supposition that there is such a surjection must be false.
{{qed}}
{{LEM||3}}
Theorem: Cantor's Theorem

There is no surjection from a set $S$ to its power set for any set $S$.
That is, $S$ is strictly smaller than its power set.

Proof:
Let $S$ be a set.
Let $\powerset S$ be the power set of $S$.
Let $f: S \to \powerset S$ be a mapping.
Let $T = \set {x \in S: \neg \paren {x \in \map f x} }$.
Then $T \subseteq S$, so $T \in \powerset S$ by the definition of power set.
We will show that $T$ is not in the image of $f$ and therefore $f$ is not surjective.
{{AimForCont}}:
:$\exists a \in S: T = \map f a$
Suppose that:
:$a \in \map f a$
Then by the definition of $T$:
:$\neg \paren {a \in T}$
Thus since $T = \map f a$:
:$\neg \paren {a \in \map f a}$
By Rule of Implication:
:$(1): \quad a \in \map f a \implies \neg \paren {a \in \map f a}$
Suppose instead that:
:$\neg \paren {a \in \map f a}$
Then by the definition of $T$:
:$a \in T$
Thus since $T = \map f a$:
:$a \in \map f a$
By Rule of Implication:
:$(2): \quad \neg \paren {a \in \map f a} \implies a \in \map f a$
By Non-Equivalence of Proposition and Negation, applied to $(1)$ and $(2)$, this is a contradiction.
As the specific choice of $a$ did not matter, we derive a contradiction by Existential Instantiation.
Thus by Proof by Contradiction, the supposition that $\exists a \in S: T = \map f a$ must be false.
It follows that $f$ is not a surjection.
{{qed}}
Theorem: Cantor's Theorem

There is no surjection from a set $S$ to its power set for any set $S$.
That is, $S$ is strictly smaller than its power set.

Proof:
Let $S$ be a set.
Let $\powerset S$ be the power set of $S$.
Let $f: S \to \powerset S$ be a mapping.
Let $T = \set {x \in S: \neg \paren {x \in \map f x} }$.
The set $T$ exists by the {{axiom-link|Specification}}.
Then:
:$T \subseteq S$
so $T \in \powerset S$ by the definition of power set.
We will show that $T$ is not in the image of $f$ and therefore $f$ is not surjective.
{{AimForCont}}:
:$\exists a \in S: T = \map f a$
This means that $f$ maps $a$ to $T$.
We claim that $a \notin T$.
{{AimForCont}}:
:$a \in T$
By definition of $T$:
:$a \notin \map f a$
This is a contradiction, since $T = \map f a$.
Thus by Proof by Contradiction, we conclude that:
:$(1): \quad a \notin T$
Since $T = \map f a$, we get:
:$a \notin \map f a$
By definition of $T$:
:$(2): \quad a \in T$
By Principle of Non-Contradiction, $(1)$ and $(2)$ cannot both be true.
We have reached a contradiction.
Thus by Proof by Contradiction, the supposition that $\exists a \in S: T = \map f a$ must be false.
It follows that $f$ is not a surjection.
{{qed}}
Theorem: Surjection Induced by Powerset is Induced by Surjection

Let $\RR \subseteq S \times T$ be a relation.
Let $\RR^\to: \powerset S \to \powerset T$ be the direct image mapping $\RR$.
Let $\RR^\to$ be a surjection.
Let $X = \Preimg \RR$, that is, the preimage of $\RR$.
Then $\RR {\restriction_X} \subseteq X \times T$, that is, the restriction of $\RR$ to $X$, is a surjection.

Proof:
Let $X$ be the preimage of $\RR$.
Suppose $\RR {\restriction_X} \subseteq X \times T$ is a mapping, but not a surjection.
Then:
:$\exists y \in T: \neg \exists x \in S: \tuple {x, y} \in \RR$
Because no element of $S$ relates to $y$, no subset of $S$ contains any element of $S$ that relates to the subset $\set y \subseteq T$.
Thus:
:$\exists \set y \in \powerset T: \neg \exists X \in \powerset S: \map {\RR^\to} X = \set y$
So we see that $\RR^\to: \powerset S \to \powerset T$ is not a surjection.
Now, suppose $\RR {\restriction_X} \subseteq X \times T$ is not even a mapping.
This could happen, according to the definition of a mapping, in one of two ways:
:$(1): \quad \exists x \in X: \neg \exists y \in T: \tuple {x, y} \in \RR$
:$(2): \quad \exists x \in S: \tuple {x, y_1} \in \RR \land \tuple {x, y_2} \in \RR: y_1 \ne y_2$
Because $X$ is already the preimage of $\RR$, the first of these cannot happen here.
For the second, it can be seen that neither $\set {y_1}$ nor $\set {y_2}$ can be in $\Rng {\map {\RR^\to} {\powerset S} }$.
Therefore $\RR^\to: \powerset S \to \powerset T$ can not be a surjection.
{{questionable|See talk page}}
Thus, by the Rule of Transposition, the result follows.
{{qed}}
Category:Surjections
Category:Direct Image Mappings
rr9tpvyoinje39rosm63dba2j6eak5h
Theorem: Mapping is Injection iff Direct Image Mapping is Injection

Let $f: S \to T$ be a mapping.
Let $f^\to: \powerset S \to \powerset T$ be the direct image mapping of $f$.
Then:
:$f^\to$ is an injection
{{iff}}
:$f: S \to T$ is also an injection.

Proof:
=== Necessary Condition ===
Suppose $f: S \to T$ is a mapping, but not injective.
Then:
:$\exists x_1 \ne x_2 \in S: \map f {x_1} = \map f {x_2} = y$
Let:
:$X_1 = \set {x_1}$
:$X_2 = \set {x_2}$
:$Y = \set y$
Then it follows that:
:$\map {f^\to} {X_1} = \map {f^\to} {X_2} = Y$
Thus $f^\to: \powerset S \to \powerset T$ is not injective.
So by the Rule of Transposition, the result follows.
{{qed|lemma}}
Theorem: Direct Image Mapping is Bijection iff Mapping is Bijection

Let $\RR \subseteq S \times T$ be a relation.
Let $\RR^\to: \powerset S \to \powerset T$ be the direct image mapping of $\RR$.
Then $\RR \subseteq S \times T$ is a bijection {{iff}} $\RR^\to: \powerset S \to \powerset T$ is a bijection.

Proof:
{{ProofWanted}}
Category:Bijections
Category:Direct Image Mappings
jhcdarz7hd2e162xhx0dlkuai318jn8
Theorem: No Bijection from Set to its Power Set

Let $S$ be a set.
Let $\powerset S$ denote the power set of $S$.
There is no bijection $f: S \to \powerset S$.

Proof:
A bijection is by its definition also a surjection.
By Cantor's Theorem there is no surjection from $S$ to $\powerset S$.
Hence the result.
{{Qed}}
Theorem: Set is Equivalent to Proper Subset of Power Set

Every set is equivalent to a proper subset of its power set:
:$\forall S: \exists T \subset \powerset S: S \sim T$

Proof:
To show equivalence between two sets, we need to demonstrate that a bijection exists between them.
We will now define such a bijection.
Let $T = \set {\set x: x \in S}$.
{{begin-eqn}}
{{eqn | q = \forall x \in S
      | l = \set x
      | o = \subseteq
      | r = S
      | c = {{Defof|Subset}}
}}
{{eqn | ll= \leadsto
      | l = \set x
      | o = \in
      | r = \powerset S
      | c = {{Defof|Power Set}}
}}
{{eqn | ll= \leadsto
      | l = T
      | o = \subseteq
      | r = \powerset S
      | c = {{Defof|Subset}}
}}
{{end-eqn}}
Now we define the mapping $\phi: S \to T$:
:$\phi: S \to T: \forall x \in S: \map \phi x = \set x$
$\phi$ is an injection:
:$\forall x, y \in S: \set x = \set Y \implies x = y$ by definition of set equality
$\phi$ is a surjection:
:$\forall \set x \in T: \exists x \in S: \map \phi x = \set x$
So $\phi$, being both an injection and a surjection, is a bijection by definition.
To show that $T \subset \powerset S$, that is, is a proper subset of $\powerset S$, we merely note that $\O \in \powerset S$ by Empty Set is Element of Power Set, but $\O \notin T$.
Thus $T \subseteq \powerset S$ but $\powerset S \nsubseteq T$.
Hence the result.
{{qed}}
Category:Power Set
Category:Proper Subsets
hnozqzw334eprx3ezytjmy07sgz4vfv
Theorem: Union of Power Sets

The union of the power sets of two sets $S$ and $T$ is a subset of the power set of their union:
:$\powerset S \cup \powerset T \subseteq \powerset {S \cup T}$

Proof:
{{begin-eqn}}
{{eqn | l = X
      | o = \in
      | r = \powerset S \cup \powerset T
      | c = 
}}
{{eqn | ll= \leadsto
      | l = X
      | o = \subseteq
      | r = S \lor X \subseteq T
      | c = {{Defof|Set Union}} and {{Defof|Power Set}}
}}
{{eqn | ll= \leadsto
      | l = X
      | o = \subseteq
      | r = S \cup T
      | c = {{Defof|Set Union}}
}}
{{eqn | ll= \leadsto
      | l = X
      | o = \in
      | r = \powerset {S \cup T}
      | c = {{Defof|Power Set}}
}}
{{end-eqn}}
{{Qed}}
Theorem: Intersection of Power Sets

The intersection of the power sets of two sets $S$ and $T$ is equal to the power set of their intersection:
:$\powerset S \cap \powerset T = \powerset {S \cap T}$

Proof:
{{begin-eqn}}
{{eqn | l = X
      | o = \in
      | r = \powerset {S \cap T}
      | c = 
}}
{{eqn | ll= \leadstoandfrom
      | l = X
      | o = \subseteq
      | r = S \cap T
      | c = {{Defof|Power Set}}
}}
{{eqn | ll= \leadstoandfrom
      | l = X
      | o = \subseteq
      | r = S \land X \subseteq T
      | c = {{Defof|Set Intersection}}
}}
{{eqn | ll= \leadstoandfrom
      | l = X
      | o = \in
      | r = \powerset S \land X \in \powerset T
      | c = {{Defof|Power Set}}
}}
{{eqn | ll= \leadstoandfrom
      | l = X
      | o = \in
      | r = \powerset S \cap \powerset T
      | c = {{Defof|Set Intersection}}
}}
{{end-eqn}}
{{qed}}
Theorem: Cantor-Bernstein-Schröder Theorem

If a subset of one set is equivalent to the other, and a subset of the other is equivalent to the first, then the two sets are themselves equivalent:
:$\forall S, T: T \sim S_1 \subseteq S \land S \sim T_1 \subseteq T \implies S \sim T$

Proof:
Recursively define a sequence $\langle C_n \rangle$ in the power set of $S$ as follows:
:$C_0 = S \setminus T$, the difference between $S$ and $T$.
:$C_{n + 1} = f \sqbrk {C_n}$, the image of $C_n$ under $f$.
Let $\ds C := \bigcup_{n \mathop \in \N} C_n$.
Define a mapping $h: S \to T$ as follows:
:$\map h x = \begin {cases} \map f x & : x \in C \\ x & : x \notin C \end {cases}$
=== $h$ is a mapping from $S$ to $T$ ===
By Law of Excluded Middle, for each $x \in S$:
:$x \in C$
or:
:$x \notin C$
Thus the construction produces a mapping on S.
It remains to be shown that:
:$\forall x \in S: \map h x \in T$
Let $x \in C$.
Then:
:$\map h x = \map f x \in T$
Let $x \notin C$.
Then by Set is Subset of Union of Family:
:$x \notin C_0$
As $x \in S$:
:$x \in S \setminus C_0$
by the definition of set difference.
By Relative Complement of Relative Complement:
:$S \setminus C_0 = T$
Thus $x \in T$ by the definition of subset.
As $\map h x = x$ in this case:
:$\map h x \in T$
{{qed|lemma}}
=== $h$ is injective ===
Let $x, y \in S$.
Suppose that $\map h x = \map h y$.
By Law of Excluded Middle for Two Variables:
:$\paren {x \in C} \land \paren {y \in C}$
or:
:$\paren {x \notin C} \land \paren {y \notin C}$
or:
:$\paren {x \in C} \land \paren {y \notin C}$
or:
:$\paren {x \notin C} \paren {y \in C}$
Let $x, y \in C$.
Then $x = y$ because $f$ is injective.
Let $x, y \notin C$.
Then $x = y$ by Identity Mapping is Injection.
Let $x \in C$ and $y \notin C$.
Then $x \in C_n$ for some $n$ by the definition of union.
By Set is Subset of Union of Family:
:$\map h x = \map f x \in C_{n + 1} \subseteq C$ 
Thus $\map h x \in C$.
:$\map h y = y$ by the definition of $h$.
Since $y \notin C$, this contradicts the assumption that $\map h x = \map h y$.
The argument for the case of $x \notin C$ and $y \in C$ is identical to the preceding.
Thus $\map h x = \map h y \implies x = y$ for all $x, y \in S$, so $h$ is injective.
{{qed|lemma}}
=== $h$ is surjective ===
Let $y \in T$.
By Law of Excluded Middle:
:$y \in C$
or:
:$y \notin C$
Let $y \notin C$.
Then:
:$\map h y = y$
Let $y \in C$.
Then as $y \notin C_0 = S \setminus T$:
:$\exists n \in \N_{>0}: y \in C_{n + 1}$
Thus:
:$\exists x \in C_n: y = \map f x$
By the definition of union:
:$x \in C$
Thus:
:$\map h x = \map f x = y$
Thus:
:$\forall y \in T: \exists x \in S: \map h x = y$
Thus by definition, $h$ is surjective.
{{qed}}
Theorem: Cantor-Bernstein-Schröder Theorem

If a subset of one set is equivalent to the other, and a subset of the other is equivalent to the first, then the two sets are themselves equivalent:
:$\forall S, T: T \sim S_1 \subseteq S \land S \sim T_1 \subseteq T \implies S \sim T$

Proof:
Define a mapping $E: \powerset S \to \powerset S$ as:
:$\map E K = S \setminus \paren {T \setminus f \sqbrk K}$
where $f \sqbrk K$ is the image of $K$ under $f$.
Then:
:$\map E K = \paren {S \setminus T} \cup f \sqbrk K$
By Image of Subset under Relation is Subset of Image and {{Corollary|Set Union Preserves Subsets}}, $E$ is increasing.
Thus by Knaster-Tarski Lemma: Power Set, $E$ has a fixed point $X$.
Then by definition of fixed point:
:$\map E X = X$
That is:
:$\paren {S \setminus \paren {T \setminus f \sqbrk X} } = X$
Taking the set difference from $S$:
:$T \setminus f \sqbrk X = S \setminus X$
Let $f'$ be the restriction of $f$ to $X \times f \sqbrk X$.
By Injection to Image is Bijection, $f'$ is a bijection.
By Identity Mapping is Bijection, the identity mapping $I_{S \mathop \setminus X}$ from $S \setminus X$ to $T \setminus f \sqbrk X$ is a bijection.
Thus by Union of Bijections with Disjoint Domains and Codomains is Bijection, $g = f' \cup i$ is the bijection we seek.
{{qed}}
Theorem: Cantor-Bernstein-Schröder Theorem

If a subset of one set is equivalent to the other, and a subset of the other is equivalent to the first, then the two sets are themselves equivalent:
:$\forall S, T: T \sim S_1 \subseteq S \land S \sim T_1 \subseteq T \implies S \sim T$

Proof:
Define $C = \{f^k(x) | k \in \N, x \in S \setminus T \}$.
Clearly, $C = C_0 \cup C_1$, where:
$C_0 = S \setminus T$, the difference between $S$ and $T$, 
$C_1 = \{f^k(x) | k \in \N_{> 0}, x \in S \setminus T \}$.
Note, that $S \setminus C_0 = S \setminus (S \setminus T) = S \cap T = T$ (use this theorem and $T \subseteq S$).
Obviously, $im(f|C) = C_1$.
Define a mapping $h: S \to S$ as follows:
$\map h x = \begin {cases} \map f x & : x \in C \\ x & : x \notin C \end {cases}$
Clearly, $h = f|C \cup I_{S \setminus C}$, where $I_{S \setminus C}$ is the  identity mapping on the set $S \setminus C$.
Note, that $dom(h) = S$;
$im(h) = im(f|C) \cup im(I_{S \setminus C}) =$
$C_1 \cup (S \setminus C) =$
$C_1 \cup (S \setminus (C_0 \cup C_1)) =$
$S \setminus C_0 =$
$T$.
Also, $h$ is an injection because $h$ is the union of the injections $f|C$ (Restriction of Injection is Injection) and $I_{S \setminus C}$,
and also $dom(f|C) \cap dom(I_{S \setminus C}) = \{\}$
and $im(f|C) \cap im(I_{S \setminus C}) = C_1 \cap (S \setminus C) = \{\}$ because $C_1 \subseteq C$.
Now $h$ is a bijection $S \to T$ because $dom(h) = S, im(h) = T$ and $h$ is an injection.
{{qed}}
Theorem: Cantor-Bernstein-Schröder Theorem

If a subset of one set is equivalent to the other, and a subset of the other is equivalent to the first, then the two sets are themselves equivalent:
:$\forall S, T: T \sim S_1 \subseteq S \land S \sim T_1 \subseteq T \implies S \sim T$

Proof:
From the facts that $T \sim S_1$ and $S \sim T_1$, we can set up the two bijections:
:$f: S \to T_1$
:$g: T \to S_1$
Let:
:$S_2 = g \sqbrk {f \sqbrk S} = g \sqbrk {T_1} \subseteq S_1$
and:
:$T_2 = f \sqbrk {g \sqbrk T} = f \sqbrk {S_1} \subseteq T_1$
So $S_2 \subseteq S_1$ and $S_2 \sim S$, while $T_2 \subseteq T_1$, and $T_2 \sim T$.
For each natural number $k$, let $S_{k + 2} \subseteq S$ be the image of $S_k$ under the mapping $g \circ f$.
{{explain|Why do these superset relations hold?}}
Then:
:$S \supseteq S_1 \supseteq S_2 \supseteq \ldots \supseteq S_k \supseteq S_{k + 1} \ldots$
Let $\ds D = \bigcap_{k \mathop = 1}^\infty S_k$.
{{explain|Why can we represent it so?}}
Now we can represent $S$ as:
{{begin-eqn}}
{{eqn | n = 1
      | l = S
      | r = \paren {S \setminus S_1} \cup \paren {S_1 \setminus S_2} \cup \ldots \cup \paren {S_k \setminus S_{k + 1} } \cup \ldots \cup D
}}
{{end-eqn}}
where $S \setminus S_1$ denotes set difference.
{{explain}}
Similarly, we can represent $S_1$ as:
{{begin-eqn}}
{{eqn | n = 2
      | l = S_1
      | r = \paren {S_1 \setminus S_2} \cup \paren {S_2 \setminus S_3} \cup \ldots \cup \paren {S_k \setminus S_{k + 1} } \cup \ldots \cup D
}}
{{end-eqn}}
Now let:
{{begin-eqn}}
{{eqn | l = M
      | r = \paren {S_1 \setminus S_2} \cup \paren {S_3 \setminus S_4} \cup \paren {S_5 \setminus S_6} \cup \ldots
      | c = 
}}
{{eqn | l = N
      | r = \paren {S \setminus S_1} \cup \paren {S_2 \setminus S_3} \cup \paren {S_4 \setminus S_5} \cup \ldots
      | c = 
}}
{{eqn | l = N_1
      | r = \paren {S_2 \setminus S_3} \cup \paren {S_4 \setminus S_5} \cup \paren {S_6 \setminus S_7} \cup \ldots
      | c = 
}}
{{end-eqn}}
and rewrite $(1)$ and $(2)$ as:
{{begin-eqn}}
{{eqn | n = 3
      | l = S
      | r = D \cup M \cup N
}}
{{eqn | n = 4
      | l = S_1
      | r = D \cup M \cup N_1
}}
{{end-eqn}}
Now:
{{begin-eqn}}
{{eqn | l = g \circ f \sqbrk {S \setminus S_1} = \paren {S_2 \setminus S_3}
      | o = \leadsto
      | r = \paren {S \setminus S_1} \sim \paren {S_2 \setminus S_3}
      | c = 
}}
{{eqn | l = g \circ f \sqbrk {S_2 \setminus S_3} = \paren {S_4 \setminus S_5}
      | o = \leadsto
      | r = \paren {S_2 \setminus S_3} \sim \paren {S_4 \setminus S_5}
      | c = 
}}
{{end-eqn}}
{{handwaving}}
and so on.
So $N \sim N_1$.
It follows from $(3)$ and $(4)$ that a bijection can be set up between $S$ and $S_1$.
But $S_1 \sim T$.
Therefore $S \sim T$.
{{qed}}
Theorem: Cantor-Bernstein-Schröder Theorem

If a subset of one set is equivalent to the other, and a subset of the other is equivalent to the first, then the two sets are themselves equivalent:
:$\forall S, T: T \sim S_1 \subseteq S \land S \sim T_1 \subseteq T \implies S \sim T$

Proof:
By Injection to Image is Bijection:
:$g: T \to g \sqbrk T$ is a bijection.
Thus $T$ is equivalent to $g \sqbrk T$.
By Composite of Injections is Injection $g \circ f: S \to g \sqbrk T \subset S$ is also an injection (to a subset of the domain of $g \circ f$).
Then by Cantor-Bernstein-Schröder Theorem: Lemma:
:There exists a bijection $h: S \to g \sqbrk T$.
Thus $S$ is equivalent to $g \sqbrk T$.
We already know that $T$ is equivalent to $g \sqbrk T$.
Thus by Set Equivalence behaves like Equivalence Relation, $S$ is equivalent to $T$.
By the definition of set equivalence:
:There is a bijection $\phi: S \to T$.
{{qed}}