nyuuzyou/wikis huggingface dataset:
Cartesian Product Preserves Cardinality

== Theorem ==
Let $R$, $S$, and $T$ be sets.
Suppose that $S$ is equivalent to $T$.
Then:
:$R \times S \sim R \times T$
:$S \times R \sim T \times R$
== Proof ==
Since $S$ and $T$ are equivalent, there exists a bijection $f: S \to T$.
Let $g: T \to S$ be the inverse of $f$; its existence is assured by Bijection iff Left and Right Inverse.
Define $\hat f: R \times S \to R \times T$ by:
:$\map {\hat f} {r, s} := \tuple {r, \map f s}$
Next, define $\hat g: R \times T \to R \times S$ by:
:$\map {\hat g} {r, t} := \tuple {r, \map g t}$
Then, for all $\tuple {r, s} \in R \times S$:
Similarly, for all $\tuple {r, t} \in R \times T$:
Thus, it follows that $\hat g$ is a inverse for $\hat f$.
From Bijection iff Left and Right Inverse, we conclude $\hat f$ is a bijection.
Hence $R \times S \sim R \times T$, by definition of set equivalence.
Mutatis mutandis, the other relation also follows.
Category:Cartesian Product
Cartesian Product is Anticommutative

== Theorem ==
Let $S, T \ne \O$.
Then:
:$S \times T = T \times S \iff S = T$
=== Corollary ===
== Proof ==
Suppose $S \times T = T \times S$.
Then:
Thus it can be seen from the definition of set equality that $S \times T = T \times S \iff S = T$.
Note that if $S = \O$ or $T = \O$ then, from Cartesian Product is Empty iff Factor is Empty, $S \times T = T \times S = \O$ whatever $S$ and $T$ are, and the result does not hold.
== Also see ==
* Bijection between S x T and T x S
== Sources ==
* : Chapter $\text {II}$: Topological Spaces: $\S 8$. Notations and definitions of set theory
::: except that the case where either set is empty has been ignored
* : $\S 1.2$
* : Introduction to Set Theory: $1$. Elementary Operations on Sets
* : $\S 2.1$: Sets: Exercise $\text{C} \ 1$
* : $1$. Preliminary ideas; sets, vector spaces: $1.1$. Sets
* : Chapter $1$. Sets: Exercise $8$
::: except that the case where either set is empty has been ignored
* : Chapter $1$: The Notation and Terminology of Set Theory: $\S 9$
* : $\S 1.9$: Cartesian Product
* : $\S 3$. Ordered pairs; cartesian product sets
* : Chapter $1$: Theory of Sets: $\S 5$: Products of Sets
::: except that the case where either set is empty has been ignored
* : Chapter $1$: Sets and Logic: Exercise $13$
* : Chapter $1$: Sets and mappings: $\S 1.3$: Mappings: Exercise $11$
Category:Cartesian Product
Cartesian Product is Anticommutative/Corollary

== Corollary to Cartesian Product is Anticommutative ==
Let $S$ and $T$ be sets.
Then:
:$S \times T = T \times S \iff S = T \lor S = \O \lor T = \O$
where $S \times T$ denotes the cartesian product of $S$ and $T$.
== Proof ==
Suppose $S \times T = T \times S$.
Then either:
:$(1): \quad S \ne \O \land T \ne \O$ and from Cartesian Product is Anticommutative, $S = T$
or:
:$(2): \quad S = \O \lor T = \O$ and from Cartesian Product is Empty iff Factor is Empty, $S \times T = T \times S = \O$.
In either case, we see that:
:$S \times T = T \times S \implies S = T \lor S = \O \lor T = \O$
Now suppose $S = T \lor S = \O \lor T = \O$.
From Cartesian Product is Empty iff Factor is Empty, we have that:
:$S = \O \lor T = \O \implies S \times T = \O = T \times S$
Similarly:
:$S = T \land \neg \paren {S = \O \lor T = \O} \implies S \times T = T \times S$
by definition of equality. 
== Sources ==
* : $\S 3$. Ordered pairs; cartesian product sets: Exercise $5$
* : Chapter $1$: Sets and mappings: $\S 1.3$: Mappings: Exercise $11$
Category:Cartesian Product
Cartesian Product is Empty iff Factor is Empty

