avewright/proofwiki-math huggingface dataset:
Theorem: Parity Multiplication is Commutative

Let $R := \struct {\set {\text{even}, \text{odd} }, +, \times}$ be the parity ring.
The operation $\times$ is commutative:
:$\forall a, b \in R: a \times b = b \times a$

Proof:
Let $a, b \in R$.
That is, $a$ and $b$ are both either $\text{even}$ or $\text{odd}$.
By definition of odd:
:$\text{odd} = 2 m + 1$
for some $m \in \Z$.
By definition of even:
:$\text{even} = 2 n + 0$
for some $n \in \Z$.
Thus we can define the mapping $f: R \to \Z$ as:
$\quad \forall x \in R: \map f x := \begin{cases}
0 & : x \text { is even} \\
1 & : x \text { is odd} \end{cases}$
Thus an element of $R$ can be expressed as an arbitrary integer of the form:
:$x = 2 k + \map f x$
where:
:$k \in \Z$ is an integer
:$\map f x$ is either $0$ or $1$ according to whether $x$ is even or odd.
Then:
{{begin-eqn}}
{{eqn | l = a \times b
      | r = \paren {2 r + \map f a} \paren {2 s + \map f b}
      | c = where $r, s \in \Z$
}}
{{eqn | r = \paren {2 s + \map f b} \paren {2 r + \map f a}
      | c = Integer Multiplication is Commutative
}}
{{eqn | r = b \times a
      | c = {{Defof|Odd Integer}} and {{Defof|Even Integer}}
}}
{{end-eqn}}
{{qed}}
Theorem: Isomorphism between Roots of Unity under Multiplication and Integers under Modulo Addition

Let $n \in \Z_{>0}$ be a (strictly) positive integer.
Let $\struct {R_n, \times}$ be the complex $n$th roots of unity under complex multiplication.
Let $\struct {\Z_n, +_n}$ be the integers modulo $n$ under modulo addition.
Then $\struct {R_n, \times}$ and $\struct {\Z_n, +_n}$ are isomorphic algebraic structures.

Proof:
The set of integers modulo $n$ is the set exemplified by the integers:
:$\Z_n = \set {0, 1, \ldots, n - 1}$
The complex $n$th roots of unity is the set:
:$R_n = \set {z \in \C: z^n = 1}$
From Complex Roots of Unity in Exponential Form:
:$R_n = \set {1, e^{\theta / n}, e^{2 \theta / n}, \ldots, e^{\left({n - 1}\right) \theta / n} }$
where $\theta = 2 i \pi$.
Let $z, w, \in R_n$.
Then:
:$\paren {z w}^n = z^n w^n = 1$
and so $z w \in R_n$.
Thus $\struct {R_n, \times}$ is a closed algebraic structure.
Consider the mapping $f: \Z_n \to R_n$ defined as:
:$\forall r \in \Z_n: \map f r = e^{r \theta / n}$
which can be seen to be a bijection by inspection.
Let $j, k \in \Z_n$.
Then:
{{begin-eqn}}
{{eqn | l = \map f j \map f k
      | r = e^{j \theta / n} e^{k \theta / n}
      | c = 
}}
{{eqn | r = e^{j \theta / n + k \theta / n}
      | c = 
}}
{{eqn | r = e^{\paren {j + k} \theta / n}
      | c = 
}}
{{eqn | r = \map f {j +_n k}
      | c = 
}}
{{end-eqn}}
Thus $f$ is an isomorphism.
{{qed}}
Theorem: Isomorphism between Gaussian Integer Units and Integers Modulo 4 under Addition

Let $\struct {U_\C, \times}$ be the group of Gaussian integer units under complex multiplication.
Let $\struct {\Z_n, +_4}$ be the integers modulo $4$ under modulo addition.
Then $\struct {U_\C, \times}$ and $\struct {\Z_4, +_4}$ are isomorphic algebraic structures.

Proof:
From Gaussian Integer Units are 4th Roots of Unity:
:$U_\C$ is the set consisting of the (complex) $4$th roots of $1$.
The result follows from Isomorphism between Roots of Unity under Multiplication and Integers under Modulo Addition.
Theorem: Isomorphism between Gaussian Integer Units and Integers Modulo 4 under Addition

