avewright/proofwiki-math huggingface dataset:
Theorem: Cauchy's Inequality

:$\ds \sum {r_i}^2 \sum {s_i}^2 \ge \paren {\sum {r_i s_i} }^2$
where all of $r_i, s_i \in \R$.

Proof:
From the Complex Number form of the Cauchy-Schwarz Inequality, we have:
{{:Cauchy-Schwarz Inequality/Complex Numbers}}
As elements of $\R$ are also elements of $\C$, it follows that:
:$\ds \sum \size {r_i}^2 \sum \size {s_i}^2 \ge \size {\sum r_i s_i}^2$
where all of $r_i, s_i \in \R$.
But from the definition of modulus, it follows that:
:$\ds \forall r_i \in \R: \size {r_i}^2 = {r_i}^2$
Thus:
:$\ds \sum {r_i}^2 \sum {s_i}^2 \ge \paren {\sum r_i s_i}^2$
where all of $r_i, s_i \in \R$.
{{qed}}
Theorem: Cancellable Finite Semigroup is Group

Let $\struct {S, \circ}$ be a non-empty finite semigroup in which all elements are cancellable.
Then $\struct {S, \circ}$ is a group.

Proof:
As $\struct {S, \circ}$ is a semigroup, it is {{afortiori}} closed and associative.
It remains to be shown that:
:$\struct {S, \circ}$ has an identity
:every element of $S$ has an inverse in $S$.
Let $a \in S$ be arbitrary.
Let the mapping $\lambda_a: S \to S$ be the left regular representation of $\struct {S, \circ}$ with respect to $a$.
By Regular Representation wrt Cancellable Element on Finite Semigroup is Bijection, $\lambda_a$ is a bijection.
We have {{hypothesis}} that:
:$\struct {S, \circ}$ is non-empty
:all elements of $S$ are cancellable
:$S$ is finite.
;Existence of Identity Element
{{begin-eqn}}
{{eqn | q = \exists e \in S
      | l = \map {\lambda_a} e
      | r = a
      | c = as $\lambda_a$ is a surjection
}}
{{eqn | ll= \leadsto
      | l = a \circ e
      | r = a
      | c = {{Defof|Left Regular Representation}}
}}
{{end-eqn}}
Let $x \in S$ be arbitrary.
Then:
{{begin-eqn}}
{{eqn | l = a \circ \paren {e \circ x}
      | r = a \circ x
      | c = {{Semigroup-axiom|0}}
}}
{{eqn | ll= \leadsto
      | l = e \circ x
      | r = x
      | c = {{Defof|Cancellable Element}}
}}
{{eqn | ll= \leadsto
      | l = x \circ \paren {e \circ x}
      | r = x \circ x
      | c = {{Semigroup-axiom|0}}
}}
{{eqn | ll= \leadsto
      | l = \paren {x \circ e} \circ x
      | r = x \circ x
      | c = {{Semigroup-axiom|1}}
}}
{{eqn | ll= \leadsto
      | l = x \circ e
      | r = x
      | c = {{Defof|Cancellable Element}}
}}
{{end-eqn}}
Thus $e$ is an identity element.
By Identity is Unique, there is only one such.
;Existence of Inverse Elements
{{begin-eqn}}
{{eqn | q = \exists y \in S
      | l = \map {\lambda_a} y
      | r = e
      | c = as $\lambda_a$ is a surjection
}}
{{eqn | ll= \leadsto
      | l = a \circ y
      | r = e
      | c = {{Defof|Left Regular Representation}}
}}
{{end-eqn}}
Hence $y$ acts as a right inverse for $a$.
As $a$ is arbitrary, it follows that all $a \in S$ have a right inverse.
From Right Inverse for All is Left Inverse, each of these elements is also a left inverse, and therefore an inverse.
Thus $S$ is closed, associative, has an identity and every element has an inverse.
So, by definition, $\struct {S, \circ}$ is a group.
{{qed}}
Theorem: Finite Semigroup Equal Elements for Different Powers

