nyuuzyou/wikis huggingface dataset:
Cardinal Product Equal to Maximum

== Theorem ==
Let $S$ and $T$ be sets that are equinumerous to their cardinal number.
Let $\card S$ denote the cardinal number of $S$.
Suppose $S$ is infinite.
Suppose $T > 0$.
Then:
:$\card {S \times T} = \map \max {\card S, \card T}$
== Proof ==
Let $x$ denote $\map \max {\card S, \card T}$.
Then by Cartesian Product Preserves Cardinality:
:$S \times T \sim \card S \times \card T$
Let $f: S \times T \to \card S \times \card T$ be a bijection.
It follows that $f: S \times T \to x \times x$ is an injection.
Hence:
Therefore:
:$\card {S \times T} \le x$
Conversely:
:$x = \card S$ if $\card T \le \card S$
and:
:$x = \card T$ if $\card S \le \card T$
By Relation between Two Ordinals:
:$x = \card S$ or $x = \card T$
It follows by Set Less than Cardinal Product that:
:$x \le \card {S \times T}$
Combining the two lemmas, it follows that:
:$x = \card {S \times T}$
== Sources ==
* : $\S 10.35$
Category:Cardinals
Cardinal Product Equinumerous to Ordinal Product

== Theorem ==
Let $S$ and $T$ be sets that are equivalent to their cardinal numbers.
Let $\card S$ denote the cardinal number of $S$.
Let $\cdot$ denote ordinal multiplication and let $\times$ denote the Cartesian product.
Then:
:$S \times T \sim \card S \cdot \card T$
== Proof ==
Let $f: S \to \card S$ and $g: T \to \card T$ be bijections.
Let $\cdot$ denote ordinal multiplication, while $\times$ shall denote the Cartesian product.
Define the function $F$ to be:
:$\forall x \in S, y \in T: \map F {x, y} = \card S \cdot \map g y + \map f x$
Suppose $\map F {x_1, y_1} = \map F {x_2, y_2}$.
It follows that $F: S \times T \to \card S \cdot \card T$ is a injection.
Furthermore, take any $z \in \card S \cdot \card T$.
By Division Theorem for Ordinals, it follows that:
:$z = \card S \cdot a + b$ for some unique $a$ and $b \in \card S$.
Moreover, $a \in \card T$ since otherwise, this would contradict the fact that $z \in \card S \cdot \card T$.
Therefore, $a = \map f x$ for some $x \in S$ and $b = \map g y$ for some $y \in T$.
Thus, $F : S \times T \to \card S \cdot \card T$ is a surjection.
Therefore, $F : S \times T \to \card S \cdot \card T$ is a bijection.
By Condition for Set Equivalent to Cardinal Number, it follows that:
:$S \times T \sim \card S \cdot \card T$
Category:Cardinals
Category:Ordinal Arithmetic
Cardinal Zero is Less than Cardinal One

== Theorem ==
The zero cardinal $0$ is less than one:
:$0 < 1$
== Proof ==
We have that the Cardinals are Totally Ordered.
Let $\RR \subseteq \O \times \set \O$ be any arbitrary relation between $\O$ and $\set \O$.
We have that $\RR$ is vacuously many-to-one.
Also vacuously, $\RR$ is left-total.
Thus by definition, $\RR$ is in fact a mapping.
From Empty Mapping is Unique, this relation $\RR$ is the unique mapping from $\O$ to $\set \O$.
Also vacuously, $\RR$ is an injection.
So, by definition, $\set \O$ dominates $\O$.
Since Empty Set is Subset of All Sets, we have $\O \subseteq \set \O$.
Hence the result.
== Sources ==
* : $\S 8$
Category:Cardinals
Cardinal of Cardinal Equal to Cardinal

== Theorem ==
Let $S$ be a set such that $S$ is equivalent to its cardinal.
If the axiom of choice holds, then this condition holds for any set.
Then:
:$\card {\paren {\card S} } = \card S$
where $\card S$ denotes the cardinal number of $S$.
=== Corollary ===
== Proof ==
By Condition for Set Equivalent to Cardinal Number:
:$S \sim \card S$
Therefore, by Equivalent Sets have Equal Cardinal Numbers:
:$\card S = \card {\paren {\card S} }$
== Sources ==
* : $\S 10.16$
Category:Cardinals
Cardinal of Cardinal Equal to Cardinal/Corollary