== Theorem ==
:$S \times T = \O \iff S = \O \lor T = \O$
Thus:
:$S \times \O = \O = \O \times T$
=== Family of Sets ===
== Proof ==
So by the Rule of Transposition:
:$S = \O \lor T = \O \iff S \times T = \O$
== Sources ==
* : $\S 6$: Ordered Pairs
* : $\S 2.1$: Sets: Exercise $\text{C} \ 5$
* : $1$. Preliminary ideas; sets, vector spaces: $1.1$. Sets
* : Chapter $\text I$: Algebraic Structures: $\S 1$: The Language of Set Theory: Exercise $1.2$
* : $\S 3$. Ordered pairs; cartesian product sets
* : $\S 8$: Cartesian product of sets
Category:Cartesian Product
Category:Empty Set
Cartesian Product is Empty iff Factor is Empty/Family of Sets

== Theorem ==
Let $I$ be an indexing set.
Let $\family {S_i}_{i \mathop \in I}$ be a family of sets indexed by $I$.
Let $\ds S = \prod_{i \mathop \in I} S_i$ be the Cartesian product of $\family {S_i}_{i \mathop \in I}$.
Then:
:$S = \O$ $S_i = \O$ for some $i \in I$
== Proof ==
=== Necessary Condition ===
By the axiom of choice, the contrapositive statement holds:
:if $S_i \ne \O$ for all $i \in I$ then $S \ne \O$
By the Rule of Transposition, the converse holds:
:if $S = \O$ then $S_i = \O$ for some $i \in I$
=== Sufficient Condition ===
Let $S_j = \O$ for some $j \in I$.
By the definition of the Cartesian product:
:$\ds \prod_{i \mathop \in I} S_i := \set {f: \paren {f: I \to \bigcup_{i \mathop \in I} S_i} \land \paren {\forall i \in I: \paren {\map f i \in S_i} } }$
For any $\ds f: I \to \bigcup_{i \mathop \in I} S_i$ we have:
:$\map f j \notin S_j$
Thus:
:$f \notin \ds \prod_{i \mathop \in I} S_i$
It follows that:
:$\ds \prod_{i \mathop \in I} S_i = \O$
Category:Cartesian Product
Category:Empty Set
Cartesian Product is Set Product

== Theorem ==
Let $S$ and $T$ be sets.
Let $S \times T$ be the Cartesian product of $S$ and $T$.
Let $\pr_1: S \times T \to S$ and $\pr_2: S \times T \to T$ be the first and second projections respectively on $S \times T$.
Then $\struct {S \times T, \pr_1, \pr_2}$ is a set product.
=== Family of Sets ===
== Proof ==
Consider any set $X$ and mappings $f_1: X \to S$ and $f_2: X \to T$.
Define $h: X \to S \times T$ by:
:$\forall x \in X: \map h x = \tuple {\map {f_1} x, \map {f_2} x}$
Then for all $x \in X$ we have:
:$\map {\paren {\pr_1 \mathop \circ h} } x = \pr_1 \tuple {\map {f_1} x, \map {f_2} x} = \map {f_1} x)$
and
:$\map {\paren {\pr_2 \mathop \circ h} } x = \pr_2 \tuple {\map {f_1} x, \map {f_2} x} = \map {f_2} x$
So:
:$\pr_1 \mathop \circ h = f_1$
:$\pr_2 \mathop \circ h = f_2$
Thus $h$ is shown to exist.
Suppose there exists a mapping $k: X \to S \times T$ such that:
:$\pr_1 \mathop \circ k = f_1$
:$\pr_2 \mathop \circ k = f_2$
Let $x \in X$ and let $\map k x = \tuple {s, t}$.
Then:
:$\map {f_1} x = \map {\paren {\pr_1 \mathop \circ k} } x = \map {\pr_1} {s, t} = s$
:$\map {f_2} x = \map {\paren {\pr_2 \mathop \circ k} } x = \map {\pr_2} {s, t} = t$
and so:
and so $k = h$.
So $h$ is unique.
Hence the result.
== Sources ==
* : Chapter $\text{I}$: Sets and Functions: Problem $\text{BB}$: Categorical Matters
* : $\S 5$. Induced mappings; composition; injections; surjections; bijections: Theorem $5.12$
* : $\S 2.5.1$
Category:Set Products
Category:Cartesian Product
Cartesian Product is Set Product/Family of Sets

