nyuuzyou/wikis huggingface dataset:
Complete Graph is Hamiltonian for Order Greater than 2

== Theorem ==
Let $n \in \Z$ be an integer such that $n > 2$.
Let $K_n$ denote the complete graph of order $n$.
Then $K_n$ is Hamiltonian.
== Proof ==
First we note that when $n = 2$ there is one edge in $K_n$.
So if you start at one vertex $u$ and travel along that edge to the other vertex $v$, you cannot return to $u$ except by using that same edge.
Consequently $K_2$ is not Hamiltonian.
Let $n = 4$.
Let us take two vertices $u, v$ of $K_n$:
From Complete Graph is Regular, the degrees of $u$ and $v$ are given by:
:$\map \deg u = \map \deg v = n - 1$
Let us remove the edge $u v$ which joins them.
Let the resulting graph be denoted $G$.
We now have that:
:$\map \deg u = \map \deg v = n - 2$
From Ore's Theorem, $G$ is Hamiltonian if for each pair of non-adjacent vertices $u, v \in V$:
:$\deg u + \deg v \ge n$
In $G$, we have that:
Hence:
Thus $G$ is Hamiltonian.
A Hamiltonian graph with another edge added is still Hamiltonian.
Thus restoring the edge $u v$ to $G$ to turn it back into $K_n$ means that $K_n$ is Hamiltonian.
When $n = 3$ we cannot use this theorem, as you then find for the resulting $G$:
:$\deg u + \deg v = 2$
which is less than $3$.
Instead we inspect the complete graph $K_3$ and see it is is the cycle graph $C_3$
:
The result follows from Cycle Graph is Hamiltonian.
Category:Complete Graphs
Category:Hamiltonian Graphs
Complete Graph is Regular

== Theorem ==
Let $K_p$ be the complete graph of order $p$.
Then $K_p$ is $p-1$-regular.
== Proof ==
By definition of complete graph, $K_p$ has $p$ vertices.
Also by definition of complete graph, each vertex of $K_p$ is adjacent to all the other $p - 1$ vertices of $K_p$.
As $K_p$ is a simple graph, there can be only one edge joining any pair of vertices of $K_p$.
So each vertex of $K_p$ has $p - 1$ edges to which it is incident.
So, by definition, $K_p$ is $p-1$-regular.
== Examples ==
== Sources ==
* : Chapter $2$: Elementary Concepts of Graph Theory: $\S 2.1$: The Degree of a Vertex
Category:Complete Graph is Regular
Category:Complete Graphs
Category:Regular Graphs
Complete Graph of Order 1 is Edgeless

== Theorem ==
The complete graph $K_1$ of order $1$ is the edgeless graph $N_1$.
== Proof ==
By definition, $K_1$ has $1$ vertex.
From Complete Graph is Regular, $K_1$ is $0$-regular.
Hence the result from Graph is 0-Regular iff Edgeless.
Category:Edgeless Graphs
Category:Complete Graphs
Complete Hamiltonian Bipartite Graph

== Theorem ==
Let $K_{m, n}$ be a complete bipartite graph.
Then:
:$K_{m, n}$ is Hamiltonian $m = n > 1$.
== Proof ==
Clearly $K_{1, 1}$ is not Hamiltonian, although it does have a Hamiltonian path.
From Condition for Bipartite Graph to be Hamiltonian, if $m \ne n$ then $K_{m, n}$ is not Hamiltonian.
So let $m = n$.
We note that the degree of any vertex in $K_{n, n}$ is $n$.
Then we can use Ore's Theorem, and the result follows directly.
Category:Hamiltonian Graphs
Category:Complete Bipartite Graphs
Complete Join Semilattice is Dual to Complete Meet Semilattice

== Theorem ==
Let $\struct {S, \preceq}$ be an ordered set.
The following are dual statements:
:$\struct{S, \preceq}$ is a complete join semilattice
:$\struct{S, \preceq}$ is a complete meet semilattice
== Proof ==
By definition of complete join semilattice:
:$\struct{S, \preceq}$ is a complete join semilattice 
:
:$\forall S' \subseteq S : \sup S' \in S$, where $\sup S'$ is the supremum of $S'$
The dual of this statement is:
:$\forall S' \subseteq S : \inf S' \in S$, where $\inf S'$ is the infimum of $S'$ by Dual Pairs (Order Theory).
By definition of complete meet semilattice:
:$\struct{S, \preceq}$ is a complete meet semilattice 
== Also see ==
* Duality Principle (Order Theory)
Category:Complete Lattices
Category:Dual Pairs (Order Theory)
Complete Lattice has Both Greatest Element and Smallest Element