== Theorem ==
Let $\NN$ denote the class of all cardinal numbers.
Let $x$ be an ordinal.
Then:
:$x \in \NN \iff x = \card x$
== Proof ==
=== Necessary Condition ===
Suppose $x = \card x$.
Then $x = \card y$ for some $y$ by Existential Generalisation.
By definition of class of all cardinals:
:$\NN = \set {x \in \On: \exists y: x = \card y}$
It follows that $x \in \NN$.
=== Sufficient Condition ===
== Sources ==
* : $\S 10.38$
Category:Cardinals
Cardinal of Finite Ordinal

== Theorem ==
Let $n$ be a finite ordinal.
Let $\card n$ denote the cardinal number of $n$.
Then:
:$\card n = n$
== Proof ==
Since $n$ is an ordinal, it follows that $\card n \le n$ by Cardinal Number Less than Ordinal: Corollary.
Hence, $\card n$ is also a finite ordinal.
Since $n$ is an ordinal, it also follows that $n \sim \card n$ by Ordinal Number Equivalent to Cardinal Number.
By Equality of Natural Numbers, it follows that $n = \card n$.
== Sources ==
* : $\S 10.19$
Category:Cardinals
Category:Finite Ordinals
Cardinal of Union Equal to Maximum

== Theorem ==
Let $S$ and $T$ be sets that are equinumerous to their cardinal number.
Let $\card S$ denote the cardinal number of $S$.
Suppose $S$ is infinite.
Then:
:$\card {S \cup T} = \map \max {\card S, \card T}$
== Proof ==
Let $x$ denote $\map \max {\card S, \card T}$.
$x = \card S$ if $\card T \le \card S$
$x = \card T$ if $\card S \le \card T$
By Relation between Two Ordinals:
:$x = \card S$ or $x = \card T$
In either case, it follows by Subset of Union that:
:$x \le \card {S \cup T}$
If $\card T = 1$ or $\card T = 0$, it follows that $\card {S \cup T} = \card S = x$ by the definition of an infinite set.
If $1 < \card T$, then $\card {S \cup T} \le \card {S \times T}$ by Cardinal of Union Less than Cardinal of Cartesian Product.
But by Cardinal Product Equal to Maximum, it follows that $\card {S \cup T} \le x$.
Combining the two lemmas, it follows that $x = \card {S \cup T}$
== Sources ==
* : $\S 10.35$
Category:Cardinals
Cardinal of Union Less than Cardinal of Cartesian Product

== Theorem ==
Let $S$ and $T$ be sets that are equivalent to their cardinal numbers.
Let $\card S$ denote the cardinal number of $S$.
Let $\card S > 1$ and $\card T > 1$.
Then:
:$\card {S \cup T} \le \card {S \times T}$
== Proof ==
Let $x_1$ and $x_2$ be distinct elements of $S$.
Let $y_1$ and $y_2$ be distinct elements of $T$.
Define the mapping $f : S \times T \to S \cup T$ as follows:
$\quad\map f {x, y} = \begin {cases}
y &: x = x_1 \\
x_1 &: x = x_2 \land y = y_1 \\
x &: \text {otherwise}
\end {cases}$
If $x \in S$, then we have that either $x = x_1$ or $x \ne x_1$.
If $x \ne x_1$, then $\map f {x, y_2} = x$ by the definition of $f$.
If $x = x_1$, then $\map f {x_2, y_1} = x_1$ by the definition of $f$.
If $y \in S$, then we have that:
:$\map f {x_1, y} = y$ by the definition of $f$.
Therefore, it follows that $f : S \times T \to S \cup T$ is a surjection.
Thus by Surjection iff Cardinal Inequality:
:$\card {S \cup T} \le \card {S \times T}$
== Sources ==
* : $\S 10.28$
Category:Cardinals
Cardinalities form Inequality implies Difference is Nonempty

== Theorem ==
Let $X, Y$ be sets.
Let
:$\card X < \card Y$
where $\card X$ denotes the cardinality of $X$.
Then:
:$Y \setminus X \ne \O$
== Proof ==
 that:
