nyuuzyou/wikis huggingface dataset:
Bézout's Identity/Principal Ideal Domain

== Theorem ==
Let $\struct {D, +, \circ}$ be a principal ideal domain.
Let $S = \set {a_1, a_2, \dotsc, a_n}$ be a set of non-zero elements of $D$.
Let $y$ be a greatest common divisor of $S$.
Then $y$ is expressible in the form:
:$y = d_1 a_1 + d_2 a_2 + \dotsb + d_n a_n$
where $d_1, d_2, \dotsc, d_n \in D$.
== Proof ==
From Finite Set of Elements in Principal Ideal Domain has GCD we have that at least one such greatest common divisor exists.
So, let $y$ be a greatest common divisor of $S$.
Let $J$ be the set of all linear combinations in $D$ of $\set {a_1, a_2, \dotsc, a_n}$.
From Set of Linear Combinations of Finite Set of Elements of Principal Ideal Domain is Principal Ideal:
:$J = \ideal x$
for some $x \in D$, where $\ideal x$ denotes the principal ideal generated by $x$.
From Finite Set of Elements in Principal Ideal Domain has GCD, $x$ is a greatest common divisor of $S$.
From Greatest Common Divisors in Principal Ideal Domain are Associates, $y$ is an associate of $x$.
By definition of associate:
:$\ideal y = \ideal x$
Therefore:
:$y \in J$
and so by definition, $y$ is expressible in the form:
:$y = d_1 a_1 + d_2 a_2 + \dotsb + d_n a_n$
where $d_1, d_2, \dotsc, d_n \in D$.
== Also known as ==
== Historical Note ==
== Sources ==
* : $\S 62.4$ Factorization in an integral domain: $\text{(iii)}$
Category:Principal Ideal Domains
Category:Bézout's Identity
Bézout's Identity/Proof 2

== Theorem ==
== Proof ==
Let $a, b \in \Z$ such that $a$ and $b$ are not both zero.
Let $S$ be the set of all positive integer combinations of $a$ and $b$:
:$S = \set {x \in \Z, x > 0: x = m a + n b: m, n \in \Z}$
First we establish that $S \ne \O$.
We have:
As it is not the case that both $a = 0$ and $b = 0$, it must be that at least one of $\size a \in S$ or $\size b \in S$.
Therefore $S \ne \O$.
As $S$ contains only positive integers, $S$ is bounded below by $0$ and therefore $S$ has a smallest element.
Call this smallest element $d$: we have $d = u a + v b$ for some $u, v \in \Z$.
Let $x \in S$.
By the Division Theorem:
: $x = q d + r, 0 \le r < d$
Suppose $d \nmid x$.
Then $x \ne q d$ and so $0 < r$.
But:
which contradicts the choice of $d$ as the smallest element of $S$.
Therefore $\forall x \in S: d \divides x$.
In particular:
:$d \divides \size a = 1 \times a + 0 \times b$
:$d \divides \size b = 0 \times a + 1 \times b$
Thus:
: $d \divides a \land d \divides b \implies 1 \le d \le \gcd \set {a, b}$
However, note that as $\gcd \set {a, b}$ also divides $a$ and $b$ (by definition), we have:
Since $d$ is the smallest number in $S$:
:$\gcd \set {a, b} = d = u a + v b$
== Sources ==
* : Chapter $3$: The Integers: $\S 11$. Highest Common Factor: Theorem $19$
* : Chapter $1$: Properties of the Natural Numbers: $\S 23$
* : Chapter $2$: Divisibility Theory in the Integers: $2.2$ The Greatest Common Divisor: Theorem $2 \text{-} 3$
Category:Bézout's Identity
Bézout's Identity/Proof 3