== Theorem ==
Let $\struct{S, \vee, \wedge, \preceq}$ be a complete lattice.
Then:
:$(\text{1}) \quad \struct{S, \preceq}$ has a smallest element, namely:
::$\quad \bot := \sup \O$
:$(\text{2}) \quad \struct{S, \preceq}$ has a greatest element, namely:
::$\quad \top := \inf \O$
== Proof ==
From Complete Lattice is Bounded:
:$\struct{S, \vee, \wedge, \preceq}$ is a bounded lattice
From Bounded Lattice has Both Greatest Element and Smallest Element:
:$(\text{1}) \quad \struct{S, \preceq}$ has a smallest element, namely:
::$\quad \bot := \sup \O$
:$(\text{2}) \quad \struct{S, \preceq}$ has a greatest element, namely:
::$\quad \top := \inf \O$
Category:Complete Lattices
Complete Lattice is Bounded

== Theorem ==
Let $L = \struct {S, \vee, \wedge, \preceq}$ be a complete lattice.
Then
:$L$ is bounded.
== Proof ==
By definition of complete lattice:
:$\O$ admits a supremum and an infimum.
By Infimum of Empty Set is Greatest Element:
:$\forall x \in S: x \preceq \inf \O$
Thus by definition:
:$L$ is bounded above.
By Supremum of Empty Set is Smallest Element:
:$\forall x \in S: \sup \O \preceq x$
Thus by definition:
:$L$ is bounded below.
Hence $L$ is bounded.
== Sources ==
* 
Category:Bounded Lattices
Category:Complete Lattices
Complete Linearly Ordered Space is Compact

== Theorem ==
Let $\struct {X, \preceq, \tau}$ be a linearly ordered space.
Let $\struct {X, \preceq}$ be a complete lattice.
Then $\struct {X, \tau}$ is compact.
== Proof ==
By Space is Compact iff exists Basis such that Every Cover has Finite Subcover, it is sufficient to prove that an open cover of $X$ consisting of open intervals and rays has a finite subcover.
Let $\AA$ be an open cover of $X$ consisting of open rays and open intervals.
Let $m = \inf X$.
This infimum exists because $\struct {X, \preceq}$ is complete.
Let $C$ be the set of all $x \in X$ such that a finite subset of $\AA$ covers $\closedint m x$.
$C$ is non-empty because $m \in C$.
Let $s = \sup C$.
Since $\AA$ covers $X$, there is a $U \in \AA$ such that $s \in U$.
Then we must have $U = \openint a b$, $U = {\dot\uparrow} a$, or $U = {\dot\downarrow} b$.
Suppose that $U = \openint a b$.
Let $V \in \UU$ contain $b$.
Then by the definition of supremum, there is an $x \succ a$ such that there is a finite $\FF \subseteq \AA$ that covers $\closedint m x$.
Then $\FF \cup \set {U, V}$ covers $\closedint m b$, contradicting the fact that $s$ is an upper bound of $C$.
Suppose next that $U = \dot\downarrow b$.
Then for some $V \in \AA$, $b \in V$.
Then $\closedint m b$ is covered by $\set {U, V}$, contradicting the fact that $s$ is the supremum of $C$.
Thus $U = \dot\uparrow a$.
By the definition of supremum, $a$ is not an upper bound of $C$.
So there is an $x \succ a$ such that there is a finite subset $\FF$ of $\AA$ that covers $\closedint m x$.
Thus $\FF \cup \set U$ is a finite subcover of $A$.
== Sources ==
* : $\S 1$: Problem $\text I$, $\S 5$: Problem $\text C$
Category:Order Topology
Complete List of Special Highly Composite Numbers

