avewright/proofwiki-math huggingface dataset:
Theorem: Young's Inequality for Products

Let $p, q \in \R_{> 0}$ be strictly positive real numbers such that:
:$\dfrac 1 p + \dfrac 1 q = 1$
Then:
:$\forall a, b \in \R_{\ge 0}: a b \le \dfrac {a^p} p + \dfrac {b^q} q$
Equality occurs {{iff}}:
:$b = a^{p - 1}$

Proof:
The result follows directly if $a = 0$ or $b = 0$.
{{WLOG}}, assume that $a > 0$ and $b > 0$. 
Recall Exponential is Strictly Convex.
Consider:
:$x := \map \ln {a^p}$
:$y := \map \ln {b^q}$
:$\alpha := p^{-1}$
:$\beta := q^{-1}$
Note that {{hypothesis}}:
:$\alpha + \beta = 1$
Thus by definition of strictly convex real function:
:$(1): \quad x \ne y \implies \map \exp {\alpha x + \beta y} < \alpha \map \exp x + \beta \map \exp y$
On the other hand:
:$(2): \quad x = y \implies \map \exp {\alpha x + \beta y} = \alpha \map \exp x + \beta \map \exp y$
since:
:$\map \exp {\alpha x + \beta y} = \map \exp x$
and:
:$\alpha \map \exp x + \beta \map \exp y = \alpha \map \exp x + \beta \map \exp x = \map \exp x$
{{explain|algebra to be worked}}
Therefore:
{{begin-eqn}}
{{eqn | l = a b
      | r = \map \exp {\map \ln {a b} }
      | c = Exponential of Natural Logarithm
}}
{{eqn | r = \map \exp {\ln a + \ln b}
      | c = Sum of Logarithms
}}
{{eqn | r = \map \exp {\frac 1 p p \ln a + \frac 1 q q \ln b}
      | c = {{Defof|Multiplicative Identity}} and {{Defof|Multiplicative Inverse}}
}}
{{eqn | r = \map \exp {\frac 1 p \map \ln {a^p} + \frac 1 q \map \ln {b^q} }
      | c = Logarithms of Powers
}}
{{eqn | o = \le
      | r = \frac 1 p \map \exp {\map \ln {a^p} } + \frac 1 q \map \exp {\map \ln {b^q} }
      | c = by $(1)$ and $(2)$
}}
{{eqn | r = \frac {a^p} p + \frac {b^q} q
      | c = Exponential of Natural Logarithm
}}
{{end-eqn}}
By $(1)$ and $(2)$, the equality:
:$a b = \dfrac {a^p} p + \dfrac {b^q} q$
occurs {{iff}}:
:$\map \ln {a^p} = \map \ln {b^q}$
{{explain|How does that work then?<br>What is not clear here?}}
That is, {{iff}}:
:$b = a^{p - 1}$
{{qed}}
Theorem: Restriction of Monotone Function is Monotone

The restriction of a monotone mapping is monotone.

Proof:
A restriction does not introduce any new arguments.
Hence the result follows trivially from the definition of monotone mapping.
{{qed}}
{{handwaving}}
Theorem: Finite Lexicographic Order on Well-Ordered Sets is Well-Ordering

Let $S$ be a set which is well-ordered by $\preccurlyeq$.
Let $\preccurlyeq_l$ be the lexicographic order on the set $T_n$ of all ordered $n$-tuples of $S$:
:$\tuple {x_1, x_2, \ldots, x_n} \prec \tuple {y_1, y_2, \ldots, y_n}$ {{iff}}:
::$\exists k: 1 \le k \le n$ such that $\forall 1 \le j < k: x_j = y_j$ but $x_k \prec y_k$ in $S$.
{{explain|Disentangle this.}}
Then for a given $n \in \N_{>0}$, $\preccurlyeq_l$ is a well-ordering on $T_n$.