== Theorem ==
== Proof ==
Consider the Euclidean algorithm in action:
First it will be established that there exist $x_i, y_i \in \Z$ such that:
:$(1): \quad a x_i + b y_i = r_i$
for $i \in \set{1, 2, \ldots, n - 1}$.
The proof proceeds by induction.
=== Basis for the Induction ===
When $i = 1$, let $x_1 = 1, y_1 = -q_1$.
When $i = 2$, let $x_2 = -q_2, y_2 = 1 + q_1 q_2$.
This is the basis for the induction.
=== Induction Hypothesis ===
Our induction hypothesis is that the integer solutions to $(1)$ have been found for all $i$ such that $i \le k$ where $k < n - 1$.
=== Induction Step ===
We know that:
:$r_{k - 1} = r_k q_{k + 1} + r_{k + 1}$
Thus, by the induction hypothesis:
:$\paren {a x_{k - 1} + b y_{k - 1} } - \paren {a x_k + b y_k} q_{k + 1} = r_{k + 1}$
which can be rewritten as:
:$\paren {x_{k - 1} - x_k q_{k + 1} } a + \paren {y_{k - 1} - y_k q_{k + 1} } b = r_{k + 1}$
Hence we have the following solutions to $(1)$ when $i = k + 1$:
:$x_{k + 1} = x_{k - 1} - x_k q_{k + 1}$
:$y_{k + 1} = y_{k - 1} - y_k q_{k + 1}$
The result follows by the Principle of Mathematical Induction.
== Sources ==
* : $\text {2-2}$ Divisibility: Corollary $\text {2-1}$
Category:Bézout's Identity
Bézout's Identity/Proof 4

== Theorem ==
== Proof ==
Let $a, b \in \Z$ such that $a$ and $b$ are not both zero.
Let $J$ be the set of all integer combinations of $a$ and $b$:
:$J = \set {x: x = m a + n b: m, n \in \Z}$
First we show that $J$ is an ideal of $\Z$
Let $\alpha = m_1 a + n_1 b$ and $\beta = m_2 a + n_2 b$, and let $c \in \Z$
Then $\alpha,\beta \in J$ and :
Thus $J$ is an integral ideal.
We have that:
$a$ and $b$ are not both zero, thus:
:$J \ne \set 0$
By the something {theorem about ideals}:
:$\exists x_0 > 0 : J = x_0 \Z$
:$a \in J \land \set {J = x_0 \Z} \implies x_0 \divides a$
:$b \in J \land \set {J = x_0 \Z} \implies x_0 \divides b$
:$x_0 \divides a \land x_0 \divides b \implies x_0 \in \map D {a, b}$
Furthermore:
:$x_0 \in J \implies \exists r, s \in \Z : x_0 = r a + s b$
Let $x_1 \in \map D {a, b}$.
Then:
Thus:
:$x_0 = \max \set {\map D {a, b} } = \gcd \set {a, b} = r a + s b$
Category:Bézout's Identity
Bézout's Identity/Proof 5

== Theorem ==
== Proof ==
Let $\gcd \set {a, b} = d$.
Let $\dfrac a d = p$ and $\dfrac b d = q$.
From Integers Divided by GCD are Coprime:
:$\gcd \left\{{p, q}\right\} = 1$
From Integer Combination of Coprime Integers:
:$\exists x, y \in \Z: p x + q y = 1$
The result follows by multiplying both sides by $d$.
== Sources ==
* : Appendix: Elementary set and number theory
Category:Bézout's Identity
Bézout's Theorem

== Theorem ==
Let $X$ and $Y$ be two plane projective curves defined over a field $F$ that do not have a common component.
Then the total number of intersection points of $X$ and $Y$ with coordinates in an algebraically closed field $E$ which contains $F$, counted with their multiplicities, is equal to the product of the degrees of $X$ and $Y$.
== Proof ==
The condition that $X$ and $Y$ have no common component is true if both $X$ and $Y$ are defined by different irreducible polynomials.
In particular, it holds for a pair of "generic" curves.
== Examples ==
== Also known as ==
== Historical Note ==
== Sources ==
* 
* 
* 
Category:Bézout's Theorem
Category:Polynomial Theory
Bézout's Theorem/Examples/Conic Sections

