nyuuzyou/wikis huggingface dataset:
Canonical P-adic Expansion of Rational is Eventually Periodic/Necessary Condition

== Theorem ==
Let $\struct {\Q_p, \norm {\,\cdot\,}_p}$ be the $p$-adic numbers for some prime $p$.
Let $x$ be a rational number.
Then:
:the canonical expansion of $x$ is eventually periodic.
== Proof ==
Let $\ldots d_n \ldots d_2 d_1 d_0 . d_{-1} d_{-2} \ldots d_{-m}$ be the canonical expansion of $x$.
It is sufficient to show that the canonical expansion $\ldots d_n \ldots d_2 d_1 d_0$ is eventually periodic.
Let $y$ be the $p$-adic number with canonical expansion:
:$\ldots d_n \ldots d_2 d_1 d_0$
We have:
:$y = x - \ds \sum_{i \mathop = -m}^{-1} d_i p^i$ 
So:
:$y$ is a rational number
By definition of $p$-adic integer:
:$y$ is a $p$-adic integer
Let:
:$y = \dfrac a b : a \in \Z, b \in Z_{> 0}$ are coprime
From Characterization of Rational P-adic Integer:
:$p \nmid b$
From Prime not Divisor implies Coprime:
:$b, p$ are coprime
=== Lemma 1 ===
=== Lemma 2 ===
For all $n \in \N$, let:
:$A_n = \dfrac a b - \paren{p^{n + 1} \dfrac {r_n} b}$
Then:
:$\dfrac a b = A_n + \paren{p^{n + 1} \dfrac {r_n} b}$
From Lemma 1, for all $n \in \N$:
:$A_n \in \N$
:$0 \le A_n \le p^{n+1} - 1$
=== Lemma 3 ===
=== Lemma 4 ===
=== Lemma 5 ===
It follows that $\ldots d_n \ldots d_2 d_1 d_0$ is eventually periodic.
Category:Canonical P-adic Expansion of Rational is Eventually Periodic
Canonical P-adic Expansion of Rational is Eventually Periodic/Sufficient Condition

== Theorem ==
Let $\struct {\Q_p, \norm {\,\cdot\,}_p}$ be the $p$-adic numbers for some prime $p$.
Let $x \in \Q_p$.
Let the canonical expansion of $x$ be eventually periodic.
Then:
:$x$ be a rational number
== Proof ==
Let the canonical expansion of $x$ be eventually periodic.
=== Lemma 6 ===
To show that $x$ is a rational number it is sufficient to show that $y$ is a rational number.
Let:
:$\dots d_{k - 1} \ldots d_1 d_0 d_{k - 1} \ldots d_1 d_0 d_{k - 1} \ldots d_1 d_0$
be the periodic canonical expansion of $y$.
By definition of a canonical expansion:
:$y = d_0 + d_1 p + \cdots + d_{k - 1} p^{k - 1} + d_0 p^k + d_1 p^{k + 1} + \cdots + d_{k - 1} p^{2 k - 1} + d_0 p^{2 k} + \cdots$
Let $a = d_0 + d_1 p + \cdots + d_{k - 1} p^{k - 1}$.
Then:
:$y = a \paren {1 + p^k + p^{2 k} + \cdots}$
=== Lemma 7 ===
Then:
:$y = \dfrac a {1 - p^k}$
Hence:
:$y$ is a rational number
It follows that $x$ is a rational number.
Category:Canonical P-adic Expansion of Rational is Eventually Periodic
Canonical Preordering of C*-Algebra is Antisymmetric

