nyuuzyou/wikis huggingface dataset:
Cardinality of Set of Combinations with Repetition

== Theorem ==
Let $S$ be a finite set with $n$ elements
The number of $k$-combinations of $S$ with repetition is given by:
:$N = \dbinom {n + k - 1} k$
== Proof ==
Let the elements of $S$ be (totally) ordered in some way, by assigning an index to each element.
Thus let $S = \left\{ {a_1, a_2, a_3, \ldots, a_n}\right\}$.
Thus each $k$-combination of $S$ with repetition can be expressed as:
:$\left\{ {\left\{ {a_{r_1}, a_{r_1}, \ldots, a_{r_k} }\right\} }\right\}$
where:
:$r_1, r_2, \ldots, r_k$ are all elements of $\left\{ {1, 2, \ldots, n}\right\}$
and such that:
:$r_1 \le r_2 \le \cdots \le r_k$
Hence the problem reduces to the number of integer solutions $\left({r_1, r_2, \ldots, r_k}\right)$ such that $1 \le r_1 \le r_2 \le \cdots \le r_k \le n$.
This is the same as the number of solutions to:
:$0 < r_1 < r_2 + 1 < \cdots < r_k + k - 1 < n + k$
which is the same as the number of solutions to:
:$0 < s_1 < s_2 < \cdots < s_k < n + k$
which is the number of ways to choose $k$ elements from $n + k - 1$.
This is the same as the number of subsets as a set with $n + k - 1$ elements.
From Cardinality of Set of Subsets:
:$N = \dbinom {n + k - 1} k$
== Sources ==
* 
* 
* : $\S 1.2.6$: Binomial Coefficients: Exercise $60$
Category:Combinations with Repetition
Cardinality of Set of Endorelations

== Theorem ==
Let $S$ be a finite set.
Let $\card S = n$, where $\card {\, \cdot \,}$ denotes cardinality (that is, the number of elements).
Let $\RR$ denote the set of all endorelations on $S$.
Then the cardinality of $\RR$ is given by:
:$\card \RR = 2^{\paren {n^2} }$
== Proof ==
By definition, an endorelation on $S$ is a relation from $S$ to itself.
From Cardinality of Set of Relations, the number of relations from $S$ to $T$ is equal to $2^{\card S \times \card T}$.
In this case $S = T$ and the result follows.
Category:Combinatorics
Category:Cardinality
Category:Endorelations
Cardinality of Set of Induced Equivalence Classes of Injection

== Theorem ==
Let $f: S \to T$ be a mapping.
Let $\RR_f \subseteq S \times S$ be the relation induced by $f$:
:$\tuple {s_1, s_2} \in \RR_f \iff \map f {s_1} = \map f {s_2}$
Let $f$ be an injection.
Then there are $\card S$ different $\RR_f$-classes.
== Proof ==
From Cardinality of Image of Injection we have that $\card {f \sqbrk S} = \card S$.
From the nature of an injection, for all $s \in S$, the $\RR_f$-class of $s$ is a singleton.
Hence the result.
== Sources ==
* : Chapter $4$: Mappings: Exercise $10 \ \text{(i) (a)}$
Category:Injections
Category:Equivalence Relations
Cardinality of Set of Induced Equivalence Classes of Surjection

== Theorem ==
Let $f: S \to T$ be a mapping.
Let $\RR_f \subseteq S \times S$ be the relation induced by $f$:
:$\tuple {s_1, s_2} \in \RR_f \iff \map f {s_1} = \map f {s_2}$
Let $f$ be a surjection.
Then there are $\card T$ different $\RR_f$-classes.
== Proof ==
From the definition of a surjection:
:$\forall t \in T: \exists s \in S: \map f s = t$
Thus there are as many $\RR_f$-classes of $f$ as there are elements of $T$.
Hence the result.
== Sources ==
* : Chapter $4$: Mappings: Exercise $10 \ \text{(i) (b)}$
Category:Surjections
Category:Equivalence Relations
Cardinality of Set of Injections

