Existence of Unique Subsemigroup Generated by Subset

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\struct {S, \circ}$ be a semigroup.

Let $\O \subset X \subseteq S$.

Let $\struct {T, \circ}$ be the subsemigroup generated by $X$.

Then $T = \gen X$ exists and is unique.


Proof 1

Existence

First, we prove that such a subsemigroup exists.

Let $\mathbb S$ be the set of all subsemigroups of $S$ which contain $X$.

$\mathbb S \ne \O$ because $S$ is itself a subsemigroup of $S$ (trivial), and thus $S \in \mathbb S$.


Let $T$ be the intersection of all the elements of $\mathbb S$.

By Intersection of Subsemigroups, $T$ is the largest element of $\mathbb S$ contained in each element of $\mathbb S$.

Thus $T$ is a subsemigroup of $S$.

Since $\forall x \in \mathbb S: X \subseteq x$, we see that $X \subseteq T$, so $T \in \mathbb S$.


Smallest

Now to show that $T$ is the smallest such subsemigroup.

If any $K \le S: X \subseteq K$, then $K \in \mathbb S$ and therefore $T \subseteq K$.

So $T$ is the smallest subsemigroup of $S$ containing $X$.


Uniqueness

Now we show that $T$ is unique.

Suppose $\exists T_1, T_2 \in \mathbb S$ such that $T_1$ and $T_2$ were two such smallest subsemigroups containing $X$.

Then, by the definition of smallest, each would be equal in size.

Without loss of generality, suppose that $T_1$ is not a subset of $T_2$.

Then their intersection (by definition containing $X$) would be a subsemigroup smaller than $T_1$.

Hence $T_1$ would not be the smallest.

Therefore each must be the subset of each other.

By definition of set equality, they must be the same set.

So the smallest subsemigroup, whose existence we have proved above, is unique.

$\blacksquare$


Proof 2

Let $\mathbb S$ be the set of all subsemigroups of $S$.

From Set of Subsemigroups forms Complete Lattice:

$\struct {\mathbb S, \subseteq}$ is a complete lattice.

where for every set $\mathbb H$ of subsemigroups of $S$:

the infimum of $\mathbb H$ necessarily admitted by $\mathbb H$ is $\ds \bigcap \mathbb H$.

Hence the result, by definition of infimum.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Existence_of_Unique_Subsemigroup_Generated_by_Subset&oldid=567150"