== Theorem ==
Let $\family {S_i}_{i \mathop \in I}$ be a family of sets.
For all $j \in I$, let $\pr_i: \ds \prod_{j \mathop \in I} \family {S_j} \to S_i$ be the $i$th projection from $\ds \prod_{j \mathop \in I} \family {S_j}$ to $S_i$.
Then $\struct {\ds \prod_{j \mathop \in I} \family {S_j}, \family {\pr_i}_{i \mathop \in I} }$ is a set product.
== Proof ==
Let $i \in I$.
Consider any set $X$ and any indexed family of mappings $\family {f_i: X \to S_i}_{i \mathop \in I}$.
Define $h: X \to \ds \prod_{j \mathop \in I} \family {S_j}$ by:
:$\forall x \in X: \map h x = \family {\map {f_i} x}_{i \mathop \in I}$
Then for all $x \in X$ and $i \in I$ we have:
:$\map {\paren {\pr_i \mathop \circ h} } x = \map {\pr_i} {\family {\map {f_i} x}_{i \mathop \in I} } = \map {f_i} x$
So:
:$\pr_i \mathop \circ h = f_i$
Thus $h$ is shown to exist.
Suppose there exists a mapping $k: X \to \ds \prod_{j \mathop \in I} \family {S_j}$ such that:
:$\forall i \in I: \pr_1 \mathop \circ k = f_i$
Let $x \in X$ and let:
:$\map k x = \family {s_j}_{j \mathop \in I}$
for some $\family {s_j}_{j \mathop \in I} \in \ds \prod_{j \mathop \in I} \family {S_j}$.
Then:
:$\map {f_i} x = \map {\paren {\pr_i \mathop \circ k} } x = \map {\pr_i} {\family {s_j}_{j \mathop \in I} } = s_i$
and so:
:$\map k x = \family {s_j}_{j \mathop \in I} = \family {\map {f_i} x}_{i \mathop \in I} = \map h x$
and so $k = h$.
So $h$ is unique.
Hence the result.
== Sources ==
* : $\S 6$. Indexed families; partitions; equivalence relations: Theorem $6.7$
Category:Set Products
Category:Cartesian Product
Cartesian Product is Small

== Theorem ==
Let $a$ and $b$ be small classes.
Then their Cartesian product $a \times b$ is small:
:$\map {\MM} {a \times b}$
== Proof ==
By Binary Cartesian Product in Kuratowski Formalization contained in Power Set of Power Set of Union:
:$a \times b \subseteq \powerset {\powerset {a \cup b} }$
By Union of Small Classes is Small, $a \cup b$ is small.
By the Axiom of Powers, $\powerset {\powerset {a \cup b} }$ is small.
By Axiom of Subsets Equivalents, $a \times b$ is small.
== Sources ==
* : $\S 6.2$
Category:Zermelo-Fraenkel Class Theory
Cartesian Product is Small iff Inverse is Small

== Theorem ==
Let $A$ and $B$ be classes.
Then the Cartesian product $A \times B$ is a small class $B \times A$ is small.
== Proof ==
Let $B \times A$ be a small class.
Then, by Inverse of Small Relation is Small, $A \times B$ is also small.
Similarly, let $A \times B$ be small.
Then, by Inverse of Small Relation is Small, $B \times A$ is also small.
== Sources ==
* : $\S 6.9 \ (1)$
Category:Zermelo-Fraenkel Class Theory
Cartesian Product is Unique

== Theorem ==
Let $A$ and $B$ be classes.
If there exists a cartesian product of $A$ and $B$, then it is unique.
== Proof ==
Let $C_1$ and $C_2$ be cartesian products of $A$ and $B$.
Then by the cartesian product definition, for an arbitrary $a$:
:$a \in C_1 \iff \exists x \in A: \exists y \in B: a = \tuple {x, y}$
:$a \in C_2 \iff \exists x \in A: \exists y \in B: a = \tuple {x, y}$
By Biconditional is Transitive:
:$a \in C_1 \iff a \in C_2$
By Axiom of Extension:
:$C_1 = C_2$
Thus the cartesian product of $A$ and $B$ is unique.
== Sources ==
* : Chapter $2$: Some Basics of Class-Set Theory: $\S 7$ Cartesian products
Category:Cartesian Product
Cartesian Product is not Associative