Let $\left({S, \circ}\right)$ be a finite semigroup.
Then:
: $\forall x \in S: \exists m, n \in \N: m \ne n: x^m = x^n$

Proof:
List the positive powers $x, x^2, x^3, \ldots$ of any element $x$ of a finite semigroup $\left({S, \circ}\right)$.
Since all are elements of $S$, and the semigroup has a finite number of elements, it follows from the Pigeonhole Principle this list must contain repetitions.
So there must be at least one instance where $x^m = x^n$ for some $m, n \in \N$.
{{Qed}}
Category:Semigroups
1xgxx01rhazfn21f659gs2m7pt8z620
Theorem: Element has Idempotent Power in Finite Semigroup

Let $\struct {S, \circ}$ be a finite semigroup.
For every element in $\struct {S, \circ}$, there is a power of that element which is idempotent.
That is:
:$\forall x \in S: \exists i \in \N: x^i = x^i \circ x^i$

Proof:
From Finite Semigroup Equal Elements for Different Powers, we have:
:$\forall x \in S: \exists m, n \in \N: m \ne n: x^m = x^n$
Let $m > n$.
Let $n = k, m = k + l$.
Then:
: $\forall x \in S: \exists k, l \in \N: x^k = x^{k + l}$
Now we show that:
:$x^k = x^{k + l} \implies x^{k l} = x^{k l} \circ x^{k l}$
That is, that $x^{k l}$ is idempotent.
First:
{{begin-eqn}}
{{eqn | l = x^k
      | r = x^{k + l}
      | c = 
}}
{{eqn | ll= \leadsto
      | l = x^k \circ x^l
      | r = x^{k + l} \circ x^l
      | c = both sides ${} \circ x^l$
}}
{{eqn | ll= \leadsto
      | l = x^{k + l}
      | r = x^{k + 2 l}
      | c = Index Laws for Semigroup: Sum of Indices
}}
{{eqn | ll= \leadsto
      | l = x^k
      | r = x^{k + 2 l}
      | c = as $x^k = x^{k + l}$
}}
{{end-eqn}}
From here we can easily prove by induction that:
: $\forall n \in \N: x^k = x^{k + n l}$
In particular:
: $x^k = x^{k + k l} = x^{k \paren {l + 1} }$
There are two cases to consider:
:$(1): \quad$ If $l = 1$, then $x^k = x^{k \paren {l + 1} } = x^{2 k} = x^k \circ x^k$, and $x^{k l} = x^k$ is idempotent.
:$(2): \quad$ If $l > 1$, then:
{{begin-eqn}}
{{eqn | l = x^k
      | r = x^{k + k l}
      | c = 
}}
{{eqn | r = x^{k \paren {l + 1} }
      | c = 
}}
{{eqn | ll= \leadsto
      | l = x^k \circ x^{k \paren {l - 1} }
      | r = x^{k \paren {l + 1} } \circ x^{k \paren {l - 1} }
      | c = both sides ${} \circ x^{k \paren {l - 1} }$
}}
{{eqn | ll= \leadsto
      | l = x^{k + k l - k}
      | r = x^{kl + k + k l - k}
      | c = Index Laws for Semigroup: Sum of Indices
}}
{{eqn | ll= \leadsto
      | l = x^{k l}
      | r = x^{k l + k l}
      | c = 
}}
{{eqn | r = x^{k l} \circ x^{k l}
      | c = 
}}
{{end-eqn}}
and again, $x^{k l}$ is idempotent.
{{Qed}}
Theorem: Integral Multiple of Ring Element