== Theorem ==
Let $\struct {A, \ast, \norm {\, \cdot \,} }$ be a $\text C^\ast$-algebra.
Let $\le_A$ be the canonical preordering of $A$.
Let $a, b \in A$ such that:
:$a \le_A b$
and:
:$b \le_A a$
Then $a = b$.
That is, $\le_A$ is antisymmetric and hence $\le_A$ is a partial ordering.
== Proof ==
From the definition of $\le_A$ we have:
:$b - a$ is positive.
Hence $b - a$ is Hermitian and:
:$\map {\sigma_A} {b - a} \subseteq \hointr 0 \infty$
From the Spectral Mapping Theorem for Polynomials, we also have:
:$\map {\sigma_A} {a - b} = \set {-t : t \in \map {\sigma_A} {a - b} } \subseteq \hointl {-\infty} 0$ 
Again from the definition of $\le_A$ we have:
:$a - b$ is positive.
Hence:
:$\map {\sigma_A} {a - b} \subseteq \hointr 0 \infty$
Hence we have:
:$\map {\sigma_A} {a - b} \subseteq \hointr 0 \infty \cap \hointl {-\infty} 0 = \set 0$
From Spectrum of Element of Banach Algebra is Non-Empty, we have $\map {\sigma_A} {a - b} \ne \O$.
Hence $\map {\sigma_A} {a - b} = \set 0$.
So $\map {r_A} {a - b} = 0$ where $r_A$ denotes spectral radius.
Hence from Spectral Radius of Normal Element of C*-Algebra Equal to Norm: Corollary we have $a - b = {\mathbf 0}_A$.
Hence $a = b$.
Category:Canonical Preorderings of C*-Algebras
Canonical Preordering of C*-Algebra of Continuous Functions Vanishing at Infinity

== Theorem ==
Let $X$ be a locally compact Hausdorff space. 
Let $A = \map {\CC_0} X$ be the set of continuous complex-valued functions vanishing at infinity.
Consider $A$ as a $\text C^\ast$-algebra with pointwise addition, pointwise scalar multiplication, pointwise multiplication and pointwise complex conjugation.
Let $\le_A$ be the canonical preordering of $A$.
Let $f, g \in \map {\CC_0} X$. 
We have $f \le_A g$ $\map g x - \map f x \in \R_{\ge 0}$ for each $x \in X$.
== Proof ==
=== Sufficient Condition ===
Suppose that:
:$\map g x - \map f x \in \R_{\ge 0}$ for each $x \in X$.
Then from Complex Number equals Conjugate iff Wholly Real we have:
:$\overline {\map g x - \map f x} = \map g x - \map f x$
Hence $g - f$ is Hermitian in $A$.
From Spectrum of Element of Space of Continuous Functions Vanishing at Infinity, we have:
:$\map {\sigma_A} {g - f} = \paren {g - f} \sqbrk X \cup \set 0 \subseteq \hointr 0 \infty$
So $g - f$ is positive. 
Hence $f \le_A g$. 
=== Necessary Condition ===
Suppose that $f \le_A g$.
Then $g - f$ is positive and:
:$\map {\sigma_A} {g - f} \subseteq \hointr 0 \infty$
From Spectrum of Element of Space of Continuous Functions Vanishing at Infinity we have:
:$\set {\map g x - \map f x : x \in X} \subseteq \map {\sigma_A} {g - f} \subseteq \hointr 0 \infty$
That is:
:$\map g x - \map f x \in \R_{\ge 0}$ for each $x \in X$.
Category:Canonical Preorderings of C*-Algebras
Category:Complex-Valued Functions Vanishing at Infinity
Cantor's Diagonal Argument

== Theorem ==
Let $S$ be a set such that $\card S > 1$, that is, such that $S$ is not a singleton.
Let $\mathbb F$ be the set of all mappings from the natural numbers $\N$ to $S$:
:$\mathbb F = \set {f: \N \to S}$
Then $\mathbb F$ is uncountably infinite.
=== Corollary ===
== Proof ==
First we note that as $\card S > 1$, there are at least two elements of $S$ which are distinct.
Call these distinct elements $a$ and $b$.
That is:
:$\exists a, b \in S: a \ne b$
First we show that $\mathbb F$ is infinite, as follows.
For each $m \in \N$, let $\phi_m$ be the mapping defined as:
:$\map {\phi_m} n = \begin{cases}
a & : n \ne m \\
b & : n = m
\end{cases}$
Then:
:$\forall m_1, m_2 \in \N: m_1 \ne m_2 \implies \phi_{m_1} \ne \phi_{m_2}$
as:
:$b = \map {\phi_{m_1} } {m_1} \ne \map {\phi_{m_2} } {m_1} = a$
So the mapping $\Psi: \N \to \mathbb F$ defined as:
:$\map \Psi n = \phi_n$
is an injection.
Thus $\mathbb F$ is infinite from Infinite if Injection from Natural Numbers.
Next we show that $\mathbb F$ is uncountable.
Let $\Phi: \N \to \mathbb F$ be a mapping.
For each $n \in \N$ let $f_n: \N \to S$ be the function $\map \Phi n$.
Let us define $g: \N \to \N$ by:
:$\map g n = \begin{cases}
a & : \map {f_n} n \ne a \\
b & : \map {f_n} n = a
\end{cases}$
Then $g \in \mathbb F$, but:
:$\forall n \in \N: \map g n \ne \map {f_n} n$
and so $g \ne f_n$.
Since $g$ is an element of $\mathbb F$ which is different from all the values taken by $\Phi$, it follows that $\Phi$ is not a surjection and hence not a bijection.
Thus no bijection exists between $\mathbb F$ and $\N$.
By definition of countably infinite, $\mathbb F$ is countably infinite there is a bijection between $\mathbb F$ and $\N$.
Therefore $\mathbb F$ is uncountable.
== Also known as ==
The technique of Cantor's Diagonal Argument is also referred to as diagonalization.
== Examples ==
== Also see ==
* Set of Infinite Sequences is Uncountable, which is a basic application of this technique.
== Historical Note ==
== Sources ==
* : Chapter $1$: Preliminaries: $1.4$ Set Notation: Infinite sets
* : Chapter $1$: General Background: $\S 3$ A non-denumerable set
* 
Category:Cantor's Diagonal Argument
Category:Mapping Theory
Category:Uncountable Sets
Category:Proof Techniques
Category:Diagonal Arguments
Cantor's Diagonal Argument/Corollary

