nyuuzyou/wikis huggingface dataset:
Young's Inequality for Products/Proof by Convexity

== Theorem ==
== Proof ==
The result follows directly if $a = 0$ or $b = 0$.
, 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 :
:$\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$
Therefore:
By $(1)$ and $(2)$, the equality:
:$a b = \dfrac {a^p} p + \dfrac {b^q} q$
occurs :
:$\map \ln {a^p} = \map \ln {b^q}$
That is, :
:$b = a^{p - 1}$
Category:Young's Inequality for Products
Yule-Simpson Effect

== Theorem ==
The Yule-Simpson Effect is a veridical paradox in the theory of contingency tables.
An association that is significant in each of two contingency tables may disappear or be reversed if the two tables are combined.
== Examples ==
== Historical Note ==
== Sources ==
* 
* 
* 
Category:Yule-Simpson Effect
Category:Contingency Tables
Category:Veridical Paradoxes
Yule-Simpson Effect/Examples/Arbitrary Example 1

== Example of Yule-Simpson Effect ==
Suppose that a new treatment $\text N$ is being compared with a standard treatment $\text S$, in an experiment with $3000$ patients.
Let a record be kept of the number of cures $\text C$ and failures $\text F$.
The numbers in each category are shown here:
:$\begin{array}{r|cc|c}
& \text S & \text N & \text {Totals} \\
\hline
\text C & 450 & 530 & 980 \\
\text F & 850 & 1170 & 2020 \\
\hline
\text {Totals} & 1300 & 1700 & 3000
\end{array}$
A $\chi$-squared test indicates a differential effect of treatments with the standard giving a greater proportion of cures.
However, when the results are broken down into patients living in urban and rural areas, the data are as given in the following tables:
:$\begin{array}{r|cc|c}
\text {Urban:} & \text S & \text N & \text {Totals} \\
\hline
\text C & 100 & 350 & 450 \\
\text F & 500 & 1050 & 1550 \\
\hline
\text {Totals} & 600 & 1400 & 2000
\end{array} \qquad \begin{array}{r|cc|c}
\text {Rural:} & \text S & \text N & \text {Totals} \\
\hline
\text C & 350 & 180 & 530 \\
\text F & 350 & 120 & 470 \\
\hline
\text {Totals} & 700 & 300 & 1000
\end{array}$
Now it is seen that in both urban and rural areas, the new drug gives a better cure rate.
== Sources ==
* 
* 
Category:Examples of Yule-Simpson Effect
Z-Module Associated with Abelian Group is Unitary Z-Module

== Theorem ==
Let $\struct {G, *}$ be an abelian group with identity $e$.
Let $\struct {G, *, \circ}_\Z$ be the $Z$-module associated with $G$.
Then $\struct {G, *, \circ}_\Z$ is a unitary $Z$-module.
== Proof ==
The notation $*^n x$ can be written as $x^n$.
Let us verify that $\struct {G, *, \circ}_\Z$ is a unitary $\Z$-module by verifying the axioms in turn.
=== ===
We need to show that:
:$n \circ \paren {x * y} = \paren {n \circ x} * \paren {n \circ y}$
From the definition:
:$n \circ x = x^n$
and so:
:$n \circ \paren {x * y} = \paren {x * y}^n$
From Power of Product in Abelian Group:
:$\paren {x * y}^n = x^n * y^n = \paren {n \circ x} * \paren {n \circ y}$
=== ===
We need to show that:
:$\paren {n + m} \circ x = \paren {n \circ x} * \paren {m \circ x}$
That is:
:$x^{n + m} = x^n * x^m$
This is an instance of Powers of Group Elements: Sum of Indices.
=== ===
We need to show that:
:$\paren {n \times m} \circ x = n \circ \paren {m \circ x}$
That is:
:$x^{n m} = \paren {x^m}^n$
This follows directly from Powers of Group Elements: Product of Indices.
=== ===
We need to show that:
:$\forall x \in G: 1 \circ x = x$
That is:
:$x^1 = x$
This follows from the definition of Power of Group Element.
Having verified all four axioms, we have shown that $\struct {G, *, \circ}_\Z$ is a unitary $\Z$-module.
== Sources ==
* : Chapter $\text {V}$: Vector Spaces: $\S 26$. Vector Spaces and Modules: Example $26.7$
Category:Examples of Unitary Modules
Category:Z-Module Associated with Abelian Group
Z/(m)-Module Associated with Ring of Characteristic m