Let $\struct {R, +, \circ}$ be a ring whose zero is $0_R$.
Let $n \cdot x$ be an integral multiple of $x$:
:<nowiki>$n \cdot x = \begin {cases}
0_R & : n = 0 \\
x & : n = 1 \\
\paren {n - 1} \cdot x + x & : n > 1
\end {cases}$</nowiki>
that is:
:$n \cdot x = \underbrace {x + x + \cdots + x}_{\text {$n$ times} }$
For $n < 0$ we use:
:$n \cdot x = \paren{-n} \cdot \paren {-x}$
Then:
:$\forall n \in \Z: \forall x \in R: \paren {n \cdot x} \circ x = n \cdot \paren {x \circ x} = x \circ \paren {n \cdot x}$

Proof:
Proof by induction:
For all $n \in \N$, let $\map P n$ be the proposition:
:$\paren {n \cdot x} \circ x = n \cdot \paren {x \circ x} = x \circ \paren {n \cdot x}$
First we verify $\map P 0$.
When $n = 0$, we have:
{{begin-eqn}}
{{eqn | l = \paren {0 \cdot x} \circ x
      | r = 0_R \circ x
      | c = 
}}
{{eqn | r = 0_R
      | c = 
}}
{{eqn | r = 0 \cdot \paren {x \circ x}
      | c = 
}}
{{eqn | r = x \circ 0_R
      | c = 
}}
{{eqn | r = x \circ \paren {0 \cdot x}
      | c = 
}}
{{end-eqn}}
So $\map P 0$ holds.
Theorem: Power of Conjugate equals Conjugate of Power

Let $\struct {G, \circ}$ be a group whose identity is $e$.
Let $x, y \in G$ such that $\exists a \in G: x \circ a = a \circ y$.
That is, let $x$ and $y$ be conjugate.
Then:
: $\forall n \in \Z: y^n = \paren {a^{-1} \circ x \circ a}^n = a^{-1} \circ x^n \circ a$
It follows directly that:
: $\exists b \in G: \forall n \in \Z: y^n = b \circ x^n \circ b^{-1}$
In particular:
: $y^{-1} = \paren {a^{-1} \circ x \circ a}^{-1} = a^{-1} \circ x^{-1} \circ a$

Proof:
Proof by induction:
For all $n \in \N$, let $\map P n$ be the proposition $y^n = a^{-1} \circ x^n \circ a$.
$\map P 0$ is true, as this just says $e =  a^{-1} \circ e \circ a$.
Theorem: Product of Conjugates equals Conjugate of Products

Let $\struct {G, \circ}$ be a group.
Then:
:$\forall a, x, y \in G: \paren {a \circ x \circ a^{-1} } \circ \paren {a \circ y \circ a^{-1} } = a \circ \paren {x \circ y} \circ a^{-1}$
That is, the product of conjugates is equal to the conjugate of the product.

Proof:
Follows directly from the group axioms.
{{Qed}}
Theorem: Power of Product with Inverse

Let $G$ be a group whose identity is $e$.
Let $a, b \in G: a b = b a^{-1}$.
Then:
: $\forall n \in \Z: a^n b = b a^{-n}$

Proof:
Proof by induction:
For all $n \in \Z$, let $\map P n$ be the proposition $a^n b = b a^{-n}$.
$\map P 0$ is trivially true, as $a^0 b = e b = b = b e = b a^{-0}$.
Theorem: Powers of Elements in Group Direct Product

Let $\struct {G, \circ_1}$ and $\struct {H, \circ_2}$ be group whose identities are $e_G$ and $e_H$.
Let $\struct {G \times H, \circ}$ be the group direct product of $G$ and $H$.
Then:
:$\forall n \in \Z: \forall g \in G, h \in H: \tuple {g, h}^n = \tuple {g^n, h^n}$

Proof:
Proof by induction:
For all $n \in \N$, let $\map P n$ be the proposition $\forall g \in G, h \in H: \tuple {g, h}^n = \tuple {g^n, h^n}$.
Theorem: General Morphism Property for Semigroups

Let $\struct {S, \circ}$ and $\struct {T, *}$ be semigroups.
Let $\phi: S \to T$ be a homomorphism.
Then:
:$\forall s_k \in S: \map \phi {s_1 \circ s_2 \circ \cdots \circ s_n} = \map \phi {s_1} * \map \phi {s_2} * \cdots * \map \phi {s_n}$
Hence it follows that:
:$\forall n \in \N_{>0}: \forall s \in S: \map \phi {s^n} = \paren {\map \phi s}^n$