== Theorem ==
There are exactly $6$ special highly composite numbers:
:$1, 2, 6, 12, 60, 2520$
== Proof ==
We have the following:
:$1$ is a Special Highly Composite Number
:$2$ is a Special Highly Composite Number
:$6$ is a Special Highly Composite Number
:$12$ is a Special Highly Composite Number
:$60$ is a Special Highly Composite Number
:$2520$ is a Special Highly Composite Number
By inspection of the sequence of highly composite numbers:
:$1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, \ldots$
it can be seen that there are no more special highly composite numbers less than $2520$.
Let $n > 18$.
From Ratio between Consecutive Highly Composite Numbers Greater than 2520 is Less than 2, the $n$th highly composite number does not divide the $n+1$th.
Hence the $n$th highly composite number is not a special highly composite number.
The result follows.
== Sources ==
* 
Category:Special Highly Composite Numbers
Complete Residue System/Examples/Modulo 11/Even Integers

== Examples of Complete Residue Systems ==
The set of integers:
::$\set {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22}$
forms a complete residue system modulo $11$.
== Proof ==
We have:
Thus we see that:
:$\set {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22}$
is equivalent to:
:$\set {2, 4, 6, 8, 10, 1, 3, 5, 7, 9, 0}$
The result follows from Initial Segment of Natural Numbers forms Complete Residue System.
== Sources ==
* : $\text {4-2}$ Residue Systems: Exercise $1 \ \text {(c)}$
Category:Examples of Residue Systems
Complete Residue System/Examples/Modulo 11/Least Absolute Residues

== Examples of Complete Residue Systems ==
The set of integers:
::$\set {-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5}$
forms a complete residue system modulo $11$.
== Proof ==
We have:
Thus we see that:
:$\set {-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5}$
is equivalent to:
:$\set {6, 7, 8, 9, 10, 0, 1, 2, 3, 4, 5}$
The result follows from Initial Segment of Natural Numbers forms Complete Residue System.
== Sources ==
* : $\text {4-2}$ Residue Systems: Exercise $1 \ \text {(d)}$
Category:Examples of Residue Systems
Complete Residue System/Examples/Modulo 11/Odd Integers

== Examples of Complete Residue Systems ==
The set of integers:
::$\set {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21}$
forms a complete residue system modulo $11$.
== Proof ==
We have:
Thus we see that:
:$\set {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21}$
is equivalent to:
:$\set {1, 3, 5, 7, 9, 0, 2, 4, 6, 8, 10}$
The result follows from Initial Segment of Natural Numbers forms Complete Residue System.
== Sources ==
* : $\text {4-2}$ Residue Systems: Exercise $1 \ \text {(b)}$
Category:Examples of Residue Systems
Complete Residue System/Examples/Modulo 11/Powers of 2

== Examples of Complete Residue Systems ==
The set of integers:
::$\set {0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512}$
forms a complete residue system modulo $11$.
== Proof ==
We have:
Thus we see that:
:$\set {0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512}$
is equivalent to:
:$\set {0, 1, 2, 4, 8, 5, 10, 9, 7, 3, 6}$
The result follows from Initial Segment of Natural Numbers forms Complete Residue System.
== Sources ==
* : $\text {4-2}$ Residue Systems: Exercise $1 \ \text {(a)}$
Category:Examples of Residue Systems
Complete Residue System/Examples/Modulo 3

== Examples of Complete Residue Systems ==
The following sets of integers are complete residue systems modulo $3$:
:$\set {1, 2, 3}$
:$\set {0, 1, 2}$
:$\set {-1, 0, 1}$
:$\set {1, 5, 9}$
== Sources ==
* : $\text {4-2}$ Residue Systems: Example $\text {4-6}$
Category:Examples of Residue Systems
Complete Residue System Modulo m has m Elements