Let $\struct {U_\C, \times}$ be the group of Gaussian integer units under complex multiplication.
Let $\struct {\Z_n, +_4}$ be the integers modulo $4$ under modulo addition.
Then $\struct {U_\C, \times}$ and $\struct {\Z_4, +_4}$ are isomorphic algebraic structures.

Proof:
Let the mapping $f: \Z_4 \to U_\C$ be defined as:
{{begin-eqn}}
{{eqn | l = \map f 0
      | r = 1
}}
{{eqn | l = \map f 1
      | r = i
}}
{{eqn | l = \map f 2
      | r = -1
}}
{{eqn | l = \map f 3
      | r = -i
}}
{{end-eqn}}
From Isomorphism by Cayley Table, the two Cayley tables can be compared by eye to ascertain that $f$ is an isomorphism:
=== Cayley Table of Integers Modulo $4$ ===
The Cayley table for $\struct {\Z_4, +_4}$ is as follows:
{{:Modulo Addition/Cayley Table/Modulo 4}}
=== Cayley Table of Gaussian Integer Units ===
The Cayley table for $\struct {U_\C, \times}$ is as follows:
{{:Group of Gaussian Integer Units/Cayley Table}}
Theorem: Gaussian Integer Units are 4th Roots of Unity

The units of the ring of Gaussian integers:
:$\set {1, i, -1, -i}$
are the (complex) $4$th roots of $1$.

Proof:
We have that $i = \sqrt {-1}$ is the imaginary unit.
Thus:
{{begin-eqn}}
{{eqn | l = 1^4
      | o = 
      | rr= = 1
}}
{{eqn | l = i^4
      | r = \paren {-1}^2
      | rr= = 1
}}
{{eqn | l = \paren {-1}^4
      | r = 1^2
      | rr= = 1
}}
{{eqn | l = \paren {-i}^4
      | r = \paren {-1}^2 \cdot \paren {-1}^2
      | rr= = 1
}}
{{end-eqn}}
So $\set {1, i, -1, -i}$ constitutes the set of the $4$th roots of unity.
{{qed}}
Theorem: Isomorphism by Cayley Table

Let $\struct {S, \circ}$ and $\struct {T, *}$ be algebraic structures whose underlying sets are both finite.
Then $\struct {S, \circ}$ and $\struct {T, *}$ are isomorphic {{iff}}:
:a bijection $f: S \to T$ can be found such that:
::the Cayley table of $\struct {T, *}$ can be generated from the Cayley table of $\struct {S, \circ}$ by replacing each entry of $S$ with its image under $f$.

Proof:
=== Necessary Condition ===
Let $S$ and $T$ be isomorphic.
Then by definition there exists an isomorphism $f: S \to T$.
An isomorphism is a bijection by definition.
Thus the existence of the posited bijection has been demonstrated.
By the definition of set equivalence, $S$ and $T$ have the same cardinality.
Let $\card S = \card T = n$.
Let:
:$S = \set {s_1, s_2, \ldots, s_n}$
and:
:$T = \set {t_1, t_2, \ldots, t_n}$
be such that:
:$\forall i \in \set {1, 2, \ldots, n}: \map f {s_i} = t_i$
Let $S \sqbrk {j, k}$ denote the entry of $S$ in row $j$ and column $k$.
Thus:
:$S \sqbrk {j, k} = s_j \circ s_k$
for some $s_j, s_k \in S$.
We have that $f$ is an isomorphism.
Thus:
:$\map f {S \sqbrk {j, k} } = \map f {s_j} * \map f {s_k}$
But:
:$\map f {S \sqbrk {j, k} } = T \sqbrk {j, k}$
:$\map f {s_j} = t_j$
:$\map f {s_k} = t_k$
Thus the Cayley table of $\struct {T, *}$ has been generated from the Cayley table of $\struct {S, \circ}$ by replacing each entry of $S$ with its image under $f$.
{{qed|lemma}}
Theorem: Bijection between Integers and Even Integers

Let $\Z$ be the set of integers.
Let $2 \Z$ be the set of even integers.
Then there exists a bijection $f: \Z \to 2 \Z$ between the two.