== Theorem ==
Let $S$ be a set such that $\card S > 1$, that is, such that $S$ is not a singleton.
Let $\mathbb G$ be the set of all mappings from the integers $\Z$ to $S$:
:$\mathbb G = \set {f: \Z \to S}$
Then $\mathbb G$ is uncountably infinite.
== Proof ==
Let $\mathbb F$ be the set of all mappings from the natural numbers $\N$ to $S$:
:$\mathbb F = \set {f: \N \to S}$
From Cantor's Diagonal Argument, $\mathbb F$ is uncountably infinite.
Let $s \in S$ be an arbitrary distinguished element of $S$.
Let $\mathbb H$ be the set of mappings $h: \Z \to S$ defined as:
:$\forall f \in \mathbf F: \forall x \in \Z: \map h x = \begin {cases} \map f x & : x \ge \0 \\ s & : x < 0 \end {cases}$
It can be shown that $\mathbf H$ and $\mathbf F$ are equivalent.
Hence as $\mathbb F$ is uncountable, $\mathbf H$ is likewise uncountable.
We also have that $\mathbf H$ is a subset of $\mathbf G$.
 $\mathbf G$ is countable.
Then from Subset of Countable Set is Countable it follows that $\mathbf H$ is countable.
Hence by Proof by Contradiction it follows that $\mathbf G$ is uncountable.
Category:Cantor's Diagonal Argument
Cantor's Paradox

== Paradox ==
Let $\CC$ be the set of all sets.
Let $\powerset \CC$ denote the power set of $C$.
Is the cardinality of $\CC$ greater than or equal to the cardinality of $\powerset \CC$?
The sets of $\powerset \CC$ must be elements of $\CC$.
Hence:
:$\powerset \CC \subseteq \CC$
Hence:
:$\card {\powerset \CC} \le \card \CC$
But by Cantor's Theorem:
:$\card {\powerset \CC} > \card \CC$
== Resolution ==
This is an antinomy.
The set of all sets is not a set.
== Sources ==
* 
* 
Category:Antinomies
Cantor's Theorem

