Dependencies

\((\forall x,\; x \cdot x = 1) \; \Longrightarrow \; G\) abelian. (Equivalently: a group of exponent \(2\) is commutative.)

\(a\mathbb {Z} + b\mathbb {Z} := \{ \, ra + sb : r, s \in \mathbb {Z} \, \} \).

\(a\mathbb {Z} + b\mathbb {Z}\) is an additive subgroup of \((\mathbb {Z}, +)\).

\(a\mathbb {Z} := \{ \, ka : k \in \mathbb {Z} \, \} \).

\(a\mathbb {Z} \cap b\mathbb {Z}\) is an additive subgroup of \((\mathbb {Z}, +)\).

\(a\mathbb {Z}\) is an additive subgroup of \((\mathbb {Z}, +)\).

Bézout: \(d = \gcd (a, b) \; \Longrightarrow \; \exists r, s : ra + sb = d\).

Bool is abelian (the smallest non-trivial abelian group, \(\mathbb {Z}/2\mathbb {Z}\)).

\(\mathbb {Z}/2\mathbb {Z}\): Bool under XOR, identity false, every element self-inverse.

The trivial subgroup is normal.

\(Z(G) := \{ \, z : \forall x,\; z \cdot x = x \cdot z \, \} \), the center of \(G\), as a subgroup.

\(G\) is abelian \(\; \Longleftrightarrow \; Z(G) = G\).

The center is a normal subgroup: \(Z(G) \triangleleft G\).

\(C_G(a) := \{ \, g \in G : g \cdot a = a \cdot g \, \} \), the centralizer of \(a\), as a subgroup of \(G\).

\(g \cdot h \cdot g^{-1} = h\) in an abelian group (conjugation is trivial).

\((a \cdot b)^{-1} = a^{-1} \cdot b^{-1}\) in an abelian group.

\((g \cdot h)^n = g^n \cdot h^n\) in an abelian group.

For each \(g \in G\), conjugation by \(g\), \(\mathrm{conj}_g : G \to G,\; x \mapsto g \cdot x \cdot g^{-1}\), is a group homomorphism (an inner automorphism of \(G\)).

Universality of \(\gcd \): any common divisor of \(a, b\) divides \(\gcd (a, b)\).

If \(m = \mathrm{lcm}(a, b)\), then both \(a\) and \(b\) divide \(m\) (Proposition 1.2.7(a)).

Euclid’s lemma: \(p\) prime, \(p \mid ab \; \Longrightarrow \; p \mid a \; \vee \; p \mid b\).

\(d = \gcd (a, b) \; \Longrightarrow \; d \mid a \; \wedge \; d \mid b\).

\(\gcd (a, b) \cdot \mathrm{lcm}(a, b) = |a \cdot b|\) for \(a, b\) both nonzero (Corollary 1.2.8).

\(\sigma ^{-1}\): swap \(\sigma .\mathrm{toFun}\) and \(\sigma .\mathrm{invFun}\).

\(\sigma \cdot \tau := \sigma \circ \tau \) on \(\mathrm{Perm}\ \alpha \).

\(\mathrm{Perm}\, \alpha \) is a group under composition.

\(1 := \mathrm{id}\) on \(\mathrm{Perm}\ \alpha \).

The inverse map is injective: \(a^{-1} = b^{-1} \; \Longrightarrow \; a = b\).

\((a^{-1})^{-1} = a\).

\(b \cdot a = 1 \; \Longrightarrow \; b = a^{-1}\).

\(S \subseteq \mathbb {Z}\) is an additive subgroup of \((\mathbb {Z}, +)\): closed under \(0\), \(+\), and negation.

Classification of subgroups of \((\mathbb {Z}, +)\): every additive subgroup equals \(a\mathbb {Z}\) for some \(a \geq 0\).

\(a, b\) are coprime if \(\gcd (a, b) = 1\).

\(a, b\) coprime \(\; \Longleftrightarrow \; \exists r, s : ra + sb = 1\).

\(\exists g \in G,\; \forall x \in G,\; x \in \langle g \rangle \) (i.e. \(G = \langle g \rangle \) for some \(g\)).

A dihedral presentation of degree \(n\) on \(G\): distinguished generators \(r, s\) with \(r^n = 1\), \(s^2 = 1\), and \(s \cdot r = r^{-1} \cdot s\).

Distinguished rotation \(r \in G\).

\(r^n = 1\).

Distinguished reflection \(s \in G\).

\(s = s^{-1}\): the reflection is an involution.

\(s \cdot r = r^{-1} \cdot s\).

\(s^2 = 1\).

\(d\) is a \(\gcd \) of \(a, b\): \(d \geq 0\) and \(d\mathbb {Z} = a\mathbb {Z} + b\mathbb {Z}\).