Proof:
$\forall s_k \in S: \map \phi {s_1 \circ s_2 \circ \cdots \circ s_n} = \map \phi {s_1} * \map \phi {s_2} * \cdots * \map \phi {s_n}$ can be proved by induction.
For all $n \in \N_{>0}$, let $\map P n$ be the proposition:
:$\map \phi {s_1 \circ s_2 \circ \cdots \circ s_n} = \map \phi {s_1} * \map \phi {s_2} * \cdots * \map \phi {s_n}$
$P(1)$ is true, as this just says:
:$\map \phi {s_1} = \map \phi {s_1}$.
Theorem: Homomorphism of Power of Group Element

Let $\struct {G, \circ}$ and $\struct {H, \ast}$ be groups.
Let $\phi: S \to T$ be a group homomorphism.
Then:
:$\forall n \in \Z: \forall g \in G: \map \phi {g^n} = \paren {\map \phi g}^n$

Proof:
The result for $n \in \N_{>0}$ follows directly from General Morphism Property for Semigroups.
For $n = 0$, we use Homomorphism with Cancellable Codomain Preserves Identity.
For $n < 0$, we use Homomorphism with Identity Preserves Inverses, along with Index Laws for Monoids: Negative Index.
{{qed}}
Theorem: Existence of Unique Subsemigroup Generated by Subset

Let $\struct {S, \circ}$ be a semigroup.
Let $\O \subset X \subseteq S$.
Let $\struct {T, \circ}$ be the subsemigroup generated by $X$.
Then $T = \gen X$ exists and is unique.

Proof:
Let $\mathbb S$ be the set of all subsemigroups of $S$.
From Set of Subsemigroups forms Complete Lattice:
:$\struct {\mathbb S, \subseteq}$ is a complete lattice.
where for every set $\mathbb H$ of subsemigroups of $S$:
:the infimum of $\mathbb H$ necessarily admitted by $\mathbb H$ is $\ds \bigcap \mathbb H$.
Hence the result, by definition of infimum.
{{qed}}
Theorem: Finite Subgroup Test

Let $\struct {G, \circ}$ be a group.
Let $H$ be a non-empty finite subset of $G$.
Then:
:$H$ is a subgroup of $G$
{{iff}}:
:$\forall a, b \in H: a \circ b \in H$
That is, a non-empty finite subset of $G$ is a subgroup {{iff}} it is closed.

Proof:
Let $H$ be a finite subset of $G$ such that $a, b \in H \implies a \circ b \in H$.
From the Two-Step Subgroup Test, it follows that we only need to show that $a \in H \implies a^{-1} \in H$.
So, let $a \in H$.
First it is straightforward to show by induction that $\set {x \in G: x = a^n: n \in \N} \subseteq H$.
That is, $a \in H \implies \forall n \in \N: a^n \in H$.
Now, since $H$ is finite, we have that the order of $a$ is finite.
Let the order of $a$ be $m$.
From Inverse Element is Power of Order Less 1 we have that $a^{m-1} = a^{-1}$.
As $a^{m-1} \in H$ (from above) the result follows.
{{qed}}
Theorem: Finite Subgroup Test

Let $\struct {G, \circ}$ be a group.
Let $H$ be a non-empty finite subset of $G$.
Then:
:$H$ is a subgroup of $G$
{{iff}}:
:$\forall a, b \in H: a \circ b \in H$
That is, a non-empty finite subset of $G$ is a subgroup {{iff}} it is closed.

