Construction of Inverse Completion

From ProofWiki
Jump to navigation Jump to search


This page consists of a series of linked theorems, each of which builds towards one result.

To access the proofs for the individual theorems, click on the links which form the titles of each major section.

Initial Definitions

Let $\struct {S, \circ}$ be a commutative semigroup which has cancellable elements.

Let $\struct {C, \circ {\restriction_C} } \subseteq \struct {S, \circ}$ be the subsemigroup of cancellable elements of $\struct {S, \circ}$, where $\circ {\restriction_C}$ denotes the restriction of $\circ$ to $C$.

Cartesian Product with Cancellable Elements

Let $\struct {S \times C, \oplus}$ be the external direct product of $\struct {S, \circ}$ and $\struct {C, \circ {\restriction_C} }$, where $\oplus$ is the operation on $S \times C$ induced by $\circ$ on $S$ and $\circ {\restriction_C}$ on $C$.

That is:

$\forall \tuple {x, y}, \tuple {u, v} \in S \times C: \tuple {x, y} \oplus \tuple {u, v} = \tuple {x \circ u, y \mathop {\circ {\restriction_C} } v}$

Then $\struct {S \times C, \oplus}$ is a commutative semigroup.

Congruence Relation

The cross-relation $\boxtimes$ is a congruence relation on $\struct {S \times C, \oplus}$.

Members of Equivalence Classes

$\forall x, y \in S, a, b \in C:$

$(1): \quad \tuple {x \circ a, a} \boxtimes \tuple {y \circ b, b} \iff x = y$
$(2): \quad \eqclass {\tuple {x \circ a, y \circ a} } \boxtimes = \eqclass {\tuple {x, y} } \boxtimes$

where $\eqclass {\tuple {x, y} } \boxtimes$ is the equivalence class of $\tuple {x, y}$ under $\boxtimes$.

Equivalence Class of Equal Elements

$\forall c, d \in C: \tuple {c, c} \boxtimes \tuple {d, d}$

Natural Number Difference

In the context of the natural numbers, the difference is defined as:

$n - m = p \iff m + p = n$

from which it can be seen that the above congruence can be understood as:

$\tuple {x_1, y_1} \boxtimes \tuple {x_2, y_2} \iff x_1 + y_2 = x_2 + y_1 \iff x_1 - y_1 = x_2 - y_2$

Thus this congruence defines an equivalence between pairs of elements which have the same difference.

Quotient Structure

Let the quotient structure defined by $\boxtimes$ be:

$\struct {T', \oplus'} := \struct {\dfrac {S \times C} \boxtimes, \oplus_\boxtimes}$

where $\oplus_\boxtimes$ is the operation induced on $\dfrac {S \times C} \boxtimes$ by $\oplus$.

Quotient Structure is Commutative Semigroup

$\struct {T', \oplus'}$ is a commutative semigroup.

Quotient Mapping is Injective

Let the mapping $\psi: S \to T'$ be defined as:

$\forall x \in S: \map \psi x = \eqclass {\tuple {x \circ a, a} } \boxtimes$

Then $\psi: S \to T'$ is an injection, and does not depend on the particular element $a$ chosen.

Quotient Mapping is Monomorphism

The mapping $\psi: S \to T'$ is a monomorphism.

Image of Quotient Mapping is Subsemigroup

Let $S'$ be the image $\psi \sqbrk S$ of $S$.

Then $\struct {S', \oplus'}$ is a subsemigroup of $\struct {T', \oplus'}$.

Quotient Mapping to Image is Isomorphism

Let $S'$ be the image $\psi \sqbrk S$ of $S$.

Then $\psi$ is an isomorphism from $S$ onto $S'$.

Image of Cancellable Elements in Quotient Mapping

The set $C'$ of cancellable elements of the semigroup $S'$ is $\psi \sqbrk C$.

Properties of Quotient Structure

Identity of Quotient Structure

Let $c \in C$ be arbitrary.


$\eqclass {\tuple {c, c} } \boxtimes$

is the identity of $T'$.

Invertible Elements in Quotient Structure

Every cancellable element of $S'$ is invertible in $T'$.

Generator for Quotient Structure

$T' = S' \cup \paren {C'}^{-1}$ is a generator for the semigroup $T'$.

Quotient Structure is Inverse Completion

$T'$ is an inverse completion of its subsemigroup $S'$.


Elements of $T'$ are equivalence classes of ordered pairs $\tuple {x, y}$ where $x \in S, y \in C$.

Each of the elements of $\eqclass {\tuple {x, y} } \boxtimes$ is such that $x \circ y^{-1}$ have the same value, where $y^{-1} \in C^{-1}$.

Hence is it a natural progression to define an operation $\odot$, say, such that:

$x \odot y \equiv x \circ y^{-1}$

In the context of the integers, this operation is minus, hence:

$x - y \equiv x + \paren {-y}$

In the context of the rational numbers, this operation is division, hence:

$\dfrac x y \equiv x \times y^{-1}$

Each element of $S$, and hence in $C$, is identified (via the isomorphism $\psi$) with one of these equivalence classes.

If $S$ is a monoid, then it has an identity $e_S$, say, which is in $C$.


$\forall x \in C: \map \psi x = \eqclass {\tuple {x, e_S} } \boxtimes$

In particular:

$\map \psi {e_S} = \eqclass {\tuple {e_S, e_S} } \boxtimes$