Proof:
Let $f: \Z \to 2 \Z$ be the mapping defined as:
:$\forall n \in \Z: \map f n = 2 n$
Let $m, n \in \Z$ such that $\map f m = \map f n$.
{{begin-eqn}}
{{eqn | l = \map f m
      | r = \map f n
}}
{{eqn | ll= \leadsto
      | l = 2 m
      | r = 2 n
      | c = Definition of $f$
}}
{{eqn | ll= \leadsto
      | l = m
      | r = n
      | c = dividing both sides by $2$
}}
{{end-eqn}}
Thus $f$ is an injection.
Let $n \in 2 Z$.
Then by definition:
:$n = 2 r$
for some $r \in \Z$
That is:
:$n = \map f r$
and so $f$ is a surjection.
So $f$ is both an injection and a surjection.
Hence by definition, $f$ is a bijection.
{{qed}}
Category:Examples of Bijections
Category:Integers
Category:Even Integers
1guf8fayzhy4b82sb3b08kplc5wrbl6
Theorem: Set of Integers under Addition is Isomorphic to Set of Even Integers under Addition

Let $\struct {\Z, +}$ be the algebraic structure formed by the set of integers under the operation of addition.
Let $\struct {2 \Z, +}$ be the algebraic structure formed by the set of even integers under the operation of addition.
Then $\struct {\Z, +}$ and $\struct {2 \Z, +}$ are isomorphic.

Proof:
Let $f: \Z \to 2 \Z$ be the mapping:
:$\forall n \in \Z: \map f n = 2 n$
From Bijection between Integers and Even Integers, $f$ is a bijection.
Let $m, n \in \Z$.
Then:
{{begin-eqn}}
{{eqn | l = \map f {m + n}
      | r = 2 \paren {m + n}
      | c = Definition of $f$
}}
{{eqn | r = 2 m + 2 n
      | c = Integer Multiplication Distributes over Addition
}}
{{eqn | r = \map f m + \map f n
      | c = Integer Multiplication Distributes over Addition
}}
{{end-eqn}}
Thus $f$ is an isomorphism by definition.
{{qed}}
Theorem: Natural Numbers under Addition do not form Group

The algebraic structure $\struct {\N, +}$ consisting of the set of natural numbers $\N$ under addition $+$ is not a group.

Proof:
From Natural Numbers under Addition form Commutative Monoid, $\struct {\N, +}$ has an identity element $0$.
However, for any $x \in \N$ such that $x \ne 0$ there exists no $y \in \N$ such that $x + y = 0$.
Thus the general element of $\struct {\N, +}$ has no inverse.
Hence the result by definition of group.
{{qed}}
Theorem: Natural Numbers under Multiplication do not form Group

The algebraic structure $\struct {\N, \times}$ consisting of the set of natural numbers $\N$ under multiplication $\times$ is not a group.

Proof:
{{AimForCont}} that $\struct {\N, \times}$ is a group.
We have that $1 \times 1 = 1$ and so is idempotent.
From Identity is only Idempotent Element in Group it follows that $1$ is the identity of $\struct {\N, \times}$.
Let $x \in \N$ such that $x \ne 0$ and $x \ne 1$.
There exists no $y \in \N$ such that $x \times y = 1$
Hence $\struct {\N, \times}$ does not fulfil {{Group-axiom|3}}.
Hence by Proof by Contradiction $\struct {\N, \times}$ is not a group.
Theorem: Rational Numbers under Multiplication do not form Group

The algebraic structure $\struct {\Q, \times}$ consisting of the set of rational numbers $\Q$ under multiplication $\times$ is not a group.

Proof:
{{AimForCont}} that $\struct {\Q, \times}$ is a group.
By the definition of the number $0 \in \Q$:
:$\forall x \in \Q: x \times 0 = 0 = 0 \times x$
Thus $0$ is a zero in the abstract algebraic sense.
From Group with Zero Element is Trivial, $\struct {\Q, \times}$ is the trivial group.
But $\Q$ contains other elements besides $0$.
From this contradiction it follows that $\struct {\Q, \times}$ is not a group.
{{qed}}
Theorem: Real Numbers under Multiplication do not form Group

The algebraic structure $\struct {\R, \times}$ consisting of the set of real numbers $\R$ under multiplication $\times$ is not a group.