Proof:
=== Sufficient Condition ===
Let $H$ be a subgroup of $G$.
Then:
:$\forall a, b \in H: a \circ b \in H$
by definition of subgroup.
{{qed|lemma}}
=== Necessary Condition ===
Let $H$ be a non-empty finite subset of $G$ such that:
:$\forall a, b \in H: a \circ b \in H$
Let $x \in H$.
We have by hypothesis that $H$ is closed under $\circ$.
Thus all elements of $\set {x, x^2, x^3, \ldots}$ are in $H$.
But $H$ is finite.
Therefore it must be the case that:
:$\exists r, s \in \N: x^r = x^s$
for $r < s$.
So we can write:
{{begin-eqn}}
{{eqn | l = x^r
      | r = x^s
      | c = 
}}
{{eqn | ll= \leadsto
      | l = x^r \circ e
      | r = x^r \circ x^{s - r}
      | c = {{Defof|Identity Element}}, Powers of Group Elements: Sum of Indices
}}
{{eqn | n = 1
      | ll= \leadsto
      | l = e
      | r = x^{s - r}
      | c = Cancellation Laws
}}
{{eqn | ll= \leadsto
      | l = e
      | o = \in
      | r = H
      | c = as $H$ is closed under $\circ$
}}
{{end-eqn}}
Then we have:
{{begin-eqn}}
{{eqn | l = e
      | r = x^{s - r}
      | c = which is $(1)$
}}
{{eqn | ll= \leadsto
      | l = e
      | r = x \circ x^{s - r - 1}
      | c = as $H$ is closed under $\circ$
}}
{{eqn | ll= \leadsto
      | l = x^{-1} \circ e
      | r = x^{-1} \circ x \circ x^{s - r - 1}
      | c = 
}}
{{eqn | n = 2
      | ll= \leadsto
      | l = x^{-1}
      | r = x^{s - r - 1}
      | c = {{Defof|Inverse Element}}, {{Defof|Identity Element}}
}}
{{end-eqn}}
But we have that:
{{begin-eqn}}
{{eqn | l = r
      | o = <
      | r = s
      | c = by hypothesis
}}
{{eqn | ll= \leadsto
      | l = s - r
      | o = <
      | r = 0
}}
{{eqn | ll= \leadsto
      | l = s - r - 1
      | o = \le
      | r = 0
}}
{{eqn | ll= \leadsto
      | l = x^{s - r - 1}
      | o = \in
      | r = \set {e, x, x^2, x^3, \ldots}
      | c = 
}}
{{eqn | ll= \leadsto
      | l = x^{s - r - 1}
      | o = \in
      | r = H
      | c = as all elements of $\set {e, x, x^2, x^3, \ldots}$ are in $H$
}}
{{end-eqn}}
So from $(2)$:
:$x^{-1} = x^{s - r - 1}$
it follows that:
: $x^{-1} \in H$
and from the Two-Step Subgroup Test it follows that $H$ is a subgroup of $G$.
{{qed}}
Theorem: Powers of Element form Subgroup

Let $\struct {G, \circ}$ be a group.
Then:
:$\forall a \in G: H = \set {a^n: n \in \Z} \le G$
That is, the subset of $G$ comprising all elements possible as powers of $a \in G$ is a subgroup of $G$.

Proof:
Clearly $a \in H$, so $H \ne \O$.
Let $x, y \in H$.
{{begin-eqn}}
{{eqn | o = 
      | r = x, y \in H
      | c = 
}}
{{eqn | o = \leadsto
      | r = \exists m, n \in \Z: x = a^m, y = a^n
      | c = 
}}
{{eqn | o = \leadsto
      | r = x^{-1} y = \paren {a^m}^{-1} a^n
      | c = 
}}
{{eqn | o = \leadsto
      | r = x^{-1} y = a^{-m} a^n = a^{n-m}
      | c = 
}}
{{eqn | o = \leadsto
      | r = x^{-1} y \in H
      | c = 
}}
{{end-eqn}}
Thus by the One-Step Subgroup Test:
: $H \le G$
{{qed}}
Theorem: Existence of Unique Subgroup Generated by Subset