== Example of Use of Bézout's Theorem ==
Two conic sections meet in at most $4$ points.
== Proof ==
From Conic Section is Curve of Second Order, the degree of the polynomial defining a conic section is $2$.
Hence, by Bézout's Theorem two such conic sections meet in at most $2 \times 2 = 4$ points.
== Sources ==
* 
Category:Examples of Use of Bézout's Theorem
C*-Algebra Generated by Commutative Self-Adjoint Set is Commutative

== Theorem ==
Let $\struct {A, \ast, \norm {\, \cdot \,} }$ be a $\text C^\ast$-algebra.
Let $S \subseteq A$ be a self-adjoint set such that:
:$x y = y x$ for each $x, y \in S$. 
Let $\map {\text C^\ast} S$ be the $\text C^\ast$-algebra generated by $S$. 
Then $\map {\text C^\ast} S$ is commutative. 
== Proof ==
Let $C$ be the subalgebra generated by $S$. 
From Subalgebra Generated by Commuting Elements is Commutative, $C$ is commutative.
From Explicit Form for Generated C*-Algebra, we have $\map {\text C^\ast} S = C^-$. 
From Closure of Commutative Set in Banach Algebra is Commutative, $C^-$ is commutative.
Hence $\map {\text C^\ast} S$ is commutative.
Category:C*-Algebras
C*-Algebra embeds into Multiplier Algebra as C*-Subalgebra

== Theorem ==
Let $\struct {A, \ast, \norm {\, \cdot \,} }$ be a $\text C^\ast$-algebra.
Let $\struct {\map M A, \ast, \norm {\, \cdot \,}_{\map M A} }$ be the multiplier algebra of $A$.
Define $\phi : A \to \map M A$ by:
:$\map \phi a = \tuple {L_a, R_a}$
for each $a \in A$, where $\tuple {L_a, R_a}$ is the double centralizer generated by $a$.
Then $\phi \sqbrk A$ is a $\text C^\ast$-subalgebra of $\map M A$. 
== Proof ==
We show that $\phi$ is a linear isometry.
Let $a, b \in A$ and $\lambda \in \C$.
Then we have for $c \in A$:
and:
Hence:
:$L_{a + \lambda b} = L_a + \lambda L_b$
and:
:$R_{a + \lambda b} = R_a + \lambda R_b$
We therefore have: 
so $\phi$ is a linear transformation.
We also have:
hence $\phi$ is a linear isometry.
We now show that $\phi$ is an algebra homomorphism.
Let $a, b, c \in A$.
We have:
so:
:$L_{a b} = L_a L_b$
Similarly we have:
so:
:$R_{a b} = R_b R_a$
Hence we have:
Hence $\phi$ is an algebra homomorphism.
We now show that $\phi$ is a $\ast$-algebra homomorphism.
We have:
and similarly:
So we have:
:$L_a^\ast = R_{a^\ast}$
and:
:$R_a^\ast = L_{a^\ast}$
We therefore have:
Now, from Image of *-Algebra under *-Algebra Homomorphism is *-Subalgebra, $\phi \sqbrk A$ is a $\ast$-subalgebra of $\map M A$. 
From Image of Closed Set under Linear Isometry from Banach Space to Normed Vector Space is Closed, $\phi \sqbrk A$ is closed in $\map M A$. 
Hence from Closed *-Subalgebra of C*-Algebra is C*-Algebra, $\phi \sqbrk A$ is a $\text C^\ast$-subalgebra of $\map M A$. 
Category:Multiplier Algebras
Category:C*-Algebras
C* Identity implies Involution is Isometry