== Theorem ==
Let $\struct {R, +, *}$ be a ring with unity whose zero is $0_R$ and whose unity is $1_R$.
Let the characteristic of $R$ be $m$.
Let $\struct {\Z_m, +_m, \times_m}$ be the ring of integers modulo $m$.
Let $\circ$ be the mapping from $\Z_m \times R$ to $R$ defined as:
:$\forall \eqclass a m \in \Z_m: \forall x \in R: \eqclass a m \circ x = a \cdot x$
where $\eqclass a m$ is the residue class of $a$ modulo $m$ and $a \cdot x$ is the $a$th power of $x$.
Then $\struct {R, +, \circ}_{\Z_m}$ is a unitary $\Z_m$-module.
== Proof ==
Let us verify that the definition of $\circ$ is well-defined.
Let $\eqclass a m = \eqclass b m$.
Then we need to show that:
:$\forall x \in R: \eqclass a m \circ x = \eqclass b m \circ x$
By the definition of congruence:
:$\eqclass a m = \eqclass b m \iff \exists k \in \Z : a = b + k m$
Then:
Thus, the definition of $\circ$ is well-defined.
Let us verify that $\struct {R, +, \circ}_{\Z_m}$ is a unitary $\Z_m$-module by verifying the axioms in turn.
=== ===
We need to show that:
:$\eqclass a m \circ \paren {x + y} = \eqclass a m \circ x + \eqclass a m \circ y$
=== ===
We need to show that:
:$\paren {\eqclass a m +_m \eqclass b m} \circ x = \eqclass a m \circ x + \eqclass b m \circ x$
=== ===
We need to show that:
:$\paren {\eqclass a m \times_m \eqclass b m} \circ x = \eqclass a m \circ \paren {\eqclass b m \circ x}$
=== ===
We need to show that:
:$\eqclass 1 m \circ x = x$
since $\eqclass 1 m$ is the unity of $\Z_m$.
That is, that $1 \cdot x = x$.
This follows from the definition of power of group element.
Having verified all four axioms, we have shown that $\struct {R, +, \circ}_{\Z_m}$ is a unitary $\Z_m$-module.
Category:Unitary Modules
Category:Group Theory
Zariski's Lemma

== Theorem ==
Let $L / k$ be a field extension.
Let $L$ be finitely generated as an algebra over $k$.
Then $L / k$ is a finite field extension.
== Proof ==
By Noether Normalization Lemma, we find a finite and injective morphism:
:$\alpha: k \sqbrk {x_1, \dotsc, x_n} \to L$
If we can prove that $n = 0$, the proof is complete.
 $n > 0$.
Then:
:$x_1 \in k \sqbrk {x_1, \dotsc, x_n}$
and:
:$\map \alpha {x_1} \ne 0$
We have that $\map \alpha {x_1}^{-1}$ is integral over $k \sqbrk {x_1, \dotsc, x_n}$.
Thus there exists a $m \in \N$ and $a_0, \dotsc, a_{m - 1} \in k \sqbrk {x_1, \dotsc, x_n}$ such that:
:$\ds \map \alpha {x_1}^{-m} + \sum_{i \mathop = 0}^{m - 1} \map \alpha {a_i} \map \alpha {x_1}^{-i} = 0$
Multiplying by $\map \alpha {x_1}^m$:
and thus, since $\alpha$ is injective, we find that:
:$\ds 1 = x_1 \paren {-\sum_{i \mathop = 0}^{m - 1} a_i x_1^{m - i - 1} }$
which means that $x_1$ is invertible. 
This contradiction shows that $n = 0$.
Category:Commutative Algebra
Category:Field Extensions
Zariski Topology is Topology