== Theorem ==
Let $m \in \Z_{\ne 0}$ be a non-zero integer.
Let $S := \set {r_1, r_2, \dotsb, r_s}$ be a complete residue system modulo $m$.
Then $s = m$.
== Proof ==
Let:
:$t_0 = 0, t_1 = 1, \dots, t_{m - 1} = m - 1$
Let $n \in \Z$.
Then from the Division Theorem there exist unique integers $q$ and $u$ such that:
:$n = m q + u$
such that $0 \le u < m$.
That is:
:$n \equiv u \pmod m$
and $u$ is one of $t_0, t_1, \ldots, t_{m - 1}$.
Also, since $\size {t_i - t_j} < m$, no two elements of $\set {t_0, t_1, \ldots, t_{m - 1} }$ are congruent.
Thus $\set {t_0, t_1, \ldots, t_{m - 1} }$ is a complete residue system modulo $m$.
So each $r_i$ is congruent to exactly one element of $\set {t_0, t_1, \ldots, t_{m - 1} }$.
So:
:$s \le m$
And since $\set {r_1, r_2, \dotsb, r_s}$ forms a complete residue system modulo $m$, every element of $\set {t_0, t_1, \ldots, t_{m - 1} }$ is congruent to exactly one element of $S$.
So:
:$m \le s$
Hence the result.
== Sources ==
* : Chapter $\text {I}$: Elementary Definitions: $\S 1$. Rings and Fields: Example $4$
* : $\text {4-2}$ Residue Systems: Theorem $\text {4-4}$
Category:Residue Classes
Complete and Totally Bounded Metric Space is Sequentially Compact

== Theorem == 
Let $M = \struct {A, d}$ be a metric space.
Let $M$ be complete and totally bounded.
Then $M$ is sequentially compact.
== Proof 1 ==
== Proof 2 ==
== Proof 3 ==
== Proof 4 ==
== Sources ==
* : Part $\text I$: Basic Definitions: Section $5$: Metric Spaces: Complete Metric Spaces
Category:Complete Metric Spaces
Category:Sequentially Compact Spaces
Category:Totally Bounded Metric Spaces
Category:Complete and Totally Bounded Metric Space is Sequentially Compact
Complete and Totally Bounded Metric Space is Sequentially Compact/Lemma

== Lemma ==
Let $\struct {A , d}$ be a totally bounded metric space.
There exists a mapping $f : \Z_{>0} \times A^\N \to A^\N$ such that:
:for all $N \in \Z_{>0}$ and $\sequence {x_n}_{n \mathop \in \N}\in A^\N$:
::$\sequence {y_n}_{n \mathop \in \N} := \map f {N, \sequence {x_n}_{n \mathop \in \N}}$ is a subsequence of $\sequence {x_n}_{n \mathop \in \N}$
:and:
::$\forall k, l \in \N: \map d {y_k, y_l} \le \dfrac 1 N$
== Proof ==
Since $\struct {A, d}$ is totally bounded, for each $N\in\Z_{>0}$ there exist:
:$\map k N \in \Z_{>0}$
and:
:$c_1^{\paren N}, \ldots, c_{\map k N}^{\paren N}\in A$
such that:
:$\ds \inf_{1 \mathop \le i \mathop \le \map k N} \map d {c_i ^{\paren N}, x} \le \dfrac 1 {2N}$
for all $x \in A$. 
We write:
:$\ds \SS_N := \tuple {c_1^{\paren N}, \ldots, c_{\map k N}^{\paren N} } \in \bigcup_{k \mathop \in \Z_{>0} } A^k$
By the axiom of countable choice, there exists a sequence $\sequence {\SS_N}_{N\in\Z_{>0}}$ of such sets.
In the following, we define $f$ using this $\sequence {\SS_N}_{N\in\Z_{>0}}$.
Given $N\in\Z_{>0}$ and $\sequence {x_n}_{n \mathop \in \N}$, consider:
:$\SS_N = \tuple {c_1 ^{\paren N},\ldots, c_{\map k N} ^{\paren N}}$
Observe:
:$\ds \N = \bigcup_{i \mathop = 1} ^{\map k N} \set {n \mathop \in \N : \map d {x_n, c_i ^{\paren N} } \le \dfrac 1 {2N} }$
As $\size \N = \infty$, we have:
:$\exists i \in \closedint 1 {\map k N} : \size {\set {n \mathop \in \N : \map d {x_n, c_i ^{\paren N}} \le \dfrac 1 {2N} } } = +\infty$
Therefore, we can choose the minimum of all such indices:
:$i_N := \min \set {i \in \closedint 1 {\map k N} : \size {\set {n \mathop \in \N : \map d {x_n, c_i ^{\paren N} } \le \dfrac 1 {2N} } } = +\infty}$
Now, we define:
:$\map f {N, \sequence {x _n}_{n \mathop \in \N}} := \sequence {x_{m_n} } _{n \mathop \in \N}$
where $m_0 < m_1 < \cdots$ are defined as:
:$\set {m_0, m_1, \ldots} = \set {n \mathop \in \N : \map d {x_n, c_{i_N}^{\paren N} } \le \dfrac 1 {2N} }$
Indeed, by :
:$\forall k, l \in \N: \map d {x_{m_k}, x_{m_l} } \le \map d {x_{m_k}, c_{i_N}^{\paren N} } + \map d {c_{i_N}^{\paren N}, x_{m_l} } \le \dfrac 1 {2N} + \dfrac 1 {2N} = \dfrac 1 N$
Category:Complete and Totally Bounded Metric Space is Sequentially Compact
Complete and Totally Bounded Metric Space is Sequentially Compact/Proof 1