== Theorem ==
Let $S$ and $T$ be finite sets.
The number of injections from $S$ to $T$, where $\card S = m, \card T = n$ is often denoted ${}^m P_n$, and is:
:${}^m P_n = \begin {cases} \dfrac {n!} {\paren {n - m}!} & : m \le n \\ 0 & : m > n \end {cases}$
=== Corollary ===
== Informal Proof ==
== Formal Proof ==
== Examples ==
== Sources ==
* : Chapter $3$. Mappings: Exercise $1$
* : Chapter $\text I$: Algebraic Structures: $\S 5$: Composites and Inverses of Functions: Exercise $5.5$
* : Chapter $4$: Mappings: Exercise $4 \ \text{(ii) (a)}$
Category:Cardinality of Set of Injections
Category:Injections
Category:Combinatorics
Category:Counting Arguments
Category:Cardinality
Cardinality of Set of Injections/Corollary

== Corollary to Cardinality of Set of Injections ==
Let $S$ and $T$ be sets.
Let $f: S \to T$ be a mapping.
Then $f$ cannot be an injection if:
:$\card S > \card T$
where $\card S$ denotes the cardinality of $S$.
== Proof ==
From Cardinality of Set of Injections:
:the number of injections from $S$ to $T$, where $\card S > \card T$, is zero.
Hence the result.
== Sources ==
* : Chapter $4$: Mappings: Exercise $4 \ \text{(ii) (b)}$
* : Chapter $2$: 'And you do addition?': $\S 2.1$: Functions: Ponderable $2.1.5$
Category:Injections
Category:Combinatorics
Category:Cardinality of Set of Injections
Cardinality of Set of Injections/Examples/Cardinality 2 to Cardinality 3

== Examples of Cardinality of Set of Injections ==
Let $A = \set {a, b}$.
Let $B = \set {1, 2, 3}$.
Then the set of injections from $A$ to $B$, expressed in two-row notation, is:
:$\set {\dbinom {a \ b} {1 \ 2}, \dbinom {a \ b} {1 \ 3}, \dbinom {a \ b} {2 \ 1}, \dbinom {a \ b} {2 \ 3}, \dbinom {a \ b} {3 \ 1}, \dbinom {a \ b} {3 \ 2} }$
thus demonstrating that there are $\dfrac {3!} {\paren {3 - 2}!} = \dfrac {3!} {1!} = \dfrac 6 1 = 6$ injections from $A$ to $B$.
== Proof ==
* : Chapter $3$. Mappings: Exercise $1$
Category:Cardinality of Set of Injections
Cardinality of Set of Injections/Informal Proof

== Theorem ==
== Informal Proof ==
This is the same question as determining how many permutations there are of $m$ objects out of $n$.
Informally, the thinking goes like this.
We pick the elements of $S$ in any arbitrary order, and assign them in turn to an element of $T$.
The first element of $S$ can be mapped to any element of $T$, so there are $n$ options for the first element.
The second element of $S$, once we've mapped the first, can be mapped to any of the remaining $n-1$ elements of $T$, so there are $n-1$ options for that one.
And so on, to the $m$th element of $S$, which has $n - \paren {m - 1}$ possible elements in $T$ that it can be mapped to.
Each mapping is independent of the choices made for all the other mappings, so the total number of mappings from $S$ to $T$ is:
:$n \paren {n - 1} \paren {n - 2} \cdots \paren {n - m + 1} = \dfrac {n!} {\paren {n - m}!}$
== Sources ==
* : $\S 3.1$: Theorem $3.1$
Category:Cardinality of Set of Injections
Category:Counting Arguments
Cardinality of Set of Relations

== Theorem ==
Let $S$ and $T$ be finite sets.
Let $\card S = n$ and $\card T = m$, where $\card {\, \cdot \,}$ denotes cardinality (that is, the number of elements).
Let $\RR$ denote the set of all relations from $S$ to $T$.
Then the cardinality of $\RR$ is given by:
:$\card \RR = 2^{n m}$
== Proof ==
By definition, a relation from $S$ to $T$ is a subset of the cartesian product $S \times T$ of $S$ and $T$.
From Cardinality of Cartesian Product of Finite Sets, we have:
:$\card {S \times T} = n m$
The number of subsets of $S \times T$ is the cardinality of the power set $\powerset {S \times T}$ of $S \times T$.
From Cardinality of Power Set of Finite Set:
:$\card {\powerset {S \times T} } = 2^{\card {S \times T} } = 2^{n m}$
Hence the result.
Category:Combinatorics
Category:Cardinality
Category:Relations
Cardinality of Set of Residue Classes

