avewright/proofwiki-math huggingface dataset:
Theorem: Equivalent Characterizations of Nonsingular Matrix

Let $\mathbf A$ be a square matrix of order $n$ over a field $K$.
{{TFAE}}
:$(1):\quad$ $\mathbf A$ is nonsingular
:$(2):\quad$ The transpose of $\mathbf A$ is nonsingular
:$(3):\quad$ $\mathbf A$ row-reduces to the identity matrix $\mathbf I_n$
:$(4):\quad$ The null space of $\mathbf A$ contains only the zero vector $\mathbf 0$
:$(5):\quad$ The homogeneous linear system $\mathbf A \mathbf x = \mathbf 0$ has only the trivial solution $\mathbf 0$
:$(6):\quad$ The linear system $\mathbf A \mathbf x = \mathbf b$ has a unique solution for every possible choice of $\mathbf b$
:$(7):\quad$ The columns of $\mathbf A$ are linearly independent
:$(8):\quad$ The column space of $\mathbf A$ is $K^n$
:$(9):\quad$ The columns of $\mathbf A$ are a basis for $K^n$
:$(10):\quad$ The rows of $\mathbf A$ are linearly independent
:$(11):\quad$ The row space of $\mathbf A$ is $K^n$
:$(12):\quad$ The rows of $\mathbf A$ are a basis for $K^n$
:$(13):\quad$ The rank of $\mathbf A$ is $n$
:$(14):\quad$ The nullity of $\mathbf A$ is zero
:$(15):\quad$ The determinant of $\mathbf A$ is not zero
:$(16):\quad$ $0_K$ is not an eigenvalue of $\mathbf A$

Proof:
=== $(3)$ iff $(5)$ ===
See Elementary Row Operation on Augmented Matrix leads to Equivalent System of Simultaneous Linear Equations/Corollary 5.
{{qed|lemma}}
Theorem: Mapping on Integers is Endomorphism of Max or Min Operation iff Increasing

Let $\Z$ denote the set of integers.
Let $f: \Z \to \Z$ be a mapping on $\Z$.
Let $\vee$ and $\wedge$ be the max operation and min operation on $\Z$ defined as:
{{begin-eqn}}
{{eqn | q = \forall x, y \in \Z
      | l = x \vee y
      | r = \max \set {x, y}
}}
{{eqn | l = x \wedge y
      | r = \min \set {x, y}
}}
{{end-eqn}}
Then:
:$f$ is an endomorphism of $\struct {\Z, \vee}$ or $\struct {\Z, \wedge}$
{{iff}}:
:$f$ is an increasing mapping.

Proof:
=== Necessary Condition ===
Suppose $f$ is an increasing mapping.
Let $x, y \in \Z$ and suppose $x \le y$.
By definition of an increasing mapping, we have $\map f x \le \map f y$.
Therefore:
:$\map f x \vee \map f y = \map f y = \map f {x \vee y}$
:$\map f x \wedge \map f y = \map f x = \map f {x \wedge y}$
Hence $f$ is an endomorphism of $\struct {\Z, \vee}$ ''and'' $\struct {\Z, \wedge}$.
As Conjunction implies Disjunction,  $f$ is an endomorphism of $\struct {\Z, \vee}$ or $\struct {\Z, \wedge}$.
{{qed|lemma}}
Theorem: Mapping on Integers is Homomorphism between Max or Min Operation iff Decreasing

Let $\Z$ denote the set of integers.
Let $f: \Z \to \Z$ be a mapping on $\Z$.
{{MissingLinks|min and max operations are defined on PW}}
Let $\vee$ and $\wedge$ be the operations on $\Z$ defined as:
{{begin-eqn}}
{{eqn | q = \forall x, y \in \Z
      | l = x \vee y
      | r = \max \set {x, y}
}}
{{eqn | l = x \wedge y
      | r = \min \set {x, y}
}}
{{end-eqn}}
Then:
:$f$ is a homomorphism either from $\struct {\Z, \vee}$ to $\struct {\Z, \wedge}$ or from $\struct {\Z, \wedge}$ to $\struct {\Z, \vee}$
{{iff}}:
:$f$ is a decreasing mapping.