:$Y \setminus X = \O$
Then by Set Difference with Superset is Empty Set:
:$Y \subseteq X$
Hence by Subset implies Cardinal Inequality:
:$\card Y \le \card X$
This contradicts:
:$\card X < \card Y$
Hence the result.
== Sources ==
* 
Category:Cardinals
Cardinality/Examples

== Examples of Cardinality ==
=== Cardinality $3$ ===
Let:
=== Cardinality of $S_1 = \set {-1, 0, 1}$ ===
=== Cardinality of $S_2 = \set {x \in \Z: 0 < x < 6}$ ===
=== Cardinality of $S_3 = \set {x^2 - x: x \in S_1}$ ===
=== Cardinality of $S_4 = \set {X \in \powerset {S_2}: \card X = 3}$ ===
=== Cardinality of $S_5 = \powerset \O$ ===
== Sources ==
* : Chapter $1$: Sets and Logic: Exercise $4$
Category:Examples of Cardinality
Cardinality/Examples/-1,0,1

== Example of Cardinality ==
Let $S_1 = \set {-1, 0, 1}$.
The cardinality of $S_1$ is given by:
:$\card {S_1} = 3$
== Proof ==
$S_1$ has $3$ elements: $-1, 0, 1$.
Hence the result by definition of cardinality.
== Sources ==
* : Chapter $1$: Sets and Logic: Exercise $4$
Category:Examples of Cardinality
Cardinality/Examples/0 less than x less than 6

== Example of Cardinality ==
Let $S_2 = \set {x \in \Z: 0 < x < 6}$.
The cardinality of $S_2$ is given by:
:$\card {S_2} = 5$
== Proof ==
The elements of $S_2$, by definition, are those integers greater than $0$ and less than $6$.
That is:
:$S_2 = \set {1, 2, 3, 4, 5}$
Thus $S_2$ has $5$ elements: $1, 2, 3, 4, 5$.
Hence the result by definition of cardinality.
== Sources ==
* : Chapter $1$: Sets and Logic: Exercise $4$
Category:Examples of Cardinality
Cardinality/Examples/3

== Example of Cardinality ==
Let $S$ be a set.
Then $S$ has cardinality $3$ :
That is:
:$S$ contains elements which can be labelled $x$, $y$ and $z$
:Each of these elements is distinct from the others
:Every element of $S$ is either $x$, $y$ or $z$.
== Historical Note ==
== Sources ==
* : Chapter $3$: The Natural Numbers: $\S 1$ Preliminaries
Category:Examples of Cardinality
Category:3
Cardinality/Examples/3/Historical Note

== Historical Note on Cardinality $3$ ==
 and others questioned the validity and usefulness of this definition of Cardinality $3$, in that one needs to have counted the elements of $S$ before starting.
Hence the intuitive notion of $3$-ness is argued to be prior to this definition.
== Sources ==
* : Chapter $3$: The Natural Numbers: $\S 1$ Preliminaries
Category:Historical Notes
Cardinality/Examples/Powerset of Arbitrary Set

== Example of Cardinality ==
Let:
:$S_4 = \set {X \in \powerset {S_2}: \card X = 3}$
where $S_2 = \set {x \in \Z: 0 < x < 6}$.
The cardinality of $S_4$ is given by:
:$\card {S_4} = 10$
== Proof ==
By Cardinality of $S_2$, we have that:
:$\card {S_2} = 5$
Then:
Hence the result by definition of cardinality.
== Sources ==
* : Chapter $1$: Sets and Logic: Exercise $4$
Category:Examples of Cardinality
Cardinality/Examples/Powerset of Empty Set

== Example of Cardinality ==
Let:
:$S_5 = \powerset \O$
where:
:$\O$ denotes the empty set
:$\powerset \O$ denotes the power set of $\O$.
The cardinality of $S_5$ is given by:
:$\card {S_5} = 1$
== Proof ==
By Power Set of Empty Set, we have that:
:$\powerset \O = \set {\O}$
Thus $\powerset \O$ contains exactly $1$ element, that is: $\O$.
Hence the result by definition of cardinality.
== Sources ==
* : Chapter $1$: Sets and Logic: Exercise $4$
Category:Examples of Cardinality
Cardinality/Examples/x^2-x