== Theorem ==
Let $m \in \Z_{>0}$ be a (strictly) positive integer.
Let $\Z_m$ be the set of residue classes modulo $m$.
Then:
:$\card {Z_m} = m$
where $\card {\, \cdot \,}$ denotes cardinality.
== Proof ==
By definition of the set of residue classes modulo $m$, $Z_m$ is the quotient set of congruence modulo $m$:
:$\Z_m = \dfrac \Z {\RR_m}$
where $\RR_m$ is the congruence relation modulo $m$ on the set of all $a, b \in \Z$:
:$\RR_m = \set {\tuple {a, b} \in \Z \times \Z: \exists k \in \Z: a = b + k m}$
Thus by definition $\Z_m$ is the set of residue classes modulo $m$:
:$\Z_m = \set {\eqclass 0 m, \eqclass 1 m, \ldots, \eqclass {m - 1} m}$
Hence:
== Sources ==
* : Appendix $\text{A}.3$: Equivalence Relations: Problem Set $\text{A}.3$: $18$
* : $\S 18.3$: Congruence classes
* : Chapter $1$: Preliminaries: $1.5$ Relations: Equivalence Relations: Example $1.4$
* 
* 
Category:Residue Classes
Cardinality of Set of Restrictions of Mapping

== Theorem ==
Let $S$ and $T$ be sets.
Let $f: S \to T$ be a mapping.
Let the cardinality of $S$ be $n$.
Let $F$ be the set of restrictions of $f$ to a subset of $S$.
Then there are $2^n$ elements of $F$.
== Proof ==
Let $A \subseteq S$ be a subset of $S$.
Let $g: A \to T$ be the restriction of $f$ to $A$.
By definition of restriction of mapping:
:$\forall x \in A: \map g x = \map f x$
and hence there is one mapping $g: A \to T$ such that $g$ is a restriction of $f$.
Therefore for each subset of $S$ there exists a unique restriction of $f$ to that subset.
Therefore there are as many restriction of $f$ as there are subsets of $S$.
That is, by definition of power set, the same as the number of elements of the power set of $S$.
From Cardinality of Power Set of Finite Set, that is $2^n$.
== Sources ==
* : Chapter $1$: Theory of Sets: $\S 9$: Inverse Functions, Extensions, and Restrictions
Category:Restrictions
Cardinality of Set of Self-Mappings on Finite Set

== Theorem ==
Let $S$ be a finite set.
Let the cardinality of $S$ be $n$.
The cardinality of the set of all mappings from $S$ to itself (that is, the total number of self-maps on $S$) is:
:$\card {S^S} = n^n$
== Proof ==
This is a specific example of Cardinality of Set of All Mappings where $S = T$.
== Sources ==
* : Chapter $\text{I}$: Semi-Groups and Groups: $1$: Definition and examples of semigroups
Category:Cardinality of Set of All Mappings
Category:Finite Sets
Cardinality of Set of Singletons

== Theorem ==
Let $S$ be a set.
Let $T = \left\{ {\left\{{x}\right\}: x \in S}\right\}$ be the set of all singletons of elements of $S$.
Then:
:$\left\vert T \right\vert = \left\vert S \right\vert$
where $\left\vert S \right\vert$ denotes the cardinality of $S$.
== Proof ==
Define a mapping $f: S \to T$:
:$\forall x \in S: f \left({x}\right) = \left\{ {x}\right\}$
By Singleton Equality:
:$\forall x, y \in S: f \left({x}\right) = f \left({y}\right) \implies x = y$
Then, by definition, $f$ is an injection.
By the definition of set $T$:
:$\forall y \in T: \exists x \in S: y = f \left({x}\right)$
Then, by definition, $f$ is a surjection.
Hence, by definition, $f: S \to T$ is a bijection.
Thus, by definition, $S$ and $T$ are equivalent:
:$S \sim T$
Thus by definition of cardinality:
:$\left\vert T \right\vert = \left\vert S \right\vert$
== Sources ==
* 
* 
Category:Cardinals
Cardinality of Set of Strictly Increasing Mappings