Proof:
=== Necessary Condition ===
Let $f$ be a decreasing mapping.
Let $x, y \in \Z$ such that $x \le y$.
By definition of a decreasing mapping, we have $\map f x \ge \map f y$.
Therefore:
:$\map f x \vee \map f y = \map f x = \map f {x \wedge y}$
:$\map f x \wedge \map f y = \map f y = \map f {x \vee y}$
Hence:
:$f$ is a homomorphism from $\struct {\Z, \vee}$ to $\struct {\Z, \wedge}$
and also:
:$f$ is a homomorphism from $\struct {\Z, \wedge}$ to $\struct {\Z, \vee}$
As Conjunction implies Disjunction,  $f$ is a homomorphism from $\struct {\Z, \vee}$ to $\struct {\Z, \wedge}$ or from $\struct {\Z, \wedge}$ to $\struct {\Z, \vee}$.
{{qed|lemma}}
Theorem: Inner Automorphism Maps Subgroup to Itself iff Normal/Sufficient Condition

Let $G$ be a group.
For $x \in G$, let $\kappa_x$ denote the inner automorphism of $x$ in $G$.
Let $H$ be a normal subgroup of $G$.
Then:
:$\forall x \in G: \kappa_x \sqbrk H = H$

Proof:
Let $H$ be a normal subgroup of $G$.
Let $x \in G$ be arbitrary.
By definition, $\kappa_x: G \to G$ is a mapping defined as:
:$\forall g \in G: \map {\kappa_x} g = x g x^{-1}$
Let $n \in N$.
Then:
{{begin-eqn}}
{{eqn | l = \map {\kappa_x} n
      | r = x n x^{-1}
      | c = 
}}
{{eqn | o = \in
      | r = N
      | c = {{Defof|Normal Subgroup}}
}}
{{end-eqn}}
Theorem: Inner Automorphism Maps Subgroup to Itself iff Normal/Necessary Condition

Let $G$ be a group.
For $x \in G$, let $\kappa_x$ denote the inner automorphism of $x$ in $G$.
Suppose that:
:$\forall x \in G: \kappa_x \sqbrk H = H$
Then $H$ is a normal subgroup of $G$.

Proof:
Suppose that:
:$\forall x \in G: \kappa_x \sqbrk H = H$
Let $x \in G$ be arbitrary.
By definition of inner automorphism of $x$ in $G$:
:$\forall h \in H: x h x^{-1} \in H$
So, by definition, $H$ is a normal subgroup of $G$
Theorem: Subset of Domain is Subset of Preimage of Image/Equality does Not Necessarily Hold

It is not necessarily the case that:
:$A \subseteq S \implies A = \paren {f^{-1} \circ f} \sqbrk A$

Proof:
Proof by Counterexample:
Let:
:$S = \set {0, 1}$
:$T = \set 2$
Let $f: S \to T$ be defined as:
:$\map f 0 = 2$
:$\map f 1 = 2$
Let $A \subseteq S$ be defined as:
:$A = \set 0$
Then we have:
:$f \sqbrk A = \set 2$
but:
:$f^{-1} \circ f \sqbrk A = f^{-1} \sqbrk 2 = \set {0, 1}$
That is:
:$A \subseteq \paren {f^{-1} \circ f} \sqbrk A$
but it is not the case that:
:$A \paren {f^{-1} \circ f} \sqbrk A$
{{qed}}
Theorem: Number times Recurring Part of Reciprocal gives 9-Repdigit/Generalization

Let $M$ be an arbitrary integer.
Then:
:$M \equiv \sqbrk {mmm \dots m} \pmod {10^c}$
for some positive integer $c$, {{iff}}:
:$M \times n \equiv -1 \pmod {10^c}$
In other words, the last $c$ digits of $M$ coincide with that of $\sqbrk {mmm \dots m}$ {{iff}} the last $c$ digits of $M \times n$ are all $9$s.

Proof:
$\sqbrk {mmm \dots m}$ can be expressed as:
:$\ds \sum_{k \mathop = 0}^{K - 1} m 10^{k d}$
for some sufficiently large $K > \dfrac c d$.
Theorem: Midy's Theorem