== Theorem ==
Let $k$ be a field.
Let $n \in \N_{>0}$.
Let $\tau$ be the Zariski topology on $k^n$.
Then $\tau$ is indeed a topology on $k^n$.
== Proof ==
Let $A := k \sqbrk {X_1, \ldots, X_n}$ be the ring of polynomials.
Recall that by definition of Zariski topology:
:$\forall U \in \tau: \exists T_U \subseteq A: U = X \setminus \map V {T_U}$
where $\map V {T_U}$ denotes the zero locus of $T_U$.
Each of the open set axioms is examined in turn:
=== ===
For each $\UU \subseteq \tau$:
=== ===
For all $U,V \in \tau$:
=== ===
Since $\map V 1 = \O$:
:$k^n = k^n \setminus \map V 1 \in \tau$
All the open set axioms are fulfilled, and the result follows.
Category:Affine Geometry
Category:Zariski Topology
Zassenhaus Lemma

== Lemma ==
Let $G$ be a group.
Let $H_1$ and $H_2$ be subgroups of $G$.
Let:
:$N_1 \lhd H_1$
:$N_2 \lhd H_2$
where $\lhd$ denotes the relation of being a normal subgroup.
Then:
:$\dfrac {N_1 \paren {H_1 \cap H_2} } {N_1 \paren {H_1 \cap N_2} } \cong \dfrac {H_1 \cap H_2} {\paren {H_1 \cap N_2} \paren {N_1 \cap H_2} } \cong \dfrac {N_2 \paren {H_1 \cap H_2} } {N_2 \paren {N_1 \cap H_2} }$
where:
:$N_1 \paren {H_1 \cap H_2}$, and so on, denotes subset product
:$\cong$ denotes group isomorphism.
== Proof ==
Because of symmetry, only the first of the isomorphisms needs to be proved.
=== Proof of Normality ===
In order for the expressions to make sense, the expressions on the bottom of the fractions need to be normal subgroups.
That is, we need to show that:
:$(1): \quad N_1 \paren {H_1 \cap N_2} \lhd N_1 \paren {H_1 \cap H_2}$
:$(2): \quad \paren {H_1 \cap N_2} \paren {N_1 \cap H_2} \lhd H_1 \cap H_2$
=== Proof of Isomorphism ===
Let:
:$H = H_1 \cap H_2$
:$N = N_1 \paren {H_1 \cap N_2}$
Then:
From Intersection with Subgroup Product of Superset:
:If $X, Y, Z$ are subgroups of a group $\struct {G, \circ}$, and $Y \subseteq X$, then:
::$X \cap \paren {Y \circ Z} = Y \circ \paren {X \cap Z}$
Thus:
Hence the result.
== Also known as ==
This lemma is also known as:
:the butterfly lemma, so named because the Hasse diagram of the various subgroups involved can be drawn to resemble a butterfly
:either the third isomorphism theorem or the fourth isomorphism theorem, which names are not recommended because of the lack of any consistent naming convention for the Isomorphism Theorems in the literature.
== Sources ==
* : Chapter $2$: Group Homomorphism and Isomorphism: $\S 70$. The Third Isomorphism Theorem
Category:Group Isomorphisms
Category:Normal Subgroups
Zeckendorf's Theorem

== Theorem ==
Every positive integer has a unique Zeckendorf representation.
That is:
Let $n$ be a positive integer.
Then there exists a unique increasing sequence of integers $\left\langle{c_i}\right\rangle$ such that:
:$\forall i \in \N: c_i \ge 2$
:$c_{i + 1} > c_i + 1$
:$\ds n = \sum_{i \mathop = 0}^k F_{c_i}$
where $F_m$ is the $m$th Fibonacci number.
For any given $n$, such a $\left\langle{c_i}\right\rangle$ is unique.
== Proof ==
First note that every Fibonacci number $F_n$ is itself a Zeckendorf representation of itself, where the sequence $\left\langle{c_i}\right\rangle$ contains $1$ term.
=== Existence ===
We will use strong induction on $n$.
We have that:
:$F_2 = 1$
:$F_3 = 2$
:$F_4 = 3$
so each of the integers $1$, $2$, and $3$ have a Zeckendorf representation.
==== Basis of the Induction ====
$4$ has the Zeckendorf representation:
:$4 = 1 + 3 = F_2 + F_4$
This is the basis for the induction.
==== Induction Hypothesis ====
Let the induction hypothesis be that each $n \le k$ has a Zeckendorf representation.
The induction step remains to be proved: that $k + 1$ has a Zeckendorf representation.
==== Induction Step ====
If $k + 1$ is a Fibonacci number, then it is itself a Zeckendorf representation.
In that case, the induction step holds.
Suppose that $k + 1$ is not a Fibonacci number.
Then:
:$\exists j \in \Z: F_j < k + 1 < F_{j + 1}$
Consider $a = k + 1 - F_j$.
Since $a \le k$, it must have a Zeckendorf representation by the induction hypothesis.
In addition:
Thus the Zeckendorf representation of $a$ does not contain $F_{j - 1}$.
Thus $k + 1$ has the Zeckendorf representation of $a + F_j$.
It follows by strong induction that for every positive integer there exists a Zeckendorf representation.
=== Uniqueness ===
Let $n \in \Z_{>0}$.
 $S$ and $T$ are distinct Zeckendorf representation for $n$.