Proof:
{{AimForCont}} that $\struct {\R, \times}$ is a group.
By the definition of the number $0 \in \R$:
:$\forall x \in \R: x \times 0 = 0 = 0 \times x$
Thus $0$ is a zero in the abstract algebraic sense.
From Group with Zero Element is Trivial, $\struct {\R, \times}$ is the trivial group.
But $\R$ contains other elements besides $0$.
From this contradiction it follows that $\struct {\R, \times}$ is not a group.
{{qed}}
Theorem: Complex Numbers under Multiplication do not form Group

The algebraic structure $\struct {\C, \times}$ consisting of the set of complex numbers $\C$ under multiplication $\times$ is not a group.

Proof:
{{AimForCont}} that $\struct {\C, \times}$ is a group.
By the definition of the number $0 \in \C$:
:$\forall x \in \C: x \times 0 = 0 = 0 \times x$
Thus $0$ is a zero in the abstract algebraic sense.
From Group with Zero Element is Trivial, $\struct {\C, \times}$ is the trivial group.
But $\C$ contains other elements besides $0$.
From this contradiction it follows that $\struct {\C, \times}$ is not a group.
{{qed}}
Theorem: Symmetry Group of Square is Group

The symmetry group of the square is a non-abelian group.

Proof:
Let us refer to this group as $D_4$.
Taking the group axioms in turn:
Theorem: Dihedral Group is Group

Let $D_n$ be the dihedral group of order $2 n$.
Then $D_n$ is indeed a group.

Proof:
$D_n$ is by definition the symmetry group of the regular $n$-gon.
The result follows from Symmetry Group is Group.
{{qed}}
Theorem: Symmetric Group is Subgroup of Monoid of Self-Maps

Let $S$ be a set.
Let $S^S$ be the set of all mappings from $S$ to itself
Let $\struct {\Gamma \paren S, \circ}$ denote the symmetric group on $S$.
Let $\struct {S^S, \circ}$ be the monoid of self-maps under composition of mappings.
Then $\struct {\Gamma \paren S, \circ}$ is a subgroup of $\struct {S^S, \circ}$.

Proof:
By Symmetric Group is Group, $\struct {\Gamma \paren S, \circ}$ is a group.
Let $\phi \in \Gamma \paren S$ be a permutation on $S$.
As a permutation is a self-map, it follows that $\phi \in S^S$.
Thus by definition $\Gamma \paren S$ is a subset of $S^S$.
So by definition, $\Gamma \paren S$, is a subgroup of $\struct {S^S, \circ}$.
{{qed}}
Category:Symmetric Groups
Category:Subgroups
Category:Monoids
i3qs8xsmtfcd76cmiw9zzh8gowaaz6s
Theorem: Cancellability by Cayley Table

Let $\struct {S, \circ}$ be a finite algebraic structure.
Let $\TT$ be the Cayley table for $\left({S, \circ}\right)$.
Let $a \in S$ be an element of $S$.
Then $a$ is cancellable for $\circ$ {{iff}}:
:$(1): \quad$ no element of $S$ is repeated in $\TT$ in the row headed by $a$
and:
:$(2): \quad$ no element of $S$ is repeated in $\TT$ in the column headed by $a$.

Proof:
=== Necessary Condition ===
Let $a \in S$ be cancellable for $\circ$.
Suppose there exists $x \in S$ which appears twice in a row in $\TT$ headed by $a$.
Thus by definition of the structure of a Cayley table:
:$\exists y_1, y_2 \in S: a \circ y_1 = x = a \circ y_2$
such that $y_1 \ne y_2$.
That contradicts the stipulation that $a$ is cancellable for $\circ$.
So no element of $S$ is repeated in $\TT$ in the row headed by $a$.
Similarly, suppose there exists $x \in S$ which appears twice in a column in $\TT$ headed by $a$.
Thus by definition of the structure of a Cayley table:
:$\exists y_1, y_2 \in S: y_1 \circ a = x = y_2 \circ a$
such that $y_1 \ne y_2$.
That contradicts the stipulation that $a$ is cancellable for $\circ$.
So no element of $S$ is repeated in $\TT$ in the column headed by $a$.
{{qed|lemma}}
Theorem: Subset not necessarily Submagma