== Theorem ==
Let $\struct {A, \ast}$ be a $\ast$-algebra over $\C$ that is a Banach algebra when given the algebra norm $\norm {\, \cdot \,}$.
Suppose that the $\text C^\ast$ identity:
:$\norm {x x^\ast} = \norm x^2$
holds for all $x \in A$. 
Then:
:$\norm x = \norm {x^\ast}$
for each $x \in A$. 
== Proof ==
Let $x \in A$. 
From Zero Vector in *-Algebra is Hermitian, we have: 
:${\mathbf 0}_A^\ast = {\mathbf 0}_A$
where ${\mathbf 0}_A$ is the zero vector of $A$.
Hence:
:$\norm x = \norm {x^\ast}$
holds in the case $x = {\mathbf 0}_A$.
Hence take $x \ne {\mathbf 0}_A$ so that $\norm x \ne 0$ by . 
We have: 
:$\norm {x x^\ast} \le \norm x \norm {x^\ast}$
from the definition of an algebra norm.
Hence we have:
:$\norm x^2 \le \norm x \norm {x^\ast}$
Hence, dividing by $\norm x$ we have:
:$\norm x \le \norm {x^\ast}$
for all $x \in A \setminus \set { {\mathbf 0}_A}$. 
Swapping $x$ for $x^\ast$ we have:
:$\norm {x^\ast} \le \norm {x^{\ast \ast} }$
From $(\text C^\ast 1)$ in the definition of an involution, we have:
:$x^{\ast \ast} = x$
and hence:
:$\norm {x^\ast} \le \norm x$
Since we have already shown that $\norm x \le \norm {x^\ast}$, we conclude:
:$\norm {x^\ast} = \norm x$ for each $x \in A$.
Category:C*-Algebras
Category:*-Algebras
C6 is not Isomorphic to S3

== Theorem ==
Let $C_6$ denote the cyclic group of order $6$.
Let $S_3$ denote the symmetric group on $3$ letters.
Then $C_6$ and $S_3$ are not isomorphic.
== Proof ==
Note that both $C_6$ and $S_3$ are of order $6$.
From Cyclic Group is Abelian, $C_6$ is abelian.
From Symmetric Group is not Abelian, $S_6$ is not abelian.
From Isomorphism of Abelian Groups, if two groups are isomorphic, they are either both abelian or both not abelian.
Hence $C_6$ and $S_3$ are not isomorphic.
== Sources ==
* : $\S 7.3$. Isomorphism: Example $136$
Category:Examples of Cyclic Groups
Category:Symmetric Group on 3 Letters
C^k Function Space is Banach Space

== Theorem ==
Let $I = \closedint a b$ be a closed real interval.
Let $\struct {\map {C^k} I, +, \, \cdot \,}_\R$ be the vector space of real-valued functions, k-times differentiable on $I$.
Let $x \in \map {C^k} I$ be a real-valued function of differentiability class $k$.
Let $\norm {\, \cdot \,}_{\map {C^k} I}$ be the $C^k$ norm on $I$.
Then $\struct {\map {C^k} I, +, \, \cdot \,}_\R$ equipped with $\norm {\, \cdot \,}_{\map {C^k} I}$ is a Banach space.
== Proof ==
== Also see ==
* Definition:C^k Norm
* C^k Norm is Norm
== Sources ==
* 
Category:Banach Spaces
C^k Norm is Norm

== Theorem ==
Let $I = \closedint a b$ be a closed real interval.
Let $\struct {\map {C^k} I, +, \, \cdot \,}_\R$ be the vector space of real-valued functions, k-times differentiable on $I$.
Let $x \in \map {C^k} I$ be a real-valued function of differentiability class $k$.
Let $\norm {\, \cdot \,}_{\map {C^k} I}$ be the $C^k$ norm on $I$.
Then $\norm {\, \cdot \,}_{\map {C^k} I}$ is a norm on $\struct {\map {C^k} I, +, \, \cdot \,}_\R$.
== Proof ==
=== Positive definiteness ===
Let $x \in \map {C^k} I$.
Then:
Suppose $\norm x_{\map {C^k} I} = 0$.
We have that the sum of non-negatives is zero if every element is zero.
Hence:
:$\forall i \in \N : 0 \le i \le k : \norm {x^{\paren i} }_\infty = 0$
That is:
:$\norm x_\infty = 0$
By Supremum Norm is Norm and :
:$\forall t \in I : \map x t = 0$
=== Positive homogeneity ===
Let $x \in \map {C^k} I$, $\alpha \in \R$.
Then:
=== Triangle inequality ===
Let $x, y \in \map {C^k} I$
== Also see ==
* Definition:C^k Norm
== Sources ==
* : $\S 1.2$: Normed and Banach spaces. Normed Spaces
Category:Examples of Norms
Caesar Cipher/Examples/Caesar Shift 5

