avewright/proofwiki-math huggingface dataset:
Theorem: Subgroups of Additive Group of Integers

Let $\struct {\Z, +}$ be the additive group of integers.
Let $n \Z$ be the additive group of integer multiples of $n$.
Every non-trivial subgroup of $\struct {\Z, +}$ has the form $n \Z$.

Proof:
First we note that, from Integer Multiples under Addition form Infinite Cyclic Group, $\struct {n \Z, +}$ is an infinite cyclic group.
From Cyclic Group is Abelian, it follows that $\struct {n \Z, +}$ is an infinite abelian group.
Let $H$ be a non-trivial subgroup of $\struct {\Z, +}$.
Because $H$ is non-trivial:
:$\exists m \in \Z: m \in H: m \ne 0$
Because $H$ is itself a group:
:$-m \in H$
So either $m$ or $-m$ is positive and therefore in $\Z_{>0}$.
Thus:
:$H \cap \Z_{>0} \ne \O$
From the Well-Ordering Principle, $H \cap \Z_{>0}$ has a smallest element, which we can call $n$.
It follows from Subgroup of Infinite Cyclic Group is Infinite Cyclic Group that:
: $\forall a \in \Z: a n \in H$
Thus:
: $n \Z \subseteq H$
{{AimForCont}}:
:$\exists m \in \Z: m \in H \setminus n \Z$
Then $m \ne 0$, and also $-m \in H \setminus n \Z$.
Assume $m > 0$, otherwise we consider $-m$.
By the Division Theorem:
:$m = q n + r$
If $r = 0$, then $m = q n \in n \Z$, so $0 \le r < n$.
Now this means $r = m - q n \in H$ and $0 \le r < n$.
This would mean $n$ was not the smallest element of $H \cap \Z$.
Hence, by Proof by Contradiction, there can be no such $m \in H \setminus n \Z$.
Thus:
:$H \setminus n \Z = \O$
Thus from Set Difference with Superset is Empty Set:
:$H \subseteq n \Z$
Thus we have $n \Z \subseteq H$ and $H \subseteq n \Z$.
Hence:
:$H = n \Z$
{{qed}}
Theorem: Integer Multiples under Addition form Infinite Cyclic Group

Let $n \Z$ be the set of integer multiples of $n$.
Then $\struct {n \Z, +}$ is a countably infinite cyclic group.
It is generated by $n$ and $-n$:
:$n \Z = \gen n$
:$n \Z = \gen {-n}$
Hence $\struct {n \Z, +}$ can be justifiably referred to as the additive group of integer multiples.

Proof:
From Integer Multiples under Addition form Subgroup of Integers, $\struct {n \Z, +}$ is a subgroup of the additive group of integers $\struct {\Z, +}$.
From Integers under Addition form Infinite Cyclic Group, $\struct {\Z, +}$ is a cyclic group.
So by Subgroup of Cyclic Group is Cyclic, $\struct {n \Z, +}$ is a cyclic group.
The final assertions follow from Subgroup of Infinite Cyclic Group is Infinite Cyclic Group.
{{qed}}
Theorem: Quotient Group of Integers by Multiples

Let $\struct {\Z, +}$ be the additive group of integers.
Let $\struct {m \Z, +}$ be the additive group of integer multiples of $m$.
Let $\struct {\Z_m, +_m}$ be the additive group of integers modulo $m$.
Then the quotient group of $\struct {\Z, +}$ by $\struct {m \Z, +}$ is $\struct {\Z_m, +_m}$.
Thus:
:$\index \Z {m \Z} = m$

Proof:
From Subgroups of Additive Group of Integers, $\struct {m \Z, +}$ is a subgroup of $\struct {\Z, +}$.
From Subgroup of Abelian Group is Normal, $\struct {m \Z, +}$ is normal in $\struct {\Z, +}$.
Therefore the quotient group $\dfrac {\struct {\Z, +} } {\struct {m \Z, +} }$ is defined.
Now $\Z$ modulo $m \Z$ is Congruence Modulo a Subgroup.
This is merely congruence modulo an integer.
Thus the quotient set $\Z / m \Z$ is $\Z_m$.
The left coset of $k \in \Z$ is denoted $k + m \Z$, which is the same thing as $\eqclass k m$ from the definition of residue class.
So $\index \Z {m \Z} = m$ follows from the definition of Subgroup Index.
{{qed}}
Theorem: Euler's Theorem (Number Theory)