== Theorem ==
== Proof ==
Let $\sequence {x_m}_{m \mathop \in \N}$ be an infinite sequence in $A$.
By the definition of a totally bounded metric space, we can use the axiom of countable choice to obtain a sequence $\sequence {F_n}_{n \mathop \in \N}$ such that:
:For all $n \in \N$, $F_n$ is a finite $2^{-n}$-net for $M$.
For all $n \in \N$ and $y \in F_n$, define:
:$\map {S_n} y = \set {m \in \N: \map d {x_m, y} < 2^{-n} }$
It follows from the definition of a net that:
:$(1): \quad \ds \N = \bigcup_{y \mathop \in F_n} \map {S_n} y$
For all $n \in \N$, define:
:$G_n = \leftset {y \in F_n: \map {S_n} y}$ is infinite$\rightset{}$
Since $F_n$ is finite by definition, it follows by $(1)$ that $G_n$ is non-empty.
For all $y \in G_n$, define:
:$\ds \map {T_n} y = \leftset {z \in G_{n + 1}: \map {S_n} y \cap \map {S_{n + 1} } z}$ is infinite$\rightset{}$
By $(1)$, it follows from the distributivity of intersection over union that:
:$\ds \map {S_n} y = \bigcup_{z \mathop \in F_{n + 1} } \paren {\map {S_n} y \cap \map {S_{n + 1} } z}$
Hence, by the definition of $G_n$, it follows that $\map {T_n} y$ is non-empty.
From Countable Union of Countable Sets is Countable, it follows that the disjoint union $\ds \bigsqcup_{n \mathop \in \N} G_n$ is countable.
Using the axiom of countable choice, there exists a sequence $\sequence {\phi_n: G_n \to G_{n + 1} }_{n \mathop \in \N}$ of mappings such that:
:$\forall n \in \N: \forall y \in G_n: \map {\phi_n} y \in \map {T_n} y$
Now, we use the Principle of Recursive Definition to construct a strictly increasing sequence $\sequence {m_k}_{k \mathop \in \N}$ in $\N$.
Let $y_0 \in G_0$.
Let $m_0 \in \map {S_0} {y_0}$.
For all $k \in \N$, let:
:$y_{k + 1} = \map {\paren {\phi_k \circ \cdots \circ \phi_1 \circ \phi_0} } {y_0}$
where $\circ$ denotes composition of mappings.
Let $m_{k + 1} > m_k$ be the smallest natural number such that:
:$m_{k + 1} \in \map {S_k} {y_k} \cap \map {S_{k + 1} } {y_{k + 1} }$
Such an $m_{k + 1}$ exists by:
:the well-ordering principle
and because:
:$\map {S_k} {y_k} \cap \map {S_{k + 1} } {y_{k + 1} }$ is infinite by the definitions of $\map {T_k} {y_k}$ and $\phi_k$.
Note that:
:$m_k, m_{k + 1} \in \map {S_k} {y_k}$
Let $\hat x_k = x_{m_k}$.
Let $i < j$, where $i, j \in \N$.
Then, by Sum of Infinite Geometric Progression:
:$\ds \map d {\hat x_i, \hat x_j} \le \sum_{k \mathop = i}^{j - 1} \paren {\map d {\hat x_k, y_k} + \map d {\hat x_{k + 1}, y_k} } < \sum_{k \mathop = i}^\infty 2^{1 - k} = 2^{2 - i}$
Hence, by Sequence of Powers of Number less than One, the sequence $\sequence {\hat x_k}_{k \mathop \in \N}$ is Cauchy.
By the assumption that $M$ is complete, the sequence $\sequence {\hat x_k}$ converges in $M$.
Since $\sequence {\hat x_k}$ is a convergent subsequence of $\sequence {x_m}$, it follows that $M$ is sequentially compact by definition.
Category:Complete and Totally Bounded Metric Space is Sequentially Compact
Complete and Totally Bounded Metric Space is Sequentially Compact/Proof 3