== Example of Caesar Cipher ==
A Caesar cipher on the English alphabet with a Caesar shift of $5$ can be depicted in two-row notation as:
:$\texttt {A B C D E F G H I J K L M N O P Q R S T U V W X Y Z}$
:$\texttt {F G H I J K L M N O P Q R S T U V W X Y Z A B C D E}$
Hence, for example:
:$\texttt {A B Y}$
is encoded as:
:$\texttt {F G D}$
== Sources ==
* 
Category:Examples of Caesar Ciphers
Calculation Rounding Error/Examples/Arbitrary Example 1

== Example of Calculation Rounding Error ==
Consider the equation:
:$x = \dfrac 1 {1 - \cos 1 \degrees}$
Evaluating the calculation while rounding to $4$ decimal places gives:
:$x = 5000$
but the true value is $6565.8$ to $1$ decimal place.
Hence the calculation rounding error of this calculation is $1.6565.8$, or some $24 \%$ or $31 \%$ relative error, depending on how the latter is calculated.
== Proof ==
We have:
:$\cos 1 \degrees = 0.999847695 \ldots$
which is $0.9998$ to $4$ decimal places.
So to $4$ decimal places:
To $9$ decimal places:
Hence we calculate the relative error as follows, using the two variants:
== Sources ==
* Rounding (or roundoff) errors
* Rounding (or roundoff) errors
Category:Examples of Calculation Rounding Errors
Can a Prime Power be a Member of an Amicable Pair?

== Open Question ==
It is not known whether it is possible for a prime power to be a member of an amicable pair.
== Progress ==
If $p^n$ is a member of an amicable pair, then:
:$p^n > 10^{1500}$
:$n > 1400$
== Sources ==
* : $220$
* : $220$
Category:Amicable Pairs
Category:Open Questions
Cancellability by Cayley Table