Consider $S' = S \setminus T$ and $T' = T \setminus S$, that is, each of the sets without their common elements.
Since $S$ and $T$ had equal sums:
:$(1): \quad \ds \sum S' = \sum T'$
, assume that $S'$ is empty.
Then in order for $T'$ to have the same sum using only positive integers, $T'$ must also be empty.
But as $S \ne T$, it follows that neither $S'$ nor $T'$ is empty.
Let the largest element of $S'$ be $F_S$.
Let the largest element of $T'$ be $F_T$.
Since $S'$ and $T'$ contain no common elements, $F_S \ne F_T$.
, let $F_S < F_T$.
From Sum of Non-Consecutive Fibonacci Numbers:
:$\ds \sum S' < F_{S + 1}$
and so:
:$\ds \sum S' < F_T$
But from $(1)$:
:$\ds \sum S' = \sum T'$
From this contradiction, it cannot be the case that $S'$ and $T'$ are non-empty.
So $S' = T' = \O$ and so $S = T$.
Thus the Zeckendorf representation is unique as desired.
== Historical Note ==
== Sources ==
* 
* 
* : $\S 1.2.8$: Fibonacci Numbers: Exercise $34$
* 
Category:Zeckendorf Representation
Zeckendorf's Theorem/Historical Note

== Historical Note on Zeckendorf's Theorem ==
Zeckendorf's Theorem appears to have been discovered in medieval India.
 rediscovered it in $1939$, but did not actually publish it until $1972$.
 had in fact published it in $1952$, and named it after at that time.
By the time published his summary of this result in $1972$ several others had been referring to it as Zeckendorf's Theorem as a result of 's article.
It is in fact a special case of a theorem by which had been published in $1922$.
== Sources ==
* 
* 
* 
* 
Category:Historical Notes
Zeckendorf Representation of Integer shifted Left

== Theorem ==
Let $f: \R \to \R$ be the real function defined as:
:$\forall x \in \R: \map f x = \floor {x + \phi^{-1} }$
where:
:$\floor {\, \cdot \,}$ denotes the floor function
:$\phi$ denotes the golden mean.
Let $n \in \Z_{\ge 0}$ be a positive integer.
Let $n$ be expressed in Zeckendorf representation:
:$n = F_{k_1} + F_{k_2} + \cdots + F_{k_r}$
with the appropriate restrictions on $k_1, k_2, \ldots, k_r$.
Then:
:$F_{k_1 + 1} + F_{k_2 + 1} + \cdots + F_{k_r + 1} = \map f {\phi n}$
== Proof ==
We have:
Hence:
We have that:
:$\hat \phi^3 + \hat \phi^5 + \hat \phi^7 + \cdots \le \hat \phi^{k_1} + \hat \phi^{k_2} + \cdots + \hat \phi^{k_r} \le \hat \phi^2 + \hat \phi^4 + \hat \phi^6 + \cdots$
Then:
Then:
Thus:
:$\phi^{-1} - 1 \le \hat \phi^{k_1} + \hat \phi^{k_2} + \cdots + \hat \phi^{k_r} \le \phi^{-1}$
and the result follows.
== Historical Note ==
== Sources ==
* : $\S 1.2.8$: Fibonacci Numbers: Exercise $41$
Category:Zeckendorf Representation
Zeckendorf Representation of Integer shifted Right