== 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 1 ==
== Proof 2 ==
== Proof 3 ==
== Also see ==
Compare this with Russell's Paradox.
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 17$: Finite Sets: Exercise $17.14$
* : $\S 10.4$ $\S 10.5$
* : $\S 4$: Number systems $\text{I}$: A set-theoretic approach
* : Chapter $4$: Mappings: Exercise $11$
* 
* 
* : Chapter $1$: General Background: $\S 4$ Larger and smaller: Theorem $4.1$ (Cantor's theorem)
Category:Cantor's Theorem
Category:Surjections
Category:Power Set
Cantor's Theorem/Proof 1

== Theorem ==
== Proof ==
 $S$ is a set with a surjection $f: S \to \powerset S$.
Then:
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.
== Sources ==
* : $\S 2.5$: The power of a set: Theorem $6$
* : Chapter $1$: Mappings: $\S 14$
* : Appendix $\text{A}.6$: Cardinality: Theorem $\text{A}.6.1$
* : Chapter $1$: General Background: $\S 3$ A non-denumerable set
Category:Cantor's Theorem
Cantor's Theorem/Proof 2

== Theorem ==
== 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 = \left\{{x \in S: \neg \left({x \in \map f x}\right)}\right\}$.
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.
:
: $\exists a \in S: T = \map f a$
Suppose that:
: $a \in \map f a$
Then by the definition of $T$:
: $\neg \left({a \in T}\right)$
Thus since $T = f \left({a}\right)$:
: $\neg \left({a \in \map f a }\right)$
By Rule of Implication:
: $(1) \quad a \in \map f a \implies \neg \left({ a \in \map f a }\right)$
Suppose instead that:
: $\neg \left({a \in \map f a}\right)$
Then by the definition of $T$:
: $a \in T$
Thus since $T = f \left({a}\right)$:
: $a \in \map f a$
By Rule of Implication:
: $(2) \quad \neg \left({ a \in \map f a }\right) \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.
== Sources ==
* : $2.10$
* : Appendix $\text{A}$: Set Theory: Cantor's Theorem
Category:Cantor's Theorem
Cantor's Theorem/Proof 3

== Theorem ==
== 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 .
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.
:
:$\exists a \in S: T = \map f a$
This means that $f$ maps $a$ to $T$.
We claim that $a \notin T$.
:
:$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.
Category:Cantor's Theorem
Cantor's Theorem (Strong Version)

== Theorem ==
Let $S$ be a set.
Let $\map {\PP^n} S$ be defined recursively by:
:$\map {\PP^n} S = \begin{cases}
S & : n = 0 \\
\powerset {\map {\PP^{n - 1} } S} & : n > 0
\end{cases}$
where $\powerset S$ denotes the power set of $S$.
Then $S$ is not equivalent to $\map {\PP^n} S$ for any $n > 0$.
== Proof 1 ==
== Proof 2 ==
== Also see ==
* Cantor's Theorem
== Sources ==
* : Chapter $1$: General Background: $\S 4$ Larger and smaller
Category:Power Set
Category:Cantor's Theorem
Cantor's Theorem (Strong Version)/Proof 1

== Theorem ==
== Proof ==
We temporarily introduce the notation:
:$a^n = \begin{cases}
a : & n = 0 \\
\set {a^{n - 1} } : & n > 0
\end{cases}$
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.
== Sources ==
* : Introduction to Set Theory: $2$. Set Theoretical Equivalence and Denumerability
Category:Cantor's Theorem
Cantor's Theorem (Strong Version)/Proof 2

== Theorem ==
== 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 ===
Category:Cantor's Theorem
Cantor's Theorem (Strong Version)/Proof 2/Induction Step

== Theorem ==
=== Induction Step ===
This is our induction hypothesis:
:There is no surjection from $S$ onto $\map {\PP^k} S$.
We are to show:
:There is no surjection from $S$ onto $\map {\PP^{k + 1} } S$.
=== Proof 1 ===
=== Proof 2 ===
Category:Cantor's Theorem
Cantor's Theorem (Strong Version)/Proof 2/Induction Step/Proof 1

== Theorem ==
=== Induction Step ===
This is our induction hypothesis:
:There is no surjection from $S$ onto $\map {\PP^k} S$.
We are to show:
:There is no surjection from $S$ onto $\map {\PP^{k + 1} } S$.
== Proof ==
It is assumed that $\map P k$ is true.
 that $f: S \to \map {\PP^{k + 1} } S$ is a surjection.
Define the mapping $g: S \to \map {\PP^k} S$ as:
:$\ds \map g x = \bigcup \map f x$
This is actually a mapping into $\map {\PP^k} S$, as follows:
:$\map f x \in \map {\PP^{k + 1} } S = \powerset {\map {\PP^k} S}$
By the definition of power set:
:$\map f x \subseteq \map {\PP^k} S$
Thus each element of $\map f x$ is a subset of $\map {\PP^{k - 1} } S$.
Thus by Union of Subsets is Subset:
:$\ds \bigcup \map f x \subseteq \map {\PP^{k - 1} } S$
Therefore:
:$\ds \bigcup \map f x \in \map {\PP^k} S$
That is, $\map g x$ is a mapping into $\map {\PP^k} S$.
Next we have that:
:$\forall y \in \map {\PP^k} S: \set y \in \map {\PP^{n + 1} } S$
But by hypothesis $f$ is surjective, and so:
:$\exists x \in S: \map f x = \set y$
Then:
:$\ds \map g x = \bigcup \set y = y$
As this holds for all such $y$, $g$ is surjective.
But this contradicts the induction hypothesis.
Thus we conclude that the theorem holds for all $n$.
Category:Cantor's Theorem
Cantor's Theorem (Strong Version)/Proof 2/Induction Step/Proof 2

== Theorem ==
=== Induction Step ===
This is our induction hypothesis:
:There is no surjection from $S$ onto $\map {\PP^k} S$.
We are to show:
:There is no surjection from $S$ onto $\map {\PP^{k + 1} } S$.
== 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 Image of Empty Set is Empty Set: Corollary 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.
 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$.
Category:Cantor's Theorem
Cantor-Bernstein-Schröder Theorem

== 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$
Alternatively, from Equivalence of Definitions of Dominate (Set Theory), this can be expressed as:
:$\forall S, T: T \preccurlyeq S \land S \preccurlyeq T \implies S \sim T$
where $T \preccurlyeq S$ denotes the fact that $S$ dominates $T$.
That is:
:If $\exists f: S \to T$ and $\exists g: T \to S$ where $f$ and $g$ are both injections, then there exists a bijection from $S$ to $T$.
== Proof Strategy ==
This theorem states in set theoretical concepts the "intuitively obvious" fact that if $a \le b$ and $b \le a$ then $a = b$.
Care needs to be taken to make well sure of this, because when considering infinite sets, intuition is frequently misleading.
In order to prove equivalence, a bijection needs to be demonstrated.
It can be significantly simpler to demonstrate an injection than a surjection.
So, proving that there is an injection from $S$ to $T$ and also one from $T$ to $S$ may be a lot less work than proving that there is both an injection and a surjection from $S$ to $T$.
== Proof 1 ==
== Proof 2 ==
== Proof 3 ==
== Proof 4 ==
== Proof 5 ==
== Proof 6 ==
== Also known as ==
== Historical Note ==
== Sources ==
* : $\S 2.6$: Theorem $7$
* : $\S 10.03$
* : $\S 8$: Theorem $8.2$: Corollary
* 
* : $2.7$
* : Appendix $\text{A}$: Set Theory: Cardinality
* 
* : Chapter $1$: General Background: $\S 4$ Larger and smaller
Category:Cantor-Bernstein-Schröder Theorem
Category:Set Theory
Category:Injections
Category:Bijections
Category:Cardinals
Cantor-Bernstein-Schröder Theorem/Also known as

== Cantor-Bernstein-Schröder Theorem: Also known as ==
The Cantor-Bernstein-Schröder Theorem is also known as:
* The Cantor-Bernstein Theorem
* The Cantor-Schroeder-Bernstein Theorem or Cantor-Schröder-Bernstein Theorem
* The Schroeder-Bernstein Theorem or Schröder-Bernstein Theorem.
== Sources ==
* : $\S 8$: Theorem $8.2$
* 
* 
* 
* 
* : Chapter $1$: General Background: $\S 4$ Larger and smaller
Category:Cantor-Bernstein-Schröder Theorem
Cantor-Bernstein-Schröder Theorem/Historical Note

== Historical Note on Cantor-Bernstein-Schröder Theorem ==
 raised the Cantor-Bernstein-Schröder Theorem as a conjecture in $1895$.
He first attempted to prove it in his $1897$ paper.
 also stated this theorem in $1896$, but his proof, as well as 's, was flawed.
It was who finally supplied a correct proof in his $1898$ Ph.D. thesis.
== Sources ==
* 
* 
Category:Historical Notes
Cantor-Bernstein-Schröder Theorem/Lemma

== Theorem ==
Let $S$ be a set.
Let $T \subseteq S$.
Suppose that $f: S \to T$ is an injection.
Then there is a bijection $g: S \to T$.
== Proof 1 ==
== Proof 2 ==
== Proof 3 ==
Category:Cantor-Bernstein-Schröder Theorem
Cantor-Bernstein-Schröder Theorem/Lemma/Proof 1

== Theorem ==
== 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$
=== $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.
=== $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.
== Sources ==
Category:Cantor-Bernstein-Schröder Theorem