Let $p$ be a prime.
Let $a \in \set {1, 2, \ldots, p - 1}$ and $b > 1$ be integers.
Let $N$ be the recurring part of the expansion of $\dfrac a p$ in base $b$.
Let $\alpha$ be the period of recurrence of $N$.
Let $\alpha = c k$ for (strictly) positive integers $c > 1$ and $k$.
Then $N$ is divisible by $b^k - 1$.
Moreover, let $N = \ds \sum_{i \mathop = 1}^c N_i \paren {b^k}^i$ for $N_i \in \set {0, 1, \ldots b^k - 1}$.
Then:
:$\ds \sum_{i \mathop = 1}^c N_i = r \paren {b^k - 1}$ for some $r \in \set {1, 2, \ldots, c - 1}$

Proof:
=== $N$ is divisible by $b^k - 1$ ===
By definition of recurrence, we have:
:$\dfrac a p b^\alpha = N + \dfrac a p$
Moreover, by definition of period of recurrence, $\alpha$ is the smallest positive integer for which this is true.
Rearranging, we obtain:
:$\dfrac a p \paren {b^\alpha - 1} = N$
In particular, $a \paren {b^\alpha - 1}$ is divisible by $p$.
As $p$ is prime:
:$p \divides a$ or $p \divides \paren {b^\alpha - 1}$
The former is false because $0 < a < p$. 
Therefore, we must have $p \divides \paren {b^\alpha - 1}$.
If $\alpha = c k$ with $c > 1$, then $b^\alpha - 1 = \paren {b^k - 1} m$ for some integer $m$.
As $p$ is prime:
:$p \divides b^k - 1$ or $p \divides m$
The former is false because $0 < k < \alpha$ and $\alpha$ is the smallest positive integer for which this is true. 
Therefore, we must have $p \divides m$.
This implies that $a \dfrac m p$ is an integer.
We then have:
:$a \dfrac m p \paren {b^k - 1} = N$
By definition, $N$ is divisible by $b^k - 1$.
{{qed|lemma}}
Theorem: Normal Subgroup which is Subset of Normal Subgroup is Normal in Subgroup

Let $G$ be a group.
Let $H$ and $K$ be normal subgroups of $G$.
Let $H \subseteq K$.
Then $H$ is a normal subgroup of $K$.

Proof:
{{begin-eqn}}
{{eqn | q = \forall g \in G
      | l = g K
      | r = K g
      | c = {{Defof|Normal Subgroup}}
}}
{{eqn | q = \forall g \in G
      | l = g H
      | r = H g
      | c = {{Defof|Normal Subgroup}}
}}
{{eqn | ll= \leadsto
      | q = \forall g \in K
      | l = g H
      | r = H g
      | c = as $K \subseteq G$
}}
{{end-eqn}}
Hence the result by definition of normal subgroup.
{{qed}}
Theorem: Exist Term in Arithmetic Sequence Divisible by Number

Let $\sequence {a_k}$ be an $n$-term arithmetic sequence in $\Z$ defined by:
:$a_k = a_0 + k d$
for $k = 0, 1, 2, \ldots, n - 1$.
Let $b$ be a (strictly) positive integer such that $b$ and $d$ are coprime and $b \le n$.
Then there exists a term in $\sequence {a_k}$ that is divisible by $b$.