== Theorem ==
Let $f: \R \to \R$ be the real function defined as:
:$\forall x \in \R: \map f x = \floor {x + \phi^{-1} }$
where:
:$\floor {\, \cdot \,}$ denotes the floor function
:$\phi$ denotes the golden mean.
Let $n \in \Z_{\ge 0}$ be a positive integer.
Let $n$ be expressed in Zeckendorf representation:
:$n = F_{k_1} + F_{k_2} + \cdots + F_{k_r}$
with the appropriate restrictions on $k_1, k_2, \ldots, k_r$.
Then:
:$F_{k_1 - 1} + F_{k_2 - 1} + \cdots + F_{k_r - 1} = \map f {\phi^{-1} n}$
== Proof ==
Follows directly from Zeckendorf Representation of Integer shifted Left, substituting $F_{k_j - 1}$ for $F_{k_j}$ throughout.
== Historical Note ==
== Sources ==
* : $\S 1.2.8$: Fibonacci Numbers: Exercise $41$
Category:Zeckendorf Representation
Zenith Distance is Complement of Celestial Altitude

== Theorem ==
Let $X$ be the position of a star (or other celestial body) on the celestial sphere.
The zenith distance $z$ of $X$ is the complement of the altitude $a$ of $X$:
:$z = 90 \degrees - a$
== Proof ==
The vertical circle through $X$ is defined as the great circle that passes through $Z$.
By definition, the angle of the arc from $Z$ to the horizon is a right angle.
Hence $z + a = 90 \degrees$.
The result follows.
== Sources ==
* : Chapter $\text {II}$. The Celestial Sphere: $18$. Altitude and azimuth.
* 
* 
Category:Spherical Astronomy
Category:Complementary Angles
Zenith Distance of North Celestial Pole equals Colatitude of Observer

== Theorem ==
Let $O$ be an observer of the celestial sphere.
Let $P$ be the position of the north celestial pole with respect to $O$.
Let $z$ denote the zenith distance of $P$.
Let $\psi$ denote the (terrestrial) colatitude of $O$.
Then:
:$z = \psi$
== Proof ==
Let $Z$ denote the zenith.
The zenith distance $z$ of $P$ is by definition the length of the arc $PZ$ of the prime vertical.
This in turn is defined as the angle $\angle POZ$ subtended by $PZ$ at $O$.
This is equivalent to the angle between the radius of Earth through $O$ and Earth's axis.
This is by definition the (terrestrial) colatitude of $O$.
Hence the result.
== Sources ==
* : Chapter $\text {II}$. The Celestial Sphere: $18$. Altitude and azimuth.
Category:Spherical Astronomy
Zeno's Paradoxes

== Paradoxes ==
Zeno's paradoxes are a set of antinomies devised by to demonstrate that the mathematical understanding of motion and space had conceptual gaps.
These paradoxes were preserved in the writings of . originals have not survived to the present day.
=== Achilles Paradox ===
=== The Dichotomy Paradox ===
=== The Arrow Paradox ===
=== The Stadium Paradox ===
== Historical Note ==
== Sources ==
* : Chapter $\text{II}$: Modern Minds in Ancient Bodies
* 
* 
* 
* 
* 
Category:Paradoxes
Zeno's Paradoxes/Historical Note

== Historical Note on Zeno's Paradoxes ==
 presented these paradoxes to the school at Athens when he visited with his patron Parmenides.
These paradoxes have been said to have shocked the philosophers there out of their complacency, and raised questions that none of them could satisfactorily answer.
== Sources ==
* : Chapter $\text{II}$: Modern Minds in Ancient Bodies
Category:Historical Notes
Zermelo's Theorem (Set Theory)