Let $\struct {S, \circ}$ be a magma.
Let $T \subseteq S$.
Then it is not necessarily the case that:
: $\struct {T, \circ} \subseteq \struct {S, \circ}$
That is, it does not always follow that $\struct {T, \circ}$ is a submagma of $\struct {S, \circ}$.

Proof:
Let $\struct {\Z, -}$ be the magma which is the set of integers under the operation of subtraction.
We have that the natural numbers $\N$ are a subset of the integers.
Consider $\struct {\N, -}$, the natural numbers under subtraction.
We have that Natural Number Subtraction is not Closed.
For example:
: $1 - 2 = -1 \notin \N$
Thus $\struct {\N, -}$ is not closed.
So $\struct {\N, -}$ is not a submagma of $\struct {\Z, -}$
Hence it is not true to write $\struct {\N, -} \subseteq \struct {\Z, -}$, despite the fact that $\N \subseteq \Z$.
Thus $\struct {\N, -}$ is not a submagma of $\struct {\Z, -}$.
{{qed}}
Theorem: Closed Subsets of Symmetry Group of Square

Recall the symmetry group of the square:

Proof:
Recall that a submagma of an algebraic structure $\SS$ is a subsets of $\SS$ which is closed.
Let $\XX$ be the set of all submagmas of $\SS$.
From Empty Set is Submagma of Magma:
:$\O \in \XX$
From Magma is Submagma of Itself:
:$\SS \in \XX$
From Idempotent Magma Element forms Singleton Submagma:
:$\set e \in \XX$
Let us refer to the Cayley table:
Theorem: Piecewise Continuous Function does not necessarily have Improper Integrals

Let $f$ be a real function defined on a closed interval $\closedint a b$, $a < b$. 
Let $f$ be a piecewise continuous function:
{{:Definition:Piecewise Continuous Function}}
Then it is not necessarily the case that $f$ is a piecewise continuous function with improper integrals:
{{:Definition:Piecewise Continuous Function with Improper Integrals}}

Proof:
Consider the function:
:<nowiki>$\map f x = \begin{cases}
0 & : x = a \\
\dfrac 1 {x - a} & : x \in \hointl a b
\end{cases}$</nowiki>
Since $\dfrac 1 {x - a}$ is continuous on $\openint a b$, $f$ is continuous on $\openint a b$.
Therefore, $f$ is a piecewise continuous function for the (finite) subdivision $\set {a, b}$ of $\closedint a b$.
We now consider whether the improper integral $\ds \int_{a^+}^{b^-} \dfrac 1 {x - a} \rd x$ exists.
Let $c$ be a point in $\openint a b$.
From the definition of improper integral, the existence of $\ds \int_{a^+}^{b^-} \dfrac 1 {x - a} \rd x$ requires that $\ds \lim_{\gamma \mathop \to a^+} \int_\gamma^c \dfrac 1 {x - a} \rd x$ exists.
We have
{{begin-eqn}}
{{eqn | l = \int_\gamma^c \frac 1 {x - a} \rd x
      | r = \bigintlimits {\map \ln {x - a} } \gamma c
}}
{{eqn | r = \map \ln {c - a} - \map \ln {\gamma - a}
}}
{{eqn | r = \map \ln {c - a} + \map \ln {\frac 1 {\gamma - a} }
}}
{{end-eqn}}
The last {{RHS}} approaches $\infty$ as $\gamma$ approaches $a$ from above.
So $\ds \int_{a^+}^c \dfrac 1 {x - a} \rd x$ does not exist.
Therefore, $\ds \int_{a^+}^{b^-} \dfrac 1 {x - a} \rd x$ does not exist either.
Accordingly, $f$ is not a piecewise continuous function with improper integrals.
{{qed}}
Category:Piecewise Continuous Functions
8obhxz73r5g5j8swmywy63k1bi62qvt
Theorem: Right Cancellable Element is Right Cancellable in Subset

Let $\struct {S, \circ}$ be an algebraic structure.
Let $\struct {T, \circ} \subseteq \struct {S, \circ}$.
Let $x \in T$ be right cancellable in $S$.
Then $x$ is also right cancellable in $T$.