Let $a, m \in \Z$ be coprime integers: $a \perp m$.
Let $\map \phi m$ be the Euler $\phi$ function of $m$.
Then:
:$a^{\map \phi m} \equiv 1 \pmod m$

Proof:
Let $\eqclass a m$ denote the residue class modulo $m$ of $a$.
Since $a \perp m$, it follows by Reduced Residue System under Multiplication forms Abelian Group that $\eqclass a m$ belongs to the abelian group $\struct {\Z'_m, \times}$.
Let $k = \order {\eqclass a m}$ where $\order {\, \cdot \,}$ denotes the order of a group element.
By Order of Element Divides Order of Finite Group:
:$k \divides \order {\Z'_m}$
By the definition of the Euler $\phi$ function:
:$\order {\Z'_m} = \map \phi m$
Thus:
{{begin-eqn}}
{{eqn | l = \eqclass a m^k
      | r = \eqclass a m
      | c = {{Defof|Order of Group Element}}
}}
{{eqn | ll= \leadsto
      | l = \eqclass a m^{\map \phi m}
      | r = \eqclass {a^{\map \phi m} } m
      | c = Congruence of Powers
}}
{{eqn | r = \eqclass 1 m
      | c = 
}}
{{eqn | ll= \leadsto
      | l = a^{\map \phi m}
      | o = \equiv
      | r = 1 \pmod m
      | c = {{Defof|Residue Class}}
}}
{{end-eqn}}
{{qed}}
Theorem: Symmetry Group is Group

Let $P$ be a geometric figure.
Let $S_P$ be the set of all symmetries of $P$.
Let $\circ$ denote composition of mappings.
The symmetry group $\struct {S_P, \circ}$ is indeed a group.

Proof:
By definition, a symmetry is a bijection, and hence a permutation.
From Symmetric Group is Group, the set of all permutations on $P$ form the symmetric group $\struct {\map \Gamma P, \circ}$ on $P$.
Thus $S_P$ is a subset of $\struct {\map \Gamma P, \circ}$.
Let $A$ and $B$ be symmetries on $P$.
From Composition of Symmetries is Symmetry, $A \circ B$ is also a symmetry on $P$.
Also, by the definition of symmetry, $A^{-1}$ is also a symmetry on $P$.
Thus we have:
:$A, B \in S_P \implies A \circ B \in S_P$
:$A \in S_P \implies A^{-1} \in \S_P$
The result follows from the Two-Step Subgroup Test.
{{qed}}
Theorem: Internal Angles of Square

The internal angles of a square are right angles.

Proof:
By definition, a square is a regular quadrilateral.
From Internal Angles of Regular Polygon, the internal angles of a square measure $\dfrac {180 \degrees \paren {4 - 2} } 4 = 90 \degrees$.
The result follows from Measurement of Right Angle.
{{qed}}
Category:Squares
Category:Internal Angles
e7un0prr5q4j459ggtc6jabni9890qc
Theorem: Area of Square

A square has an area of $L^2$ where $L$ is the length of a side of the square.
Thus we have that the area is a function of the length of the side:
:$\forall L \in \R_{\ge 0}: \map \Area L = L^2$
where it is noted that the domain of $L$ is the set of non-negative real numbers.

Proof:
=== Integer Side Length ===
In the case where $L = 1$, the statement follows from the definition of area.
If $L \in \N, L > 1$, then we can divide the square into smaller squares, each of side length one.
Since there will be $L$ squares of side length one on each side, it follows that there will be $L \cdot L = L^2$ squares of side length one.
Thus, the area of the square of side length $L$ is $L^2 \cdot 1 = L^2$.
{{Qed|lemma}}
=== Rational Side Length ===
Let $A$ be the area of the square $S$ with side length $L$.
If $L$ is a rational number, then:
:$\exists p, q \in \N: L = \dfrac p q$
Create a square of side length $p$.
From the integer side length case, its area equals $p^2$.
Divide the sides into $q$ equal parts.
Thus the square of side length $p$ is divided into $q^2$ small squares.
As they all have side length $\dfrac p q$, each of them equals $S$.
It follows arithmetically:
:$A = \dfrac {p^2} {q^2} = \paren {\dfrac p q}^2 = L^2$
{{Qed|lemma}}
=== Irrational Side Length ===
Let $L$ be an irrational number.
Then from Rationals are Everywhere Dense in Topological Space of Reals we know that within an arbitrarily small distance $\epsilon$ from $L$, we can find a rational number less than $L$ and a rational number greater than $L$.
In formal terms, we have:
:$\forall \epsilon > 0: \exists A, B \in \Q_+: A < L < B: \left|{A - L}\right| < \epsilon, \left|{B - L}\right| < \epsilon$
Thus:
: $\displaystyle \lim_{\epsilon \to 0^+} A = L$
: $\displaystyle \lim_{\epsilon \to 0^+} B = L$
Since a square of side length $B$ can contain a square of side length $L$, which can in turn contain a square of side length $A$, then:
: $\operatorname {area} \Box B \ge \operatorname {area} \Box L \ge \operatorname {area}\Box A$
By the result for rational numbers:
: $\operatorname {area}\Box B = B^2$
: $\operatorname {area}\Box A = A^2$
We also note that:
: $\displaystyle \lim_{B \to L} B^2 = L^2 = \lim_{A \to L} A^2$
Thus:
: $\displaystyle \lim_{B \to L} \operatorname {area} \Box B = \lim_{B \to L} B^2 = L^2$
: $\displaystyle \lim_{A \to L} \operatorname {area} \Box A = \lim_{A \to L} A^2 = L^2$
Finally:
: $L^2 \ge \operatorname {area}\Box L \ge L^2$
so:
: $\operatorname {area}\Box L = L^2$
{{Qed}}
Theorem: Area of Square

A square has an area of $L^2$ where $L$ is the length of a side of the square.
Thus we have that the area is a function of the length of the side:
:$\forall L \in \R_{\ge 0}: \map \Area L = L^2$
where it is noted that the domain of $L$ is the set of non-negative real numbers.

Proof:
Let $\Box ABCD$ be a square whose side $AB$ is of length $L$.
Let $\Box EFGH$ be a square whose side $EF$ is of length $1$.
:300px
From the Axioms of Area, the area of $\Box EFGH$ is $1$.
By definition, $AB : EF = L : 1$.
From Similar Polygons are composed of Similar Triangles, the ratio of the areas of $\Box ABCD$ to $\Box EFGH$ is the duplicate ratio of the ratio of $AB$ to $EF$.
Thus by definition of duplicate ratio:
: $\Box ABCD : \Box EFGH = \left({AB : EF}\right)^2$
That is:
: $\dfrac {\Box ABCD} {\Box EFGH} = \left({\dfrac L 1}\right)^2 = L^2$
That is, the area of $\Box ABCD$ has $L^2$ as many units as $\Box EFGH$.
Hence the result.
{{qed}}
Theorem: Area of Square

A square has an area of $L^2$ where $L$ is the length of a side of the square.
Thus we have that the area is a function of the length of the side:
:$\forall L \in \R_{\ge 0}: \map \Area L = L^2$
where it is noted that the domain of $L$ is the set of non-negative real numbers.

Proof:
Let a square have a side length $a \in \R$.
This square is equivalent to the area under the graph of $\map f x = a$ from $0$ to $a$.
Thus from the geometric interpretation of the definite integral, the area of the square will be the integral:
:$\ds A = \int_0^a a \rd l$
Thus:
{{begin-eqn}}
{{eqn | l = A
      | r = \int_0^a a \rd l
}}
{{eqn | r = \bigintlimits {l \cdot a} 0 a
      | c = Integral of Constant
}}
{{eqn | r = a \cdot a - 0 \cdot a
}}
{{eqn | r = a^2
}}
{{end-eqn}}
{{Qed}}
=== Warning ===
'''This proof is circular.'''
The use of the definite integral to represent area is based on the fact that the area of a rectangle is the product of the rectangle's width and height.
That fact is in turn derived from this one.
However, this demonstration neatly parallels the integration based proofs of the areas of other figures, for example Area of Circle.
Theorem: Order of Symmetric Group

Let $S$ be a finite set of cardinality $n$.
Let $\struct {\map \Gamma S, \circ}$ be the symmetric group on $S$.
Then $\struct {\map \Gamma S, \circ}$ has $n!$ elements (see factorial).

Proof:
A direct application of Cardinality of Set of Bijections.
{{qed}}
Theorem: Powers of Permutation Element

Let $S_n$ denote the symmetric group on $n$ letters.
Let $\pi \in S_n$, and let $i \in \N^*_n$.
Let $k \in \Z: k > 0$ be the smallest such that:
:$\map {\pi^k} i \in \set {i, \map \pi i, \map {\pi^2} i, \ldots, \map {\pi^{k - 1} } i}$
Then $\map {\pi^k} i = i$.

Proof:
{{AimForCont}} $\map {\pi^k} i = \map {\pi^r} i$ for some $r > 0$.
Then, since $\pi$ has an inverse, $\map {\pi^{k - r} } i = i$.
This contradicts the definition of $k$, so $r = 0$.
{{qed}}
Category:Symmetric Groups
07qq48opp9x93zw1utfe45zwng026lm
Theorem: Fixed Elements form 1-Cycles

Let $S_n$ denote the symmetric group on $n$ letters.
Let $\pi \in S_n$.
Let $\Fix \pi$ be the set of elements fixed by $\pi$.
For any $\pi \in S_n$, all the elements of $\Fix \pi$ form $1$-cycles.

Proof:
Let $\pi$ be a permutation, and let $x \in \Fix \pi$.
From the definition of a fixed element:
:$\map \pi x = x$
From the definition of a $k$-cycle, we see that $1$ is the smallest $k \in \Z: k > 0$ such that:
:$\map {\pi^k} x = x$
The result follows.
{{qed}}
Category:Fixed Elements under Permutations
Category:Symmetric Groups
0okeqx8swwqjm87tchf0hw8pngsagep
Theorem: Equality of Cycles

Let $S_n$ denote the symmetric group on $n$ letters, realised as the permutations of $\set {1, \ldots, n}$.
Let:
:$\rho = \begin {bmatrix} a_0 & \cdots & a_{k - 1} \end {bmatrix} \in S_n$
:$\sigma = \begin {bmatrix} b_0 & \cdots & b_{k - 1} \end {bmatrix} \in S_n$
be $k$-cycles of $S_n$.
For $d \in \Z$, by Integer is Congruent to Integer less than Modulus we can associate to $d$ a unique integer $\tilde d \in \set {0, \ldots, k - 1}$ such that:
:$d \equiv \tilde d \pmod k$
Define $a_d$ and $b_d$ for any $d \in \Z$ by $a_d = a_{\tilde d}$ and $b_d = b_{\tilde d}$
Choose $i, j \in \set {1, \ldots, k}$ such that:
:$\ds a_i = \min \set {a_0, \ldots, a_{k - 1} }$
:$\ds b_j = \min \set {b_0, \ldots, b_{k - 1} }$
Then:
:$\rho = \sigma$
{{iff}}:
:$\forall d \in \Z: a_{i + d} = b_{j + d}$
That is, $\rho = \sigma$ {{iff}} they are identical when written with the lowest element first.

Proof:
{{ProofWanted}}
Category:Symmetric Groups
1zc47z6t6vjz3fckdm4zldg8bqcv4kj
Theorem: Identity Permutation is Disjoint from All

Let $S_n$ denote the symmetric group on $n$ letters.
Let $e \in S_n$ be the identity permutation on $S_n$.
Then $e$ is disjoint from every permutation $\pi$ on $S_n$ (including itself).

Proof:
By definition of the identity permutation:
:$\forall i \in \N_{>0}: \map e i = i$
Thus $e$ fixes all elements of $S_n$.
Thus each element moved by a permutation $\pi$ is fixed by $e$.
The set of elements moved by $e$ is $\O$, so the converse is true vacuously.
{{qed}}
Category:Symmetric Groups
Category:Identity Mappings
8wazjmgedwxex7foh48y8u9j6gy44od
Theorem: Disjoint Permutations Commute

Let $S_n$ denote the symmetric group on $n$ letters.
Let $\rho, \sigma \in S_n$ such that $\rho$ and $\sigma$ are disjoint.
Then $\rho \sigma = \sigma \rho$.

Proof:
Let $\rho$ and $\sigma$ be disjoint permutations.
Let $i \in \Fix \rho$.
Then:
:$\map {\sigma \rho} i = \map \sigma i$
whereas:
:$\map {\rho \sigma} i = \map \rho {\map \sigma i}$
{{AimForCont}} $\map \sigma i \notin \Fix \rho$.
Then because $\sigma$ and $\rho$ are disjoint it follows that:
{{begin-eqn}}
{{eqn | l = \map \sigma i
      | o = \in
      | r = \Fix \sigma
}}
{{eqn | ll= \leadsto
      | l = \map {\sigma^2} i
      | r = \map \sigma i
}}
{{eqn | ll= \leadsto
      | l = \map {\sigma^{-1} \sigma^2} i
      | r = \map {\sigma^{-1} \sigma} i
}}
{{eqn | ll= \leadsto
      | l = \map \sigma i
      | r = i
}}
{{end-eqn}}
But it was previously established that $i \in \Fix \rho$.
This is a contradiction.
Therefore:
:$\map \sigma i \in \Fix \rho$
and so:
:$\map {\rho \sigma} i = \map \sigma i = \map {\sigma \rho} i$
Let $i \notin \Fix \rho$.
Then:
: $i \in \Fix \sigma$
and the same proof can be performed with $\rho$ and $\sigma$ exchanged.
{{qed}}
Theorem: Permutation Induces Equivalence Relation

Let $S_n$ denote the symmetric group on $n$ letters.
Let $\pi \in S_n$.
Let $\RR_\pi$ be the relation defined by:
:$i \mathrel {\RR_\pi} j \iff \exists k \in \Z: \map {\pi^k} i = j$
Then $\RR_\pi$ is an equivalence relation.

Proof:
Let $\pi \in S_n$.
From Element of Finite Group is of Finite Order, every element of a finite group has finite order.
Thus $\pi$ has finite order.
So:
:$\exists r \in \Z: \pi^r = e$
Checking in turn each of the criteria for equivalence:
Theorem: Existence and Uniqueness of Cycle Decomposition

Let $S_n$ denote the symmetric group on $n$ letters.
Every element of $S_n$ may be uniquely expressed as a cycle decomposition, up to the order of factors.

Proof:
By definition, a cycle decomposition of an element of $S_n$ is a product of disjoint cycles.
Theorem: Powers of Disjoint Permutations

Let $S_n$ denote the symmetric group on $n$ letters.
Let $\rho, \sigma$ be disjoint permutations.
Then:
: $\forall k \in \Z: \paren {\sigma \rho}^k = \sigma^k \rho^k$

Proof:
A direct application of Power of Product of Commutative Elements in Group, and the fact that Disjoint Permutations Commute.
{{qed}}
Theorem: Order of Product of Disjoint Permutations

Let $S_n$ denote the symmetric group on $n$ letters.
Let $\pi$ be a product of disjoint permutations of orders $k_1, k_2, \ldots, k_r$.
Then:
:$\order \pi = \lcm \set {k_1, k_2, \ldots, k_r}$
where:
:$\order \pi$ denotes the order of $\pi$ in $S_n$
:$\lcm$ denotes lowest common multiple.

Proof:
Suppose $\pi$ is a cycle.
Then from Order of Cycle is Length of Cycle, $\order \pi$ is its length.
As the LCM of $n \in \Z$ is $n$ itself, the result follows.
Let $\pi = \rho_1 \rho_2 \cdots \rho_r$ where:
: each $\rho_s$ is of order $k_s$
: $\rho_1$ to $\rho_r$ are mutually disjoint permutations.
Let $t = \lcm \set {k_1, k_2, \ldots, k_r}$.
From Disjoint Permutations Commute:
:$\pi^t = \rho_1^t \rho_2^t \cdots \rho_r^t$
We have that:
:$\forall s: 1 \le s \le r: \exists m \in \Z: t = m s$
Hence:
:$\forall s: \rho_s^t = e$
Thus $\pi^t = e$ and certainly $\order \pi \divides t$.
Let $\pi^u = e$ for some $u \in \Z_{>0}$.
We have that $\rho_1, \rho_2, \cdots, \rho_r$ are mutually disjoint permutations.
Thus $\rho_1^u, \rho_2^u, \cdots, \rho_r^u$ are also mutually disjoint permutations.
Then we have that each $\rho_s^u = e$.
Hence $k_s \divides u$.
Thus, if $\pi^u = e$, then:
:$t \divides u$
Thus, by choosing $u = \order \pi$:
:$\order \pi = t = \lcm \set {k_1, k_2, \ldots, k_r}$
{{qed}}
Theorem: Group Action defines Permutation Representation

Let $\map \Gamma X$ be the set of permutations on a set $X$.
Let $G$ be a group.
Let $\phi: G \times X \to X$ be a group action.
For $g \in G$, let $\phi_g: X \to X$ be the mapping defined as:
:$\map {\phi_g} x = \map \phi {g, x}$
Let $\tilde \phi: G \to \map \Gamma X$ be the permutation representation associated to $\phi$, defined by:
:$\map {\tilde \phi} g := \phi_g$
Then $\tilde \phi$ is a group homomorphism.

Proof:
From Group Action determines Bijection:
:$\phi_g \in \map \Gamma X$
for $g \in G$.
Let $g, h \in G$.
{{Recall|Group Action}}
:$\forall \tuple {g, x} \in G \times X: \map \phi {g, x} \in X = g \wedge x \in X$
First we show that for all $x \in X$:
:$\map {\phi_g \circ \phi_h} x = \map {\phi_{g h} } x$
Thus:
{{begin-eqn}}     
{{eqn | l = \map {\phi_g \circ \phi_h} x
      | r = g \wedge \paren {h \wedge x}
      | c = Definition of $\phi_g$, $\phi_h$
}}
{{eqn | r = \paren {g h} \wedge x
      | c = {{Defof|Group Action}}
}}
{{eqn | r = \map {\phi_{g h} } x
      | c = Definition of $\phi_{g h}$
}}
{{end-eqn}}
Also, we have:
:$e \wedge x = x \implies \map {\phi_e} x = x$
where $e$ is the identity of $G$.
Therefore, we have shown that $\tilde \phi: G \to \map \Gamma X: g \mapsto \phi_g$ is a group homomorphism.
{{qed}}
Theorem: Group Action determines Bijection

Let $*$ be a group action of $G$ on $X$.
Then each $g \in G$ determines a bijection $\phi_g: X \to X$ given by:
:$\map {\phi_g} x = g * x$
Its inverse is:
:$\phi_{g^{-1} }: X \to X$.
These bijection are sometimes called '''transformations''' of $X$.

Proof:
=== Proof of Injectivity ===
Let $x, y \in X$
Then:
{{begin-eqn}}
{{eqn | l = \map {\phi_g} x
      | r = \map {\phi_g} y
      | c = 
}}
{{eqn | ll= \leadsto
      | l = g * x
      | r = g * y
      | c = 
}}
{{eqn | ll= \leadsto
      | l = g^{-1} * \paren {g * x}
      | r = g^{-1} * \paren {g * y}
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \paren {g^{-1} g} * x
      | r = \paren {g^{-1} g} * y
      | c = 
}}
{{eqn | ll= \leadsto
      | l = e * x
      | r = e * y
      | c = 
}}
{{eqn | ll= \leadsto
      | l = x
      | r = y
      | c = 
}}
{{end-eqn}}
Thus $\phi_g$ is an injection.
{{qed|lemma}}
Theorem: Group Action Induces Equivalence Relation

Let $\struct {G, \circ}$ be a group whose identity is $e$.
Let $X$ be a set.
Let $*: G \times S \to S$ be a group action.
Let $\RR_G$ be the relation induced by $G$, that is:
:$\forall x, y \in X: x \mathrel {\RR_G} y \iff y \in \Orb x$
where:
:$\Orb x$ denotes the orbit of $x \in X$.
Then:
:$\RR_G$ is an equivalence relation
and:
:the equivalence class of an element of $X$ is its orbit.

Proof:
Let $x \mathrel {\RR_G} y \iff y \in \Orb x$.
Checking in turn each of the criteria for equivalence:
Theorem: Partition Equation

Let group $G$ act on a finite set $X$.
Let the distinct orbits of $X$ under the action of $G$ be:
:$\Orb {x_1}, \Orb {x_2}, \ldots, \Orb {x_s}$
Then:
:$\card X = \card {\Orb {x_1} } + \card {\Orb {x_2} } + \cdots + \card {\Orb {x_s} }$

Proof:
Follows trivially from the fact that the Group Action Induces Equivalence Relation.
{{explain|cite a result about equiv rels and partitions, and one about cardinality and partitions}}
{{qed}}
Category:Group Actions
Category:Named Theorems
pwvgvk2c6p89r84hq9vudcd3u47firc
Theorem: Stabilizer is Subgroup

Let $\struct {G, \circ}$ be a group which acts on a set $X$.
Let $\Stab x$ be the stabilizer of $x$ by $G$.
Then for each $x \in X$, $\Stab x$ is a subgroup of $G$.

Proof:
From the {{GroupActionAxiom|2}}:
:$e * x = x \implies e \in \Stab x$
and so $\Stab x$ cannot be empty.
Let $g, h \in \Stab x$.
{{begin-eqn}}
{{eqn | l = g, h
      | o = \in
      | r = \Stab x
      | c = 
}}
{{eqn | ll= \leadsto
      | l = g * x
      | r = x
      | c = {{Defof|Stabilizer}} of $x$ by $G$
}}
{{eqn | lo= \land
      | l = h * x
      | r = x
      | c = {{Defof|Stabilizer}} of $x$ by $G$
}}
{{eqn | ll= \leadsto
      | l = g * \paren {h * x}
      | r = x
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \paren {g \circ h} * x
      | r = x
      | c = {{GroupActionAxiom|1}}
}}
{{eqn | ll= \leadsto
      | l = g \circ h
      | o = \in
      | r = \Stab x
      | c = {{Defof|Stabilizer}} of $x$ by $G$
}}
{{end-eqn}}
Let $g \in \Stab x$.
Then:
:$x = \paren {g^{-1} \circ g} * x = g^{-1} * \paren {g * x} = g^{-1} * x$
Hence $g^{-1} \in \Stab x$.
Thus the conditions for the Two-Step Subgroup Test are fulfilled, and $\Stab x \le G$.
{{qed}}
Theorem: Orbit-Stabilizer Theorem

Let $G$ be a group which acts on a finite set $X$.
Let $x \in X$.
Let $\Orb x$ denote  the orbit of $x$.
Let $\Stab x$ denote the stabilizer of $x$ by $G$.
Let $\index G {\Stab x}$ denote the index of $\Stab x$ in $G$.
Then:
:$\order {\Orb x} = \index G {\Stab x} = \dfrac {\order G} {\order {\Stab x} }$

Proof:
Let us define the mapping:
:$\phi: G \to \Orb x$
such that:
:$\map \phi g = g * x$
where $*$ denotes the group action.
It is clear that $\phi$ is surjective, because from the definition $x$ was acted on by all the elements of $G$.
Next, from Stabilizer is Subgroup: Corollary:
:$\map \phi g = \map \phi h \iff g^{-1} h \in \Stab x$
This means:
:$g \equiv h \pmod {\Stab x}$
Thus there is a well-defined bijection:
:$G \mathbin / \Stab x \to \Orb x$
given by:
:$g \, \Stab x \mapsto g * x$
So $\Orb x$ has the same number of elements as $G \mathbin / \Stab x$.
That is:
:$\order {\Orb x} = \index G {\Stab x}$
The result follows.
{{qed}}