Let $\struct {G, \circ}$ be a group.
Let $\O \subset S \subseteq G$.
Let $\struct {H, \circ}$ be the subgroup generated by $S$.
Then $H = \gen S$ exists and is unique.
Also, $\struct {H, \circ}$ is the intersection of all of the subgroups of $G$ which contain the set $S$:
:$\ds \gen S = \bigcap_i {H_i}: S \subseteq H_i \le G$

Proof:
=== Existence ===
First, we prove that such a subgroup exists.
Let $\mathbb S$ be the set of all subgroups of $G$ which contain $S$.
$\mathbb S \ne \O$ because $G$ is itself a subgroup of $G$, and thus $G \in \mathbb S$.
Let $H$ be the intersection of all the elements of $\mathbb S$.
By Intersection of Subgroups is Subgroup, $H$ is the largest element of $\mathbb S$ contained in each element of $\mathbb S$.
Thus $H$ is a subgroup of $G$.
Since $\forall x \in \mathbb S: S \subseteq x$, we see that $S \subseteq H$, so $H \in \mathbb S$.
Theorem: Homomorphism of Generated Group

Let $\struct {G, \circ}$ and $\struct {H, \circ}$ be groups.
Let $\phi: G \to H$ and $\psi: G \to H$ be homomorphisms. 
Let $\gen S = G$ be the group generated by $S$.
Let:
:$\forall x \in S: \map \phi x = \map \psi x$
Then:
:$\phi = \psi$

Proof:
Let $H = \set {x \in G: \map \phi x = \map \psi x}$.
From Elements of Group with Equal Images under Homomorphisms form Subgroup, $H$ is a subgroup of $G$.
But from the definition of the group generated by $S$, the smallest subgroup that contains $S$ is $G$ itself.
Thus:
:$G = \set {x \in G: \map \phi x = \map \psi x}$
and so:
:$\phi = \psi$
{{Qed}}
Theorem: Set of Words Generates Group

Let $S \subseteq G$ where $G$ is a group.
Let $\hat S$ be defined as $S \cup S^{-1}$, where $S^{-1}$ is the set of all the inverses of all the elements of $S$.
Then $\gen S = \map W {\hat S}$, where $\map W {\hat S}$ is the set of words of $\hat S$.

Proof:
Let $H = \gen S$ where $S \subseteq G$.
$H$ must certainly include $\hat S$, because any group containing $s \in S$ must also contain $s^{-1}$.
Thus $\hat S \subseteq H$.
By {{Group-axiom|0}}, $H$ must also contain all products of a finite number of elements of $\hat S$.
Thus $\map W {\hat S} \subseteq H$.
Now we prove that $\map W {\hat S} \le G$.
By the Two-Step Subgroup Test:
Let $x, y \in \map W {\hat S}$.
As $x$ and $y$ are both products of a finite number of elements of $\hat S$, it follows that so is their product $x y$.
Thus $x y \in \map W {\hat S}$ and {{Group-axiom|0}} is satisfied.
Let $x = s_1 s_2 \ldots s_n \in \map W {\hat S}$.
Then $x^{-1} = s_n^{-1} \ldots s_2^{-1} s_1^{-1} \in \map W {\hat S}$.
Thus the conditions of the Two-Step Subgroup Test are fulfilled, and $\map W {\hat S} \le G$.
Thus $\map W {\hat S}$ is the subgroup of $G$ generated by $S$.
{{qed}}
Theorem: Subset Product is Subset of Generator

Let $\struct {G, \circ}$ be a group.
Let $X, Y \subseteq \struct {G, \circ}$.
Then $X \circ Y \subseteq \gen {X, Y}$ where:
:$X \circ Y$ is the Subset Product of $X$ and $Y$ in $G$.
:$\gen {X, Y}$ is the subgroup of $G$ generated by $X$ and $Y$.

