nyuuzyou/wikis huggingface dataset:
Cardinality of Reduced Residue System

== Theorem ==
Let $n \ge 2$.
Let $\Z'_n$ be the reduced residue system modulo $n$.
Then:
:$\card {\Z'_n} = \map \phi n$
where $\map \phi n$ is the Euler phi function.
== Proof ==
Recall the definition of $\Z'_n$:
:$\Z'_n = \set {\eqclass k n \in \Z_n: k \perp n}$
and the definition of $\map \phi n$:
:$\map \phi n = \card {\set {k: 1 \le k \le n, k \perp n} }$
The result follows from Integer is Congruent to Integer less than Modulus.
== Sources ==
* : $\text {4-2}$ Residue Systems: Theorem $\text {4-5}$
Category:Reduced Residue Systems
Category:Euler Phi Function
Cardinality of Set Difference

== Theorem ==
Let $S$ and $T$ be sets such that $T$ is finite.
Then:
:$\card {S \setminus T} = \card S - \card {S \cap T}$
where $\card S$ denotes the cardinality of $S$.
== Proof ==
From Intersection is Subset:
:$S \cap T \subseteq S$
:$S \cap T \subseteq T$
From Subset of Finite Set is Finite:
:$S \cap T$ is finite.
We have:
Category:Set Difference
Category:Cardinality
Cardinality of Set Difference with Subset

== Theorem ==
Let $S$ and $T$ be sets such that $T$ is finite.
Let $T \subseteq S$.
Then:
:$\card {S \setminus T} = \card S - \card T$
where $\card S$ denotes the cardinality of $S$.
== Proof ==
From Set Difference with Superset is Empty Set:
:$T \subseteq S \iff T \setminus S = \O$
From Set Difference and Intersection form Partition:
:$S = \paren {S \setminus T} \cup T$
Thus from Cardinality of Set Union:
:$\card S = \card T + \card {S \setminus T} - \card {T \cap \paren {S \setminus T} }$
But from Set Difference Intersection with Second Set is Empty Set:
:$T \cap \paren {S \setminus T} = 0$
Hence the result.
== Sources ==
* : $\S 1.6$. Difference and complement: Example $20$
Category:Set Difference
Category:Cardinality
Cardinality of Set Union

== Theorem ==
=== Union of 2 Sets ===
=== Union of 3 Sets ===
=== General Case ===
=== Corollary ===
== Examples ==
== Also see ==
* Inclusion-Exclusion Principle
== Sources ==
* : $\S 1$. Sets; inclusion; intersection; union; complementation; number systems: Exercise $8$
Category:Set Union
Category:Combinatorics
Category:Cardinality
Category:Cardinality of Set Union
Cardinality of Set Union/2 Sets

== Theorem ==
Let $S_1$ and $S_2$ be finite sets.
Then:
:$\card {S_1 \cup S_2} = \card {S_1} + \card {S_2} - \card {S_1 \cap S_2}$
== Proof ==
We have that Cardinality is Additive Function.
From Additive Function is Strongly Additive:
:$\card {S_1 \cup S_2} + \card {S_1 \cap S_2} = \card {S_1} + \card {S_2}$
from which the result follows.
== Sources ==
* : $\S 1.4$. Union: Example $16$
* : $\S 1$. Sets; inclusion; intersection; union; complementation; number systems: Exercise $8$
* : Chapter $\text {III}$: The Natural Numbers: $\S 19$: Combinatorial Analysis: Exercise $19.1$
* : Chapter $1$: Mappings: $\S 15 \beta$
* : Chapter $1$: Sets and Logic: Exercise $8 \ \text{(b)}$
* : Chapter $1$: Sets and mappings: $\S 1.2$: Sets: Exercise $3$
* 
Category:Cardinality of Set Union
Cardinality of Set Union/3 Sets

== Theorem ==
Let $S_1$, $S_2$ and $S_3$ be finite sets.
Then:
 
== Proof ==
This is a specific example of Cardinality of Set Union: General Case.
== Sources ==
* : $\S 1$. Sets; inclusion; intersection; union; complementation; number systems: Exercise $8$
* 
Category:Cardinality of Set Union
Cardinality of Set Union/Corollary

== Theorem ==
Let $S_1, S_2, \ldots, S_n$ be finite sets which are pairwise disjoint.
Then:
:$\ds \card {\bigcup_{i \mathop = 1}^n S_i} = \sum_{i \mathop = 1}^n \card {S_i}$
Specifically:
:$\card {S_1 \cup S_2} = \card {S_1} + \card {S_2}$
== Proof ==
As $S_1, S_2, \ldots, S_n$ are pairwise disjoint, their intersections are all empty.
The Cardinality of Set Union holds, but from Cardinality of Empty Set, all the terms apart from the first vanish.
== Sources ==
* : $\S 13$: Arithmetic
* : Chapter $1$: Sets and Logic: Exercise $8 \ \text{(a)}$
* : Chapter $1$: Sets and mappings: $\S 1.2$: Sets: Exercise $3$
Category:Cardinality of Set Union
Cardinality of Set Union/Examples/3 Arbitrary Sets

== Example of Use of Cardinality of Set Union ==
Let $A_1, A_2, A_3$ be finite sets.
Let:
Then:
:$26 \le \card {A_1 \cup A_2 \cup A_3} \le 28$
== Proof ==
We have that:
and:
Then:
But as $\card {A_1 \setminus A_2} = 2$, we have that:
:$\card {\paren {A_1 \cap A_3} \setminus A_2} \le 2$
and so:
:$11 \le \card {\paren {A_1 \cup A_3} \setminus A_2} \le 13$
and so:
:$11 + \card {A_2} \le \card {\paren {A_1 \cup A_3} \setminus A_2} + \card {A_2} \le 13 + \card {A_2}$
We have that:
:$A_1 \cup A_2 \cup A_3 = \paren {\paren {A_1 \cup A_3} \setminus A_2} + \cup A_2$
As $\card {A_2} = 15$ the result follows.
== Sources ==
* : Chapter $1$. Sets: Exercise $5$
Category:Examples of Use of Cardinality of Set Union
Cardinality of Set Union/Examples/Examination Candidates

== Example of Use of Cardinality of Set Union ==
In a particular examination, there were $3$ questions.
All candidates attempted at least one of the questions.
:$40$ candidates attempted question $1$.
:$47$ candidates attempted question $2$.
:$31$ candidates attempted question $3$.
Also, it was apparent that:
:$9$ candidates attempted at least questions $1$ and $2$.
:$15$ candidates attempted at least questions $1$ and $3$.
:$11$ candidates attempted at least questions $2$ and $3$.
and:
:exactly $6$ candidates attempted all $3$ questions.
It follows that $89$ candidates sat the examination in total.
== Proof ==
Let:
:$S_1$ denote the set of candidates who attempted question $1$.
:$S_2$ denote the set of candidates who attempted question $2$.
:$S_3$ denote the set of candidates who attempted question $3$.
The number of candidates $N$ who sat the examination in total is therefore:
:$N = S_1 \cup S_2 \cup S_3$
From Cardinality of Set Union: 3 Sets:
 
From the question:
Hence:
 
== Sources ==
* : $\S 1$. Sets; inclusion; intersection; union; complementation; number systems: Exercise $9$
Category:Examples of Use of Cardinality of Set Union
Cardinality of Set Union/Examples/Student Subjects

== Example of Use of Cardinality of Set Union ==
In a particular group of $75$ students, all studied at least one of the subjects mathematics, physics and chemistry.
All candidates attempted at least one of the questions.
:$40$ students studied mathematics.
:$60$ students studied physics.
:$25$ students studied chemistry.
Also:
:exactly $5$ students studied all $3$ subjects.
It follows that:
==== Mathematics and Physics ====
==== Physics and Chemstry ====
==== Mathematics and Chemistry ====
== Sources ==
* : $\S 1$. Sets; inclusion; intersection; union; complementation; number systems: Exercise $10$
Category:Examples of Use of Cardinality of Set Union
Cardinality of Set Union/Examples/Student Subjects/Mathematics and Chemistry

== Example of Use of Cardinality of Set Union ==
In a particular group of $75$ students, all studied at least one of the subjects mathematics, physics and chemistry.
All candidates attempted at least one of the questions.
:$40$ students studied mathematics.
:$60$ students studied physics.
:$25$ students studied chemistry.
Also:
:exactly $5$ students studied all $3$ subjects.
It follows that:
:no more than $20$ students studied both mathematics and chemistry.
== Proof ==
Let:
:$S_1$ denote the set of students who studied mathematics.
:$S_2$ denote the set of students who studied physics.
:$S_3$ denote the set of students who studied chemistry.
Knowledge of the total number of students gives us:
:$S_1 \cup S_2 \cup S_3 = 75$
Let $N$ denote the number of students $N$ who studied both mathematics and chemistry:
:$N = S_1 \cap S_3$
From the question:
First we calculate how many students took just mathematics or chemistry, but who did not take physics.
We have
So only $15$ students did not take physics.
Thus no more than $15$ students can have taken both mathematics and chemistry, without taking physics.
However, we are also told that $5$ students took all $3$ courses.
So, in addition to the maximum $15$ who took mathematics and chemistry, without taking physics, this takes the total to a maximum of $20$ students all told who took both mathematics and chemistry.
== Sources ==
* : $\S 1$. Sets; inclusion; intersection; union; complementation; number systems: Exercise $10 \ \text {(c)}$
Category:Examples of Use of Cardinality of Set Union
Cardinality of Set Union/Examples/Student Subjects/Mathematics and Physics

== Example of Use of Cardinality of Set Union ==
In a particular group of $75$ students, all studied at least one of the subjects mathematics, physics and chemistry.
All candidates attempted at least one of the questions.
:$40$ students studied mathematics.
:$60$ students studied physics.
:$25$ students studied chemistry.
It follows that:
:at least $25$ students studied both mathematics and physics.
== Proof ==
Let:
:$S_1$ denote the set of students who studied mathematics.
:$S_2$ denote the set of students who studied physics.
:$S_3$ denote the set of students who studied chemistry.
Knowledge of the total number of students gives us:
:$S_1 \cup S_2 \cup S_3 = 75$
Let $N$ denote the number of students $N$ who studied both mathematics and physics:
:$N = S_1 \cap S_2$
From the question:
The number of students $\card {S_1 \cup S_2}$ who studied either mathematics or physics is not more than $75$, the total number of students.
We have therefore:
 
== Sources ==
* : $\S 1$. Sets; inclusion; intersection; union; complementation; number systems: Exercise $10 \ \text {(a)}$
Category:Examples of Use of Cardinality of Set Union
Cardinality of Set Union/Examples/Student Subjects/Physics and Chemstry

== Example of Use of Cardinality of Set Union ==
In a particular group of $75$ students, all studied at least one of the subjects mathematics, physics and chemistry.
All candidates attempted at least one of the questions.
:$40$ students studied mathematics.
:$60$ students studied physics.
:$25$ students studied chemistry.
It follows that:
:at least $10$ students studied both physics and chemistry.
== Proof ==
Let:
:$S_1$ denote the set of students who studied mathematics.
:$S_2$ denote the set of students who studied physics.
:$S_3$ denote the set of students who studied chemistry.
Knowledge of the total number of students gives us:
:$S_1 \cup S_2 \cup S_3 = 75$
Let $N$ denote the number of students $N$ who studied both physics and chemistry:
:$N = S_2 \cap S_3$
From the question:
The number of students $\card {S_2 \cup S_3}$ who studied either physics or chemistry is not more than $75$, the total number of students.
We have therefore:
 
== Sources ==
* : $\S 1$. Sets; inclusion; intersection; union; complementation; number systems: Exercise $10 \ \text {(b)}$
Category:Examples of Use of Cardinality of Set Union
Cardinality of Set Union/General Case

== Theorem ==
Let $\sequence {S_n}_{n \mathop \in \N}$ be a sequence of sets.
Then:
 
== Proof ==
By Cardinality is Additive Function, we can apply the Inclusion-Exclusion Principle:
If $f: \SS \to \R$ is an additive function, then:
 
== Sources ==
* : Chapter $1$. Sets: Exercise $4$
Category:Cardinality of Set Union
Cardinality of Set is Finite iff Set is Finite

== Theorem ==
Let $A$ be a set.
:$\card A$ is finite
:
:$A$ is finite
where $\card A$ denotes the cardinality of $A$.
== Proof ==
Definition of cardinal:
:$(1): \quad \card A \sim A$
:$\card A$ is finite
:
:$\exists n \in \N: \card A \sim \N_n$ by definition of finite set
:
:$\exists n \in \N: A \sim \N_n$ by $(1)$ and Set Equivalence behaves like Equivalence Relation
:
:$A$ is finite by definition of finite set.
== Sources ==
* 
Category:Cardinals
Cardinality of Set is Topological Property

== Theorem ==
Let $T = \struct {S, \tau}$ be a topological space.
The cardinality of $S$ is a topological property of $T$.
== Proof ==
Let $T_1 = \struct {S_1, \tau_1}$ and $T_2 = \struct {S_2, \tau_2}$ be topological spaces.
Let $T_1$ and $T_2$ be homeomorphic.
Then by definition there exists a homeomorphism $f: T_1 \to T_2$.
Hence by definition $f$ is a bijection.
Hence by definition $S$ and $T$ are equjivalent.
That is, they have the same cardinality.
Thus cardinality is preserved by homeomorphism.
Hence the result by definition of topological property.
== Examples ==
Category:Examples of Topological Properties
Cardinality of Set is Topological Property/Examples/Set with 7 Elements

== Examples of Use of Cardinality of Set is Topological Property ==
Let $P$ be the property defined as:
:$\map P M := $ The set $M$ contains $7$ elements.
Then $P$ is a topological property.
== Sources ==
* : $3$: Continuity generalized: topological spaces: $3.6$: Homeomorphisms: Examples $3.6.4$
Category:Examples of Topological Properties
Cardinality of Set less than Cardinality of Power Set

== Theorem ==
Let $X$ be a set.
Then:
:$\card X < \card {\powerset X}$
where
:$\card X$ denotes the cardinality of $X$,
:$\powerset X$ denotes the power set of $X$.
== Proof ==
By No Bijection from Set to its Power Set:
: there exist no bijections $X \to \powerset X$
Then by definition of set equivalence:
:$X \not\sim \powerset X$
Hence by definition of cardinality:
:$(1): \quad \card X \ne \card {\powerset X}$
By Cardinality of Set of Singletons:
:$(2): \quad \card {\set {\set {x}: x \in X} } = \card X$
By definition of subset:
:$\forall x \in X: \set {x} \subseteq X$
Then by definition of power set:
:$\forall x \in X: \set {x} \in \powerset X$
Hence by definition of subset:
:$\set {\set {x}: x \in X} \subseteq \powerset X$
Then by Subset implies Cardinal Inequality and $(2)$:
:$\card X \le \card {\powerset X}$
Thus by $(1)$:
:$\card X < \card {\powerset X}$
== Sources ==
* 
Category:Cardinals
Category:Power Set
Category:Cardinality
Cardinality of Set of All Mappings

== Theorem ==
Let $S$ and $T$ be sets.
The cardinality of the set of all mappings from $S$ to $T$ (that is, the total number of mappings from $S$ to $T$) is:
:$\card {T^S} = \card T^{\card S}$
== Proof for Finite Sets ==
== Proof for Infinite Sets ==
== Examples ==
== Comment ==
The question of whether to define $0^0 = 0$ or $0^0 = 1$ keeps students awake arguing for hours.
Here's another argument, in case you're not convinced, for defining $0^0 = 1$ as opposed to $0^0 = 0$ - another result kept nice and neat.
Category:Combinatorics
Category:Mapping Theory
Category:Cardinality
Category:Cardinality of Set of All Mappings
Cardinality of Set of All Mappings/Examples

== Examples of Cardinality of Set of All Mappings ==
=== $2$ Elements to $2$ Elements ===
=== $2$ Elements to $3$ Elements ===
=== $3$ Elements to $2$ Elements ===
=== Set of Cardinality $4$ to Itself ===
Category:Cardinality of Set of All Mappings
Cardinality of Set of All Mappings/Examples/2 Elements to 2 Elements

== Example of Cardinality of Set of All Mappings ==
Let $X = \set {a, b}$.
Let $Y = \set {u, v}$.
Then the mappings from $X$ to $Y$ are:
$f_1$ and $f_4$ are bijections.
$f_2$ and $f_3$ are neither surjections nor injections.
== Sources ==
* : Chapter $2$: Maps and relations on sets: Example $2.6$
Category:Cardinality of Set of All Mappings
Cardinality of Set of All Mappings/Examples/2 Elements to 3 Elements

== Example of Cardinality of Set of All Mappings ==
Let $S = \set {1, 2}$.
Let $T = \set {a, b, c}$.
Then the mappings from $S$ to $T$ in two-row notation are:
:$\dbinom {1 \ 2} {a \ a}, \dbinom {1 \ 2} {a \ b}, \dbinom {1 \ 2} {a \ c}, \dbinom {1 \ 2} {b \ a}, \dbinom {1 \ 2} {b \ b}, \dbinom {1 \ 2} {b \ c}, \dbinom {1 \ 2} {c \ a}, \dbinom {1 \ 2} {c \ b}, \dbinom {1 \ 2} {c \ c}$
a total of $3^2 = 9$.
All but the first, fifth and last are injections.
None are surjections.
== Sources ==
* : Chapter $2$: Maps and relations on sets: Exercise $1$
Category:Cardinality of Set of All Mappings
Cardinality of Set of All Mappings/Examples/3 Elements to 2 Elements

== Example of Cardinality of Set of All Mappings ==
Let $S = \set {1, 2, 3}$.
Let $T = \set {a, b}$.
Then the mappings from $S$ to $T$ in two-row notation are:
:$\dbinom {1 \ 2 \ 3} {a \ a \ a}, \dbinom {1 \ 2 \ 3} {a \ a \ b}, \dbinom {1 \ 2 \ 3} {a \ b \ a}, \dbinom {1 \ 2 \ 3} {a \ b \ b}, \dbinom {1 \ 2 \ 3} {b \ a \ a}, \dbinom {1 \ 2 \ 3} {b \ a \ b}, \dbinom {1 \ 2 \ 3} {b \ b \ a}, \dbinom {1 \ 2 \ 3} {b \ b \ b}$
a total of $2^3 = 8$.
All but the first and last are surjections.
None are injections.
== Sources ==
* : $\S 3.2$. Equality of mappings
* : $\S 3.3$. Injective, surjective, bijective; inverse mappings: Example $47$
* : Chapter $2$: Maps and relations on sets: Exercise $1$
Category:Cardinality of Set of All Mappings
Cardinality of Set of All Mappings/Examples/Set of Cardinality 4

== Example of Cardinality of Set of All Mappings ==
Let $S$ be a set whose cardinality is $4$:
:$\card S = 4$
Then there are $256$ mappings from $S$ to itself.
== Proof ==
Let $T$ be the set of mappings from $S$ to itself.
From Cardinality of Set of All Mappings:
:$\card T = \card S^\card S = 4^4 = 256$
The result follows by Examples of Factorials.
== Sources ==
* : Chapter $1$: Sets and mappings: $\S 1.3$: Mappings: Exercise $1 \ \text {(i)}$
Category:Cardinality of Set of All Mappings
Cardinality of Set of All Mappings/Finite Sets

== Theorem ==
Let $S$ and $T$ be finite sets.
The cardinality of the set of all mappings from $S$ to $T$ (that is, the total number of mappings from $S$ to $T$) is:
:$\card {T^S} = \card T^{\card S}$
== Proof ==
Let $\card S = n$ and $\card T = m$.
First suppose that $n = 0$, that is, that $S = \O$.
From Cardinality of Set of All Mappings from Empty Set:
:$\card {T^\O} = 1 = m^0$
and the result is seen to hold for $n = 0$.
Next, suppose that $m = 0$, that is, that $T = \O$.
From Cardinality of Set of All Mappings to Empty Set:
:$\card {\O^S} = \begin {cases}
1 & : S = \O \\ 
0 & : S \ne \O
\end {cases}$
So if $n > 0$:
:$\card {\O^S} = 0 = 0^n$
and if $n = 0$:
:$\card {T^S} = 1 = 0^0 = m^n$
and the result holds.
This fits in with the preferred definition of the value of $0^0$.
Finally, suppose $m > 0$ and $n > 0$.
Let $\sigma: \N_n \to S$ and $\tau: T \to \N_n$ be bijections.
Then the mapping $\Phi: T^S \to \paren {\N_m}^{\paren {\N_n} }$ defined as:
:$\forall f \in T^S: \map \Phi f = \tau \circ f \circ \sigma$
(where $\paren {\N_m}^{\paren {\N_n} }$ is the set of all mappings from $\N_n$ to $\N_m$) is also a bijection.
So we need only consider the case where $S = \N_n$ and $T = \N_m$.
Let $m \in \N_{>0}$.
For each $n \in \N$, let $\Bbb T \paren {n, m}$ be the set of all mappings from $\N_n$ to $\N_m$.
Let:
:$\Bbb S = \set {n \in \N: \card {\Bbb T \tuple {n, m} } = m^n}$
We have seen that $0 \in \Bbb S$.
Let $n \in \Bbb S$.
Let $\rho: \Bbb T \tuple {n + 1, m} \to \Bbb T \paren {n, m}$ defined by:
:$\forall f \in \Bbb T \tuple {n + 1, m}: \rho \paren f =$ the restriction of $f$ to $\N_n$
Given that $g \in \Bbb T \tuple {n, m}$, and $k \in \N_m$, let $g_k: \N_{n + 1} \to \N_m$ be defined by:
:$\forall x \in \N_{n + 1}: \map {g_k} x = \begin {cases}
\map g x & : x \in \N_n \\
k & : x = n
\end {cases}$
Then:
:$\rho^{-1} \sqbrk {\set g} = \set {g_0, \ldots, g_{m - 1} }$
Thus $\rho^{-1} \sqbrk {\set g}$ has $m$ elements.
So clearly:
:$\set {\rho^{-1} \sqbrk {\set g}: g \in \Bbb T \tuple {n, m} }$
is a partition of $\Bbb T \tuple {n + 1, m}$.
Hence, as $n \in \Bbb S$, the set $\Bbb T \tuple {n + 1, m}$ has $m \cdot m^n = m^{n + 1}$ elements by Number of Elements in Partition.
Thus $n + 1 \in \Bbb S$.
By the Principle of Mathematical Induction:
:$\Bbb S = \N$
and the proof is complete.
== Sources ==
* : $\S 13$: Arithmetic
* : $\S 3.2$. Equality of mappings
* : Chapter $\text I$: Algebraic Structures: $\S 1$: The Language of Set Theory: Exercise $1.9 \ \text{(a)}$
* : Chapter $\text {III}$: The Natural Numbers: $\S 19$: Combinatorial Analysis: Theorem $19.4$
* : Chapter $1$: Theory of Sets: $\S 9$: Inverse Functions, Extensions, and Restrictions: Exercise $4$
* : Chapter $4$: Mappings: Exercise $4 \ \text{(i)}$
* : Chapter $1$: Sets and mappings: Further exercises: $2$
* : Appendix $\text{A}.10$: Finite Sequences
Category:Cardinality of Set of All Mappings
Category:Finite Sets
Cardinality of Set of All Mappings/Infinite Sets

== Theorem ==
Let $S$ and $T$ be sets such that either $S$ or $T$ is infinite.
The cardinality of the set of all mappings from $S$ to $T$ (that is, the total number of mappings from $S$ to $T$) is:
:$\card {T^S} = \card T^{\card S}$
== Proof ==
Category:Cardinality of Set of All Mappings
Category:Infinite Sets
Cardinality of Set of All Mappings from Empty Set

== Theorem ==
Let $T$ be a set.
Let $T^\O$ denote the set of all mappings from $\O$ to $S$.
Then:
:$\card {T^\O} = 1$
where $\card {T^\O}$ denotes the cardinality of $\O^S$.
== Proof ==
The only element of $T^\O$ is the null relation:
:$\O \times T$
From Null Relation is Mapping iff Domain is Empty Set, $\O \times T$ is a mapping from $\O$ to $T$.
The result follows from Empty Mapping is Unique.
That is:
:$\card {T^\O} = 1$
== Sources ==
* : $\S 8$: Functions: Exercise $\text{(i)}$
* : Chapter $\text I$: Algebraic Structures: $\S 1$: The Language of Set Theory: Exercise $1.9 \ \text{(b)}$
Category:Combinatorics
Category:Mapping Theory
Cardinality of Set of All Mappings to Empty Set

== Theorem ==
Let $S$ be a set.
Let $\O^S$ be the set of all mappings from $S$ to $\O$.
Then:
:$\card {\O^S} = \begin{cases}
1 & : S = \O \\ 
0 & : S \ne \O
\end{cases}$
where $\card {\O^S}$ denotes the cardinality of $\O^S$.
== Proof ==
From Null Relation is Mapping iff Domain is Empty Set, the null relation:
:$\RR = \O \subseteq S \times T$
is not a mapping unless $S = \O$.
So if $S \ne \O$:
:$\card {\O^S} = 0$
If $S = \O$:
:$\card {\O^S} = 1$
Hence the result.
== Sources ==
* : $\S 8$: Functions: Exercise $\text{(ii)}$
* : Chapter $\text I$: Algebraic Structures: $\S 1$: The Language of Set Theory: Exercise $1.9 \ \text{(c), (d)}$
Category:Combinatorics
Category:Mapping Theory
Cardinality of Set of Bijections

== Theorem ==
Let $S$ and $T$ be finite sets with the same cardinality:
:$\size S = \size T = n$
Then there are $n!$ bijections from $S$ to $T$.
== Proof ==
Follows directly from Cardinality of Set of Injections and Equivalence of Mappings between Finite Sets of Same Cardinality.
== Examples ==
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 19$: Combinatorial Analysis: Theorem $19.7$
Category:Combinatorics
Category:Bijections
Category:Cardinality
Category:Cardinality of Set of Bijections
Cardinality of Set of Bijections/Examples/Set of Cardinality 4

== Examples of Use of Cardinality of Set of Bijections ==
Let $S$ be a set whose cardinality is $4$:
:$\card S = 4$
Then there are $24$ bijections from $S$ to itself.
== Proof ==
Let $T$ be the set of bijections from $S$ to itself.
From Cardinality of Set of Bijections:
:$\card T = \paren {\card S}!$
The result follows by Examples of Factorials.
== Sources ==
* : Chapter $1$: Sets and mappings: $\S 1.3$: Mappings: Exercise $1 \ \text {(ii)}$
Category:Cardinality of Set of Bijections
Cardinality of Set of Characteristic Functions on Finite Set

== Theorem ==
Let $I$ be a finite set.
The number of characteristic functions on $I$ is:
:$2^{\card I}$ 
where $\card I$ denotes the cardinality of $I$.
== Proof ==
Let $A = \set {0, 1}$.
A characteristic function of $I$ is a mapping from $I$ to $A$.
Hence the set of characteristic functions on $I$ is the indexed Cartesian space $A_I$:
:$A^I = \ds \prod_{i \mathop \in I} A := \set {f: \paren {f: I \to A} \land \paren {\forall i \in I: \paren {\map f i \in A} } }$
Hence from Cardinality of Set of All Mappings:
:$\card {A^I} = 2^{\card I}$
== Sources ==
* : Chapter $1$: Theory of Sets: $\S 10$: Arbitrary Products: Exercise $1$
Category:Characteristic Functions
Category:Indexed Families