== Theorem ==
== Proof ==
Let $M$ be both complete and totally bounded.
Let $\sequence {a_k}$ be any infinite sequence in $A$.
Let $\epsilon \in \R_{>0}$.
Let $x_1, \ldots, x_n \in X$ be a finite set of points such that:
:$\ds A = \bigcup_{i \mathop = 1}^n \map {B_\epsilon} {x_i}$
where $\map {B_\epsilon} {x_i}$ represents the open $\epsilon$-ball of $x_i$.
This is known to exist as $M$ is totally bounded.
Then for every $k \in \N$, there is some $j_k \in \set {0, \dots, n}$ such that $\map d {a_k, x_{j_k} } \le \epsilon$.
For some $j \in \set {0, \dots, n}$, we must have $j_k = j$ for infinitely many $k$, and it follows by setting $x := x_{j_k}$.
Setting $x := x_{j_k}$, we see that:
:$(1): \quad$ There is some $x \in X$ such that $\map d {a_k, x} \le \epsilon$ for infinitely many $k$.
Now let $\sequence {a_k}$ be any infinite sequence in $A$.
By $(1)$, there is some $x_1 \in X$ such that $\map d {a_k, x_1} \le \dfrac 1 2$ for infinitely many $k$. 
Now we can apply $(1)$ to the subsequence of $\sequence {a_k}$ which consisting of those elements for which $\map d {a_k, x_1} \le \dfrac 1 2$.
Thus we can find $x_2 \in A$ such that infinitely many $k$ satisfy both $\map d {a_k, x_2} \le \dfrac 1 4$ and $\map d {a_k, x_1} \le \dfrac 1 2$.
Now we proceed inductively, to obtain a sequence $\sequence {x_m}$ with the property that there exist infinitely many $k$ such that, for $1 \le j \le m$:
:$(2) \quad \map d {a_k, x_j} \le 2^{-j}$
Now define a subsequence $\sequence {a_{k_m} }$ inductively by letting $k_0$ be arbitrary, and choosing $k_{m + 1}$ minimal such that $k_{m + 1} > k_m$ and such that $(2)$ holds for $k = k_m$ and all $1 \le j \le m$. 
Let $\epsilon > 0$, and choose $n$ sufficiently large that $\paren {\dfrac 1 2}^{n - 1} < \epsilon$.
Then:
:$\map d {a_{k_r}, a_{k_s} } \le \map d {a_{k_r}, x_n} + \map d {a_{k_s}, x_n} \le 2 \cdot 2^{-n} < \epsilon$
whenever $r, s \ge n$.
So this subsequence is a Cauchy sequence and hence, because $M$ is complete by assumption, it is convergent.
Thus we see that $\sequence {a_k}$ has a convergent subsequence.
Hence, by definition, $M$ is sequentially compact.
Category:Complete and Totally Bounded Metric Space is Sequentially Compact
Complete and Totally Bounded Metric Space is Sequentially Compact/Proof 4