\(m\) is an \(\mathrm{lcm}\) of \(a, b\): \(m \geq 0\) and \(m\mathbb {Z} = a\mathbb {Z} \cap b\mathbb {Z}\).

\(H \triangleleft G\): \(\forall g \in G,\, h \in H,\; g \cdot h \cdot g^{-1} \in H\).

Intersection of two normal subgroups is normal.

\(n {\gt} 0 \; \wedge \; g^n = 1 \; \wedge \; (\forall k,\; 0 {\lt} k {\lt} n \Longrightarrow g^k \neq 1)\).

\(\mathrm{IsOrderOf}\, 1\, 1\).

Proposition 1.3.11: if \(\mathrm{ord}(g) = n\), then \(\mathrm{ord}(g^k) = n / \gcd (n, k)\).

Corollary 1.3.12: in \(\langle g \rangle \) with \(\mathrm{ord}(g) = n\), the power \(g^k\) has the same order \(n\) — i.e. generates the same cyclic subgroup — iff \(\gcd (n, k) = 1\).

\(\mathrm{IsOrderOf}\, g\, m \; \wedge \; \mathrm{IsOrderOf}\, g\, n \; \Longrightarrow \; m = n\).

Universality of \(\mathrm{lcm}\): if \(a \mid n\) and \(b \mid n\), then \(\mathrm{lcm}(a, b) \mid n\) (Proposition 1.2.7(b)).

A left inverse and a right inverse of the same element are equal: if \(\ell \cdot a = 1\) and \(a \cdot r = 1\), then \(\ell = r\).

\(a \cdot b = c \; \Longleftrightarrow \; a = c \cdot b^{-1}\) — the basic rearrangement move.

\(a \cdot b = a \; \Longleftrightarrow \; b = 1\) (the second form of the cancellation law).

\((a \cdot b)^{-1} = b^{-1} \cdot a^{-1}\).

\(a \cdot b = a \cdot c \; \Longrightarrow \; b = c\).

\(\forall a,\; a \cdot 1 = a\).

\(b \cdot a = c \cdot a \; \Longrightarrow \; b = c\).

\(\forall a,\; a \cdot a^{-1} = 1\).

A group with \(\forall a, b,\; a \cdot b = b \cdot a\).

Commutativity: \(\forall a, b,\; a \cdot b = b \cdot a\).

A type \(G\) with \(\cdot : G \times G \to G\), identity \(1\), and inverse \((-)^{-1}\) satisfying associativity, left identity \(1 \cdot a = a\), and left inverse \(a^{-1} \cdot a = 1\). The right-handed duals follow as theorems.

Associativity: \(\forall a, b, c,\; (a \cdot b) \cdot c = a \cdot (b \cdot c)\).

Left inverse: \(\forall a,\; a^{-1} \cdot a = 1\).

Left identity: \(\forall a,\; 1 \cdot a = a\).