== Theorem ==
Let $\struct {S, \preceq}$ and $\struct {T, \preccurlyeq}$ be tosets.
Let the cardinality of $S$ and $T$ be:
:$\card S = m, \card T = n$
Then the number of strictly increasing mappings from $S$ to $T$ is:
:$\dbinom n m = \dfrac {n!} {m! \ \paren {n - m}!}$.
where $\dbinom n m$ is a binomial coefficient.
== Proof ==
From:
:Mapping from Totally Ordered Set is Order Embedding iff Strictly Increasing
and:
:Strictly Monotone Mapping with Totally Ordered Domain is Injective
a strictly increasing mapping $\phi$ from $S$ to $T$ is an order isomorphism from $S$ to $\map \phi S$.
Let $\mathbb F$ be the set of all strictly increasing mappings from $S$ to $T$.
Let $\mathbb G$ be the set of all subsets of $T$ with $m$ elements.
By Unique Isomorphism between Equivalent Finite Totally Ordered Sets, the mapping $\Phi: \mathbb F \to \mathbb G$ defined as:
:$\forall \phi \in \mathbb F: \Phi: \phi \to \map \phi S$
is a bijection.
The result follows from Cardinality of Set of Subsets.
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 19$: Combinatorial Analysis: Theorem $19.11$
Category:Combinatorics
Cardinality of Set of Subsets

== Theorem ==
Let $S$ be a set such that $\card S = n$.
Let $m \le n$.
Then the number of subsets $T$ of $S$ such that $\card T = m$ is:
:$\dbinom n m = \dfrac {n!} {m! \paren {n - m}!}$
== Proof 1 ==
== Proof 2 ==
== Proof 3 ==
== Proof 4 ==
== Also denoted as ==
== Also presented as ==
== Examples ==
== Also see ==
* Definition:Binomial Coefficient
* Binomial Theorem
== Sources ==
* : Introduction $\S 1$: Operations on Sets
* : $\text I$. Algebra: Permutations and Combinations
* : Problems
* : $\S 2.3$. Partitions: Example $35$
* : Chapter $\text I$: Algebraic Structures: $\S 5$: Composites and Inverses of Functions: Exercise $5.4$
* : $\S 0.6$: Theorem $8: \ 3$
* : $35$
* : $35$
* 
* 
* 
Category:Combinations
Category:Combinatorics
Category:Cardinality of Set of Subsets
Cardinality of Set of Subsets/Also denoted as

== Theorem ==
The number of subsets of cardinality $m$ that can be taken from a set of cardinality $n$ can also be seen as:
:${}_n C_m$
:${}^n C_m$
:${C_n}^m$
In order to avoid any ambiguity, will tend to use $\dbinom n m$.
== Sources ==
* : $\text I$. Algebra: Permutations and Combinations
* : Problems
* 
Category:Cardinality of Set of Subsets
Cardinality of Set of Subsets/Also presented as

== Theorem ==
This result is also presented in the form:
:The number of combinations of $n$ objects taken $m$ at a time
or:
:The number of selections of $n$ objects taken $r$ at a time
or:
:The number of ways of selecting $m$ objects out of $n$
or:
:The number of ways of choosing $m$ objects from $n$ where order does not matter
or:
:The number of ways of choosing a set of $m$ elements from the $n$ elements of the set $S$
Such wording is insufficiently precise for .
== Sources ==
* : $\text I$. Algebra: Permutations and Combinations
* : Problems
* : $\S 2.3$. Partitions: Example $35$
* : $35$
* : $35$
* 
Category:Cardinality of Set of Subsets
Cardinality of Set of Subsets/Proof 1

