nyuuzyou/wikis huggingface dataset:
Set of Finite Character with Choice Function is Type M

== Theorem ==
Let $S$ be a set of sets of finite character.
Let $S$ have a choice function $C$ for its union $\ds \bigcup S$.
Then $S$ is of type $M$.
That is:
:every element of $S$ is a subset of a maximal element of $S$ under the subset relation.
== Proof ==
By Class of Finite Character is Swelled, a set of finite character is swelled.
By Class of Finite Character is Closed under Chain Unions a set of finite character is closed under chain unions.
The result follows from Swelled Set which is Closed under Chain Unions with Choice Function is Type $M$.
== Sources ==
* : Chapter $4$: Superinduction, Well Ordering and Choice: Part $\text {II}$ -- Maximal principles: $\S 6$ Another approach to maximal principles: Corollary $6.4$
Category:Finite Character
Category:Choice Functions
Category:Type M Sets
Set of Finite Character with Choice Function is of Type M

== Theorem ==
Let $S$ be a set of sets with finite character.
Let there exist a choice function for $S$.
Then $S$ is of type $M$, that is:
:every element of $S$ is a subset of a maximal element of $S$ under the subset relation.
== Proof ==
Let $S$ be according to the hypothesis.
From Class of Finite Character is Closed under Chain Unions:
:$S$ is closed under chain unions.
From Closed Set under Chain Unions with Choice Function is of Type $M$:
:$S$ is of type $M$.
== Sources ==
* : Chapter $4$: Superinduction, Well Ordering and Choice: Part $\text {II}$ -- Maximal principles: $\S 5$ Maximal principles
Category:Finite Character
Category:Choice Functions
Category:Type M Sets
Set of Finite Character with Countable Union is Type M

== Theorem ==
Let $S$ be a set of sets of finite character.
Let its union $\bigcup S$ be countable.
Then $S$ is of type $M$.
That is:
:every element of $S$ is a subset of a maximal element of $S$ under the subset relation.
== Proof 1 ==
== Proof 2 ==
Category:Set of Finite Character with Countable Union is Type M
Category:Finite Character
Category:Choice Functions
Category:Type M Sets
Set of Finite Character with Countable Union is Type M/Proof 1

== Theorem ==
== Proof ==
By Countable Set has Choice Function, $S$ has a choice function.
The result follows from Set of Finite Character with Choice Function is Type $M$.
== Sources ==
* : Chapter $4$: Superinduction, Well Ordering and Choice: Part $\text {II}$ -- Maximal principles: $\S 6$ Another approach to maximal principles: Corollary $6.5$
Category:Set of Finite Character with Countable Union is Type M
Set of Finite Character with Countable Union is Type M/Proof 2

== Theorem ==
== Proof ==
Let $S$ be a set of sets of finite character whose union $\bigcup S$ is countable.
Let $D := \bigcup S$ be enumerated as:
:$D = \set {d_1, d_2, \ldots, d_n, d_{n + 1}, \ldots}$
Let $b \in S$ be arbitrary.
From the Principle of Recursive Definition, we can generate a countable sequence of elements of $S$ as follows:
Let $b_0 := b$.
Let it be assumed that $b_n$ has been defined.
Then we take:
:$b_{n + 1} := \begin{cases} b_n \cup \set {d_n} & : \text {if $b_n \cup \set {d_n}$ is an element of $S$} \\ b_n & : \text {otherwise} \end{cases}$
Let $C$ be the set defined as
:$C := \set {b_0, b_1, \ldots, b_n, b_{n + 1}, \ldots}$
From Increasing Sequence of Sets forms Nest, $C$ is a nest which, as $C$ is a set, is in fact a chain.
Hence $\bigcup C \in S$.
From Union of Chain in Set of Finite Character with Countable Union is Maximal Element, $\bigcup C$ is a maximal element of $S$ under the subset relation.
Thus $b$ is a subset of a maximal element of $S$ under the subset relation.
As $b$ is arbitrary, the result follows.
== Historical Note ==
== Sources ==
* 
* : Chapter $4$: Superinduction, Well Ordering and Choice: Part $\text {II}$ -- Maximal principles: $\S 6$ Another approach to maximal principles
Category:Set of Finite Character with Countable Union is Type M
Set of Finite Character with Countable Union is Type M/Proof 2/Historical Note