Proof:
It is clear from Set of Words Generates Group that $\map W {\hat X \cup \hat Y} = \gen {X, Y}$.
It is equally clear that $X \circ Y \subseteq \map W {\hat X \cup \hat Y}$.
{{qed}}
Category:Group Theory
Category:Subset Products
3cekksmrfte9xtmhqnc5h4td9k4wcc6
Theorem: Order of Subset Product with Singleton

Let $\struct {G, \circ}$ be a group.
Let $X, Y \subseteq \struct {G, \circ}$ such that $X$ is a singleton:
:$X = \set x$
Then:
:$\order {X \circ Y} = \order Y = \order {Y \circ X}$
where $\order S$ is defined as the order of $S$.

Proof:
From Regular Representations of Subset Product, we have that the left regular representation of $\struct {S, \circ}$ with respect to $a$ is:
:$\lambda_x \sqbrk S = \set x \circ S = x \circ S$
The result then follows directly from Regular Representation of Invertible Element is Permutation.
{{qed}}
Theorem: Product of Subset with Intersection

Let $\struct {G, \circ}$ be an algebraic structure.
Let $X, Y, Z \subseteq G$.
Then:
:$X \circ \paren {Y \cap Z} \subseteq \paren {X \circ Y} \cap \paren {X \circ Z}$
:$\paren {Y \cap Z} \circ X \subseteq \paren {Y \circ X} \cap \paren {Z \circ X}$
where $X \circ Y$ denotes the subset product of $X$ and $Y$.

Proof:
Let $x \in X, t \in Y \cap Z$.
By the definition of intersection, $t \in Y$ and $t \in Z$.
Consider $X \circ \paren {Y \cap Z}$.
We have $x \circ t \in X \circ \paren {Y \cap Z}$ by definition of subset product.
As $t \in Y$ and $t \in Z$, we also have $x \circ t \in X \circ Y$ and $x \circ t \in X \circ Z$.
The result follows.
Similarly, consider $\paren {Y \cap Z} \circ X$.
Then we have $t \circ x \in \paren {Y \cap Z} \circ X$ by definition of subset product.
As $t \in Y$ and $t \in Z$, we also have $t \circ x \in Y \circ X$ and $t \circ x \in Z \circ X$.
Again, the result follows.
{{Qed}}
Theorem: Product of Subset with Intersection

Let $\struct {G, \circ}$ be an algebraic structure.
Let $X, Y, Z \subseteq G$.
Then:
:$X \circ \paren {Y \cap Z} \subseteq \paren {X \circ Y} \cap \paren {X \circ Z}$
:$\paren {Y \cap Z} \circ X \subseteq \paren {Y \circ X} \cap \paren {Z \circ X}$
where $X \circ Y$ denotes the subset product of $X$ and $Y$.

Proof:
Consider the relation $\RR \subseteq G \times G$ defined as:
:$\forall g, h \in G: \tuple {g, h} \in \RR \iff \exists g \in X$
Then:
:$\forall S \subseteq G: X \circ S = \RR \sqbrk S$
Then:
{{begin-eqn}}
{{eqn | l = X \circ \paren {Y \cap Z}
      | r = \RR \sqbrk {Y \cap Z}
      | c = 
}}
{{eqn | o = \subseteq
      | r = \RR \sqbrk Y \cap \RR \sqbrk Z
      | c = Image of Intersection under Relation
}}
{{eqn | r = \paren {X \circ Y} \cap \paren {X \circ Z}
      | c = 
}}
{{end-eqn}}
Next, consider the relation $\RR \subseteq G \times G$ defined as:
:$\forall g, h \in G: \tuple {g, h} \in \RR \iff \exists h \in X$
Then:
:$\forall S \subseteq G: S \circ X = \RR \sqbrk S$
Then:
{{begin-eqn}}
{{eqn | l = \paren {Y \cap Z} \circ X
      | r = \RR \sqbrk {Y \cap Z}
      | c = 
}}
{{eqn | o = \subseteq
      | r = \RR \sqbrk Y \cap \RR \sqbrk Z
      | c = Image of Intersection under Relation
}}
{{eqn | r = \paren {Y \circ X} \cap \paren {Z \circ X}
      | c = 
}}
{{end-eqn}}
{{qed}}
Theorem: Order of Subgroup Product