Proof:
Let $x \in T$ be right cancellable in $S$.
That is:
:$\forall a, b \in S: a \circ x = b \circ x \implies a = b$
Therefore:
:$\forall c, d \in T: c \circ x = d \circ x \implies c = d$
Thus $x$ is right cancellable in $T$.
{{qed}}
Category:Abstract Algebra
nrnys061i0ttzgrwzrlslxd3d9q0jel
Theorem: Left Cancellable Element is Left Cancellable in Subset

Let $\struct {S, \circ}$ be an algebraic structure.
Let $\struct {T, \circ} \subseteq \struct {S, \circ}$.
Let $x \in T$ be left cancellable in $S$.
Then $x$ is also left cancellable in $T$.

Proof:
Let $x \in T$ be left cancellable in $S$.
That is:
:$\forall a, b \in S: x \circ a = x \circ b \implies a = b$
Therefore:
:$\forall c, d \in T: x \circ c = x \circ d \implies c = d$
Thus $x$ is left cancellable in $T$.
{{qed}}
Category:Abstract Algebra
qf6y06293gf4xvsea4gad3uofljsg07
Theorem: Left Cancellable Elements of Semigroup form Subsemigroup

Let $\struct {S, \circ}$ be a semigroup.
Let $C_\lambda$ be the set of left cancellable elements of $\struct {S, \circ}$.
Then $\struct {C_\lambda, \circ}$ is a subsemigroup of $\struct {S, \circ}$.

Proof:
Let $C_\lambda$ be the set of left cancellable elements of $\struct {S, \circ}$:
:$C_\lambda = \set {x \in S: \forall a, b \in S: x \circ a = x \circ b \implies a = b}$
Let $x, y \in C_\lambda$.
Then:
{{begin-eqn}}
{{eqn | l = \paren {x \circ y} \circ a
      | r = \paren {x \circ y} \circ b
      | c =
}}
{{eqn | ll= \leadsto
      | l = x \circ \paren {y \circ a}
      | r = x \circ \paren {y \circ b}
      | c = by associativity of $\circ$
}}
{{eqn | ll= \leadsto
      | l = x \circ a
      | r = x \circ b
      | c = as $y \in C_\lambda$
}}
{{eqn | ll= \leadsto
      | l = a
      | r = b
      | c = as $x \in C_\lambda$
}}
{{eqn | ll= \leadsto
      | l = x \circ y
      | o = \in
      | r = C_\lambda
      | c = 
}}
{{end-eqn}}
Thus $\struct {C_\lambda, \circ}$ is closed.
Therefore by the Subsemigroup Closure Test $\struct {C_\lambda, \circ}$ is a subsemigroup of $\struct {S, \circ}$.
{{qed}}
Category:Subsemigroups
Category:Cancellability
seoif9yk7nxcmygydsrrus264ywzxz8
Theorem: Right Cancellable Elements of Semigroup form Subsemigroup

Let $\struct {S, \circ}$ be a semigroup.
Let $C_\rho$ be the set of right cancellable elements of $\struct {S, \circ}$.
Then $\struct {C_\rho, \circ}$ is a subsemigroup of $\struct {S, \circ}$.

Proof:
Let $C_\rho$ be the set of right cancellable elements of $\struct {S, \circ}$:
:$C_\rho = \set {x \in S: \forall a, b \in S: a \circ x = b \circ x \implies a = b}$
Let $x, y \in C_\rho$.
Then:
{{begin-eqn}}
{{eqn | l = a \circ \paren {x \circ y}
      | r = b \circ \paren {x \circ y}
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \paren {a \circ x} \circ y
      | r = \paren {b \circ x} \circ y
      | c = by associativity of $\circ$
}}
{{eqn | ll= \leadsto
      | l = a \circ x
      | r = b \circ x
      | c = as $y \in C_\rho$
}}
{{eqn | ll= \leadsto
      | l = a
      | r = b
      | c = as $x \in C_\rho$
}}
{{eqn | ll= \leadsto
      | l = x \circ y
      | o = \in
      | r = C_\rho
      | c = 
}}
{{end-eqn}}
Thus $\struct {C_\rho, \circ}$ is closed.
Therefore by the Subsemigroup Closure Test $\struct {C_\rho, \circ}$ is a subsemigroup of $\struct {S, \circ}$.
{{qed}}
Category:Subsemigroups
Category:Cancellability
553g7fnvrglpt8egqz4mvzub562xt0r
Theorem: Surjection iff Right Cancellable/Necessary Condition

