avewright/proofwiki-math huggingface dataset:
Theorem: Non-Zero Integers are Cancellable for Multiplication

Every non-zero integer is cancellable for multiplication.
That is:
:$\forall x, y, z \in \Z, x \ne 0: x y = x z \iff y = z$

Proof:
Let $x y = x z$.
There are two cases to investigate: $x > 0$ and $x < 0$.
Let $x > 0$.
From Natural Numbers are Non-Negative Integers, $x \in \N_{> 0}$.
By the Extension Theorem for Distributive Operations and Ordering on Natural Numbers is Compatible with Multiplication, $x$ is cancellable for multiplication.
{{qed|lemma}
Let $x < 0$.
We know that the Integers form Integral Domain and are thus a ring.
Then $-x > 0$ and so:
{{begin-eqn}}
{{eqn | l = x y
      | r = x z
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \paren {-\paren {-x} } y
      | r = \paren {-\paren {-x} } z
      | c = Negative of Ring Negative
}}
{{eqn | ll= \leadsto
      | l = -\paren {\paren {-x} y}
      | r = -\paren {\paren {-x} z}
      | c = Product with Ring Negative
}}
{{eqn | ll= \leadsto
      | l = -y
      | r = -z
      | c = as $-x$ is (strictly) positive, the above result holds
}}
{{eqn | ll= \leadsto
      | l = y
      | r = z
      | c = $\struct {\Z, +}$ is a group: {{Group-axiom|3}}
}}
{{end-eqn}}
{{qed|lemma}}
So whatever non-zero value $x$ takes, it is cancellable for multiplication.
{{Qed}}
Theorem: Multiplicative Ordering on Integers

Let $x, y, z \in \Z$ such that $z > 0$.
Then:
:$x < y \iff z x < z y$
:$x \le y \iff z x \le z y$

Proof:
Let $z > 0$.
Let $M_z: \Z \to \Z$ be the mapping defined as:
:$\forall x \in \Z: \map {M_z} x = z x$
It is sufficient to show that $M_z$ is an order embedding from $\struct {\Z, +, \le}$ to itself.
By Monomorphism from Total Ordering, it is sufficient to show that:
:$x < y \implies z x < z y$
Let $x < y$.
Then:
:$0 < y - x$
So $z \in \N$.
Hence by Natural Numbers are Non-Negative Integers:
:$y - x \in \N$
Thus by Ordering on Natural Numbers is Compatible with Multiplication:
:$z \paren {y - x} \in \N$
Therefore:
:$0 < z \paren {y - x} = z y - z x$
That is:
:$z x < z y$
{{qed}}
Theorem: Invertible Integers under Multiplication

The only invertible elements of $\Z$ for multiplication (that is, units of $\Z$) are $1$ and $-1$.

Proof:
Let $x > 0$ and $x y > 0$.
{{AimForCont}} first that $y \le 0$.
Then from Multiplicative Ordering on Integers and Ring Product with Zero:
:$x y \le x \, 0 = 0$
From this contradiction we deduce that $y > 0$.
Let $x > 0$ and $x y = 1$.
Then:
:$y > 0$
and by Natural Numbers are Non-Negative Integers:
:$y \in \N$
Hence by Invertible Elements under Natural Number Multiplication:
:$x = 1$
Thus $1$ is the only element of $\N$ that is invertible for multiplication.
Therefore by Natural Numbers are Non-Negative Integers and Product with Ring Negative, the result follows.
{{qed}}
Theorem: Totally Ordered Abelian Group Isomorphism

Let $\struct {\Z', +', \le'}$ be a totally ordered abelian group.
Let $0'$ be the identity of $\struct {\Z', +', \le'}$.
Let $\N' = \set {x \in \Z': x \ge' 0'}$.
Let $\Z'$ contain at least two elements.
Let $\N'$ be well-ordered for the ordering induced on $\N'$ by $\le'$.
Then the mapping $g: \Z \to \Z'$ defined by:
:$\forall n \in \Z: \map g n = \paren {+'}^n 1'$
is an isomorphism from $\struct {\Z, +, \le}$ onto $\struct {\Z', +', \le'}$, where $1'$ is the smallest element of $\N' \setminus \set {0'}$.

Proof:
First we establish that $g$ is a homomorphism.
Suppose $z \in \Z'$ such that $z \ne 0'$.
Then by Ordering of Inverses in Ordered Monoid, either $z >' 0'$ or $-z >' 0'$.
Thus either:
:$z \in \N' \setminus \set {0'}$
or:
:$-z \in \N' \setminus \set {0'}$
and thus $\N' \setminus \set {0'}$ is not empty.
Therefore $\N' \setminus \set {0'}$ has a minimal element.
Call this minimal element $1'$.
It is clear that $\N'$ is an ordered semigroup satisfying:
:{{NOSAxiom|1}}
:{{NOSAxiom|2}}
:{{NOSAxiom|4}}.
Also:
{{begin-eqn}}
{{eqn | o = 
      | r = 0' \le' x \le' y
      | c = 
}}
{{eqn | o = \leadsto
      | r = 0' \le' y - x
      | c = 
}}
{{eqn | o = \leadsto
      | r = y - x \in \N' \land x +' \paren {y - x} = y
      | c = 
}}
{{end-eqn}}
Thus $\N'$ also satisfies {{NOSAxiom|3}}.
So $\struct {\N', +', \le'}$ is a naturally ordered semigroup.
So, by Naturally Ordered Semigroup is Unique, the restriction to $\N$ of $g$ is an isomorphism from $\struct {\N, +, \le}$ to $\struct {\N', +', \le'}$.
By Index Law for Sum of Indices, $g$ is a homomorphism from $\struct {\Z, +}$ into $\struct {\Z', +'}$.
Next it is established that $g$ is surjective.
Let $y \in \Z': y <' 0'$.
{{begin-eqn}}
{{eqn | o = 
      | r = y <' 0'
      | c = 
}}
{{eqn | o = \leadsto
      | r = -y >' 0'
      | c = 
}}
{{eqn | o = \leadsto
      | r = \exists n \in \N: -y = \map g n
      | c = 
}}
{{eqn | o = \leadsto
      | r = y = -\map g n = \map g {-n}
      | c = Homomorphism with Identity Preserves Inverses
}}
{{end-eqn}}
Therefore $g$ is a surjection.
Now to show that $g$ is a monomorphism, that is, it is injective.
Let $n < m$.
{{begin-eqn}}
{{eqn | o = 
      | r = n < m
      | c = 
}}
{{eqn | o = \leadsto
      | r = m - n \in \N_{>0}
      | c = 
}}
{{eqn | o = \leadsto
      | r = \map g m - \map g n - \map g {m - n} \in \N' \setminus \set {0'}
      | c = 
}}
{{eqn | o = \leadsto
      | r = \map g n <' \paren {\map g m - \map g n} +' \map g n = \map g m
      | c = Strict Ordering Preserved under Product with Cancellable Element
}}
{{end-eqn}}
Therefore it can be seen that $g$ is strictly increasing.
It follows from Monomorphism from Total Ordering that $g$ is a monomorphism from $\struct {\Z, +, \le}$ to $\struct {\Z', +', \le'}$.
A surjective monomorphism is an isomorphism, and the result follows.
{{Qed}}
Theorem: Integers under Addition form Totally Ordered Group

Then the ordered structure $\struct {\Z, +, \le}$ is a totally ordered group.

Proof:
=== $\struct {\Z, +, \le}$ is an Ordered Structure ===
Theorem: Integers form Totally Ordered Ring

The structure $\struct {\Z, +, \times, \le}$ is a totally ordered ring.

Proof:
From Integers form Commutative Ring, $\struct {\Z, +, \times}$ is a commutative ring.
We need to show that $\le$ is a compatible ordering on $\Z$.
That is, that:
:$(1): \quad \le$ is compatible with $+$
:$(2): \quad \forall x, y \in \Z: 0 \le x, 0 \le y \implies 0 \le x \times y$
The first one follows from the fact that Integers under Addition form Totally Ordered Group.
Now, from Multiplicative Ordering on Integers, we have:
:$\forall z, x, y \in \Z, 0 < y: z \le x \iff y \times z \le y \times x$
Let $z = 0, 0 \le x$.
Then:
:$0 = x \times z \le x \times y = y \times x$
So if $y \ne 0$, the condition $0 \le x, 0 \le y \implies 0 \le x \times y$ holds.
Now if $y = 0$, we have $x \times y = 0$ and thus $0 \le x \times y$.
Thus $\le$ is compatible with $\Z$, and the result follows.
{{qed}}
Theorem: Congruences on Rational Numbers

There are only two congruence relations on the field of rational numbers $\struct {\Q, +, \times}$:
:$(1): \quad$ The diagonal relation $\Delta_\Q$
:$(2): \quad$ The trivial relation $\Q \times \Q$.

Proof:
From:
:Diagonal Relation is Universally Congruent and
:Trivial Relation is Universally Congruent
we know that both these relations are congruent with both addition and multiplication on $\Q$.
Now we need to show that these are the ''only'' such relations.
Let $\RR$ be a congruence on $\Q$, such that $\RR \ne \Delta_\Q$.
{{begin-eqn}}
{{eqn | l = \RR
      | o = \ne
      | r = \Delta_\Q
      | c = 
}}
{{eqn | ll= \leadsto
      | q = \exists r, s \in \Q
      | l = r
      | o = \ne
      | r = s \land r \RR s
      | c = 
}}
{{eqn | ll= \leadsto
      | q = \exists h \in \Q, h \ne 0
      | l = h
      | r = r - s
      | c = 
}}
{{eqn | ll= \leadsto
      | l = h
      | o = \RR
      | r = 0
      | c = as $\RR$ is a congruence relation for $+$
}}
{{end-eqn}}
Then:
{{begin-eqn}}
{{eqn | q = \forall x \in \Q
      | l = \paren {x / h}
      | o = \RR
      | r = \paren {x / h}
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \paren {\paren {x / h} \times h}
      | o = \RR
      | r = \paren {\paren {x / h} \times 0}
      | c = as $\RR$ is a congruence relation for $\times$
}}
{{eqn | ll= \leadsto
      | l = x
      | o = \RR
      | r = 0
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \eqclass 0 \RR
      | r = \Q
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \RR
      | r = \Q \times \Q
      | c = 
}}
{{end-eqn}}
{{qed}}
Theorem: Number of Elements in Partition

Let $S$ be a set.
Let there be a partition on $S$ of $n$ subsets, each of which has $m$ elements.
Then:
:$\card S = n m$

Proof:
Let the partition of $S$ be $S_1, S_2, \ldots, S_n$.
Then:
:$\forall k \in \set {1, 2, \ldots, n}: \card {S_k} = m$
By definition of multiplication:
:$\ds \sum_{k \mathop = 1}^n \card {S_k} = n m$
and the result follows from the Fundamental Principle of Counting.
{{qed}}
Theorem: Cardinality of Complement

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.
{{qed}}
Theorem: Cardinality of Cartesian Product of Finite Sets

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.

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.
{{qed}}
Theorem: Cardinality of Cartesian Product of Finite Sets

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.

Proof:
{{begin-eqn}}
{{eqn | l = \card {S \times T}
      | r = \card S \times \card T
      | c = Cardinality of Cartesian Product of Finite Sets
}}
{{eqn | r = \card T \times \card S
      | c = Integer Multiplication is Commutative
}}
{{eqn | r = \card {T \times S}
      | c = Cardinality of Cartesian Product of Finite Sets
}}
{{end-eqn}}
{{qed}}
Theorem: Cardinality of Cartesian Product of Finite Sets

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.

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:
{{begin-eqn}}
{{eqn | l = \map f {s_1, t_1}
      | r = \map f {s_2, t_2}
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \tuple {t_1, s_1}
      | r = \tuple {t_2, s_2}
      | c = Definition of $f$
}}
{{eqn | ll= \leadsto
      | l = \tuple {s_1, t_1}
      | r = \tuple {s_2, t_2}
      | c = Equality of Ordered Pairs
}}
{{end-eqn}}
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.
{{qed}}
Theorem: Cardinality of Power Set of Finite Set

Let $S$ be a set such that:
:$\card S = n$
where $\card S$ denotes the cardinality of $S$,
Then:
:$\card {\powerset S} = 2^n$
where $\powerset S$ denotes the power set of $S$.

Proof:
Given an element $x$ of $S$, each subset of $S$ either includes $x$ or does not include $x$ (this follows directly from the definition of a set), which gives us two possibilities.
The same reasoning holds for any element of $S$.
One can intuitively see that this means that there are $\ds \underbrace {2 \times 2 \times \ldots \times 2}_{\card S} = 2^{\card S}$ total possible combinations of elements of $S$.
This is exactly $\card {\powerset S}$.
{{qed}}
Theorem: Cardinality of Power Set of Finite Set

Let $S$ be a set such that:
:$\card S = n$
where $\card S$ denotes the cardinality of $S$,
Then:
:$\card {\powerset S} = 2^n$
where $\powerset S$ denotes the power set of $S$.

Proof:
Let $T = \set {0, 1}$.
For each $A \in \powerset S$, we consider the characteristic function $\chi_A: S \to T$ defined as:
:<nowiki>$\forall x \in S: \map {\chi_A} x = \begin{cases}
1 & : x \in A \\
0 & : x \notin A
\end{cases}$</nowiki>
Now consider the mapping $f: \powerset S \to T^S$:
:$\forall A \in \powerset S: \map f A = \chi_A$
where $T^S$ is the set of all mappings from $S$ to $T$.
Also, consider the mapping $g: T^S \to \powerset S$:
:$\forall \phi \in T^S: \map g \phi = \phi^{-1} \sqbrk {\set 1}$
where $\phi^{-1} \sqbrk {\set 1}$ is the preimage of $\set 1$ under $\phi$.
Consider the characteristic function of $\phi^{-1} \sqbrk {\set 1}$, denoted $\chi_{\phi^{-1} \sqbrk {\set 1} }$.
We have:
{{begin-eqn}}
{{eqn | q = \forall x \in S
      | l = \map {\chi_{\phi^{-1} \sqbrk {\set 1} } } x
      | r = \begin{cases} 1 & : x \in \phi^{-1} \sqbrk {\set 1} \\ 0 & : x \notin \phi^{-1} \sqbrk {\set 1} \end{cases}
      | c =
}}
{{eqn | r = \begin{cases} 1 & : \map \phi x = 1 \\ 0 & : \map \phi x = 0 \end{cases}
      | c =
}}
{{eqn | r = \map \phi x
      | c =
}}
{{end-eqn}}
So:
{{begin-eqn}}
{{eqn | q = \forall \phi \in T^S
      | l = \map {\paren {f \circ g} } \phi
      | r = \map f {\phi^{-1} } {\sqbrk {\set 1} }
      | c = 
}}
{{eqn | r = \chi_{\phi^{-1} \sqbrk {\set 1} }
      | c = 
}}
{{eqn | r = \phi
      | c = 
}}
{{end-eqn}}
So $f \circ g = I_{T^S}$, that is, the identity mapping on $T^S$.
So far so good. Now we consider the preimage of $\set 1$ under $\chi_A$:
: $\chi_A^{-1} \sqbrk {\set 1} = A$
from the definition of the characteristic function $\chi_A$ above.
Thus:
{{begin-eqn}}
{{eqn | q = \forall A \in \powerset S
      | l = \map {\paren {g \circ f} } A
      | r = \map g {\map f A}
      | c = 
}}
{{eqn | r = \map g {\chi_A}
      | c = 
}}
{{eqn | r = \chi_A^{-1} \sqbrk {\set 1}
      | c = 
}}
{{eqn | r = A
      | c = 
}}
{{end-eqn}}
So $g \circ f = I_{\powerset S}$, that is, the identity mapping on $\powerset S$.
It follows from Bijection iff Left and Right Inverse that $f$ and $g$ are bijections.
Thus by Cardinality of Set of All Mappings the result follows.
{{Qed}}
Theorem: Cardinality of Power Set of Finite Set

Let $S$ be a set such that:
:$\card S = n$
where $\card S$ denotes the cardinality of $S$,
Then:
:$\card {\powerset S} = 2^n$
where $\powerset S$ denotes the power set of $S$.

Proof:
Enumerating the subsets of $S$ is equivalent to counting all of the ways of selecting $k$ out of the $n$ elements of $S$ with $k = 0, 1, \ldots, n$.
So, from Cardinality of Set of Subsets, the number we are looking for is:
:$\ds \card {\powerset S} = \sum_{k \mathop = 0}^n \binom n k$
But from the binomial theorem:
:$\ds \paren {x + y}^n = \sum_{k \mathop = 0}^n \binom n k x^{n - k} y^k$
It follows that:
:$2^n = \ds \paren {1 + 1}^n = \sum_{k \mathop = 0}^n \binom n k \paren 1^{n - k} \paren 1^k = \sum_{k \mathop = 0}^n \binom n k = \card {\powerset S}$
{{Qed}}
Theorem: Cardinality of Power Set of Finite Set

Let $S$ be a set such that:
:$\card S = n$
where $\card S$ denotes the cardinality of $S$,
Then:
:$\card {\powerset S} = 2^n$
where $\powerset S$ denotes the power set of $S$.

Proof:
Proof by induction:
For all $n \in \N$, let $\map P n$ be the proposition:
:$\card S = n \implies \card {\powerset S} = 2^n$
Do not confuse $\map P n$, which is a propositional function on $\N$, with $\powerset S$, the power set of $S$.
=== Basis for the Induction ===
From Cardinality of Empty Set:
: $S = \O \iff \card S = 0$
Then:
: $\powerset \O = \set \O$
has one element, that is, $\O$.
So:
: $\card {\powerset \O} = \card {\set \O} = 1 = 2^0$
thus confirming that $\map P 0$ holds.
This is our basis for the induction.
=== Induction Hypothesis ===
Now we need to show that, if $\map P k$ is true, where $k \ge 2$, then it logically follows that $\map P {k + 1}$ is true.
So this is our induction hypothesis:
:$\card S = k \implies \card {\powerset S} = 2^k$
Then we need to show:
:$\card S = k + 1 \implies \card {\powerset S} = 2^{k + 1}$
=== Induction Step ===
This is our induction step:
Let $\card S = k + 1$.
Let $x \in S$.
Consider the set $S' = S \setminus \set x$ where $x$ is any element of $S$.
We see that $\card {S'} = k$.
Now adjoin $x$ to all the subsets of $S'$.
Counting the subsets of $S$, we have:
: all the subsets of $S'$
and:
: all the subsets of $S'$ with $x$ adjoined to them.
From the induction hypothesis, there are $2^k$ subsets of $S'$.
Adding $x$ to each of these does not change their number, so there are another $2^k$ subsets of $S$ consisting of all the subsets of $S'$ with $x$ adjoined to them.
In total that makes $2^k + 2^k = 2 \times 2^k = 2^{k + 1}$ subsets of $S$.
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\forall n \in \N: \card S = n \implies \card {\powerset S} = 2^n$
{{qed}}
Theorem: Cardinality of Set of Bijections

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.
{{Qed}}
Theorem: Cardinality of Set of Subsets

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:
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.
{{qed}}
Theorem: Cardinality of Set of Subsets

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:
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:
{{begin-eqn}}
{{eqn | l = m! \cdot \dbinom n m
      | r = {}^m P_n
      | c = Product Rule for Counting
}}
{{eqn | r = \frac {n!} {\paren {n - m}!}
      | c = Number of Permutations
}}
{{eqn | ll= \leadsto
      | l = \dbinom n m
      | r = \frac {n!} {m! \paren {n - m}!}
      | c = Product Rule for Counting
}}
{{end-eqn}}
{{qed}}
Theorem: Cardinality of Set of Subsets

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:
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.
{{qed}}
Theorem: Cardinality of Set of Subsets

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:
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:
{{begin-eqn}}
{{eqn | l = \dbinom 1 m
      | r = \dfrac {1!} {1! \paren {m - 1}!}
      | c = 
}}
{{eqn | r = \begin {cases} 1 & : m = 0 \text { or } m = 1 \\ 0 & : \text {otherwise} \end {cases}
      | c = 
}}
{{eqn | r = \dfrac {1!} {0! \paren {1 - 0}!}
      | c = for $m = 0$
}}
{{eqn | r = \dfrac {1!} {1! \paren {1 - 1}!}
      | c = for $m = 1$
}}
{{end-eqn}}
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)
{{begin-eqn}}
{{eqn | l = \dbinom {k + 1} m
      | r = \binom k m + \binom k {m - 1}
      | c = 
}}
{{eqn | r = \dfrac {k!} {m! \paren {k - m}!} + \dfrac {k!} {\paren {m - 1}! \paren {k - m + 1}!}
      | c = Induction Hypothesis
}}
{{eqn | r = \dfrac {\paren {k + 1}!} {m! \paren {k - m + 1}!}
      | c = after algebra
}}
{{eqn | r = \binom {k + 1} m
      | c = 
}}
{{end-eqn}}
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}!}$