== Example of Cardinality ==
Let:
:$S_3 = \set {x^2 - x: x \in S_1}$
where $S_1 = \set {-1, 0, 1}$.
The cardinality of $S_3$ is given by:
:$\card {S_3} = 2$
== Proof ==
The elements of $S_3$ can be found by calculation:
Thus by definition of set:
:$S_3 = \set {0, 2}$
Thus $S_3$ has $2$ elements: $0, 2$.
Hence the result by definition of cardinality.
== Sources ==
* : Chapter $1$: Sets and Logic: Exercise $4$
Category:Examples of Cardinality
Cardinality Less One

== Theorem ==
Let $S$ be a finite set.
Let:
:$\card S = n + 1$
where $\card S$ is the cardinality of $S$.
Let $a \in S$.
Then:
:$\card {S \setminus \set a} = n$
where $\setminus$ denotes set difference.
== Proof ==
This follows as an immediate consequence of Set Equivalence Less One Element.
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 17$: Finite Sets: Theorem $17.4$
Category:Set Theory
Cardinality is Additive Function

== Theorem ==
Let $S$ be a finite set.
Let $\powerset S$ be the power set of $S$.
The function $C: \powerset S \to \R$, where $C$ is defined as the cardinality of a set, is an additive function.
== Proof ==
We have that $\powerset S$ is an algebra of sets.
Category:Set Systems
Cardinality of Basis of Sorgenfrey Line not greater than Continuum

== Theorem ==
Let $T = \struct {\R, \tau}$ be the Sorgenfrey line.
Let
:$\BB = \set {\hointr x y: x, y \in \R \land x < y}$
be the basis of $T$.
Then $\card \BB \le \mathfrak c$
where
:$\card \BB$ denotes the cardinality of $\BB$
:$\mathfrak c = \card \R$ denotes the continuum.
== Proof ==
Define a mapping $f: \BB \to \R \times \R$:
:$\forall I \in \BB: \map f I = \tuple {\min I, \sup I}$
That is:
:$\map f {\hointr x y} = \tuple {x, y} \forall x, y \in \R: x < y$
We will show that $f$ is an injection by definition.
Let $I_1, I_2 \in \BB$ such that:
:$\map f {I_1} = \map f {I_2}$
So:
:$I_1 = I_2$
Thus $f$ is an injection.
By Injection implies Cardinal Inequality:
:$\card \BB \le \card {\R \times \R}$
By Cardinal Product Equal to Maximum:
:$\card {\R \times \R} = \map \max {\mathfrak c, \mathfrak c}$
Thus:
:$\card \BB \le \mathfrak c$
== Sources ==
* 
* 
Category:Sorgenfrey Line
Cardinality of Cartesian Product of Finite Sets

== Theorem ==
Let $S \times T$ be the cartesian product of two finite sets $S$ and $T$.
Then:
:$\card {S \times T} = \card S \times \card T$
where $\card S$ denotes cardinality.
This is convenient, given the symbology.
=== Corollary ===
=== General Result ===
== Proof ==
Let $\card S = n$ and $\card T = m$.
If either $n = 0$ or $m = 0$, then from Cartesian Product is Empty iff Factor is Empty:
:$S \times T = \O$
and the result holds, as $n m = 0 = \card \O$ from Cardinality of Empty Set.
So, we assume that $n > 0$ and $m > 0$.
For each $a \in S$, we define the mapping $g_a: T \to \set a \times T$ such that:
:$\forall y \in T: \map {g_a} y = \tuple {a, y}$
The mapping $g_a$ is a bijection, so:
:$\card {\set a \times T} = m$
Now let:
:$\mathbb T = \set {\set a \times T: a \in S}$
We define the mapping $h: S \to \mathbb T$:
:$\forall a \in S: \map h a = \set a \times T$
The mapping $h$ is a bijection, so $\card {\mathbb T} = n$.
Thus $\mathbb T$ is a partition of $S \times T$ containing $n$ sets.
Hence from Number of Elements in Partition:
:$\card {S \times T} = n m$
and the result follows.
== Examples ==
== Sources ==
* : Introduction $\S 2$: Product sets, mappings
* : $\S 13$: Arithmetic
* : $\S 2.1$: Sets: Exercise $\text{C} \ 3$
* : $\S 1.7$. Pairs. Product of sets: Example $22$
* : Chapter $\text I$: Algebraic Structures: $\S 1$: The Language of Set Theory: Exercise $1.2$
* : Chapter $\text {III}$: The Natural Numbers: $\S 19$: Combinatorial Analysis: Theorem $19.3$
* : Chapter $\text{I}$: Sets and Functions: Exercise $\text{N}$
* : Chapter $1$: Mappings: $\S 15 \gamma$
* : $\S 1.9$: Cartesian Product: Exercise $5$
* : Chapter $1$: Theory of Sets: $\S 5$: Products of Sets: Exercise $2$
* : Appendix $\text{A}.2$: Cartesian Products and Relations
* : $\S 8.1$: Cartesian product of sets
* : Chapter $1$: Preliminaries: $1.4$ Set Notation: Example $1.2$
* : Chapter $1$: Sets and mappings: $\S 1.2$: Sets: Exercise $3$
* : Chapter $2$: Some Basics of Class-Set Theory: $\S 7$ Cartesian products: Remark
Category:Combinatorics
Category:Cartesian Product
Category:Cardinality
Category:Cardinality of Cartesian Product
Cardinality of Cartesian Product of Finite Sets/Corollary