== Historical Note on Proof $2$ of Set of Finite Character with Countable Union is Type $M$ ==
According to and , this proof was put in place by .
This was reported by in $1930$.
== Sources ==
* 
* : Chapter $4$: Superinduction, Well Ordering and Choice: Part $\text {II}$ -- Maximal principles: $\S 6$ Another approach to maximal principles
Category:Set of Finite Character with Countable Union is Type M
Set of Finite Strings/Examples/Over One Element

== Example of Set of Finite Strings ==
Let $\Sigma$ be the alphabet defined as:
:$\Sigma = \set a$
Then the set of finite strings $\Sigma^*$ over $\Sigma$ is:
:$\Sigma^* = \set {\epsilon, a, aa, aaa, aaaa, \ldots}$
where $\epsilon$ denotes the null string.
== Sources ==
* : Chapter $1$: Preliminaries: $1.1$ Strings, Alphabets and Languages
Category:Examples of Sets of Finite Strings
Set of Finite Strings/Examples/Over Two Elements

== Example of Set of Finite Strings ==
Let $\Sigma$ be the alphabet defined as:
:$\Sigma = \set {0, 1}$
Then the set of finite strings $\Sigma^*$ over $\Sigma$ is:
:$\Sigma^* = \set {\epsilon, 0, 1, 00, 01, 10, 11, 000, 001, \ldots}$
where $\epsilon$ denotes the null string.
== Sources ==
* : Chapter $1$: Preliminaries: $1.1$ Strings, Alphabets and Languages
Category:Examples of Sets of Finite Strings
Set of Finite Strings is Countably Infinite

== Theorem ==
Let $\Sigma$ be a finite alphabet.
Let $\Sigma^*$ be the set of finite strings of $\Sigma$.
Then $\Sigma^*$ is a countably infinite set.
== Proof ==
== Sources ==
* : Chapter $1$: Preliminaries: $1.4$ Set Notation: Infinite sets
Category:Sets of Finite Strings
Category:Infinite Sets
Category:Countable Sets
Set of Finite Subsets of Countable Set is Countable

== Theorem ==
Let $A$ be a countable set.
Then the set of finite subsets of $A$ is countable.
== Proof 1 ==
== Proof 2 ==
== Proof 3 ==
== Sources ==
* : Chapter $1$: General Background: $\S 2$ Countable or uncountable?
Category:Subsets
Category:Countable Sets
Category:Set of Finite Subsets of Countable Set is Countable
Set of Finite Subsets of Countable Set is Countable/Proof 1

== Theorem ==
== 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.
Category:Set of Finite Subsets of Countable Set is Countable
Set of Finite Subsets of Countable Set is Countable/Proof 2