Proof:
Consider $T_n$ where $n \in \N_{>0}$.
It is clear that $\struct {T_1, \preccurlyeq_l}$ is order isomorphic to  $\struct {S, \preccurlyeq}$.
Thus as $\preccurlyeq$ is a well-ordering on $S$, $\preccurlyeq_l$ is a well-ordering on $T_1$.
Now, let us assume that $\preccurlyeq_l$ is a well-ordering on $T_k$ for some $k \in \N: k \ge 1$.
Let $A$ be a non-empty subset of $T_{k + 1}$.
Let $A_1$ be the set of all of the first components of the ordered $n$-tuples that comprise $A$.
Since $A_1$ is a non-empty subset of $S$, and $S$ is itself well-ordered by $\preccurlyeq$, it follows that $A_1$ contains a minimal element $x$ by $\preccurlyeq_l$.
Let $A_x$ be the subset of $A$ in which the first component equals $x$.
We may consider $A_x$ to be a subset of $T_k$ where this first component $x$ has been suppressed.
But we assumed that $T_k$ is well-ordered by $\preccurlyeq_l$.
So $A_x$ contains a minimal element $\tuple {x, x_2, x_3, \ldots, x_{k + 1} }$ by $\preccurlyeq_l$.
This element $\tuple {x, x_2, x_3, \ldots, x_{k + 1} }$ is the minimal element of $A$ by $\preccurlyeq_l$.
Hence, by definition, $T_{k + 1}$ is well-ordered by $\preccurlyeq_l$.
The result follows by induction.
{{qed}}
Theorem: Infinite Lexicographic Order on Well-Ordered Sets is not Well-Ordering

Let $\struct {S, \preccurlyeq}$ be a well-ordered set.
Let $\preccurlyeq_l$ be the lexicographic order on the set $T$ of all ordered tuples of $S$:
:$\tuple {x_1, x_2, \ldots, x_m} \prec \tuple {y_1, y_2, \ldots, y_n}$ {{iff}}:
::$\exists k: 1 \le k \le \map \min {m, n}$ such that $\forall 1 \le j < k: x_j = y_j$ but $x_k \prec y_k$ in $S$
:or:
::$m < n$ and $\forall 1 \le j < m: x_j = y_j$.
Then $\preccurlyeq_l$ is '''not''' a well-ordering on $T$.

Proof:
Consider a set $S = \set {a, b}$ such that $a \prec b$.
Then the set $\set {\tuple b, \tuple {a, b}, \tuple {a, a, b}, \tuple {a, a, a, b}, \ldots}$ has no minimal element by $\preccurlyeq_l$.
{{handwaving}}
Thus $T$ is not well-ordered by $\preccurlyeq_l$.
{{qed}}
Theorem: Transfinite Recursion Theorem/Theorem 1

Let $G$ be a (class) mapping from $\On^{\On}$ to $\On$.
Let $K$ be a class of mappings $f$ that satisfy: 
:the domain of $f$ is some ordinal $y$
:$\forall x \in y: \map f x = \map G {f {\restriction_x} }$
where $f {\restriction_x}$ denotes the restriction of $f$ to $x$.
Let $F = \bigcup K$ be the union of $K$.
Then:
:$(1): \quad F$ is a mapping with domain $\On$
:$(2): \quad \forall x \in \On: \map F x = \map G {F {\restriction_x} }$
:$(3): \quad F$ is unique. That is, if another mapping $A$ has the above two properties, then $A = F$.

Proof:
First a lemma:
Theorem: Squeeze Theorem for Absolutely Convergent Series

Let $\ds \sum \size {a_n}$ be an absolutely convergent series in $\R$.
Suppose that:
:$\ds -\sum \size {a_n} = \sum \size {a_n}$
Then $\ds \sum a_n$ equals the above two series.