Let $G$ be a group.
Let $H$ and $K$ be subgroups of $G$.
Then:
:$\order {H K} = \dfrac {\order H \order K} {\order {H \cap K} }$
where:
:$H K$ denotes subset product
:$\order H$ denotes the order of $H$.
{{questionable|The {{RHS}} does not make sense if $\order {H \cap K} {{=}} +\infty$, because it is then $\dfrac {+\infty}{+\infty}$. Can someone check the source?}}

Proof:
From Intersection of Subgroups is Subgroup, we have that $H \cap K \le H$.
Let the number of left cosets of $H \cap K$ in $H$ be $r$.
Then the left coset space of $H \cap K$ in $H$ is:
: $\set {x_1 \paren {H \cap K}, x_2 \paren {H \cap K}, \ldots, x_r \paren {H \cap K} }$
So each element of $H$ is in $x_i \paren {H \cap K}$ for some $1 \le i \le r$.
Also, if $i \ne j$, we have:
:$x_j^{-1} x_i \notin H \cap K$
Let $h k \in H K$.
We can write $h = x_i g$ for some $1 \le i \le r$ and some $g \in K$.
Thus:
:$h k = x_i \paren {g k}$
Since $g, k \in K$, this shows $h k \in x_i K$.
{{AimForCont}} the left cosets $x_i K$ are not all disjoint.
Then by Left Coset Space forms Partition:
:$x_i K = x_j K$ for some $i, j$.
So by Left Congruence Class Modulo Subgroup is Left Coset:
:$x_j^{-1} x_i \in K$
Since $x_i, x_j \in H$, we have:
:$x_j^{-1} x_i \in H \cap K$
which contradicts the definition.
Therefore the left cosets $x_i K$ are disjoint for $1 \le i \le r$.
This leads us to:
:$\dfrac {\order H} {\order {H \cap K} } = \dfrac {\order {H K} } {\order K} = r$
whence the result.
{{qed}}
Theorem: Order of Subgroup Product

Let $G$ be a group.
Let $H$ and $K$ be subgroups of $G$.
Then:
:$\order {H K} = \dfrac {\order H \order K} {\order {H \cap K} }$
where:
:$H K$ denotes subset product
:$\order H$ denotes the order of $H$.
{{questionable|The {{RHS}} does not make sense if $\order {H \cap K} {{=}} +\infty$, because it is then $\dfrac {+\infty}{+\infty}$. Can someone check the source?}}

Proof:
=== Lemma ===
{{:Order of Subgroup Product/Lemma}}{{qed|lemma}}
We have that $H K$ is the union of all left cosets $h K$ with $h \in H$:
:$\ds H K = \bigcup_{h \mathop \in H} h K$
From Left Coset Space forms Partition, unequal $h K$ are disjoint.
From Cosets are Equivalent, each $h K$ contains $\order K$ elements.
From the Lemma, the number of different such left cosets is:
:$\index H {H \cap K}$
where $\index H {H \cap K}$ denotes the index of $H \cap K$ in $H$.
First, let $\order H < + \infty$.
Then, from Lagrange's Theorem:
$\index H {H \cap K} = \dfrac {\order H} {\order {H \cap K} }$
Hence:
:$\order {H K} = \dfrac {\order H \order K} {\order {H \cap K} }$
Finally, let $\order H = + \infty$.
Recall that $G$, $H$ and $K$ have the same identity element $e$ by Identity of Subgroup.
By {{Defof|Subset Product}}:
:$H = H \set e \subseteq H K$
In particular, $\order {H K} = + \infty$,
Hence:
:$\order {H K} = \dfrac {\order H \order K} {\order {H \cap K} } = + \infty$
{{finish|How to handle the case $\order {H \cap K} {{=}} +\infty$? The statement of the theorem leaves the ambiguity.}}