== Theorem ==
Every set of cardinals is well-ordered with respect to $\le$.
== Proof ==
Let $S_1$ and $S_2$ be sets which are not empty.
Suppose there exists an injection $f: S_1 \to S_2$ and another injection $g: S_2 \to S_1$.
Then by the Cantor-Bernstein-Schröder Theorem there exists a bijection between $S_1$ and $S_2$ and by definition $S_1$ is equivalent to $S_2$.
Let $\AA$ be the set of invertible mappings $\phi: A \to B$ where $A \subseteq S_1$ and $B \subseteq S_2$.
Since $S_1$ and $S_2$ are not empty, $\exists s_1 \in S_1$ and $\exists s_2 \in S_2$.
Thus we can construct the mapping $\alpha: \set {s_1} \to \set {s_2}$ such that $\map \alpha {s_1} = s_2$.
This is trivially an invertible mapping, so $\AA$ is not empty.
We can impose an ordering $\le$ on $\AA$ by letting $\phi_1 \le \phi_2 \iff \phi_1 \subseteq \phi_2$, that is, if $\phi_2$ is an extension of $\phi_1$.
Let $\CC$ be a chain in $\struct {\AA, \le}$.
Then $\ds \bigcup \set {\phi \in \CC}$ is an upper bound of every $\phi \in \CC$, and it lies in $\AA$.
The conditions of Zorn's Lemma are satisfied, so we can find a maximal element $M$ in $\AA$.
Let:
:$M_1 = \set {s_1: \tuple {s_1, s_2} \in M}$
:$M_2 = \set {s_2: \tuple {s_1, s_2} \in M}$
We have that $M_1 \subsetneq S_1$ and $M_2 \subsetneq S_2$ both together contradict the fact that $M$ is maximal element.
Thus either $M_1 = S_1$ or $M_2 = S_2$, and possibly both.
Thus either:
:$M$ is an injection of $S_1$ into $S_2$
or:
:$M^{-1}$ is an injection of $S_2$ into $S_1$.
Thus either $S_1 \le S_2$ or $S_2 \le S_1$, and the result follows.
== Also known as ==
This is called by some authors the Trichotomy Problem.
== Also see ==
* Zermelo's Well-Ordering Theorem
== Sources ==
* : Introduction to Set Theory: $3$. The Axiom of Choice and Its Equivalents
* : $\S 8$: Theorem $8.3$
* 
Category:Set Theory
Zermelo's Well-Ordering Theorem

== Theorem ==
Let the Axiom of Choice be accepted.
Then every set is well-orderable.
== Proof 1 ==
== Proof 2 ==
== Proof 3 ==
== Also known as ==
== Also see ==
* Zermelo's Well-Ordering Theorem/Converse
* Zermelo's Well-Ordering Theorem is Equivalent to Axiom of Choice
== Sources ==
* : Introduction to Set Theory: $3$. The Axiom of Choice and Its Equivalents
* 
* 
* 
* 
* : Chapter $4$: Superinduction, Well Ordering and Choice: Part $\text I$ -- Superinduction and Well Ordering: $\S 1$ Introduction to well ordering
Category:Zermelo's Well-Ordering Theorem
Category:Well-Orderings
Category:Equivalents of Axiom of Choice
Zermelo's Well-Ordering Theorem/Also known as