Proof:
From Absolutely Convergent Real Series is Convergent, the convergence of:
:$\ds \sum_{n \mathop = 1}^\infty \size {a_n}$
implies that of:
:$\ds \sum_{n \mathop = 1}^\infty a_n$
By Negative of Absolute Value:
:$\ds -\size {\sum_{n \mathop = 1}^j a_n} \le \sum_{n \mathop = 1}^j a_n \le \size {\sum_{n \mathop = 1}^j a_n}$
By repeated application of Triangle Inequality:
:$\ds -\sum_{n \mathop = 1}^j \size {a_n} \le \sum_{n \mathop = 1}^j a_n \le \sum_{n \mathop = 1}^j \size {a_n}$
We have {{hypothesis}} that the leftmost and rightmost terms converge as $j \to +\infty$.
Hence the result, from Squeeze Theorem for Real Sequences.
{{qed}}
Category:Series
q4yusedjoqvhax9wc72lfniszxfcr1e
Theorem: N Choose k is not greater than n^k

:$\forall n \in \Z, k \in \Z: 1 \le k \le n: \dbinom n k < n^k$ 
where $\dbinom n k$ is a binomial coefficient.
Equality holds when $k = 0$ and $k = 1$.

Proof:
First let $k > 1$.
{{begin-eqn}}
{{eqn | l = \binom n k
      | r = \frac {n!} {k! \, \paren {n - k}!}
      | c = {{Defof|Binomial Coefficient}}
}}
{{eqn | o = <
      | r = \frac {n!} {\paren {n - k}!}
      | c = as $k! > 0$ by {{Defof|Factorial}}
}}
{{eqn | r = \underbrace {n \paren {n - 1} \cdots (n - k + 1)}_{k \text { factors} }
      | c = expanding the factorials
}}
{{eqn | o = <
      | r = n^k
      | c = for all $n, k$ here considered
}}
{{end-eqn}}
For $k > 1$, the product has at least two factors.
Hence at least one factor is strictly less than $n$.
{{qed|lemma}}
Let $k < 0$.
By definition of binomial coefficient:
:$\dbinom n k = 0$
while $n^k > 0$.
Hence the result follows for $k < 0$.
{{qed|lemma}}
Finally let $0 \le k \le 1$.
From Binomial Coefficient with Zero:
:$\dbinom n 0 = 1 = n^0$
From Binomial Coefficient with One:
:$\dbinom n 1 = n = n^1$
So equality holds when $k = 0$ or $k = 1$.
{{qed|lemma}}
Hence the result has been shown to hold for all $k \in \Z$.
{{qed}}
Theorem: N Choose k is not greater than n^k

:$\forall n \in \Z, k \in \Z: 1 \le k \le n: \dbinom n k < n^k$ 
where $\dbinom n k$ is a binomial coefficient.
Equality holds when $k = 0$ and $k = 1$.

Proof:
We dismiss the cases where $k < 0$ by observing that in such cases $\dbinom n k = 0$ while $n^k > 0$.
Similarly we dismiss $k = 0$: we have $\dbinom n 0 = 1 = n^0$.
Let:
: $N = \set {1, \ldots, n}$
: $K = \set {1, \ldots, k}$
From Cardinality of Set of Strictly Increasing Mappings, $\dbinom n k$ is the number of strictly increasing mappings from $K$ to $N$.
From Cardinality of Set of All Mappings, $n^k$ is the number of all mappings from $K$ to $N$.
For $k = 1$ there is exactly 1 mapping from $K$ to $N$ which is trivially strictly increasing.
Otherwise we have that $K$ has more than one element, and so therefore does $n$.
The mapping $f: K \to N: \forall s \in K: \map f s = 1$ is clearly not a strictly increasing mapping.
So not all mappings from $K$ to $N$ are strictly increasing.
Hence a strict inequality holds, and so $\dbinom n k < n^k$.
{{qed}}
Theorem: Set is Element of its Power Set

A set is an element of its power set:
:$S \in \powerset S$

Proof:
{{begin-eqn}}
{{eqn | q = \forall S
      | l = S
      | o = \subseteq
      | r = S
      | c = Set is Subset of Itself
}}
{{eqn | ll= \leadsto
      | q = \forall S
      | l = S
      | o = \in
      | r = \powerset S
      | c = {{Defof|Power Set}}
}}
{{end-eqn}}
{{qed}}
Theorem: Power Set of Empty Set