Let $f$ be a surjection.
Then $f$ is right cancellable.

Proof:
Let $f: X \to Y$ be surjective.
Let $h_1: Y \to Z, h_2: Y \to Z: h_1 \circ f = h_2 \circ f$.
As $f$ is a surjection:
:$\Img f = Y$
by definition.
But in order for $h_1 \circ f$ to be defined, it is necessary that $Y = \Dom {h_1}$.
Similarly, for $h_2 \circ f$ to be defined, it is necessary that $Y = \Dom {h_2}$.
So it follows that the domains of $h_1$ and $h_2$ are the same.
Also:
:The codomain of $h_1$ equals the codomain of $h_1 \circ f$
:The codomain of $h_2$ equals the codomain of $h_2 \circ f$
again by definition of composition of mappings.
Now, we have shown that the domains and codomains of $h_1$ and $h_2$ are the same.
All we need to do now to prove that $h_1 = h_2$, and therefore that $f$ is right cancellable, is to show that:
:$\forall y \in Y: h_1 \paren y = h_2 \paren y$.
So, let $y \in Y$.
As $f$ is surjective:
: $\exists x \in X: y = f \paren x$
Thus:
{{begin-eqn}}
{{eqn | l = h_1 \paren y
      | r = h_1 \paren {f \paren x}
      | c = Definition of $y$
}}
{{eqn | r = h_1 \circ f \paren x
      | c = {{Defof|Composition of Mappings}}
}}
{{eqn | r = h_2 \circ f \paren x
      | c = By Hypothesis
}}
{{eqn | r = h_2 \paren {f \paren x}
      | c = {{Defof|Composition of Mappings}}
}}
{{eqn | r = h_2 \paren y
      | c = Definition of $y$
}}
{{end-eqn}}
Thus $h_1 \paren y = h_2 \paren y$ and thus $f$ is right cancellable.
Theorem: Surjection iff Right Cancellable/Necessary Condition

Let $f$ be a surjection.
Then $f$ is right cancellable.

Proof:
Let $f: X \to Y$ be surjective.
Then from Surjection iff Right Inverse:
:$\exists g: Y \to X: f \circ g = I_Y$
Suppose $h \circ f = k \circ f$ for two mappings $h: Y \to Z$ and $k: Y \to Z$.
Then:
{{begin-eqn}}
{{eqn | l = h
      | r = h \circ I_Y
      | c = 
}}
{{eqn | r = h \circ \paren {f \circ g}
      | c = 
}}
{{eqn | r = \paren {h \circ f} \circ g
      | c = Composition of Mappings is Associative
}}
{{eqn | r = \paren {k \circ f} \circ g
      | c = by hypothesis
}}
{{eqn | r = k \circ \paren {f \circ g}
      | c = Composition of Mappings is Associative
}}
{{eqn | r = k \circ I_Y
      | c = 
}}
{{eqn | r = k
      | c = 
}}
{{end-eqn}}
Thus $f$ is right cancellable.
So surjectivity implies right cancellability.
Theorem: Surjection iff Right Cancellable/Sufficient Condition

Let $f$ be a mapping which is right cancellable.
Then $f$ is a surjection.

Proof:
Suppose $f$ is a mapping which is not surjective.
Then:
:$\exists y_1 \in Y: \neg \exists x \in X: \map f x = y_1$
Let $Z = \set {a, b}$.
Let $h_1$ and $h_2$ be defined as follows. 
:$\map {h_1} y = a: y \in Y$
:<nowiki>$\map {h_2} y = \begin {cases}
a & : y \ne y_1 \\
b & : y = y_1
\end {cases}$</nowiki>
Thus we have $h_1 \ne h_2$ such that $h_1 \circ f = h_2 \circ f$.
Therefore $f$ is not right cancellable.
It follows from the Rule of Transposition that if $f$ is right cancellable, then $f$ must be surjective.