== Theorem ==
== Proof ==
For each $X \subseteq \N_n$ and $Y \subseteq S$, let $\map B {X, Y}$ be the set of all bijections from $X$ onto $Y$.
Let $\Bbb S$ be the set of all subsets of $S$ with $m$ elements.
By Cardinality of Power Set of Finite Set and Cardinality of Subset of Finite Set, $\Bbb S$ is finite, so let $s = \card {\Bbb S}$.
Let $\beta: \map B {\N_n, S} \to \Bbb S$ be the mapping defined as:
:$\forall f \in \map B {\N_n, S}: \map \beta f = \map f {\N_m}$
For each $Y \in \Bbb S$, the mapping:
:$\Phi_Y: \map {\beta^{-1} } Y \to \map B {\N_m, Y} \times \map B {\N_n - \N_m, S - Y}$
defined as:
:$\map {\Phi_Y} f = \tuple {f_{\N_m}, f_{\N_n - \N_m} }$
is also (clearly) a bijection.
By Cardinality of Set of Bijections:
:$\card {\map B {\N_m, Y} } = m!$
and:
:$\card {\map B {\N_n - \N_m, S - Y} } = \paren {n - m}!$
So by Cardinality of Cartesian Product of Finite Sets:
:$\card {\map {\beta^{-1} } Y} = m! \paren {n - m}!$
It is clear that $\set {\map {\beta^{-1} } Y: Y \in \Bbb S}$ is a partition of $\map B {\N_n, S}$.
Therefore by Number of Elements in Partition:
:$\card {\map B {\N_n, S} } = m! \paren {n - m}! s$
Consequently, as $\card {\map B {\N_n, S} } = n!$ by Cardinality of Set of Bijections, it follows that:
:$m! \paren {n - m}! s = n!$
and the result follows.
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 19$: Combinatorial Analysis: Theorem $19.8$
Category:Cardinality of Set of Subsets
Cardinality of Set of Subsets/Proof 2

== Theorem ==
== Proof ==
Let $\dbinom n m$ denote the number of subsets of $m$ elements of $S$.
From Number of Permutations, the number of $m$-permutations of $S$ is:
:${}^m P_n = \dfrac {n!} {\paren {n - m}!}$
Consider the way ${}^m P_n$ can be calculated.
First one makes the selection of which $m$ elements of $S$ are to be arranged.
This number is $\dbinom n m$.
Then for each selection, the number of different arrangements of these is $m!$, from Number of Permutations.
So:
== Sources ==
* : $\text I$. Algebra: Permutations and Combinations: The value of ${}_n C_r$
* : Problems
* : $\text {3-1}$ Permutations and Combinations: Theorem $\text {3-2}$
* : $\S 1.2.6$: Binomial Coefficients
Category:Cardinality of Set of Subsets
Cardinality of Set of Subsets/Proof 3

== Theorem ==
== Proof ==
Let $\N_n$ denote the set $\set {1, 2, \ldots, n}$.
Let $\struct {S_n, \circ}$ denote the symmetric group on $\N_n$.
Let $r \in \N: 0 < r \le n$.
Let $B_r$ denote the set of all subsets of $\N_n$ of cardinality $r$:
:$B_r := \set {S \subseteq \N_n: \card S = r}$
Let $*$ be the mapping $*: S_n \times B_r \to B_r$ defined as:
:$\forall \pi \in S_n, \forall S \in B_r: \pi * B_r = \pi \sqbrk S$
where $\pi \sqbrk S$ denotes the image of $S$ under $\pi$.
From Group Action of Symmetric Group on Subset it is established that $*$ is a group action.
The stabilizer of any $U \in B_r$ is the set of permutations on $\N_n$ that fix $U$.
Let $U = \set {1, 2, \ldots, r}$.
So:
:$\tuple {a_1, a_2, \ldots, a_r}$ can be any one of the $r!$ permutations of $1, 2, \ldots, r$
:$\tuple {a_{r + 1}, a_{r + 2}, \ldots, _n}$ can be any one of the $\paren {n - r}!$ permutations of $r + 1, r + 2, \ldots, n$.
Thus:
:$\order {\Stab U} = r! \paren {n - r}!$
From Group Action of Symmetric Group on Subset is Transitive:
:$B_r = \Orb U$
and so:
:$\card {B_r} = \card {\Orb U}$
From the Orbit-Stabilizer Theorem:
:$\card {\Orb U} = \dfrac {\order {S_n} } {\order {\Stab U} } = \dfrac {n!} {r! \paren {n - r}!}$
But $\card {B_r}$ is the number of subsets of $\N_n$ of cardinality $r$.
Hence the result.
== Sources ==
* : $\S 6.5$. Orbits: Example $120$
Category:Cardinality of Set of Subsets
Cardinality of Set of Subsets/Proof 4