== Zermelo's Well-Ordering Theorem: Also known as ==
Zermelo's well-ordering theorem is also known just as the well-ordering theorem.
Some sources omit the hyphen: (Zermelo's) well ordering theorem.
It is also known just as Zermelo's theorem.
Under this name it can often be seen worded:
:Every set of cardinals is well-ordered with respect to $\le$.
This is called by some authors the trichotomy problem.
It is also referred to as the well-ordering principle, but this causes confusion with the result that states that the natural numbers are well-ordered.
Category:Zermelo's Well-Ordering Theorem
Zermelo's Well-Ordering Theorem/Converse/Proof 1

== Theorem ==
== Proof ==
Let $S$ be an arbitrary set.
By assumption $S$ is well-orderable.
From Well-Orderable Set has Choice Function, $S$ has a choice function.
As $S$ is arbitrary, the result follows.
== Also known as ==
== Sources ==
* : Chapter $4$: Superinduction, Well Ordering and Choice: Part $\text I$ -- Superinduction and Well Ordering: $\S 4$ Well ordering and choice: Theorem $4.9$
Category:Zermelo's Well-Ordering Theorem
Zermelo's Well-Ordering Theorem/Converse/Proof 2

== Theorem ==
== Proof ==
Let $\FF$ be an arbitrary collection of sets.
By assumption all sets can be well-ordered.
Hence the set $\bigcup \FF$ of all elements of sets contained in $\FF$ is well-ordered by some ordering $\preceq$.
By definition then, every subset of $\ds \bigcup \FF$ has a smallest element under $\preceq$.
Also, note that each set in $\FF$ is a subset of $\bigcup \FF$.
Thus, we may define the choice function $C$:
:$C: \FF \to \bigcup \FF, \map C X = \min X$
where $\min X$ is the smallest element of $X$ under $\preceq$.
== Also known as ==
Category:Zermelo's Well-Ordering Theorem
Zermelo's Well-Ordering Theorem/Proof 1

== Theorem ==
== Proof ==
Let $S$ be a set.
Let $\powerset S$ be the power set of $S$.
By the , there exists a choice function on $S$.
The result follows from Set with Choice Function is Well-Orderable.
== Also known as ==
== Sources ==
* : Chapter $4$: Superinduction, Well Ordering and Choice: Part $\text I$ -- Superinduction and Well Ordering: $\S 4$ Well ordering and choice: Theorem $4.8$
Category:Zermelo's Well-Ordering Theorem
Zermelo's Well-Ordering Theorem/Proof 2

== Theorem ==
== Proof ==
Let $S$ be a set.
Let $\powerset S$ be the power set of $S$.
By the Axiom of Choice, there is a choice function $c$ defined on $\powerset S \setminus \set \O$.
We will use $c$ and the Principle of Transfinite Induction to define a bijection between $S$ and some ordinal.
Intuitively, we start by pairing $\map c S$ with $0$, and then keep extending the bijection by pairing $\map c {S \setminus X}$ with $\alpha$, where $X$ is the set of elements already dealt with.
=== Basis for the Induction ===
$\alpha = 0$
Let $s_0 = \map c S$.
=== Inductive Step ===
Suppose $s_\beta$ has been defined for all $\beta < \alpha$.
If $S \setminus \set {s_\beta: \beta < \alpha}$ is empty, we stop.
Otherwise, define:
:$s_\alpha := \map c {S \setminus \set {s_\beta: \beta < \alpha} }$
The process eventually stops, else we have defined bijections between subsets of $S$ and arbitrarily large ordinals.
Now, we can impose a well-ordering on $S$ by embedding it via $s_\alpha \to \alpha$ into the ordinal $\beta = \ds {\bigcup_{s_\alpha \mathop \in S} \alpha}$ and using the well-ordering of $\beta$.
== Also known as ==
Category:Zermelo's Well-Ordering Theorem
Zermelo's Well-Ordering Theorem/Proof 3

== Theorem ==
== Proof ==
Let $S$ be a non-empty set.
Let $C$ be a choice function for $S$.
Let $A$ be an arbitrary set.
Let the mapping $h$ be defined as:
:$\map h A = \begin {cases} \map C {S \setminus A} & : A \subsetneqq S \\ x & : \text {otherwise} \end {cases}$
where $x$ is an arbitrary element such that $x \notin S$.
The latter is known to exist from Exists Element Not in Set.
From the Transfinite Recursion Theorem: Formulation $5$, there exists a mapping $F$ on the class of all ordinals $\On$ such that:
:$\forall \alpha \in \On: \map F \alpha = \map h {F \sqbrk \alpha}$
It remains to show the following:
:$(1): \quad \exists \delta \in \On: \map F \delta \notin S$
:$(2): \quad$ Let $\beta$ be the smallest ordinal such that $\map F \beta \notin S$. Then:
::::$F \sqbrk \beta = S$
:::and:
::::$F \restriction \beta$ is injective
:::and so $\beta$ can be put into a one-to-one correspondence with $S$.
Hence $S$ can be well-ordered.
== Also known as ==
== Sources ==
* : Chapter $6$: Order Isomorphism and Transfinite Recursion: $\S 5$ Transfinite recursion theorems: Exercise $5.3$
Category:Zermelo's Well-Ordering Theorem