The power set of the empty set $\O$ is the set $\set \O$.

Proof:
From Empty Set is Element of Power Set and Set is Element of its Power Set:
:$\O \in \powerset \O$
From Empty Set is Subset of All Sets:
:$S \subseteq \O \implies S = \O$
That is:
:$S \in \powerset \O \implies S = \O$
Hence the only element of $\powerset \O$ is $\O$.
{{qed}}
Theorem: Symmetric Difference is Subset of Union

The symmetric difference of two sets is a subset of their union:
:$S \symdif T \subseteq S \cup T$

Proof:
{{begin-eqn}}
{{eqn | l = S \symdif T
      | r = \paren {S \cup T} \setminus \paren {S \cap T}
      | c = {{Defof|Symmetric Difference|index = 2}}
}}
{{eqn | o = \subseteq
      | r = \paren {S \cup T}
      | c = Set Difference is Subset
}}
{{end-eqn}}
{{qed}}
Theorem: Sum of Projections/Binary Case

Let $H$ be a Hilbert space.
Let $P, Q$ be projections.
Then $P + Q$ is a projection {{iff}} $\Rng P \perp \Rng Q$.

Proof:
=== Necessary Condition ===
Suppose $P + Q$ is a projection. Then:
{{begin-eqn}}
{{eqn | l = P + Q
      | r = \paren {P + Q}^2
      | c = $P + Q$ is an idempotent
}}
{{eqn | r = P^2 + P Q + Q P + Q^2
}}
{{eqn | r = P + P Q + Q P + Q
      | c = $P$ and $Q$ are idempotents
}}
{{eqn | ll= \leadstoandfrom
      | l = PQ + QP
      | r = 0
}}
{{end-eqn}}
Now suppose that $h \in \Rng Q$; say $h = Q q$ for $q \in H$.
Then it follows that $Q h = Q Q q = Q q = h$ as $Q$ is idempotent.
It follows that:
:$0 = P Q h + Q P h = P h + Q P h$
From Characterization of Projections, statement $(6)$, $\innerprod {Q P h} {P h}_H \ge 0$.
Next, observe:
:$0 = \innerprod {P h + Q p h} {P h}_H = \innerprod {P h} {P h}_H + \innerprod {Q P h} {P h}_H$
As the second term is non-negative, the first is non-positive; it follows that $P h = \mathbf 0_H$ from the definition of the inner product.
Hence:
:$h \in \ker P = \paren {\Rng P}^\perp$
It follows that $\Rng Q \perp \Rng P$, as asserted.
{{qed|lemma}}
Theorem: Product of Projections

Let $H$ be a Hilbert space.
Let $P, Q$ be projections.
{{TFAE}}
{{begin-itemize}}
{{item|(1):|$P Q$ is a projection}}
{{item|(2):|$P Q {{=}} Q P$}}
{{item|(3):|$P + Q - P Q$ is a projection}}
{{end-itemize}}
{{MissingLinks|Provide proper linking to the def of addition and multiplication of operators}}

Proof:
The proof proceeds by first showing that $(1)$ is equivalent to $(2)$.
Then, these are combined and shown equivalent to $(3)$.
Theorem: Difference of Projections

Let $H$ be a Hilbert space.
Let $P, Q$ be projections.
{{TFAE}}
{{begin-itemize}}
{{item|(1):|$P - Q$ is a projection}}
{{item|(2):|$P Q {{=}} Q$}}
{{item|(3):|$Q P {{=}} Q$}}
{{end-itemize}}
{{MissingLinks|Provide proper linking to the def of addition of operators}}

Proof:
First it is shown that $(2)$ is equivalent to $(3)$.
Then, equivalence to $(1)$ is shown.
Theorem: Union of Countable Sets of Sets

Let $\AA$ and $\BB$ be countable sets of sets.
Then:
:$\set {A \cup B: A \in \AA, B \in \BB}$
is also countable.