Proof:
We claim that at least one of the first $b$ terms:
:$a_0, a_0 + d, a_0 + 2 d, \dots, a_0 + \paren {b - 1} d$
is divisible by $b$.
Let $S$ be the set of remainders of each term after division by $b$.
$S$ can take on values of $0 \le r < b$.
If $0 \in S$ then the proof is complete.
{{AimForCont}} that $0 \ne S$.
Since there are $b$ terms but only $b - 1$ possible remainders, by Pigeonhole Principle at least two terms must share a remainder.
That is:
:$a_0 + i d \equiv a_0 + j d \pmod b$
for some $i, j$ where and $0 \le i < j \le b - 1$.
But then:
:$\paren {j - i} d \equiv 0 \pmod b$
so $b \divides \paren {j - i} d$.
Since $b \perp d$, by Euclid's Lemma we have $b \divides \paren {j - i}$.
Since $0 < j - i < b$ we must have $b \nmid \paren {j - i}$ by Absolute Value of Integer is not less than Divisors.
This is a contradiction.
Therefore there is at least one term that is divisible by $b$.
{{qed}}
{{expand|Proof based on $d$ coprime with $b$ is invertible in $\struct {\Z_b, \times}$ so that we can take $d^{-1}a_0 \pmod b$ for $k$}}
Category:Arithmetic Sequences
Category:Divisibility
d04q4q7cae4s13kqdtqbyj78no3otpf
Theorem: Equivalence Relation induced by Congruence Relation on Quotient Structure is Congruence

Let $\struct {A, \oplus}$ be an algebraic structure.
Let $\RR$ be a congruence relation on $\struct {A, \oplus}$.
Let $\SS$ be a congruence relation on the quotient structure $\struct {A / \RR, \oplus_\RR}$ defined by $\RR$.
Let $\TT$ be the relation on $A$ defined as:
:$\forall x, y \in A: x \mathrel \TT y \iff \eqclass x \RR \mathrel \SS \eqclass y \RR$
Then:
:$\TT$ is a congruence relation on $\struct {A, \oplus}$
and:
:there exists a unique isomorphism $\phi$ from $\paren {A / \RR} / \SS$ to $A / \TT$ which satisfies:
::$\phi \circ q_\SS \circ q_\RR = q_\TT$
:where $q_\SS$, $q_\RR$ and $q_\TT$ denote the quotient epimorphisms as appropriate.

Proof:
Recall that by definition $\RR$ and $\SS$ are {{afortiori}} equivalence relations.
First it is demonstrated that $\TT$ is an equivalence relation.
Checking in turn each of the criteria for equivalence:
Theorem: Existence of Niven Number for Any Sum of Digits

Let $b, s$ be integers such that $b > 1$ and $s > 0$.
Then there exists a Niven Number in base $b$ with sum of digits $s$.

Proof:
Consider the prime factorization of $b$:
:$b = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}$
where $a_1, a_2, \dots, a_k \ge 1$.
Write:
:$s = p_1^{c_1} p_2^{c_2} \dots p_k^{c_k} t$
where $b$ and $t$ are coprime.
Let $c = \max \set {c_1, c_2, \dots, c_k}$.
We will show that the number:
:$n = b^c \paren {b^{\map \phi t} + b^{2 \map \phi t} + \dots + b^{s \map \phi t} }$
is a Niven Number in base $b$, where $\map \phi t$ denotes the Euler totient function.
Notice that $n$ is a sum of distinct powers of $b$.
By Basis Representation Theorem, we can write:
:$\ds n = \sum_{j \mathop = 0}^d r_j b^j$
and we see that:
:$r_j = 1$ for $j = c + x \map \phi t$ for $x = 1, 2, \dots, s$
:$r_j = 0$ otherwise
Therefore the base $b$ representation of $n$ contains $s$ $1$'s and all other digits are zero.
Thus the sum of digits of $n$ in base $b$ is $s$.
It remains to show that $n$ is divisible by $s$.
We have:
:$c_i \le c \le a_1 c$
for any $1 \le i \le k$.
Thus we have, by Product of Divisors is Divisor of Product:
:$\dfrac s t = p_1^{c_1} p_2^{c_2} \dots p_k^{c_k} \divides p_1^{a_1 c} p_2^{a_2 c} \dots p_k^{a_k c} = b^c$
We also have:
{{begin-eqn}}
{{eqn | l = b^{\map \phi t} + b^{2 \map \phi t} + \dots + b^{s \map \phi t}
      | o = \equiv
      | r = 1 + 1^2 + \dots + 1^s
      | rr= \pmod t
      | c = Euler's Theorem (Number Theory), Congruence of Powers
}}
{{eqn | o = \equiv
      | r = s
      | rr= \pmod t
      | c = 
}}
{{eqn | o = \equiv
      | r = 0
      | rr= \pmod t
      | c = because $t \divides s$
}}
{{end-eqn}}
and thus $t \divides b^{\map \phi t} + b^{2 \map \phi t} + \dots + b^{s \map \phi t}$.
By Product of Divisors is Divisor of Product again:
:$s = \dfrac s t \times t \divides b^c \paren {b^{\map \phi t} + b^{2 \map \phi t} + \dots + b^{s \map \phi t} } = n$
Hence the result.
{{qed}}
Theorem: Divisibility of Common Difference of Arithmetic Sequence of Primes