== Theorem ==
== 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^{\left({n}\right)}$ the set of subsets of $A$ that have precisely $n$ elements.
For $A' \in A^{\left({n}\right)}$, we write $A' = \left\{{a'_1, a'_2, \ldots, a'_n}\right\}$ uniquely so that $i < j$ implies $a'_i <_f a'_j$.
Then we define $f^{\left({n}\right)}: A^{\left({n}\right)} \to \N$ by:
:$\displaystyle f^{\left({n}\right)} \left({A'}\right) := \prod_{i \mathop = 1}^n p_i^{f \left({a'_i}\right)}$
where $p_i$ denotes the $i$th prime.
By the Fundamental Theorem of Arithmetic, if $f^{\left({n}\right)} \left({A'}\right) = f^{\left({n}\right)} \left({A}\right)$, then:
:$\left({f \left({a'_1}\right), \dotsc, f \left({a'_n}\right)}\right) = \left({f \left({a_1}\right), \dotsc, f \left({a_n}\right)}\right)$
As $f$ is injective, also:
:$\left({a'_1, \dotsc, a'_n}\right) = \left({a_1, \dotsc, a_n}\right)$
and in particular $A' = A$.
Thus $f^{\left({n}\right)}: A^{\left({n}\right)} \to \N$ is an injection.
So $A^{\left({n}\right)}$ is countable.
Now define $f^{\text{fin}}: A^{\text{fin}} \to \N \times \N$ by:
:$f^{\text{fin}} \left({A'}\right) := \left({n, f^{\left({n}\right)} \left({A'}\right)}\right)$
where $n = \left\vert{A'}\right\vert$ is the cardinality of $A'$.
Suppose that:
:$f^{\text{fin}} \left({A'}\right) = f^{\text{fin}} \left({A}\right)$
Then by Equality of Ordered Pairs:
:$n = \left\vert{A'}\right\vert = \left\vert{A}\right\vert$
and:
:$f^{\left({n}\right)} \left({A'}\right) = f^{\left({n}\right)} \left({A}\right)$
Since $f^{\left({n}\right)}$ 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.
Category:Set of Finite Subsets of Countable Set is Countable
Set of Finite Subsets of Countable Set is Countable/Proof 3

== Theorem ==
== 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.
 
== Sources ==
* : Introduction to Set Theory: $2$. Set Theoretical Equivalence and Denumerability
Category:Set of Finite Subsets of Countable Set is Countable
Set of Finite Subsets under Induced Operation is Closed

== Theorem ==
Let $\struct {S, \circ}$ be a magma.
Let $\struct {\powerset S, \circ_\PP}$ be the power structure of $\struct {S, \circ}$
Let $T \subseteq \powerset S$ be the set of all finite subsets of $S$.
Then the algebraic structure $\struct {T, \circ_\PP}$ is closed.
== Proof ==
Let $X, Y \in T$.
Then:
== Sources ==
* : Chapter $\text {II}$: New Structures from Old: $\S 9$: Compositions Induced on the Set of All Subsets: Exercise $9.8$
Category:Power Structures
Set of Finite Suprema is Directed

== Theorem ==
Let $\struct {S, \vee, \preceq}$ be a join semilattice.
Let $X$ be a non-empty subset of $S$.
Then
:$\set {\sup A: A \in \map {\operatorname {Fin} } X \land A \ne \O}$ is directed.
where $\map {\operatorname {Fin} } X$ denotes the set of all finite subsets of $X$.
== Proof ==
By Existence of Non-Empty Finite Suprema in Join Semilattice:
:for every $A \in \map {\operatorname {Fin} } S$ if $A \ne \O$, then $A$ admits a supremum.
By definition of non-empty set:
:$\exists a: a \in X$
By definitions of subset and singleton:
:$\set x \subseteq X$
By Singleton is Finite:
:$\set x$ is finite
By definitions of non-empty set and singleton:
:$\set x \ne \O$
By definition of $\operatorname {Fin}$:
:$\sup {\set x} \in \set {\sup A: A \in \map {\operatorname{Fin} } X \land A \ne \O}$
Thus by definition:
:$\set {\sup A: A \in \map {\operatorname {Fin} } X \land A \ne \O}$ is a non-empty set.
Let $x, y \in \set {\sup A: A \in \map {\operatorname {Fin} } X \land A \ne \O}$
Then
:$\exists A \in \map {\operatorname {Fin} } X: x = \sup A$ and $A \ne \O$
and
:$\exists B \in \map {\operatorname {Fin} } X: y = \sup B$ and $B \ne \O$
By Finite Union of Finite Sets is Finite:
:$A \cup B$ is finite
By Union of Subsets is Subset:
:$A \cup B \subseteq X$
By definitions of non-empty set and union:
:$A \cup B \ne \O$
By definition of $\operatorname {Fin}$:
:$\map \sup {A \cup B} \in \set {\sup A: A \in \map {\operatorname {Fin} } X \land A \ne \O}$
By Set is Subset of Union:
:$A \subseteq A \cup B$ and $B \subseteq A \cup B$
Thus by Supremum of Subset:
:$x \preceq \map \sup {A \cup B}$ and $y \preceq \map \sup {A \cup B}$
Thus by definition:
:$\set {\sup A: A \in \map {\operatorname {Fin} } X \land A \ne \O}$ is directed.
== Sources ==
* 
* 
Category:Join and Meet Semilattices
Set of Finitely Supported Functions on Integers is Countable

== Theorem ==
Let $\SS$ be the set of functions $f : \Z \to \Z$ for which there exists $N \in \N$ such that:
:$\map f n = 0$ for all $n \in \Z$ with $\size n > N$.
Then $\SS$ is countable.
== Proof ==
Let $\sequence {p_n}_{n \mathop \in \N}$ be an enumeration of the prime numbers.
For each $f \in \SS$ let $N_f \in \N$ be least such that:
:$\map f n = 0$ for all $n \in \Z$ with $\size n > N_f$.
Then for each $f \in \SS$, define $\map \phi f$ by:
:$\ds \map \phi f = 2^{\map f 0} \prod_{j \mathop = 1}^{N_f} p_{2 j + 1}^{\map f j} \prod_{j \mathop = 1}^{N_f} p_{2 \paren {j + 1} }^{\map f {-j} }$
We show that $\phi : \SS \to \N$ is an injection.
Suppose that $f, g \in \SS$ and that $\map \phi f = \map \phi g$.
We have:
:$\ds 2^{\map f 0} \prod_{j \mathop = 1}^{N_f} p_{2 j + 1}^{\map f j} \prod_{j \mathop = 1}^{N_f} p_{2 \paren {j + 1} }^{\map f {-j} } = 2^{\map g 0} \prod_{j \mathop = 1}^{N_g} p_{2 j + 1}^{\map g j} \prod_{j \mathop = 1}^{N_g} p_{2 \paren {j + 1} }^{\map g {-j} }$
Since $N_f$ and $N_g$ were picked to be least, we must have $N_f = N_g$.
Further from the Fundamental Theorem of Arithmetic, we must have:
:$\map f j = \map g j$ for all $j \in \Z$.
Hence $f = g$. 
Hence $\phi$ is an injection.
So $\SS$ is countable.
Category:Countable Sets
Set of Functions on Circle forms Vector Space

the set of functions $\map f \phi$ on the circle (0 \le \phi < 2 \pi) forms a vector space:
:$\ds \map f \phi = \sum_{m \mathop = -\infty}^{+\infty} a_m e^{i m \phi}$
for integer m
* : Chapter $1$: Introductory Concepts: $1$. Basic Building Blocks: $4$. LINEAR VECTOR SPACE: Example $4$
Set of Gödel Numbers of Arithmetic Theorems Not Definable in Arithmetic

== Theorem ==
Let $T$ be the set of theorems of some consistent theory in the language of arithmetic which contains minimal arithmetic.
The set of Gödel numbers of the theorems of $T$ is not definable in $T$.
== Proof ==
The proof is by contradiction.
Let $\Theta$ be the set of Gödel numbers of the theorems of $T$.
Suppose it is defined in $T$ by the formula $\map \theta y$.
Since $T$ contains $Q$, we may apply the Diagonal Lemma to $\neg \map \theta y$.
This gives us a sentence $G$ such that
:$T \vdash G \leftrightarrow \neg \map \theta {\hat G}$
where $\hat G$ is the Gödel number of $G$ (more accurately, it is the term in the language of arithmetic obtained by applying the function symbol $s$ to $0$ this many times).
Suppose $G$ is not a theorem of $T$.
:Then the Gödel number of $G$ is not in $\Theta$.
:Since $\theta$ defines $\Theta$ in $T$, this means that:
::$T \vdash \neg \map \theta {\hat G}$
:But, by choice of $G$ (specifically, the bi-implication above), this gives us:
::$T\vdash G$
:which contradicts $G$ not being a theorem of $T$
Thus, $G$ is a theorem of $T$.
:But, then the Gödel number of $G$ is in $\Theta$, and
:since $\theta$ defines $\Theta$ in $T$, this means that
::$T \vdash \map \theta {\hat G}$
:But, then this gives us
::$T \vdash \neg G$
:which contradicts $G$ being a theorem of $T$, since $T$ is consistent.
Since assuming $\Theta$ was definable in $T$ necessarily leads to a contradiction, we conclude that it is impossible.
== Sources ==
* 
Category:Mathematical Logic
Set of Homomorphisms to Abelian Group is Subgroup of All Mappings

== Theorem ==
Let $\struct {S, \circ}$ be an algebraic structure.
Let $\struct {T, \oplus}$ be an abelian group.
Let $\struct {T^S, \oplus}$ be the algebraic structure on $T^S$ induced by $\oplus$.
Then the set of all homomorphisms from $\struct {S, \circ}$ into $\struct {T, \oplus}$ is a subgroup of $\struct {T^S, \oplus}$.
== Proof ==
Let $H$ be the set of all homomorphisms from $\struct {S, \circ}$ into $\struct {T, \oplus}$.
=== ===
We have that $\struct {T, \oplus}$ be an abelian group.
Hence $\struct {T, \oplus}$ is a commutative semigroup.
From Homomorphism on Induced Structure to Commutative Semigroup:
:$\forall f, g \in H: f \oplus g$ is a homomorphism from $\struct {S, \circ}$ into $\struct {T, \oplus}$.
Hence $\struct {H, \oplus}$ is closed.
=== ===
From Inverse Mapping in Induced Structure of Homomorphism to Abelian Group, if $g$ is a homomorphism then its pointwise inverse $g^*$ is one also.
Thus $g \in H \implies g^* \in H$.
So by the Two-Step Subgroup Test, $\struct {H, \oplus}$ is a subgroup of $\struct {T^S, \oplus}$.
== Sources ==
* : Chapter $\text {II}$: New Structures from Old: $\S 13$: Compositions Induced on Cartesian Products and Function Spaces: Theorem $13.7$: Corollary
Category:Homomorphisms (Abstract Algebra)
Category:Subgroups
Category:Abelian Groups
Set of Ideals forms Complete Lattice

== Theorem ==
Let $\struct {K, +, \circ}$ be a ring.
Let $\mathbb K$ be the set of all ideals of $K$.
Then $\struct {\mathbb K, \subseteq}$ is a complete lattice.
== Proof ==
Let $\O \subset \mathbb S \subseteq \mathbb K$.
By Intersection of Ring Ideals is Largest Ideal Contained in all Ideals:
:$\bigcap \mathbb S$ is the largest ideal of $K$ contained in each of the elements of $\mathbb S$.
By Intersection of Ring Ideals Containing Subset is Smallest:
:The intersection of the set of all ideals of $K$ containing $\bigcup \mathbb S$ is the smallest ideal of $K$ containing $\bigcup \mathbb S$.
Thus, not only is $\bigcap \mathbb S$ a lower bound of $\mathbb S$, but also the largest, and therefore an infimum.
The supremum of $\mathbb S$ is the join of the set of all ideals of $\mathbb S$.
From Sum of Ideals is Ideal: General Result, this supremum is:
:$\ds \sum_{S \mathop \in \mathbb S} \struct {S, +, \circ}$
That is:
:$\struct {S_1, +, \circ} + \struct {S_2, +, \circ} + \dotsb$
where addition of ideals is as defined in subset product.
Therefore $\struct {\mathbb K, \subseteq}$ is a complete lattice.
== Sources ==
* : Chapter $\text {IV}$: Rings and Fields: $22$. New Rings from Old: Theorem $22.4$: Corollary
Category:Complete Lattices
Category:Ideal Theory
Set of Idempotent Elements of Entropic Structure is Closed

== Theorem ==
Let $\struct {S, \odot}$ be an algebraic structure such that $\odot$ is entropic.
Let $T \subseteq S$ be the set of idempotent elements of $S$.
Then $\struct {T, \odot}$ is closed.
== Proof ==
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 16$: The Natural Numbers: Exercise $16.27 \ \text {(b)}$
Category:Idempotence
Category:Entropic Structures
Set of Images of Reflexive Relation is Cover of Set

== Theorem ==
Let $\RR \subseteq S \times S$ be a reflexive relation in $S$.
Let $\II = \set{\map \RR x : x \in S}$ be the set of images under $\RR$. 
Then:
:$\II$ is a cover of $S$
== Proof ==
By definition of reflexive relation:
:$\forall x \in S : \tuple{x, x} \in \RR$
By definition of image:
:$\forall x \in S : x \in \map \RR x$
Hence, $\II$ is a cover of $S$ by definition.
Category:Reflexive Relations
Category:Covers
Set of Infima for Sequence is Directed

== Theorem ==
Let $\struct {S, \vee, \wedge, \preceq}$ be a complete lattice.
Let $\struct {A, \precsim}$ be a non-empty directed set.
Let $Z: A \to S$ be a net.
Let $D = \set {\map \inf {Z \sqbrk {\map \precsim j} }: j \in A}$ be a subset of $S$.
Then $D$ is directed.
== Proof ==
By definition of non-empty set:
:$\exists j: j \in A$
By definition of $D$:
:$\inf \left({Z \sqbrk {\map \precsim j} }\right) \in D$
Hence by definition:
:$D$ is a non-empty set.
Let $x, y \in D$.
By definition of $D$:
:$\exists j_1 \in A: x = \map \inf {Z \sqbrk {\map \precsim {j_1} } }$
and
:$\exists j_2 \in A: y = \map \inf {Z \sqbrk {\map \precsim {j_2} } }$
By definition of directed set:
:$\exists j \in A: j_1 \precsim j \land j_2 \precsim j$
By Preceding implies Image is Subset of Image:
:$\map \precsim j \subseteq \map {\mathord \precsim} {j_1}$ and $\map \precsim j \subseteq \map {\mathord \precsim} {j_2}$
By Image of Subset under Mapping is Subset of Image:
:$Z \sqbrk {\map \precsim j} \subseteq Z \sqbrk {\map \precsim {j_1} }$ and $Z \sqbrk {\map \precsim j} \subseteq Z \sqbrk {\map \precsim {j_2} }$
Thus by definition of $D$:
:$z := \map \inf {Z \sqbrk {\map \precsim j} } \in D$
Thus by Infimum of Subset:
:$x \preceq z$ and $y \preceq z$
== Sources ==
* 
Category:Order Theory
Set of Infinite Sequences is Uncountable

== Theorem ==
Let $S$ be a set which contains more than one element.
Let $S^\infty$ denote the set of all sequences of elements of $S$.
Then $S^\infty$ is uncountable.
== Proof ==
As $S$ has more than one element, it must have at least two.
So, let $a, b \in S$ be those two elements.
Let $Z$ be the set of all sequences from $\set {a, b}$.
Suppose $S^\infty$ were countable.
From Subset of Countably Infinite Set is Countable, $Z$ is likewise countable.
So by definition, it would be possible to set up a bijection $\phi: Z \leftrightarrow \N$ between $Z$ and the set $\N$ of natural numbers:
where each of $z_{rs}$ is:
: an element of $\set {a, b}$
: the $s$'th element of $\sequence {z_r}$, the particular sequence which is in correspondence with $r \in \N$.
Now we create the sequence $Q = \sequence {q_{dd} }$ where:
:$q_{dd} = \begin{cases} a & : z_{dd} = b \\ b & : z_{dd} = a \end{cases}$
Thus:
:$\forall n \in \N: q_{nn} \notin \sequence {z_n}$
and so:
:$\forall n \in \N: Q \ne \sequence {z_n}$
So $Q \notin Z$.
That is, we have constructed a sequence which has not been placed into correspondence with an element of $\N$.
Thus by definition $Z$ is uncountable.
Hence, by the Rule of Transposition, $S^\infty$ is likewise uncountable.
== Sources ==
* : Chapter $1$: Mappings: $\S 15 \zeta$
* : $2.9$
Category:Countable Sets
Category:Diagonal Arguments
Set of Integer Combinations equals Set of Multiples of GCD

== Theorem ==
The set of all integer combinations of $a$ and $b$ is precisely the set of all integer multiples of the GCD of $a$ and $b$:
:$\gcd \set {a, b} \divides c \iff \exists x, y \in \Z: c = x a + y b$
== Proof ==
=== Necessary Condition ===
Let $d = \gcd \set {a, b}$.
Then:
:$d \divides c \implies \exists m \in \Z: c = m d$
So:
Thus:
:$\gcd \set {a, b} \divides c \implies \exists x, y \in \Z: c = x a + y b$
=== Sufficient Condition ===
Suppose $\exists x, y \in \Z: c = x a + y b$.
From Common Divisor Divides Integer Combination, we have:
:$\gcd \set {a, b} \divides \paren {x a + y b}$
It follows directly that $\gcd \set {a, b} \divides c$ and the proof is finished.
== Sources ==
* : $\text {2-2}$ Divisibility: Corollary $\text {2-2}$
* : Chapter $2$: Some Properties of $\Z$: Exercise $2.4$
* : Chapter $2$: Divisibility Theory in the Integers: $2.2$ The Greatest Common Divisor: Theorem $2 \text{-} 3$: Corollary
* : Chapter $2$: Divisibility Theory in the Integers: $2.2$ The Greatest Common Divisor: Problems $2.2$: $13 \ \text {(a)}$
* : Appendix $1$: Some Results from the Elementary Theory of Numbers: Lemma $2$
Category:Integer Combinations
Category:Greatest Common Divisor
Set of Integer Combinations includes Zero

== Lemma ==
Let $a, b \in \Z$ be integers.
Let $S = \set {a x + b y: x, y \in \Z}$ be the set of integer combinations of $a$ and $b$.
Then $0 \in S$.
== Proof ==
By setting $x = 0$ and $y = 0$:
:$a \cdot 0 + b \cdot 0 = 0$
== Sources ==
* : Appendix $1$: Some Results from the Elementary Theory of Numbers: Lemma $1$
Category:Integer Combinations
Set of Integer Combinations includes those Integers

== Lemma ==
Let $a, b \in \Z$ be integers.
Let $S = \set {a x + b y: x, y \in \Z}$ be the set of integer combinations of $a$ and $b$.
Then $a \in S$ and $b \in S$.
== Proof ==
By setting $x = 1$ and $y = 0$:
:$a \cdot 1 + b \cdot 0 = a$
By setting $x = 0$ and $y = 1$:
:$a \cdot 0 + b \cdot 1 = b$
== Sources ==
* : Appendix $1$: Some Results from the Elementary Theory of Numbers: Lemma $1$
Category:Integer Combinations