Proof:
Since $\AA$ is countable, its contents can be arranged in a sequence:
:$\AA = \set {A_1, A_2, \ldots}$
Let $B \in \BB$.
Consider the sequence of sets:
:$\sequence {A_1 \cup B, A_2 \cup B, \ldots}$
We may leave out any possible repetitions, and obtain a countable set:
:$\set {A \cup B: A \in \AA}$
for every $B \in \BB$.
Thus as $B$ varies over all the elements of $\BB$, we obtain the countable family:
:$\sequence {A \cup B: A \in \AA}_{\paren {B \mathop \in \BB} }$
From Countable Union of Countable Sets is Countable, their union is countable.
{{qed}}
{{AoC|Countable Union of Countable Sets is Countable|proof}}
Theorem: Union of Countable Sets of Sets

Let $\AA$ and $\BB$ be countable sets of sets.
Then:
:$\set {A \cup B: A \in \AA, B \in \BB}$
is also countable.

Proof:
Both $\AA$ and $\BB$ are countable.
Enumerate their elements by the sequences $\sequence {A_n}_{n \mathop \in \N}$ and $\sequence {B_n}_{n \mathop \in \N}$ respectively.
When one of $\AA$ and $\BB$ would be finite, achieve such sequences by allowing elements to occur multiple times.
Define $\CC := \set {A \cup B: A \in \AA, B \in \BB}$.
For each $C \in \CC$, define the set $N_C := \set {\tuple {i, j} \in \N \times \N: A_i \cup B_j = C}$.
The definition of $\CC$ ensures that $N_C \ne \O$ for all $C \in \CC$.
Consider the lexicographic ordering $\preccurlyeq_l$ on $\N \times \N$.
Combining the Well-Ordering Principle with Finite Lexicographic Order on Well-Ordered Sets is Well-Ordering, $\preccurlyeq_l$ is a well-ordering on $\N \times \N$.
As $N_C \subseteq \N \times \N$ is non-empty, it thus has a smallest element; call it $n_C$.
Define now the map $\phi: \CC \to \N \times \N$ by $\map \phi C = n_C$.
Well-Ordering Minimal Elements are Unique ensures that $\phi$ is well-defined.
Now suppose that $C_1, C_2 \in \CC$ satisfy:
:$\map \phi {C_1} = \map \phi {C_2}$
that is, $n_{C_1} = n_{C_2}$, which in turn equal some $\tuple {i, j} \in \N \times \N$.
As $\tuple {i, j} \in N_{C_1}$ and $\tuple {i, j} \in N_{C_2}$, $C_1 = A_i \cup B_j = C_2$.
It follows that $\phi$ is an injection.
Finally, $\N \times \N$ is countable by Cartesian Product of Countable Sets is Countable.
Let $\psi: \N \times \N \to \N$ be an injection.
Then $\psi \circ \phi: \CC \to \N$ is also an injection by Composite of Injections is Injection.
Hence $\CC$ is countable.
{{qed}}
Theorem: Union of Countable Sets of Sets

Let $\AA$ and $\BB$ be countable sets of sets.
Then:
:$\set {A \cup B: A \in \AA, B \in \BB}$
is also countable.

Proof:
Since $\AA$ and $\BB$ are countable, $\AA \times \BB$ is countable by Cartesian Product of Countable Sets is Countable.
Thus by Surjection from Natural Numbers iff Countable there is a surjection $f: \N \to \AA \times \BB$.
Let $\CC = \set {A \cup B: A \in \AA, B \in \BB}$.
Let $g: \AA \times \BB \to \CC$ be defined by letting $\map g {A, B} = A \cup B$.
$g$ is a surjection:
Let $C \in \CC$.
Then there exist $A \in \AA$ and $B \in \BB$ such that $C = A \cup B$.
By the definition of Cartesian product:
: $\tuple {A, B} \in \AA \times \BB$
Then:
: $\map g {A, B} = A \cup B = C$
It follows that $g$ is a surjection.
By Composite of Surjections is Surjection, $g \circ f: \N \to \CC$ is surjective.
Hence $\CC$ is countable.
{{qed}}
Theorem: Set of Finite Subsets of Countable Set is Countable