== Theorem ==
== Proof ==
The proof proceeds by induction.
For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:
:$\dbinom n m = \dfrac {n!} {m! \paren {n - m}!}$
=== Basis for the Induction ===
$\map P 1$ is the case:
Thus $\map P 1$ is seen to hold.
This is the basis for the induction.
=== Induction Hypothesis ===
Now it needs to be shown that, if $\map P k$ is true, where $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.
So this is the induction hypothesis:
:$\dbinom k m = \dfrac {k!} {m! \paren {k - m}!}$
from which it is to be shown that:
:$\dbinom {k + 1} m = \dfrac {\paren {k + 1}!} {m! \paren {k + 1 - m}!}$
=== Induction Step ===
This is the induction step:
The number of ways to choose $m$ elements from $k + 1$ elements is:
:the number of ways to choose $m$ elements elements from $k$ elements (deciding not to select the $k + 1$th element)
added to:
:the number of ways to choose $m - 1$ elements elements from $k$ elements (after having selected the $k + 1$th element for the $n$th selection)
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\forall n \in \Z_{>0}: \dbinom n m = \dfrac {n!} {m! \paren {n - m}!}$
== Sources ==
* : $\text {3-1}$ Permutations and Combinations: Exercise $4$
Category:Cardinality of Set of Subsets
Cardinality of Set of Surjections

== Theorem ==
Let $S$ and $T$ be finite sets.
Let $\card S = m, \card T = n$.
Let $C$ be the number of surjections from $S$ to $T$.
Then:
:$C = n! \ds {m \brace n}$
where $\ds {m \brace n}$ denotes a Stirling number of the second kind.
== Proof ==
Let $T$ be the codomain of a surjection $f$ from $S$ to $T$.
By the Quotient Theorem for Surjections, $f$ induces an equivalence $\RR_f$ on $T$:
:$f = r \circ q_{\RR_f}$
where:
:$\RR_f$ is the equivalence induced by $f$ on $T$
:$r: S / \RR_f \to T$ is a bijection from the quotient set $S / \RR_f$ to $T$
:$q_{\RR_f}: S \to S / \RR_f$ is the quotient mapping induced by $\RR_f$.
From the Fundamental Theorem on Equivalence Relations, $\RR_f$ induces a partition on $S$.
From Cardinality of Set of Induced Equivalence Classes of Surjection, $\RR_f$ has $m$ components.
From Number of Set Partitions by Number of Components, there are $\ds {m \brace n}$ different ways of performing such a partitioning.
From Cardinality of Set of Injections, there are $n!$ different bijections from $S / \RR_f \to T$.
The total number of surjections is then the product of these:
:$C = n! \ds {m \brace n}$
== Examples ==
Category:Surjections
Category:Combinatorics
Category:Counting Arguments
Category:Cardinality of Set of Surjections
Cardinality of Set of Surjections/Examples/m=n+1

== Example of Cardinality of Set of Surjections ==
Let $S$ and $T$ be finite sets.
Let $\card S = m, \card T = n$.
Let $C$ be the number of surjections from $S$ to $T$.
Let $m = n + 1$.
Then:
:$C = \dfrac {n \paren {n + 1}!} 2$
== Proof ==
From Cardinality of Set of Surjections:
:$C = n! \ds {n + 1 \brace n}$
where $\ds {n + 1 \brace n}$ denotes a Stirling number of the second kind.
== Sources ==
* : Chapter $4$: Mappings: Exercise $4 \ \text{(iii)}$
Category:Examples of Cardinality of Set of Surjections
Cardinality of Set of Surjections/Examples/m=n+2