If $n$ terms of an arithmetic sequence are primes, then the common difference must be divisible by all primes less than $n$.

Proof:
{{WLOG}} suppose the arithmetic sequence is increasing.
We also disregard the trivial case of zero common difference (do note that the theorem also holds in this case).
The proof proceeds by induction:
Theorem: Quotient Theorem for Group Homomorphisms/Corollary 2

Let $\struct {G, \odot}$ and $\struct {H, *}$ be groups whose identities are $e_G$ and $e_H$ respectively.
Let $\phi: G \to H$ be a group epimorphism.
Let $K$ be the kernel of $\phi$.
Let $N$ be a normal subgroup of $G$.
Let $q_N: G \to G / N$ denote the quotient epimorphism from $G$ to the quotient group $G / N$.
Then:
:$N \subseteq K$
{{iff}}:
:there exists a group epimorphism $\psi: G / N \to H$ such that $\phi = \psi \circ q_N$

Proof:
From {{Corollary|Quotient Theorem for Group Homomorphisms|1}}:
:$N \subseteq K$
{{iff}}:
:there exists a group homomorphism $\psi: G / N \to H$ such that $\phi = \psi \circ q_N$
From Surjection if Composite is Surjection, it follows that the group homomorphism $\psi$ is a surjection.
Hence by definition, $\psi$ is an epimorphism.
{{qed}}
Theorem: Quotient Theorem for Group Homomorphisms/Corollary 2

Let $\struct {G, \odot}$ and $\struct {H, *}$ be groups whose identities are $e_G$ and $e_H$ respectively.
Let $\phi: G \to H$ be a group epimorphism.
Let $K$ be the kernel of $\phi$.
Let $N$ be a normal subgroup of $G$.
Let $q_N: G \to G / N$ denote the quotient epimorphism from $G$ to the quotient group $G / N$.
Then:
:$N \subseteq K$
{{iff}}:
:there exists a group epimorphism $\psi: G / N \to H$ such that $\phi = \psi \circ q_N$

Proof:
Let $e$ be the identity element of $G$.
Let $\RR$ be the congruence relation defined by $N$ in $G$.
Let $\RR_\phi$ be the equivalence relation induced by $\phi$.
From Condition for Existence of Epimorphism from Quotient Structure to Epimorphic Image:
:there exists an epimorphism $\psi$ from $G / N$ to $H$ which satisfies $\psi \circ q_N = \phi$
{{iff}}:
:$\RR \subseteq \RR_\phi$
It remains to be shown that:
:$\RR \subseteq \RR_\phi$
{{iff}}:
:$N \subseteq K$
{{finish}}
Theorem: Arzelà-Ascoli Theorem

Let $X$ be a compact Hausdorff space.
Let $Y$ be a metric space.
Let $\CC$ be the set of all continuous functions $X \to Y$.
Consider $\CC$ as a metric space with the supremum metric:
:$\ds \map {d_\infty} {f, g} := \sup_{x \mathop \in X} \map d {\map f x, \map g x}$
Then a set $F \subseteq \CC$ is relatively compact {{iff}} it is pointwise equicontinuous and pointwise relatively compact.

Proof:
=== Pointwise properties imply relative compactness ===
By Sequentially Compact Metric Space is Compact, it suffices to show that every sequence in $F$ has a uniformly convergent subsequence.
Note that the limit need not lie in $F$.
For the proof, we will first construct a set $P \subseteq X$ which we will use like a countable dense subset.
Then we will use $P$ to construct a subsequence of any given sequence in $F$.
This subsequence will yield the result.
{{qed|lemma}}
Theorem: Group Epimorphism Preserves Subgroups