A group homomorphism \(\varphi : G \to G'\).

Composition of homomorphisms is a homomorphism: \((\psi \circ \varphi )(a) := \psi (\varphi (a))\).

The identity homomorphism \(\mathrm{id}_G : G \to G\).

\(\mathrm{im}\, \varphi \) as a subgroup of \(G'\).

Image of a subgroup \(H \leq G\) under \(\varphi \): \(\varphi (H) := \{ \, \varphi (h) : h \in H \, \} \leq G'\). Specializes to 102 at \(H = \top \).

\(\varphi \) injective \(\; \Longleftrightarrow \; \ker \varphi = \{ 1\} \).

\(\varphi (a^{-1}) = \varphi (a)^{-1}\): homomorphisms preserve inverses.

\(\ker \varphi \) as a subgroup of \(G\).

Kernels are normal: \(\ker \varphi \triangleleft G\).

Kernel test: \(\varphi (a) = \varphi (b) \; \Longleftrightarrow \; a^{-1} \cdot b \in \ker \varphi \).

Multiplicativity: \(\forall a, b,\; \varphi (a \cdot b) = \varphi (a) \cdot \varphi (b)\).

\(\varphi (1) = 1\): homomorphisms preserve the identity.

\(\varphi (a^n) = \varphi (a)^n\) for \(n : \mathbb {N}\): homomorphisms preserve natural-number powers.

Preimage of a subgroup \(K \leq G'\) under \(\varphi \): \(\varphi ^{-1}(K) := \{ \, x \in G : \varphi (x) \in K \, \} \leq G\). Specializes to 103 at \(K = \bot \).

Preimage of a normal subgroup under a homomorphism is normal: \(K \triangleleft G' \; \Longrightarrow \; \varphi ^{-1}(K) \triangleleft G\).

Underlying function \(G \to G'\).

The trivial homomorphism \(\tau : G \to G',\; x \mapsto 1\).

A group isomorphism: a homomorphism bundled with a two-sided inverse function.

Composition of isomorphisms is an isomorphism.

The identity isomorphism \(\mathrm{id}_G : G \xrightarrow {\sim } G\).

Two-sided inverse function \(G' \to G\).

Left inverse: \(\forall x,\; \mathrm{invFun}(\mathrm{toFun}\, x) = x\).

Right inverse: \(\forall y,\; \mathrm{toFun}(\mathrm{invFun}\, y) = y\).

The inverse isomorphism \(e^{-1} : G' \xrightarrow {\sim } G\).

A predicate \(H : G \to \mathrm{Prop}\) with \(1 \in H\), closed under \(\cdot \) and \((-)^{-1}\).

\(\bot := \{ 1\} \) (the trivial subgroup).

Closure of \(U\) under \(1\), \(\cdot \) and \((-)^{-1}\) — the underlying predicate of \(\langle U \rangle \).

Subgroup criterion: a non-empty \(P : G \to \mathrm{Prop}\) closed under \(a, b \mapsto a \cdot b^{-1}\) is a subgroup. (One-shot test in place of checking \(1 \in P\), closure under \(\cdot \), closure under \((-)^{-1}\) separately.)

\(\langle g \rangle \): the cyclic subgroup generated by \(g\).

Proposition 1.3.3: \(\langle g \rangle \) is the smallest subgroup containing \(g\). Concretely: any subgroup \(H\) containing \(g\) also contains \(\langle g \rangle \).

The closure of \(\{ g\} \) under \(1\), \(\cdot \), and \((-)^{-1}\) — the underlying predicate of \(\langle g \rangle \).

\(\langle U \rangle \): the subgroup generated by \(U \subseteq G\).

\(\langle U \rangle \) is the smallest subgroup containing \(U\): \(U \subseteq H \; \Longrightarrow \; \langle U \rangle \subseteq H\).

The intersection of an arbitrary family of subgroups is a subgroup.

\(H \cap K\) is a subgroup.

\(\forall n : \mathbb {N},\; g^n \in \langle g \rangle \).

\(g \in \langle g \rangle \).

\(U \subseteq \langle U \rangle \).

\(\top := G\) (the whole group as a subgroup of itself).

\(H\) is normal in \(G\) iff its normalizer is all of \(G\): \(H \triangleleft G \; \Longleftrightarrow \; \forall g \in G,\; g \in N_G(H)\).

In an abelian group, every subgroup is normal.

\(N_G(H) := \{ \, g : \forall h,\; h \in H \iff g h g^{-1} \in H \, \} \), the normalizer of \(H\) in \(G\), as a subgroup.

\(g^n\): product of \(n\) copies of \(g\) on the right of \(1\).

The identity is its own inverse: \(1^{-1} = 1\).

\((\forall a,\; e \cdot a = a) \; \Longrightarrow \; e = 1\).

A bijection \(\alpha \to \alpha \): a forward function paired with a two-sided inverse.

\(\sigma .\mathrm{toFun} = \tau .\mathrm{toFun} \; \Longrightarrow \; \sigma = \tau \).

Sign of a permutation of Bool, valued in Bool_group: identity \(\mapsto \) false (\(+1\)); swap \(\mapsto \) true (\(-1\)).

Sign is a group homomorphism on \(\mathrm{Perm}(\mathrm{Bool})\): \(\mathrm{sgn}(\sigma \cdot \tau ) = \mathrm{sgn}(\sigma ) \cdot \mathrm{sgn}(\tau )\) (the right-hand multiplication is XOR in Bool_group).

\(\mathrm{sgn}(1) = +1\).

\(\mathrm{sgn}(\mathrm{swap}) = -1\).

\(g^{m+n} = g^m \cdot g^n\).

If \(n\) is the order of \(g\), then \(g^m = 1 \; \Longleftrightarrow \; n \mid m\).

Proposition 1.3.6(b) (Nat form): for \(k \leq \ell \), \(g^k = g^\ell \; \Longleftrightarrow \; \mathrm{ord}(g) \mid (\ell - k)\).

\((g^m)^n = g^{m \cdot n}\).

\(g^{n+1} = g^n \cdot g\).

\(g^0 = 1\).

\(b \cdot a = a \; \Longleftrightarrow \; b = 1\) (the dual cancellation statement on the left).

Proposition 1.3.14(a): every subgroup of a cyclic group is cyclic.

Stated for a subgroup \(H \subseteq \langle g \rangle \) of an ambient cyclic-style subgroup: there exists \(g' \in H\) such that \(H = \langle g' \rangle \) — i.e. \(H\) is itself cyclic, generated by some element of \(H\).

Every subgroup is contained in its own normalizer: \(H \subseteq N_G(H)\).

The swap on Bool: a concrete permutation exchanging true and false.

\(\mathrm{swap} \cdot \mathrm{swap} = 1\).

The whole group is normal in itself.

The trivial group: Unit with its single element.