== Example of Cardinality of Set of Surjections ==
Let $S$ and $T$ be finite sets.
Let $\card S = m, \card T = n$.
Let $C$ be the number of surjections from $S$ to $T$.
Let $m = n + 2$.
Then:
:$C = \dfrac {n \paren {3 n + 1} \paren {n + 2}!} {24}$
== Proof ==
From Cardinality of Set of Surjections:
:$C = n! \ds {n + 1 \brace n}$
where $\ds {n + 1 \brace n}$ denotes a Stirling number of the second kind.
== Sources ==
* : Chapter $4$: Mappings: Exercise $4 \ \text{(iii)}$
Category:Examples of Cardinality of Set of Surjections
Cardinality of Singleton

== Theorem ==
Let $A$ be a set.
Then $\card A = 1$ $\exists a: A = \set a$
where $\card A$ denotes the cardinality of $A$.
== Proof ==
=== Sufficient Condition ===
Assume that
:$\card A = 1$
By definition of cardinality of finite set:
:$A \sim \N_{< 1} = \set 0$
where $\sim$ denotes set equivalence.
By Set Equivalence behaves like Equivalence Relation:
:$\set 0 \sim A$
By definition of set equivalence there exists a bijection:
:$f: \set 0 \to A$
By definition of bijection:
:$f$ is s surjection.
Thus
=== Necessary Condition ===
Assume that:
:$\exists a: A = \set a$
Define a mapping $f: A \to \set 0$:
:$\map f a = 0$
It is easy to see by definition that
:$f$ is an injection and a surjection.
By definition
:$f$ is bijection.
By definition of set equivalence:
:$A \sim \set 0 = \N_{< 1}$
Thus by definition of cardinality of finite set:
:$\card A = 1$
== Sources ==
* 
Category:Cardinals
Category:Cardinality
Cardinality of Subset Relation on Power Set of Finite Set

== Theorem ==
Let $S$ be a set such that:
:$\card S = n$
where $\card S$ denotes the cardinality of $S$.
From Subset Relation on Power Set is Partial Ordering we have that $\struct {\powerset S, \subseteq}$ is an ordered set.
The cardinality of $\subseteq$ as a relation is $3^n$.
== Proof ==
Let $X \in \powerset S$.
Since $X \subseteq S$, it follows that:
:$X' \subseteq X \implies X' \in \powerset S$
because the Subset Relation is Transitive.
From Cardinality of Power Set of Finite Set, it follows that for any $X \in \powerset S$:
:$\set {X' \in \powerset S: X' \subseteq X}$
has $2^{\card X}$ elements.
Therefore, the cardinality of $\subseteq$ is given by:
:$\ds \sum_{X \mathop \subseteq S} 2^{\card X}$
Let us split the sum over $\card X$:
:$\ds \sum_{X \mathop \subseteq S} 2^{\card X} = \sum_{k \mathop = 0}^n \sum_{\substack {X \mathop \subseteq S \\ \card X \mathop = n}} 2^{\card X}$
It now follows from Cardinality of Set of Subsets that:
:$\ds \card \subseteq = \sum_{k \mathop = 0}^n \binom n k 2^k$
From Binomial Theorem for Integral Index:
:$\ds \sum_{k \mathop = 0}^n \binom n k 2^k = \paren {1 + 2}^n$
Hence:
:$\card \subseteq = 3^n$
== Sources ==
* : $\S 1$: Sets and Set Inclusion
Category:Set Theory
Cardinality of Subset of Finite Set

== Theorem ==
Let $A$ and $B$ be finite sets such that $A \subseteq B$.
Let
:$\card B = n$
where $\card {\, \cdot \,}$ denotes cardinality.
Then $\card A \le n$.
== Proof ==
Let $A \subseteq B$.
There are two cases:
$(1): \quad A \ne B$
In this case:
:$A \subsetneqq B$
and from Cardinality of Proper Subset of Finite Set:
:$\card A < n$
$(2): \quad A = B$
In this case:
:$\card A = \card B$
and so:
:$\card A = n$
In both cases:
:$\card A \le n$
Hence the result.
== Also see ==
* Subset of Finite Set is Finite
== Sources ==
* : Chapter $\text {III}$: The Natural Numbers: $\S 17$: Finite Sets: Theorem $17.5$
* : Chapter $1$: Preliminaries: $1.4$ Set Notation: Infinite sets
Category:Subsets
Category:Finite Sets
Category:Cardinality