Let $\struct {G_1, \circ}$ and $\struct {G_2, *}$ be groups.
Let $\phi: \struct {G_1, \circ} \to \struct {G_2, *}$ be a group epimorphism.
Then:
:$H \le G_1 \implies \phi \sqbrk H \le G_2$
where:
:$\phi \sqbrk H$ denotes the image of $H$ under $\phi$
:$\le$ denotes subgroup.
That is, group epimorphism preserves subgroups.

Proof:
By definition, $\phi$ is {{afortiori}} a group homomorphism.
The result then follows from Group Homomorphism Preserves Subgroups.
{{qed}}
Theorem: Preimage of Image of Subgroup under Group Epimorphism

Let $\struct {G_1, \circ}$ and $\struct {G_2, *}$ be groups.
Let $\phi: \struct {G_1, \circ} \to \struct {G_2, *}$ be a group epimorphism.
Let $K = \map \ker \phi$ denote the kernel of $\phi$.
Then:
:$\phi^{-1} \sqbrk {\phi \sqbrk H} = H \circ K$
where:
:$\phi \sqbrk H$ denotes the image of $H$ under $\phi$
:$\phi^{-1} \sqbrk {\phi \sqbrk H}$ denotes the preimage of $\phi \sqbrk H$ under $\phi$
:$H \circ K$ denotes the subset product of $H$ with $K$.

Proof:
Let $e_2$ be the identity element of $\struct {G_2, *}$.
Let $x \in \phi^{-1} \sqbrk {\phi \sqbrk H}$.
Then:
{{begin-eqn}}
{{eqn | l = x
      | o = \in
      | r = \phi^{-1} \sqbrk {\phi \sqbrk H}
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \map \phi x
      | o = \in
      | r = \phi \sqbrk H
      | c = {{Defof|Preimage of Element under Mapping}}
}}
{{eqn | ll= \leadsto
      | q = \exists b \in H
      | l = \map \phi x
      | r = \map \phi b
      | c = {{Defof|Image of Element under Mapping}}
}}
{{eqn | ll= \leadsto
      | l = \map \phi x * \paren {\map \phi b}^{-1}
      | r = e_2
      | c = {{Defof|Inverse Element}} in $G_2$
}}
{{eqn | ll= \leadsto
      | l = \map \phi {x \circ b^{-1} }
      | r = e_2
      | c = as $\phi$ is a homomorphism
}}
{{eqn | ll= \leadsto
      | l = x \circ b^{-1}
      | o = \in
      | r = K
      | c = {{Defof|Kernel of Group Homomorphism}}
}}
{{eqn | ll= \leadsto
      | l = b^{-1} \circ x
      | o = \in
      | r = K
      | c = {{Defof|Normal Subgroup}}: Kernel is Normal Subgroup of Domain
}}
{{eqn | ll= \leadsto
      | l = x
      | o = \in
      | r = H \circ K
      | c = as $x = b \circ \paren {b^{-1} \circ x}$
}}
{{end-eqn}}
So we have shown that:
:$\phi^{-1} \sqbrk {\phi \sqbrk H} \subseteq H \circ K$
Now suppose that $x \in H \circ K$.
Then:
{{begin-eqn}}
{{eqn | l = x
      | o = \in
      | r = H \circ K
      | c = 
}}
{{eqn | ll= \leadsto
      | q = \exists b \in H, a \in K
      | l = x
      | r = b \circ a
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \map \phi x
      | r = \map \phi b * \map \phi a
      | c = as $\phi$ is a homomorphism
}}
{{eqn | r = \map \phi b * e_2
      | c = as $a \in K$
}}
{{eqn | r = \map \phi b
      | c =
}}
{{eqn | ll= \leadsto
      | l = \map \phi x
      | o = \in
      | r = \phi \sqbrk H
      | c = as $b \in H$
}}
{{eqn | ll= \leadsto
      | l = x
      | o = \in
      | r = \phi^{-1} \sqbrk {\phi \sqbrk H}
      | c = {{Defof|Preimage of Subset under Mapping}}
}}
{{end-eqn}}
So we have shown that:
:$H \circ K \subseteq \phi^{-1} \sqbrk {\phi \sqbrk H}$
Hence the result by definition of set equality.
{{qed}}
Theorem: Preimage of Subgroup under Epimorphism is Subgroup