== Theorem ==
Let $A, B, C$ be non-empty sets.
Then:
:$A \times \paren {B \times C} \ne \paren {A \times B} \times C$
where $A \times B$ is the cartesian product of $A$ and $B$.
== Intuitive Proof ==
== Formal Proof ==
== Comment ==
Despite this result, the cartesian product of three sets is usually just written $A \times B \times C$ and understood to be the set of all ordered triples.
That is, as the set of all elements like $\tuple {a, b, c}$.
From Cardinality of Cartesian Product of Finite Sets, we have that:
:$\card {A \times \paren {B \times C} } = \card {\paren {A \times B} \times C}$
and so:
:$A \times \paren {B \times C} \sim \paren {A \times B} \times C$
where $\sim$ denotes set equivalence.
So it matters little whether $A \times B \times C$ is defined as being $A \times \paren {B \times C}$ or $\paren {A \times B} \times C$, and it is rare that one would even need to know.
When absolute rigour is required, the cartesian product of more than two sets can be defined using ordered $n$-tuples or, even more generally, by indexed sets.
== Also see ==
* Bijection between R x (S x T) and (R x S) x T
* Equality of Cartesian Products
== Sources ==
* : Exercise $1.2: \ 13$
* : Chapter $1$. Sets: Exercise $8$
* : Chapter $1$: The Notation and Terminology of Set Theory: $\S 9 \beta$
Category:Cartesian Product
Category:Cartesian Product is not Associative
Cartesian Product is not Associative/Proof 1

== Theorem ==
== Intuitive Proof ==
By definition:
:$A \times B = \set {\tuple {a, b}: a \in A, b \in B}$
that is, the set of all ordered pairs $\tuple {a, b}$ such that $a \in A$ and $b \in B$.
Now:
:Elements of $A \times \paren {B \times C}$ are in the form $\tuple {a, \tuple {b, c} }$
:Elements of $\paren {A \times B} \times C$ are in the form $\tuple {\tuple {a, b}, c}$.
So for $A \times \paren {B \times C} = \paren {A \times B} \times C$ we would need to have that $a = \tuple {a, b}$ and $\tuple {b, c} = c$.
This can not possibly be so, except perhaps in the most degenerate cases.
So from the strict perspective of the interpretation of the pure definitions:
:$A \times \paren {B \times C} \ne \paren {A \times B} \times C$
Category:Cartesian Product is not Associative
Cartesian Product is not Associative/Proof 2