== Corollary to Cardinality of Cartesian Product of Finite Sets ==
Let $S \times T$ be the cartesian product of two sets $S$ and $T$ which are both finite.
Then:
:$\card {S \times T} = \card {T \times S}$
where $\card {S \times T}$ denotes the cardinality of $S \times T$.
== Proof 1 ==
== Proof 2 ==
== Sources ==
* : Chapter $3$. Mappings: Exercise $9 \ \text {(i)}$
* : $1$: Set Theory and Logic: $\S 5$: Cartesian Products: Exercise $1$
Category:Cardinality of Cartesian Product
Cardinality of Cartesian Product of Finite Sets/Corollary/Proof 2

== Corollary to Cardinality of Cartesian Product of Finite Sets ==
== Proof ==
Let $f: S \times T \to T \times S$ be the mapping defined as:
:$\forall \tuple {s, t} \in S \times T: \map f {s, t} = \tuple {t, s}$
which is shown to be bijective as follows:
showing $f$ is an injection.
Let $\tuple {t, s} \in T \times S$.
Then:
:$\exists \tuple {s, t} \in S \times T: \map f {s, t} = \tuple {t, s}$
showing that $f$ is a surjection.
So we have demonstrated that there exists a bijection from $S \times T$ to $T \times S$.
The result follows by definition of set equivalence.
== Sources ==
* : Chapter $\text{I}$: Sets and Functions: Exercise $\text{P}$
* : $\S 8$: Example $8.1$
Category:Cardinality of Cartesian Product
Cardinality of Cartesian Product of Finite Sets/Examples/Sets with 3 and 5 Elements

== Example of Use of Cardinality of Cartesian Product of Finite Sets ==
Let $S$ be a set whose cardinality is $3$.
Let $T$ be a set whose cardinality is $5$.
Then the cardinality of $S \times T$ is $15$.
== Sources ==
* : Chapter $2$: Some Basics of Class-Set Theory: $\S 7$ Cartesian products: Remark
Category:Examples of Use of Cardinality of Cartesian Product
Cardinality of Cartesian Product of Finite Sets/General Result