Let $\struct {G_1, \circ}$ and $\struct {G_2, *}$ be groups.
Let $\phi: \struct {G_1, \circ} \to \struct {G_2, *}$ be a group epimorphism.
Let $H$ be a subgroup of $\struct {G_2, *}$.
Then:
:$\phi^{-1} \sqbrk H$ is a subgroup of $\struct {G_1, \circ}$
where $\phi^{-1} \sqbrk H$ denotes the preimage of $H$ under $\phi$.

Proof:
Let $H$ be a subgroup of $\struct {G_2, *}$.
First note that from Null Relation is Mapping iff Domain is Empty Set:
:$\phi^{-1} \sqbrk H = \O \implies H = \O$
But $H \ne \O$.
Hence $\phi^{-1} \sqbrk H$ is not empty.
Next, let $x, y \in \phi^{-1} \sqbrk H$.
Then:
:$\exists h_1, h_2 \in H: h_1 = \map \phi x, h_2 = \map \phi y$
From the definition of Group Homomorphism, we have:
:$\map \phi {x^{-1} \circ y} = h_1^{-1} * h_2$
Since $H$ is a subgroup:
:$h_1^{-1} * h_2 \in H$
Hence:
:$x^{-1} \circ y \in \phi^{-1} \sqbrk H$
Thus from the One-Step Subgroup Test:
:$\phi^{-1} \sqbrk H$ is a subgroup of $G_1$.
{{qed}}
Theorem: Unique Epimorphism from Quotient Group to Quotient Group

Let $\struct {G_1, \circledcirc}$ and $\struct {G_2, \circledast}$ be groups.
Let $\phi: \struct {G_1, \circledcirc} \to \struct {G_2, \circledast}$ be a group epimorphism.
Let $K$ be the kernel of $\phi$.
Let $H_1$ be a normal subgroup of $\struct {G_1, \circledcirc}$.
Let $H_2 := \phi \sqbrk {H_1}$ be the image of $H_1$ under $\phi$.
Then there exists a unique epimorphism $\psi$ from $G_1 / H_1$ to $G_2 / H_2$ such that:
:$\psi \circ q_{H_1} = q_{H_2} \circ \phi$
where:
:$G_1 / H_1$ and $G_2 / H_2$ are quotient groups of $G_1$ by $H_1$ and of $G_2$ by $H_2$ respectively
:$q_{H_1}: G_1 \to G_1 / H_1$ and $q_{H_2}: G_2 \to G_2 / H_2$ are their respective quotient mappings.
The kernel of $\psi$ is given by:
:$\map \ker \psi = \dfrac {H_1 \circledcirc K} {H_1}$

Proof:
First we note that by Group Epimorphism Preserves Normal Subgroups, $H_2$ is indeed a normal subgroup of $\struct {G_2, \circledast}$.
Hence $G_2 / H_2$ and $q_{H_2}: G_2 \to G_2 / H_2$ are appropriately defined.
Let $\RR$ be the congruence relation induced on $\struct {G_1, \circledcirc}$ by $H$.
Let $q_\RR$ be the quotient mapping induced by $\RR$.
Then by definition $q_\RR = q_{H_1}$.
We are given that $\phi$ is a group epimorphism.
We also have from Quotient Group Epimorphism is Epimorphism that $q_{H_2}$ is also a group epimorphism.
Hence from Composite of Group Epimorphisms is Epimorphism, $q_{H_2} \circ \phi$ is also a group epimorphism.
So from Quotient Theorem for Epimorphisms, there exists a unique epimorphism $\psi$ from $G_1 / H_1$ to $G_2 / H_2$ such that:
:$\psi \circ q_{H_1} = q_{H_2} \circ \phi$
It remains to be shown that:
:$\map \ker \psi = \dfrac {H_1 \circledcirc K} {H_1}$
{{ProofWanted}}