Let $A$ be a countable set.
Then the set of finite subsets of $A$ is countable.

Proof:
By the definition of a countable set, there exists an injection $g: A \to \N$.
Let $\FF$ denote the set of all finite subsets of $A$.
Let $f: \FF \to \N$ be the mapping defined by:
:$\ds \map f F = \prod_{k \mathop \in \map g F} p_{k + 1}$
where $p_n$ denotes the $n$th prime number.
We define $\map f \O = 1$, the vacuous product.
Let $F, G \in \FF$, and suppose that $\map f F = \map f G$.
By Expression for Integer as Product of Primes is Unique:
:$\map g F = \map g G$
By Subset equals Preimage of Image iff Mapping is Injection:
:$F = \map {g^{-1} } {\map g F} = \map {g^{-1} } {\map g G} = G$
That is, $f$ is an injection.
{{qed}}
Theorem: Set of Finite Subsets of Countable Set is Countable

Let $A$ be a countable set.
Then the set of finite subsets of $A$ is countable.

Proof:
By definition of a countable set, there is an injection $f: A \to \N$.
Let $\le_f$ be the ordering induced by $f$ on $A$.
By Injection Induces Well-Ordering, $\le_f$ is a well-ordering.
Let $A^{\text {fin} }$ be the set of finite subsets of $A$.
For $n \in \N$, denote with $A^{\paren n}$ the set of subsets of $A$ that have precisely $n$ elements.
For $A' \in A^{\paren n}$, we write $A' = \set {a'_1, a'_2, \ldots, a'_n}$ uniquely so that $i < j$ implies $a'_i <_f a'_j$.
Then we define $f^{\paren n}: A^{\paren n} \to \N$ by:
:$\ds \map {f^{\paren n} } {A'} := \prod_{i \mathop = 1}^n p_i^{\map f {a'_i} }$
where $p_i$ denotes the $i$th prime.
By the Fundamental Theorem of Arithmetic, if $\map {f^{\paren n} } {A'} = \map {f^{\paren n} } {A' '}$, then:
:$\tuple {\map f {a'_1}, \dotsc, \map f {a'_n} } = \tuple {\map f {a' '_1}, \dotsc, \map f {a' '_n} }$
As $f$ is injective, also:
:$\tuple {a'_1, \dotsc, a'_n} = \tuple {a' '_1, \dotsc, a' '_n}$
and in particular $A' = A''$.
Thus $f^{\paren n}: A^{\paren n} \to \N$ is an injection.
So $A^{\paren n}$ is countable.
Now define $\map {f^{\text{fin} } }: A^{\text {fin} } \to \N \times \N$ by:
:$\map {f^{\text{fin} } } {A'} := \tuple {n, \map {f^{\paren n} } {A'} }$
where $n = \card {A'}$ is the cardinality of $A'$.
Suppose that:
:$\map {f^{\text{fin} } } {A'} = \map {f^{\text{fin} } } {A' '}$
Then by Equality of Ordered Pairs:
:$n = \card {A'} = \card {A' '}$
and:
:$\map {f^{\paren n} } {A'} = \map {f^{\paren n} } {A' '}$
Since $f^{\paren n}$ was already shown to be an injection, it follows that:
:$A' = A' '$
Thus $f^{\text {fin} }$ is also an injection.
By Cartesian Product of Natural Numbers with Itself is Countable, $\N \times \N$ is countable.
The result follows from Domain of Injection to Countable Set is Countable.
{{qed}}
Theorem: Set of Finite Subsets of Countable Set is Countable

Let $A$ be a countable set.
Then the set of finite subsets of $A$ is countable.

Proof:
Let $A^{\paren n}$ be the set of subsets of $A$ with no more than $n$ elements.
Thus:
:$A^{\paren 0} = \set \O$
:$A^{\paren 1} = A^{\paren 0} \cup \set {\set a: a \in A}$
and $\forall n \ge 0$:
:$A^{\paren {n + 1} } = \set {a^{\paren n} \cup a^{\paren 1}: a^{\paren n} \in A^{\paren n} \land a^{\paren 1} \in A^{\paren 1} }$
Let us verify by induction that each $A^{\paren n}$ is countable.
Let $A$ be countable.
:$A^{\paren 1}$ is countable, as its cardinality is $1 + \card A$.
Suppose $A^{\paren n}$ is countable.
Then by Union of Countable Sets of Sets, so $A^{\paren {n + 1} }$ also countable.
By induction, each $A^{\paren n}$ is countable.
Denote with $A^f$ the set of finite subsets of $A$.
It is apparent that every finite subset is in some $A^{\paren n}$, and so:
:$A^f = \ds \bigcup_{n \mathop \in \N} A^{\paren n}$
The result follows from Countable Union of Countable Sets is Countable.
{{qed}}
Theorem: Cantor's Theorem (Strong Version)

Let $S$ be a set.
Let $\map {\PP^n} S$ be defined recursively by:
:<nowiki>$\map {\PP^n} S = \begin{cases}
S & : n = 0 \\
\powerset {\map {\PP^{n - 1} } S} & : n > 0
\end{cases}$</nowiki>
where $\powerset S$ denotes the power set of $S$.
Then $S$ is not equivalent to $\map {\PP^n} S$ for any $n > 0$.

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 (Strong Version)

Let $S$ be a set.
Let $\map {\PP^n} S$ be defined recursively by:
:<nowiki>$\map {\PP^n} S = \begin{cases}
S & : n = 0 \\
\powerset {\map {\PP^{n - 1} } S} & : n > 0
\end{cases}$</nowiki>
where $\powerset S$ denotes the power set of $S$.
Then $S$ is not equivalent to $\map {\PP^n} S$ for any $n > 0$.

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 (Strong Version)

Let $S$ be a set.
Let $\map {\PP^n} S$ be defined recursively by:
:<nowiki>$\map {\PP^n} S = \begin{cases}
S & : n = 0 \\
\powerset {\map {\PP^{n - 1} } S} & : n > 0
\end{cases}$</nowiki>
where $\powerset S$ denotes the power set of $S$.
Then $S$ is not equivalent to $\map {\PP^n} S$ for any $n > 0$.

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: Ordering Induced by Injection is Ordering

Let $\left({T, \le}\right)$ be an ordered set, and let $S$ be a set.
Let $f: S \to T$ be an injection.
Then $\le_f$, the ordering induced by $f$, is an ordering.

Proof:
To establish that $\le_f$ is an ordering on $S$, we need to show that it is reflexive, antisymmetric and transitive.
So, checking in turn each of the criteria for an ordering:
Theorem: Injection Induces Total Ordering

Let $\left({T, \le}\right)$ be a totally ordered set, and let $S$ be a set.
Let $f: S \to T$ be an injection.
Then $\le_f$, the ordering induced by $f$, is a total ordering.

Proof:
By Ordering Induced by Injection is Ordering, $\le_f$ is an ordering.
Let $s_1, s_2 \in S$.
Then as $\le$ is a total ordering, at least one of the following holds:
:$(1): \qquad f \left({s_1}\right) \le f \left({s_2}\right)$
:$(2): \qquad f \left({s_2}\right) \le f \left({s_1}\right)$
If $(1)$ holds, the definition of $\le_f$ implies that $s_1 \le s_2$.
Similarly, if $(2)$ holds, $s_2 \le s_1$.
This leads to the conclusion that at least one of $s_1 \le s_2$ and $s_2 \le s_1$ holds.
Hence $\le_f$ is a total ordering.
{{qed}}
Category:Total Orderings
Category:Injections
2yzdr7kcr2eanxa3w2vp8budup2vozf