== Theorem ==
Let $\ds \prod_{k \mathop = 1}^n S_k$ be the cartesian product of a (finite) sequence of sets $\sequence {S_n}$.
Then:
:$\ds \card {\prod_{k \mathop = 1}^n S_k} = \prod_{k \mathop = 1}^n \card {S_k}$
This can also be written:
:$\card {S_1 \times S_2 \times \ldots \times S_n} = \card {S_1} \times \card {S_2} \times \ldots \times \card {S_n}$
=== Corollary ===
== Proof ==
Proof by mathematical induction.
Let:
:$\ds \map P n = \paren {\card {\prod_{k \mathop = 1}^n S_k} = \prod_{k \mathop = 1}^n \card {S_k} }$
For $n = 1$:
:$\ds \card {\prod_{k \mathop = 1}^1 S_k} = \card{S_1} = \prod_{k \mathop = 1}^1 \card {S_k}$
These equalities follow directly from the definition of a finite cartesian product.
Thus $\map P n$ is true for $n = 1$. 
For $n = m + 1$ we have:
:$\ds \card {\prod_{k \mathop = 1}^{m + 1} S_k} = \card {\paren {\prod_{k \mathop = 1}^m S_k} \times S_{m + 1} }$
Applying Cardinality of Cartesian Product of Finite Sets:
:$\ds \card {\paren {\prod_{k \mathop = 1}^m S_k} \times S_{m + 1} } = \card {\prod_{k \mathop = 1}^m S_k} \times \card {S_{m + 1} }$
Applying the induction step for $n = m$:
:$\ds \card {\prod_{k \mathop = 1}^m S_k} \times \card {S_{m + 1} } = \prod_{k \mathop = 1}^m \card {S_k} \times \card {S_{m + 1} } = \prod_{k \mathop = 1}^{m + 1} \card {S_k}$
Hence for $n = m + 1$, assuming $\map P m$:
:$\ds \card {\prod_{k \mathop = 1}^{m + 1} S_k} = \prod_{k \mathop = 1}^{m + 1} \card {S_k}$
which completes the proof.
Category:Cardinality of Cartesian Product
Cardinality of Cartesian Product of Finite Sets/General Result/Corollary

== Theorem ==
Let $S$ be a finite set.
Let $S^n$ be a cartesian space on $S$.
Then:
:$\card {S^n} = \card S^n$
where $\card {\, \cdot \,}$ denotes cardinality.
== Proof ==
This is an instance of Cardinality of Cartesian Product of Finite Sets: General Result, where each set is equal. 
Category:Cardinality of Cartesian Product
Cardinality of Codomain of Surjection

== Theorem ==
Let $S$ be a set.
Let:
:$\card S = n$
where $\card S$ denotes the cardinality of $S$.
Let $f: S \to T$ be a surjection.
Then $\card T \le n$.
The equality:
:$\card T = n$
occurs $f$ is a bijection.
== Proof ==
We have that $\card S = n$.
Then by definition of cardinality:
:there is a surjection from $S$ to $T$
:
:there is a surjection from $\N_n$ to $T$.
So we need consider the case only when $S = \N_n$.
By definition of surjection:
:$\forall x \in T: f^{-1} \sqbrk {\set x} \ne \O$
where $f^{-1} \sqbrk {\set x}$ denotes the preimage of $\set x$ under $f$.
From the Well-Ordering Principle, $\N$ is well-ordered.
Therefore by Subset of Well-Ordered Set is Well-Ordered, $S = \N_n$ is well-ordered.
We have that $f^{-1} \sqbrk {\set x} \subseteq S$.
Therefore $f^{-1} \sqbrk {\set x}$ is also well-ordered.
Therefore, by definition of well-ordered set, $f^{-1} \sqbrk {\set x}$ has a smallest element.
Let $g: T \to S$ be the mapping defined as:
:$\forall x \in T: g \paren x =$ the smallest element of $f^{-1} \sqbrk {\set x}$
Let $x \in T$.
Then:
:$g \paren x \in f^{-1} \sqbrk {\set x}$
so:
:$f \paren {g \paren x} = x$
Thus:
:$f \circ g = I_T$
and by Identity Mapping is Bijection:
:$I_T: T \to g \sqbrk T$ is a bijection.
By Cardinality of Subset of Finite Set:
:$\card {g \sqbrk T} \le n$
Let $\card {g \sqbrk T} = m$.
By Set Equivalence behaves like Equivalence Relation:
:$\card T = m$
elements.
Suppose $m = n$.
Then by Cardinality of Subset of Finite Set:
:$g \sqbrk T = S$
so $g: T \to S$ is a bijection.
Therefore:
So $f: S \to T$ is a bijection.
== Also presented as ==
This result can also be presented as:
:The mapping $f: S \to T$ cannot be a surjection if $\card S < \card T$.
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 17$: Finite Sets: Theorem $17.6$
* : Appendix $\text{A}.10$: Finite Sequences: Proposition $\text{A}.10.1: \ 2$
* : Chapter $2$: 'And you do addition?': $\S 2.1$: Functions: Ponderable $2.1.4$
Category:Surjections
Category:Bijections
Category:Cardinality
Cardinality of Complement

