[Discrete Mathematics] lecture 6 - algebra

Overview

This lecture introduces the concept of an algebraic structure, defined by a carrier set, operations, and constants. It covers foundational ideas like closure, subalgebras, identity and zero elements, and inverses. Key structures are introduced, including semigroups, monoids, and groups, along with the hierarchy among them.

The lecture also defines homomorphisms (structure-preserving maps between algebras) and explores their types: epimorphisms, monomorphisms, and isomorphisms. Finally, it introduces congruence relations as equivalence relations compatible with algebraic operations, and discusses how they relate to structure preservation within algebras.

Introduction to Algebra

Definition 1 (algebra) 
An algebra must specify these three things: 
‣ A set called the carrier of the algebra 
‣ Operators defined on the carrier 
‣ Distinguished elements of the carrier called constants of the algebra

Definition 2 (closed) 
Let $\circ$ and $\triangleright$ be binary and unary operations on a set $T$, and let $T'$ be a subset of $T$. 
‣ If $x,y \in T' \implies x \circ y \in T'$ , then $T'$ is closed with respect to $\circ$,
‣ If $x \in T' \implies \triangleright x\in T'$ , then $T'$ is closed with respect to $\triangleright$.

Definition 3 (subalgebra) 
Let $A= \left<S,\circ,\triangleright, k\right>$ and $B= \left<S',\circ',\triangleright', k'\right>$ be algebras. Then $a'$ is a subalgebra of A if 
‣ $S' \subseteq S$ 
‣ $\forall a,b \in S' , :a \circ ' b = a \circ b$ 
‣ $\forall a \in S' , : \triangleright ' a = \triangleright a$ 
‣ $k' = k$

Definition 4 (identity/zero) 
Let $\circ$ be a binary operation. 
‣ An element $1$ of a set $S$ is an identity for $\circ$ if
$\forall x \in S , : 1 \circ x = x \circ 1 = x$ 
‣ An element $0$ of a set $S$ is a zero for $\circ$ if
$\forall x \in S , : 0 \circ x = x \circ 0 = 0$

Definition 5 
Let $\circ$ be a binary operation. 
‣ An element $1_{l}$ of a set $S$ is a left identity for $\circ$ if
$\forall x \in S , : 1_{l} \circ x= x$ 
‣ An element $0_{l}$ of a set $S$ is a left zero for $\circ$ if
$\forall x \in S , : 0_{l} \circ x = 0_{l}$
‣ Similarly, right identity and right zero for $\circ$ is defined.

Definition 6 (inverse)
Let $\circ$ be a binary operation and 1 an identity for the operation $\circ$.
‣ If $x \circ y = 1$, then $x$ is a left inverse of $y$ and $y$ is a right inverse of $x$.
‣ If $x \circ y = y \circ x = 1$ , then $x$ is an inverse of $y$ with respect to the operation \circ

Definition 7 (semigroup) 
A semigroup is an algebra with signature $\left<S,\circ\right>$ such that \circ is a associative operation on $S$.

Theorem 1 
If $\left<S,\circ\right>$ is a semigroup and $\left<T, \circ\right>$ is a subalgebra of $\left<S,\circ\right>$, then $\left<T,\circ\right>$ is a semigroup.

Definition 8 (monoid) 
A monoid is an algebra with signature $\left<S,\circ,1\right>$ such that $\circ$ is a associative operation on $S$ and 1 is an identity for $\circ$.

Definition 9 (group) 
A group is an algebra with signature $\left<S,\circ, \triangleright,1\right>$ such that $\circ$ is a associative operation on $S$, 1 is an identity for $\circ$, and $\triangleright x$ is a inverse of $x$.

Note: It can be concluded that every element of $S$ has an inverse with respect to $\circ$ since $S$ is closed with respect to the unary operator.

($\because \forall x \in S, : (\triangleright x) \circ x = x \circ (\triangleright x) = 1 $)

Theorem 2 
Let $\left<S,\circ, \triangleright,1\right>$ be a group. Every element of $S$ has a unique inverse with respect to $\circ$.

Note: {semigroups} $\supseteq$ {monoids} $\supseteq$ {groups}

Definition 10 (homomorphism) 
Let $A= \left<S,\circ \right>$ and $A'= \left<S',\circ' \right>$ be algebras. A function $f: S \to S'$ is a homomorphism from $A$ to $A'$ if 
$ h(x\circ y) = h(x) \circ' h(y)$

Theorem 3 
Let $A= \left<S,\circ, \triangleright,k\right>$ and $A'= \left<S',\circ', \triangleright',k'\right>$ be groups, and $h: S \to S'$ be a homomorphism from $A$ to $A'$. Then, 
‣ $h(k) = k'$ 
‣ $h(\triangleright x) = \triangleright' h(x)$

Definition 11 
‣ Epimorphism is onto and homomorphism. 
‣ Monomorphism is one-to-one and homomorphism. 
‣ Isomorphism is bijective and homomorphism.

Definition 12 (congruence)
Let $A= \left<S,\circ, \triangleright\right>$ be an algebra. An equivalence relation $E$ on $S$ is a right congruence relation on $A$ if,
‣ $\left<x,y\right> \in E \rightarrow \left<x \circ z, y \circ z\right> \in E$ 
‣ $\left<x,y\right> \in E \rightarrow \left<\triangleright x, \triangleright y\right> \in E$ 
The left congruence relation is defined similarly.

Definition 13 
Let $A= \left<S,\circ, \triangleright\right>$ be an algebra. An equivalence relation $E$ on $S$ is a congruence relation on $A$ if $E$ is a right and left congruence relation.

Theorem 4 
Let $A= \left<S,\circ \right>$ be an algebra and $E$ be a equivalence relation on $S$. Then, $E$ is a congruence relation on $A$ if and only if
$\left(\left<x_1,y_1\right> \in E \wedge \left<x_2,y_2\right> \in E\right)$ $\implies \left<x_1 \circ x_2, y_1 \circ y_2\right> \in E$