== Theorem ==
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$ :
:$(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$.
=== Sufficient Condition ===
Let $a$ be such that:
:$(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$.
Thus from $(1)$:
:$\forall y_1, y_2 \in S: y_1 \ne y_2 \implies a \circ y_1 \ne a \circ y_2$
So by the Rule of Transposition:
:$\forall y_1, y_2 \in S: a \circ y_1 = a \circ y_2 \implies y_1 = y_2$
Also from $(2)$:
:$\forall y_1, y_2 \in S: y_1 \ne y_2 \implies y_1 \circ a \ne y_2 \circ a$
So by the Rule of Transposition:
:$\forall y_1, y_2 \in S: y_1 \circ a = y_2 \circ a \implies y_1 = y_2$
Thus it follows that $a$ is cancellable for $\circ$.
== Sources ==
* : Chapter $\text I$: Algebraic Structures: $\S 7$: Semigroups and Groups
Category:Cayley Tables
Cancellability of Congruences

== Theorem ==
Let $a, b, c, n \in \Z$ be integers.
Then:
:$c a \equiv c b \pmod n \iff a \equiv b \pmod {n / d}$
where $d = \gcd \set {c, n}$.
=== Corollary 1 ===
=== Corollary 2 ===
== Proof ==
Let $c a \equiv c b \pmod n$.
Then we have that $c a - c b = k n$ for some $k \in \Z$ by definition of congruence.
Now $d = \gcd \set {c, n}$, so from Integers Divided by GCD are Coprime we have:
:$\exists r, s \in Z: r \perp s: c = d r, n = d s$
So we substitute for $c$ and $n$ in $c a - c b = k n$:
:$d r a - d r b = k d s$
which leads us to:
:$r \paren {a - b} = k s$
So $s \divides \paren {a - b}$ and as $r \perp s$, from Euclid's Lemma $s \divides \paren {a - b}$.
So $a \equiv b \pmod s$ where $s = \dfrac n d$.
Now suppose $a \equiv b \pmod {n / d}$ where $d = \gcd \set {c, n}$.
Then:
:$\exists k \in \Z: a - b = k \dfrac n d$
Hence:
:$c a - c b = \dfrac {k c} d n$
As $d = \gcd \set {c, n}$ we have $d \divides c$ and so $\dfrac c d \in \Z$.
So:
:$c a \equiv c b \pmod n$
Category:Modulo Multiplication
Category:Modulo Arithmetic
Category:Cancellability of Congruences
Cancellability of Congruences/Corollary 1

== Corollary to Cancellability of Congruences ==
Let $c$ and $n$ be coprime integers, that is:
:$c \perp n$
Then:
:$c a \equiv c b \pmod n \implies a \equiv b \pmod n$
where $\equiv$ denotes congruence.
== Proof 1 ==
== Proof 2 ==
== Proof 3 ==
Category:Cancellability of Congruences
Cancellability of Congruences/Corollary 1/Proof 2

== Corollary to Cancellability of Congruences ==
== Proof ==
We are given that $c$ and $n$ are coprime.
So:
Then:
Thus:
== Sources ==
* : $\S 2.3$: Congruences: Theorem $1 \ \text{(iii)}$
Category:Cancellability of Congruences
Cancellability of Congruences/Corollary 1/Proof 3

== Corollary to Cancellability of Congruences ==
== Proof ==
Let:
:$c a \equiv c b \pmod n$
Then by definition of congruence:
:$n \divides k \paren {x - y}$
We have that:
:$c \perp n$
Thus by Euclid's Lemma:
:$n \divides \paren {x - y}$
So by definition of congruence:
:$a \equiv b \pmod n$
== Sources ==
* : Chapter $\text {I}$: The Group Concept: $\S 6$: Examples of Finite Groups: $\text{(iii)} \ \text{(D)}$
Category:Cancellability of Congruences
Cancellability of Congruences/Corollary 2

== Corollary to Cancellability of Congruences ==
Let $a, b, c$ be integers.
Let $p$ be a prime number such that $p \nmid c$.
Then:
:$c a \equiv c b \pmod p \implies a \equiv b \pmod p$
where $\equiv$ denotes congruence.
== Proof ==
As $p \nmid c$, it follows from Prime not Divisor implies Coprime that:
:$p \perp c$
where $\perp$ denotes that $p$ and $c$ are coprime.
The result follows from .
== Sources ==
* : $\text {4-1}$ Basic Properties of Congruences: Exercise $4$
Category:Cancellability of Congruences
Cancellable Element is Cancellable in Subset

== Theorem ==
Let $\struct {S, \circ}$ be an algebraic structure.
Let $\struct {T, \circ} \subseteq \struct {S, \circ}$.
Let $x \in T$ be cancellable in $S$.
Then $x$ is also cancellable in $T$.
== Proof ==
Let $x \in T$ be cancellable in $S$.
Then by definition, $x \in T$ is left cancellable in $S$.
It follows from Left Cancellable Element is Left Cancellable in Subset that $x \in T$ is left cancellable in $T$.
Again by definition, $x \in T$ is right cancellable in $S$.
It follows from Right Cancellable Element is Right Cancellable in Subset that $x \in T$ is right cancellable in $T$.
Thus $x$ is also both left cancellable and right cancellable in $T$.
So by definition, $x$ is cancellable in $T$.
== Sources ==
* : Chapter $\text {II}$: New Structures from Old: $\S 8$: Compositions Induced on Subsets
Category:Cancellability
Cancellable Elements of Monoid form Submonoid

== Theorem ==
The cancellable elements of a monoid $\struct {S, \circ}$ form a submonoid of $\struct {S, \circ}$.
== Proof ==
Let $C$ be the set of cancellable elements of $\struct {S, \circ}$.
Obviously $C \subseteq S$.
From Cancellable Elements of Semigroup form Subsemigroup, $\struct {C, \circ}$ is a subsemigroup of $S$.
Let $e_S$ be the identity of $\struct {S, \circ}$.
From Identity of Monoid is Cancellable, $e_S$ is cancellable, therefore $e_S \in C$.
As $e_S$ is the identity of $S$, we have that:
:$\forall x \in C: x \circ e_S = x = e_S \circ x$.
Thus $e_S$ is the identity of $\struct {C, \circ}$, which is therefore a monoid.
As $C \subseteq S$, the result follows.
Category:Monoids
Cancellable Elements of Semigroup form Subsemigroup

== Theorem ==
Let $\struct {S, \circ}$ be a semigroup.
Let $C$ be the set of cancellable elements of $\struct {S, \circ}$.
Then $\struct {C, \circ}$ is a subsemigroup of $\struct {S, \circ}$.
== Proof ==
Now let $C$ be the set of cancellable elements of $\struct {S, \circ}$.
Let $x, y \in C$.
Then $x$ and $y$ are both left cancellable and right cancellable.
Thus by Left Cancellable Elements of Semigroup form Subsemigroup:
:$x \circ y$ is left cancellable
and by Right Cancellable Elements of Semigroup form Subsemigroup:
:$x \circ y$ is right cancellable.
Thus $x \circ y$ is both left cancellable and right cancellable, and therefore cancellable.
Thus $x \circ y \in C$.
Thus $\struct {C, \circ}$ is closed and is therefore by the Subsemigroup Closure Test a subsemigroup of $\struct {S, \circ}$.
== Sources ==
* : Chapter $\text {II}$: New Structures from Old: $\S 8$: Compositions Induced on Subsets: Theorem $8.5$
Category:Subsemigroups
Category:Cancellability
Cancellable Finite Semigroup is Group

== Theorem ==
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 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 that:
:$\struct {S, \circ}$ is non-empty
:all elements of $S$ are cancellable
:$S$ is finite.
;Existence of Identity Element
Let $x \in S$ be arbitrary.
Then:
Thus $e$ is an identity element.
By Identity is Unique, there is only one such.
;Existence of Inverse Elements
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.
== Also see ==
* Cancellable Infinite Semigroup is not necessarily Group
== Sources ==
* : Chapter $\text {I}$: The Group Concept: $\S 4$: Alternative Axioms for Finite Groups: Theorem $1$
* : Chapter $2$: The Definition of Group Structure: $\S 26 \delta$
* : Chapter $6$: An Introduction to Groups: Exercise $3$
Category:Semigroups
Category:Finite Groups
Category:Cancellability
Cancellable Infinite Semigroup is not necessarily Group

== Theorem ==
Let $\struct {S, \circ}$ be a semigroup whose underlying set is infinite.
Let $\struct {S, \circ}$ be such that all elements of $S$ are cancellable.
Then it is not necessarily the case that $\struct {S, \circ}$ is a group.
== Proof ==
Consider the semigroup $\struct {\N, +}$.
From Natural Numbers under Addition form Commutative Semigroup, $\struct {\N, +}$ forms a semigroup.
From Natural Numbers are Infinite, the underlying set of $\struct {\N, +}$ is infinite.
From Natural Number Addition is Cancellable, all elements of $\struct {\N, +}$ are cancellable.
But from Natural Numbers under Addition do not form Group, $\struct {\N, +}$ is not a group.
== Sources ==
* : Chapter $6$: An Introduction to Groups: Exercise $3$
Category:Semigroups
Category:Cancellability