== Theorem ==
== Formal Proof ==
Assign to every set $X$ the following number $\map n X \in \N$:
:$\map n X = \begin {cases} 0 & : X = \O \\ 1 + \max_{Y \mathop \in X} \map n Y & : \text{ otherwise} \end {cases}$
From the Axiom of Foundation:
:$\forall X \in \N: \map n X < \infty$
Now let $a \in A$ be such that:
:$\map n a = \min_{b \mathop \in A} \map n b$
Suppose that:
:$\exists a' \in A, b \in B: a = \tuple {a', b}$
That is, that $a$ equals the ordered pair of $a'$ and $b'$. 
Then it follows that:
That is:
:$\map n {a'} < \map n a$
contradicting the assumed minimality of the latter. 
Therefore:
:$a \notin A \times B$
and hence:
:$A \nsubseteq A \times B$
It follows from Equality of Cartesian Products that:
:$A \times \paren {B \times C} \ne \paren {A \times B} \times C$
Category:Cartesian Product is not Associative
Cartesian Product of Bijections is Bijection

== Theorem ==
Let $S_1 \times S_2$ be the Cartesian product of two sets $S_1$ and $S_2$.
Let $T_1 \times T_2$ be the Cartesian product of two sets $T_1$ and $T_2$.
Let $f_1: S_1 \to T_1$ and $f_2: S_2 \to T_2$ be bijections.
Let $f_1 \times f_2: S_1 \times S_2 \to T_1 \times T_2$ be the Cartesian product of $f_1$ and $f_2$ defined as:
:$\forall \left({s_1, s_2}\right) \in S_1 \times S_2: f_1 \times f_2 \left({s_1, s_2}\right) := \left({f_1 \left({s_1}\right), f_2 \left({s_2}\right)}\right)$
Then $f_1 \times f_2$ is a bijection.
=== General Result ===
== Proof ==
Because $f_1$ and $f_2$ are both bijections, it follows by definition that they are both surjections.
Let $\left({t_1, t_2}\right) \in T_1 \times T_2$.
Then:
:as $f_1$ is a surjection, $\exists s_1 \in S_1: f_1 \left({s_1}\right) = t_1$
:as $f_2$ is a surjection, $\exists s_2 \in S_2: f_2 \left({s_2}\right) = t_2$
Thus:
:$\exists \left({s_1, s_2}\right) \in S_1 \times S_2: f_1 \times f_2 \left({s_1, s_2}\right) = \left({t_1, t_2}\right)$
So $f_1 \times f_2$ is a surjection.
Because $f_1$ and $f_2$ are both bijections, it follows by definition that they are both injections.
Let:
: $f_1 \times f_2 \left({a_1, a_2}\right) = \left({c_1, c_2}\right), f_1 \times f_2 \left({b_1, b_2}\right) = \left({d_1, d_2}\right)$
for some $\left({a_1, a_2}\right), \left({b_1, b_2}\right) \in S_1 \times S_2$.
Suppose $\left({c_1, c_2}\right) = \left({d_1, d_2}\right)$.
Then by Equality of Ordered Pairs:
:$c_1 = d_1$
:$c_2 = d_2$
By definition of $f_1 \times f_2$:
:$f_1 \left({a_1}\right) = c_1$
:$f_1 \left({b_1}\right) = d_1$
and:
:$f_2 \left({a_2}\right) = c_2$
:$f_2 \left({b_2}\right) = d_2$
As $f_1$ is an injection:
:$c_1 = d_1 \implies a_1 = b_1$
and as $f_2$ is an injection:
:$c_2 = d_2 \implies a_2 = b_2$
Thus it follows that:
:$\left({c_1, c_2}\right) = \left({d_1, d_2}\right) \implies \left({a_1, a_2}\right) = \left({b_1, b_2}\right)$
and so $f_1 \times f_2$ is an injection.
So $f_1 \times f_2$ is a surjection and also an injection.
Hence by definition, $f_1 \times f_2$ is a bijection.
Category:Bijections
Category:Cartesian Product
Cartesian Product of Bijections is Bijection/General Result

== Theorem ==
Let $I$ be an indexing set.
Let $\family {S_i}_{i \mathop \in I}$ and $\family {T_i}_{i \mathop \in I}$ be families of sets indexed by $I$.
Let $\ds \SS := \prod_{i \mathop \in I} S_i$ and $\ds \TT := \prod_{i \mathop \in I} T_i$ be the Cartesian products of $\family {S_i}_{i \mathop \in I}$ and $\family {T_i}_{i \mathop \in I}$ respectively.
For all $i \in I$, let $f_i: S_i \to T_i$ be a bijection.
Let $\ds \FF: \SS \to \TT := \prod_{i \mathop \in I} \paren {f_i: S_i \to T_i}$ be the Cartesian product of $\family {f_i}_{i \mathop \in I}$ defined as:
:$\ds \forall \mathbf s \in \SS: \map \FF {\mathbf s} := \prod_{i \mathop \in I} \paren {\map {f_i} {s_i} }$
where $\mathbf s := \family {S_i}_{i \mathop \in I}$ is an arbitrary element of $\family {S_i}_{i \mathop \in I}$.
Then $\FF$ is a bijection.
== Proof ==
Because $f_i$ are bijections, it follows by definition that they are surjections.
Let $\mathbf t := \family {t_i}_{i \mathop \in I} \in \TT$.
Then as $f_i$ is a surjection:
:$\forall i \in I: \exists s_i \in S_i: \map {f_i} {s_i} = t_i$
Thus:
:$\exists \mathbf s \in \SS: \map \FF {\mathbf s} = \mathbf t$
So $\FF$ is a surjection.
Because $f_i$ are bijections, it follows by definition that they are injections.
Let:
:$\mathbf t_1 := \family {t_{i 1} }_{i \mathop \in I} \in \TT$
:$\mathbf t_2 := \family {t_{i 2} }_{i \mathop \in I} \in \TT$
Let:
:$\map \FF {\mathbf s_1} = \paren {\mathbf t_1}, \map \FF {\mathbf s_2} = \mathbf t_2$
for some $\mathbf s_1, \mathbf s_2 \in \SS$ where:
:$\mathbf s_1 := \family {s_{i 1} }_{i \mathop \in I}$
:$\mathbf s_2 := \family {s_{i 2} }_{i \mathop \in I}$
Suppose $\mathbf t_1 = \mathbf t_2$.
Then:
:$\forall i \in I: t_{i 1} = t_{i 2}$
By definition of $\FF$:
:$\forall i \in I: \map {f_i} {s_{i 1} } = t_{i 1}$
:$\forall i \in I: \map {f_i} {s_{i 2} } = t_{i 2}$
As $f_i$ is an injection for all $i \in I$:
:$\forall i \in I: t_{i 1} = t_{i 2} \implies s_{i 1} = s_{i 2}$
Thus it follows that:
:$\mathbf t_1 = \mathbf t_2 \implies \mathbf s_1 = \mathbf s_2$
and so $\FF$ is an injection.
So $\FF$ is a surjection and also an injection.
Hence by definition, $\FF$ is a bijection.
== Sources ==
* : Chapter $1$: Theory of Sets: $\S 10$: Arbitrary Products: Exercise $2$
Category:Bijections
Category:Cartesian Product
Category:Indexed Families
Cartesian Product of Countable Sets is Countable

== Theorem ==
The cartesian product of two countable sets is countable.
=== Corollary ===
== Informal Proof ==
== Formal Proof 1 ==
== Formal Proof 2 ==
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 18$: Induced $N$-ary Operations: Exercise $18.16$
* : Chapter $1$: Mappings: $\S 15 \delta$
* : Chapter $1$: Preliminaries: Exercises: $1.12$
* : $1$: Set Theory and Logic: $\S 7$: Countable and Uncountable Sets: Theorem $7.6$
* : Appendix $\text{A}$: Set Theory: Countable Sets
Category:Set Theory
Category:Cartesian Product
Category:Countable Sets
Category:Cartesian Product of Countable Sets is Countable
Cartesian Product of Countable Sets is Countable/Corollary

== Corollary to Cartesian Product of Countable Sets is Countable ==
Let $k$ be an integer such that $k > 1$.
Then the cartesian product of $k$ countable sets is countable.
== Proof 1 ==
== Proof 2 ==
== Sources ==
* : Appendix $\text{A}$: Set Theory: Countable Sets
* : Chapter $\text {III}$: The Natural Numbers: $\S 18$: Induced $N$-ary Operations: Exercise $18.16$
Category:Cartesian Product of Countable Sets is Countable
Cartesian Product of Countable Sets is Countable/Corollary/Proof 1

== Corollary to Cartesian Product of Countable Sets is Countable ==
== Proof ==
Let $S_1, S_2, \ldots, S_k$ be countable sets. Equivalently, there exists an injection $f_i: S_i \to \N$ for each $i \in \{ 1, \dots, k \}$.
Therefore, the mapping $g: S_1 \times S_2 \times \cdots \times S_k \to \N^k$ defined by (for $x_i \in S_i$):
:$\map g {x_1, x_2, \dotsc, x_k} = \tuple {\map {f_1} {x_1}, \map {f_2} {x_2}, \dotsc, \map {f_k} {x_k} }$
is also injective.
Now let $p_1, p_2, \ldots, p_k$ be the first $k$ prime numbers.
From the Fundamental Theorem of Arithmetic, $f: \N^k \to \N$ defined as:
:$\map f {n_1, n_2, \ldots, n_k} = p_1^{n_1} p_2^{n_2} \cdots p_k^{n_k}$
is an injection.
From Composite of Injections is Injection, $f \circ g: S_1 \times S_2 \times \cdots \times S_k \to \N$ is injective.
== Sources ==
* : Exercise $18.16$
* : Appendix $\text{A}$: Set Theory: Countable Sets
Category:Cartesian Product of Countable Sets is Countable
Cartesian Product of Countable Sets is Countable/Corollary/Proof 2

== Corollary to Cartesian Product of Countable Sets is Countable ==
== Proof ==
Proof by induction:
=== Basis for the Induction ===
When $k = 2$, the case is the same as Cartesian Product of Countable Sets is Countable.
So shown for basis for the induction.
=== Induction Hypothesis ===
This is our induction hypothesis:
:$\exists f_k: S_1 \times S_2 \times \cdots \times S_k \to \N$
where $f_k$ is an injection.
Now we need to show that for $n = k + 1$:
:$\exists f_{k+1}: S_1 \times S_2 \times \cdots \times S_k \times S_{k+1} \to \N$
where $f_{k+1}$ is an injection.
=== Induction Step ===
This is our induction step:
By the induction hypothesis:
:$\exists f_k: S_1 \times S_2 \times \cdots \times S_k \to \N$
where $f_k$ is an injection.
Thus by definition, $S_1 \times S_2 \times \cdots \times S_k$ is countable.
By hypothesis $S_{k + 1}$ is countable.
So by the basis for the induction:
:$\exists g: \left({S_1 \times S_2 \times \cdots \times S_k}\right) \times S_{k+1} \to \N \times \N$
where $g$ is an injection.
By Cartesian Product of Countable Sets is Countable,
:$\exists r: \N \times \N \to \N$
where $r$ is an injection.
Therefore, by Composite of Injections is Injection:
:$f_{k+1} = r \circ g: S_1 \times S_2 \times \cdots \times S_k \times S_{k+1} \to \N$
is an injection.
The result follows by induction.
== Sources ==
* : $1$: Set Theory and Logic: $\S 7$: Countable and Uncountable Sets: Theorem $7.6$
Category:Cartesian Product of Countable Sets is Countable
Cartesian Product of Countable Sets is Countable/Formal Proof 1

== Theorem ==
== Proof ==
Let $S, T$ be countable sets.
From the definition of countable, there exists a injection from $S$ to $\N$, and similarly one from $T$ to $\N$.
Hence there exists an injection $g$ from $S \times T$ to $\N^2$.
Now let us investigate the cardinality of $\N^2$.
From the Fundamental Theorem of Arithmetic, every natural number greater than $1$ has a unique prime decomposition.
Thus, if a number can be written as $2^n 3^m$, it can be done thus in only one way.
So, consider the function $f: \N^2 \to \N$ defined by:
:$\map f {n, m} = 2^n 3^m$.
Now suppose $\exists m, n, r, s \in \N$ such that $\map f {n, m} = \map f {r, s}$.
Then $2^n 3^m = 2^r 3^s$ so that $n = r$ and $m = s$.
Thus $f$ is an injection, whence $\N^2$ is countably infinite.
Now we see that as $g$ and $f$ are injective, it follows from Composite of Injections is Injection that $f \circ g: S \times T \to \N$ is also injective.
Hence the result.
Category:Cartesian Product of Countable Sets is Countable
Cartesian Product of Countable Sets is Countable/Formal Proof 2

== Theorem ==
== Proof ==
Let $S, T$ be countable sets.
Let $S = \set {s_1, s_2, s_3, \dotsc}$ and $T = \set {t_1, t_2, t_3, \dotsc}$ be enumerations of $S$ and $T$ respectively.
Let $f: S \times T: \N$ be the mapping defined as:
:$\forall \tuple {s_k, t_l} \in S \times T: \map f {s_k, t_l} = \dfrac {\paren {k + l - 1} \paren {k + l - 2} } 2 + \dfrac {l + \paren {-1}^{k + 1} } 2 k + \dfrac {1 + \paren {-1}^{k + l - 1} } 2 l$
Then $f$ gives an enumeration of $S \times T$.
This enumeration can be depicted schematically as:
:$\begin {array} {} \tuple {s_1, t_1} & & \tuple {s_1, t_2} & \to & \tuple {s_1, t_3} & & \tuple {s_1, t_4} & \to & \dotsc \\
\downarrow & \nearrow & & \swarrow & & \nearrow & \dotsc \\
\tuple {s_2, t_1} & & \tuple {s_2, t_2} & & \tuple {s_2, t_3} & \dotsc \\
& \swarrow & & \nearrow & \dotsc \\
\tuple {s_3, t_1} & & \tuple {s_2, t_3} & \dotsc \\
\downarrow & \nearrow & \dotsc \\
\tuple {s_3, t_1} & \dotsc \\
\vdots \\
\end{array}$
Hence the result.
== Sources ==
* : Introduction to Set Theory: $2$. Set Theoretical Equivalence and Denumerability
Category:Cartesian Product of Countable Sets is Countable