== Theorem ==
== Proof ==
We use the following lemma, that depends on the axiom of countable choice.
=== Lemma ===
Let $\sequence {x_n}_{n \mathop \in \N}$ be a sequence in $A$.
In the following, we will construct recursively nested subsequences:
:$\sequence {x^{\paren 0}_n}_{n \mathop \in \N}\supseteq \sequence {x^{\paren 1}_n}_{n \mathop \in \N}\supseteq \sequence {x ^{\paren 2}_n}_{n \mathop \in \N} \supseteq\cdots$
such that:
:$\forall N\in\Z_{>0} : \forall k,l \in \N: \map d {x^{\paren N}_k, x^{\paren N}_l} \le \dfrac 1 N$
First, let:
:$\sequence {x^{\paren 0}_n}_{n \mathop \in \N} = \sequence {x_n}_{n \mathop \in \N}$
Then, for each $N \in \Z_{>0}$, applying $f$ from lemma, let:
:$\sequence {x^{\paren N}_n}_{n \mathop \in \N} := \map f {N, \sequence {x^{\paren {N - 1} }_n}_{n \mathop \in \N}}$
Now, let:
:$y_n := x^{\paren n}_n$
for all $n \in \N$.
By construction:
:$\sequence {y_n}_{n \mathop \in \N}$ is a subsequence of $\sequence {x_n}_{n \mathop \in \N}$
and:
:$\forall N \in \Z_{>0}: \sequence {y_n}_{n \mathop \ge N}$ is a subsequence of $\sequence {x^{\paren N}_n}_{n \mathop \in \N}$
From the latter follows:
:$\forall N\in\Z_{>0} : \forall m, n \ge N : \map d {y_m, y_n} \le \dfrac 1 N $
that implies that $\sequence {y_n}_{n \mathop \ge N}$ is a Cauchy sequence.
As $\struct {A, d}$ is complete, $\sequence {y_n}_{n \mathop \in \N}$ is convergent.
Category:Complete and Totally Bounded Metric Space is Sequentially Compact
Completed Riemann Zeta Function has Order One

== Theorem ==
The completed Riemann zeta function $\xi$ has order at most $1$.
== Proof ==
We are required to prove that:
:$\map \xi s = \dfrac 1 2 s \paren {s - 1} \pi^{-s/2} \map \Gamma {\dfrac s 2} \map \zeta s \ll \map \exp {\size s^\beta}$
for all $\beta > 1$, where $\ll$ is the order notation.
Note that by the Functional Equation for Riemann Zeta Function, it is sufficient to check this for $\map \Re s \ge \dfrac 1 2$.
We simply check this fact for each factor.
Evidently:
for some $c_1 > 0$.
For the gamma factor, we have Stirling's Formula for Gamma Function:
:$\ds \log \map \Gamma s = \paren {s - \frac 1 2} \log s - s + \frac {\log 2 \pi} 2 + \sum_{n \mathop = 1}^{d-1} \frac {B_{2 n} } {2 n \paren {2 n - 1}s^{2 n - 1} } + \map \OO {s^{1 - 2 d} }$
This is valid only away from the poles of $\Gamma$ at $s = 0, -1, -2, \ldots$
However, it is assumed that $\map \Re s \ge \dfrac 1 2$, so this is not a problem.
The error term $\map \OO {s^{1 - 2 d} }$ is small for large $s$.
More generally, the largest contribution is the term $\paren {s - \dfrac 1 2} \log s$, so we have:
:$\log \map \Gamma {\dfrac s 2} \ll \size s \log \size s$
That is:
:$\map \Gamma {\dfrac s 2} \ll \map \exp {\size s \log \size s}$
Finally, from Integral Representation of Riemann Zeta Function in terms of Fractional Part, for $\map \Re s > \dfrac 1 2$:
:$\ds \map \zeta s = \frac s {s - 1} - s \int_1^\infty \fractpart x x^{-s - 1} \rd x$
It is seen that for $\map \Re s > \dfrac 1 2$, the integral is bounded, and therefore:
:$\paren {1 - s} \map \zeta s \ll \map \OO {\size s^2} \ll \map \exp {\size s}$
Combining these facts, and using that $\log s \ll s^\epsilon$ for all $\epsilon > 0$ (shown by Upper Bound of Natural Logarithm), we have:
:$\size {\map \xi s} \ll \map \exp {\size s^{1 + \epsilon} }$ 
for all $\epsilon > 0$, and the proof is complete.
Category:Riemann Zeta Function
Completely Additive Function is Additive

== Theorem ==
Let $f: \N \to \C$ be a completely additive function.
Then $f$ is also additive.
== Proof ==
Let $m, n$ be coprime integers.
Then in particular, $m, n \in \Z$.
Hence, since $f$ is completely additive:
:$f \left({m \times n}\right) = f \left({m}\right) + f \left({n}\right)$
and $f$ is additive, as desired.
Category:Number Theory
Category:Ring Theory