== Theorem ==
Let $T \subseteq S$ such that $\card S = n, \card T = m$.
Then:
:$\card {\relcomp S T} = \card {S \setminus T} = n - m$
where:
:$\relcomp S T$ denotes the complement of $T$ relative to $S$
:$S \setminus T$ denotes the difference between $S$ and $T$.
== Proof ==
The result is obvious for $S = T$ or $T = \O$.
Otherwise, $\set {T, S \setminus T}$ is a partition of $S$.
Let $\card {S \setminus T} = p$.
Then by the Fundamental Principle of Counting:
:$m + p = n$
and the result follows.
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 19$: Combinatorial Analysis: Theorem $19.2$
Category:Combinatorics
Category:Set Difference
Category:Cardinality
Cardinality of Empty Set

== Theorem ==
:$\card S = 0 \iff S = \O$
That is, the empty set is finite, and has a cardinality of zero.
== Proof ==
Zero is defined as the cardinal of the empty set.
The result follows from Finite Cardinals and Ordinals are Equivalent.
== Sources ==
* : $\S 1.3$. Intersection
* : $\S 8$
* : $0$
* : $2$. Graphs: Sets
Category:Empty Set
Category:Cardinality
Category:Finite Sets
Cardinality of Even and Odd Permutations on Finite Set

== Theorem ==
Let $n \in \N_{> 0}$ be a natural number greater than $0$.
Let $S$ be a set of cardinality $n$.
Let $S_n$ denote the symmetric group on $S$ of order $n$.
Let $R_e$ and $R_o$ denote the subsets of $S_n$ consisting of even permutations and odd permutations respectively.
Then the cardinality of both $R_e$ and $R_o$ is $\dfrac {n!} 2$.
== Proof ==
From Order of Symmetric Group:
:$\order {S_n} = n!$
where:
:$\order {S_n}$ denotes the order of $S_n$
:$n!$ denotes the factorial of $n$.
By definition:
:$\card {R_e} + \card {R_o} = \order {S_n}$
From Odd and Even Permutations of Set are Equivalent:
:$\card {R_e} = \card {R_o}$
The result follows.
== Sources ==
* : Appendix: Elementary set and number theory
Category:Odd Permutations
Category:Even Permutations
Cardinality of Extensions of Function on Subset of Finite Set

== Theorem ==
Let $m, n \in \Z_{>0}$ be (strictly) positive integers.
Let $S$ be a set with $m$ elements.
Let $T$ be a set with $n$ elements.
Let $A$ be a subset of $S$ with $r$ elements where $0 \le r < m$.
Let $f: A \to T$ be a mapping.
Then there are $n^{m - r}$ distinct extensions of $f$ to $S$.
== Proof ==
Let $N$ denote the number of distinct extensions of $f$ to $S$.
The question is equivalent to asking the number of distinct mappings from $S \setminus A$ to $T$.
There are $m - r$ elements in $S \setminus A$.
Hence from Cardinality of Set of All Mappings:
:$N = n^{m - r}$
== Sources ==
* : Chapter $1$: Theory of Sets: $\S 9$: Inverse Functions, Extensions, and Restrictions: Exercise $4$
Category:Finite Sets
Category:Restrictions
Category:Mapping Theory
Category:Cardinality
Cardinality of Finite Set is Well-Defined

== Theorem ==
Let $S$ be a finite set.
Then there is a unique natural number $n$ such that $S \sim \N_n$, where:
:$\sim$ represents set equivalence
and:
:$\N_n = \set {0, 1, \dotsc, n - 1}$ is the initial segment of $\N$ determined by $n$.
== Proof ==
By the definition of finite set, there is an $n \in \N$ such that $S \sim \N_n$.
Suppose $m \in \N$ and $S \sim \N_m$.
It follows from Set Equivalence behaves like Equivalence Relation that $\N_n \sim \N_m$.
Thus by Equality of Natural Numbers, $n = m$. 
Therefore the cardinality of a finite set is well-defined.
== Sources ==
* : $\S 2.4$: Corollary $2.19.1$
* : $\S 3.7$. Similar sets
* : $1$: Set Theory and Logic: $\S 6$: Finite Sets: Corollary $6.5$
Category:Set Theory
Category:Cardinality