Algebraic Systems

Author

Li Hui

Operations and Their Properties

Algebraic systems are systems defined by a number of algebraic operations on an abstract set.

Different mathematical structures often share the same algebraic operation properties. Abstracting these common properties and studying them uniformly gives rise to the science of Abstract Algebra.

Definition of Algebraic Operations

Let $A$ be a nonempty set and $n$ a positive integer. A mapping $f:A^n{\rightarrow}A$ from $A^n=A{\times}A{\times}\cdots{\times}A$ to $A$ is called an $n$-ary algebraic operation on $A$, or simply an $n$-ary operation; $n$ is called the order of the operation.

When $n=1$, $f:A{\rightarrow}A$ is called a unary operation (Unary operation) on $A$;

When $n=2$, $f:A^2{\rightarrow}A$ is called a binary operation (Binary operation) on $A$.

Example: The unary operation $f:R{\rightarrow}R$, where $f(x)=-x$ for any $x{\in}R$, is the usual negation operation.

Example: The unary operation $f:R^+{\rightarrow}R^+$, where $f(x)=1/x$ for any $x{\in}R^+$, is the usual reciprocal operation.

Example: The binary operation $f:R^2{\rightarrow}R$, where $f(x_1,x_2)=x_1+x_2$ for any $x_1,x_2{\in}R$, is the usual addition operation.

For an algebraic operation $f:A^n{\rightarrow}A$:

The domain $\text{dom}\,(f)=A^n$ is called the totality of the algebraic operation.

The range $\text{ran}\,(f){\subseteq}A$ is called the closure of the algebraic operation.

For example, on the set of integers $Z$, addition, subtraction, and multiplication are all binary operations, since the sum, difference, and product of any two integers is again an integer.

However, division is not a binary operation on $Z$, since the quotient of two integers need not be an integer, and the divisor cannot be zero.

In fact, addition and multiplication are binary operations on the natural numbers; addition, subtraction, and multiplication are binary operations on the set of integers and also on the set of real numbers; multiplication and division are binary operations on $R{\setminus}\{0\}$.

Example: Let the function $f:S{\rightarrow}S$ be defined on $S=\{1,2,\cdots,n,\tfrac{1}{2},\tfrac{1}{3},\cdots,\tfrac{1}{n}\}$, where for any $x{\in}S$, $f(x)=\tfrac{1}{x}$. Then $f$ is a unary operation on $S$.

The symbol $\sim$ or $\lnot$ is commonly used to denote a unary operator; the above example is written as: $\sim(x)=\tfrac{1}{x}$.

For example, ${\sim}(5)=\tfrac{1}{5}$, ${\sim}(7)=\tfrac{1}{7}$, ${\sim}(12)=\tfrac{1}{12}$. Symbols such as $*$, $\circ$, $\bullet$, $\oplus$, $\otimes$ are used to denote binary operators.

Example: Let $N$ be the set of natural numbers. The function $f:N^2{\rightarrow}N$ is defined as: for any ${\langle}n_1,n_2{\rangle}{\in}N^2$, \[f(n_1,n_2)=\text{lcm}(n_1,n_2).\] That is, the least common multiple (Least common multiple) of $n_1$ and $n_2$. $f$ is a binary operation on $N$.

Using $*$ to denote the operator: \[f(1,1)=\text{lcm}(1,1)=1*1=1\] \[f(2,3)=2*3=6\] \[f(4,8)=4*8=8\]

Example: Let $R$ be the set of real numbers and $n$ a positive integer. The function $f:R^n{\rightarrow}R$ is defined as: for any ${\langle}r_1,r_2,\cdots,r_n{\rangle}{\in}R^n$, \[f(r_1,r_2,\cdots,r_n)=r_1\] Then $f$ is an $n$-ary operation on $R$.

Using $\circ$ to denote the operator: \[\circ(r_1,r_2,\cdots,r_n)=r_1\]

Definition: Let $*$ be an $n$-ary operation on a set $A$. If for any ${\langle}a_1,a_2,\cdots,a_n{\rangle}{\in}A^n$ we have \[*(a_1,a_2,\cdots,a_n){\in}A,\] then $*$ is said to be closed on $A$.

Example: Determine whether the following sets are closed under ordinary addition “+” and ordinary multiplication “$\times$”:

\[A=\{0,1\}\] \[B=\{x|x=2^n,n{\in}N\}\] \[C=\{-1,1\}\] \[D=\{x|x=2n,n{\in}N\}\]

Solution: The “$\times$” operation is closed on all four sets. For the “+” operation:

$A$ is not closed, since $1{\in}A$ but $1+1=2{\notin}A$.

$B$ is not closed, since $2$ and $2^2$ both belong to $B$ but $2+2^2=6{\notin}B$.

$C$ is not closed, since $1{\in}C$ but $1+1=2{\notin}C$.

$D$ is closed.

Example: The function $f:Z^2{\rightarrow}Z$ is defined as: for any ${\langle}n_1,n_2{\rangle}{\in}Z^2$, $f(n_1,n_2)=n_1-n_2$.

The operation “$-$” is closed on $Z$. However, taking $N$ instead, “$-$” is not closed on $N$, since $2,3{\in}N$ but $2-3{\notin}N$.

Example: The function $f:N^2{\rightarrow}N$ is defined as: for any ${\langle}n_1,n_2{\rangle}{\in}N^2$, $f(n_1,n_2)=n_1+n_2$.

The operation “+” is closed on $N$. However, taking $N{\cup}\{-1\}$, “+” is not closed on $N{\cup}\{-1\}$.

Since the operations defined in algebraic systems can extend beyond number fields, operation rules need not be expressible by a single analytic formula; they are usually defined by operation tables.

For finite sets, unary and binary operations on $A$ are commonly represented by operation tables.

For example, a unary operation and a binary operation on the set $S=\{a_1,a_2,\cdots,a_n\}$ are represented respectively by the following operation tables, where $\sim$ and $*$ denote the unary and binary operators respectively.

\[ \begin{array}{cc} a_1 & {\sim}(a_1)\\ a_2 & {\sim}(a_2)\\ \vdots & \vdots\\ a_n & {\sim}(a_n)\\ \end{array} \]

\[ \begin{array}{ccccc} * & a_1 & a_2 & \cdots & a_n\\ a_1 & a_1*a_1 & a_1*a_2 & \cdots & a_1*a_n \\ a_2 & a_2*a_1 & a_2*a_2 & \cdots & a_2*a_n \\ \vdots & \vdots & \vdots & \vdots & \vdots\\ a_n & a_n*a_1 & a_n*a_2 & \cdots & a_n*a_n \\ \end{array} \]

Example: Let $S=\{1,2,-1,-2\}$. Construct the operation table for the unary negation operation on $S$.

Solution: The operation table is as follows:

\[ \begin{array}{cc} a_i & {\sim}(a_i)\\ 1 & -1\\ 2 & -2\\ -1 & 1\\ -2 & 2\\ \end{array} \]

Example: Let $S=\{a,b,c\}$. A binary operation on $S$ is given by the following table:

\[ \begin{array}{cccc} * & a & b & c \\ a & a & b & c \\ b & b & c & a \\ c & c & a & b \\ \end{array} \]

Find $a*b$, $b*c$, $c*c$.

Solution:

\[a*b=b\]

\[b*c=a\]

\[c*c=b\]

Properties of Algebraic Operations

Definition: Let $*$ be a binary operation defined on a set $A$. If for any $a,b{\in}A$ we have: \[a*b=b*a\] then $*$ is said to be commutative (Commutative) on $A$. ($*$ satisfies the commutative law)

Definition: If for any $a,b,c{\in}A$ we have: \[(a*b)*c=a*(b*c)\] then $*$ is said to be associative (Associative) on $A$. ($*$ satisfies the associative law)

For example, ordinary addition “+” and multiplication “$\times$” on the set of natural numbers are both commutative, since for $a,b{\in}N$: \[a+b=b+a,\,\,\,a{\times}b=b{\times}a.\] Example: Let $Q$ be the set of rational numbers, and let $*$ be a binary operation on $Q$ defined by: \[a*b=a+b-a{\times}b\] for any $a,b{\in}Q$. Is $*$ commutative?

Solution: For any $a,b{\in}Q$: \[a*b=a+b-a{\times}b=b+a-b{\times}a=b*a\] Therefore, the operation $*$ is commutative.

Example: Let $N$ be the set of natural numbers. For each of the following cases, determine whether the operation $\circ$ is associative:

For any $a,b{\in}N$, define: $a{\circ}b=\max(a,b)$

Solution: For any $a,b,c{\in}N$:

\[(a{\circ}b){\circ}c=\max(a,b){\circ}c\] \[=\max(\max(a,b),c)=\max(a,b,c)\]

\[a{\circ}(b{\circ}c)=a{\circ}\max(b,c)\] \[=\max(a,\max(b,c))=\max(a,b,c)\]

Therefore, the operation $\circ$ is associative.

For any $a,b{\in}N$, define $a{\circ}b=a+2b$.

Solution: For any $a,b,c{\in}N$:

\[(a{\circ}b){\circ}c=(a+2b){\circ}c=(a+2b)+2c=a+2b+2c.\]

\[a{\circ}(b{\circ}c)=a{\circ}(b+2c)=a+2(b+2c)=a+2b+4c.\] So $(a{\circ}b){\circ}c{\neq}a{\circ}(b{\circ}c)$.

Therefore, the operation $\circ$ is not associative.

Example: Determine whether the following binary operations $\circ$ on the set of real numbers $R$ are commutative and/or associative:

$a{\circ}b=b$
$a{\circ}b=|a+b|$

Solution: (1) For any $a,b,c{\in}R$:

\[(a{\circ}b){\circ}c=b{\circ}c=c\]

\[a{\circ}(b{\circ}c)=a{\circ}c=c\]

So $(a{\circ}b){\circ}c=a{\circ}(b{\circ}c)$.

Therefore, $\circ$ is associative.

But $a{\circ}b=b$ and $b{\circ}a=a$; when $a{\neq}b$, $a{\circ}b{\neq}b{\circ}a$.

Therefore, $\circ$ is not commutative.

Taking $a=b=1$, $c=-2$: \[(a{\circ}b){\circ}c=||1+1|-2|=0\] \[a{\circ}(b{\circ}c)=|1+|1-2||=2\]

Clearly $(a{\circ}b){\circ}c{\neq}a{\circ}(b{\circ}c)$, so ${\circ}$ is not associative.

For any $a,b{\in}R$:

\[a{\circ}b=|a+b|=|b+a|=b{\circ}a.\]

Therefore ${\circ}$ is commutative.

Definition: Let $*$ be a binary operation on a set $A$ that is associative. For any $x{\in}A$, define: \[x^n=x*x*{\cdots}*x\,\text{($n$ copies of $x$ under $*$)}\] called the $n$-th power (Power) of $x$, and $n$ is called the exponent (Exponent) of $x$.

The inductive definition of $x^n$ is: \[ \begin{cases} x^1=x & \\ x^{n+1}=x^n*x & n=1,2,3,\cdots\\ \end{cases} \]

Theorem: For any positive integers $m$ and $n$:

$x^m*x^n=x^{m+n}$
$(x^m)^n=x^{mn}$

Definition: Let $*$ be a binary operation defined on a set $A$. If there exists $x{\in}A$ such that $x*x=x$, then $x$ is called an idempotent element of $*$.

If every element of $A$ is an idempotent element with respect to $*$, then $*$ is said to satisfy the idempotent law.

For example, for multiplication “${\times}$” on $R$, $1$ is an idempotent element since $1{\times}1=1$.

For addition “+” on $R$, $0$ is an idempotent element since $0+0=0$.

But neither of these two operations satisfies the idempotent law.

Also, for the power set $P(S)$ of any set $S$, both “$\cap$” and “$\cup$” satisfy the idempotent law.

Since every element of $P(S)$ is idempotent with respect to both operations: for any $A{\in}P(S)$, \[A{\cup}A=A,\,\,A{\cap}A=A.\]

Definition: Let $*$ and $\Delta$ be two binary operations defined on a set $A$. For any $a,b,c{\in}A$, if:

$a*(b{\Delta}c)=(a*b){\Delta}(a*c)$
$(b{\Delta}c)*a=(b*a){\Delta}(c*a)$

then $*$ is said to be distributive (Distributive) over $\Delta$, or $*$ satisfies the distributive law over $\Delta$.

If only (1) holds, then $*$ is said to satisfy the left distributive law over $\Delta$.

If only (2) holds, then $*$ is said to satisfy the right distributive law over $\Delta$.

Let $S=\{0,1\}$. Two binary operations $*$ and $\Delta$ on $S$ are defined as:

\[ \begin{array}{ccc} * & 0 & 1\\ 0 & 0 & 1\\ 1 & 1 & 0\\ \end{array} \]

\[ \begin{array}{ccc} \Delta & 0 & 1\\ 0 & 0 & 0\\ 1 & 0 & 1\\ \end{array} \]

Question: Is $*$ distributive over $\Delta$?

Solution: \[1*\{0{\Delta}1\}=1*0=1\] \[(1*0)\Delta(1*1)=1{\Delta}0=0\]

\[1*(0{\Delta}1{\neq}(1*0)\Delta(1*1)\] Therefore $*$ is not distributive over $\Delta$.

Example: On the set of real numbers $R$, multiplication $\times$ is distributive over addition $+$, but addition $+$ is not distributive over multiplication $\times$.

Definition: Let $*$ and $\Delta$ be two binary operations defined on a set $A$. For any $a,b{\in}A$, if:

$a*(a{\Delta}b)=a$
$(a{\Delta}b)*a=a$

then $*$ is said to be absorptive (Absorptive) over $\Delta$, or $*$ satisfies the absorption law over $\Delta$.

If only (1) holds, then $*$ is said to be left absorptive over $\Delta$.

If only (2) holds, then $*$ is said to be right absorptive over $\Delta$.

For the power set $P(S)$ of any set $S$: “$\cap$” satisfies the absorption law over “$\cup$”, and “$\cup$” satisfies the absorption law over “$\cap$”.

Because for any $A,B{\in}P(S)$: $A{\cup}(A{\cap}B)=A,\,\,\,A{\cap}(A{\cup}B)=A.$

Special Elements

Definition: Let $*$ be a binary operation defined on a set $S$:

If there exists $e_l{\in}S$ such that $e_l*x=x$ for all $x{\in}S$, then $e_l$ is called a left identity element (left unity) of $S$ with respect to $*$.
If there exists $e_r{\in}S$ such that $x*e_r=x$ for all $x{\in}S$, then $e_r$ is called a right identity element (right unity) of $S$ with respect to $*$.
If there exists $e{\in}S$ that is both a left identity element and a right identity element, then $e$ is called an identity element (unity) of $S$ with respect to $*$.

For example, let $R^*$ denote the set of all nonzero real numbers, and define the binary operation ${\circ}$ on $R^*$ by $a{\circ}b=a$.

Clearly, there is no left identity element, while every element of $R^*$ is a right identity element.

If instead we define $\circ$ by $a{\circ}b=b$, then there is no right identity element, while every element of $R^*$ is a left identity element.

For example, $N$ is the set of natural numbers, and $+$ is ordinary addition. Clearly, the identity element of $N$ with respect to $+$ is $0$, since $a+0=0+a=a$ for any $a{\in}N$.

Theorem: Let $*$ be a binary operation defined on a set $S$. If $*$ has both a left identity element $e_l$ and a right identity element $e_r$, then $e_l=e_r=e$, and $e$ is the unique identity element of $S$ with respect to $*$.

Let $S=\{\alpha,\beta,\gamma,\delta\}$. A binary operation on $S$ is defined as follows. Identify the left identity element(s), right identity element(s), and identity element of each operation.

\[ \begin{array}{ccccc} * & \alpha & \beta & \gamma & \delta\\ \hline \alpha & \delta & \alpha & \beta & \gamma\\ \beta & \alpha & \beta & \gamma & \delta\\ \gamma & \alpha & \beta & \gamma & \gamma\\ \delta & \alpha & \beta & \gamma & \delta\\ \end{array} \]

Solution: For the $*$ operation, $\beta$ and $\delta$ are left identity elements; there is no right identity element. There is no identity element.

Let $S=\{\alpha,\beta,\gamma,\delta\}$. Another binary operation on $S$ is defined as follows. Identify the left identity element(s), right identity element(s), and identity element of each operation.

\[ \begin{array}{ccccc} \Delta & \alpha & \beta & \gamma & \delta\\ \hline \alpha & \alpha & \beta & \delta & \gamma\\ \beta & \beta & \alpha & \gamma & \delta\\ \gamma & \gamma & \delta & \alpha & \beta\\ \delta & \delta & \delta & \beta & \gamma\\ \end{array} \]

Solution: For the $\Delta$ operation, $\alpha$ is a right identity element; there is no left identity element. There is no identity element.

Example: Let $S=\{\text{light},\text{dark}\}$. A binary operation $*$ on $S$ is defined as follows. Identify the identity element.

\[ \begin{array}{ccc} * & \text{light} & \text{dark}\\ \hline \text{light} & \text{light} & \text{dark}\\ \text{dark} & \text{dark} & \text{dark}\\ \end{array} \]

Solution: Light is the identity element of $S$ with respect to the $*$ operation.

Definition: Let $*$ be a binary operation defined on a set $S$.

If there exists $\theta_l{\in}S$ such that $\theta_l*x=\theta_l$ for all $x{\in}S$, then $\theta_l$ is called a left zero element of $S$ with respect to $*$.
If there exists $\theta_r{\in}S$ such that $x*\theta_r=\theta_r$ for all $x{\in}S$, then $\theta_r$ is called a right zero element of $S$ with respect to $*$.
If there exists $\theta{\in}S$ that is both a left zero element and a right zero element, then $\theta$ is called a zero element of $S$ with respect to $*$.

Example: Let $S=\{\text{light},\text{dark}\}$. A binary operation $*$ on $S$ is defined as follows. Identify the zero element.

\[ \begin{array}{ccc} * & \text{light} & \text{dark}\\ \hline \text{light} & \text{light} & \text{dark}\\ \text{dark} & \text{dark} & \text{dark}\\ \end{array} \]

Solution: Dark is the zero element of $S$ with respect to the $*$ operation.

Let $S=\{1,2,3\}$. The binary operations on $S$ are defined as follows. Identify the left and right zero elements of each operation.

\[ \begin{array}{ccc} * & 1 & 2 & 3\\ \hline 1 & 2 & 2 & 1\\ 2 & 3 & 2 & 2\\ 3 & 1 & 2 & 2\\ \end{array} \]

\[ \begin{array}{ccc} + & 1 & 2 & 3\\ \hline 1 & 1 & 1 & 1\\ 2 & 3 & 2 & 2\\ 3 & 3 & 3 & 3\\ \end{array} \]

\[ \begin{array}{ccc} \times & 1 & 2 & 3\\ \hline 1 & 2 & 1 & 3\\ 2 & 3 & 2 & 3\\ 3 & 3 & 3 & 3\\ \end{array} \]

Solution: For $*$: $2$ is a right zero element; there is no left zero element. For $+$: both $1$ and $3$ are left zero elements; there is no right zero element. For $\times$: $3$ is both a left and right zero element, so $3$ is the zero element of $\times$.

Theorem: Let $*$ be a binary operation defined on a set $S$. If $*$ has both a left zero element $\theta_l$ and a right zero element $\theta_r$, then: \[\theta_l=\theta_r=\theta\] and $\theta$ is the unique zero element of $S$ with respect to $*$.

Definition: Let $*$ be a binary operation defined on a set $S$, and let $e$ be the identity element of $S$ with respect to $*$. For $x{\in}S$:

If there exists $b_l{\in}S$ such that $b_l*x=e$, then $x$ is said to be left invertible, and $b_l$ is called a left inverse element of $x$.
If there exists $b_r{\in}S$ such that $x*b_r=e$, then $x$ is said to be right invertible, and $b_r$ is called a right inverse element of $x$.
If there exists $b{\in}S$ such that $x*b=b*x=e$, then $x$ is said to be invertible, and $b$ is called an inverse element of $x$.

For example, for ordinary multiplication $\times$ on $R$, the identity element is $1$.

For any $a{\in}R$ with $a{\neq}0$, $1/a{\in}R$ satisfies $a{\times}1/a=1/a{\times}a=1$. Thus every nonzero real number in $R$ is invertible with respect to $\times$.

Example: Let $S=\{\alpha,\beta,\gamma,\delta,\zeta\}$, and let $*$ be a binary operation on $S$ defined as follows. Identify the left and right inverse elements of each element of $S$ (if they exist).

\[ \begin{array}{cccccc} * & \alpha & \beta & \gamma & \delta & \zeta \\ \alpha & \alpha & \beta & \gamma & \delta & \zeta\\ \beta & \beta & \delta & \alpha & \gamma & \delta\\ \gamma & \gamma & \alpha & \beta & \alpha & \beta\\ \delta & \delta & \alpha & \gamma & \delta & \gamma\\ \zeta & \zeta & \delta & \alpha & \gamma & \zeta\\ \end{array} \]

Solution:

The identity element is $\alpha$.

\[ \begin{array}{ccc} & \text{Left} & \text{Right}\\ \beta & \gamma,\delta & \gamma \\ \gamma & \beta,\zeta & \beta,\delta \\ \delta & \gamma & \beta \\ \zeta & \text{none} & \gamma \\ \end{array} \]

Example: Let $S=\{1,2,3,4\}$, and let $*$ be a binary operation on $S$ defined as follows. Identify the left and right inverse elements of each element of $S$ (if they exist).

\[ \begin{array}{ccccc} * & 1 & 2 & 3 & 4 \\ 1 & 2 & 3 & 1 & 3 \\ 2 & 1 & 4 & 2 & 2 \\ 3 & 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 4 & 1 \\ \end{array} \]

Solution: The identity element is $3$, i.e., $e=3$.

$1$’s left inverse element is $4$; right inverse elements are $2$ and $4$.

$2$’s left inverse element is $1$; no right inverse element exists.

$3$’s left inverse element is $3$; right inverse element is $3$.

$4$’s left inverse element is $1$; right inverse element is $1$.

$1$ and $4$ are mutual inverses:

$1^{-1}=4$, $4^{-1}=1$.

Theorem: Let $*$ be a binary operation defined on a set $S$ satisfying the associative law, and let $e$ be the identity element of $S$ with respect to $*$. If an element $x{\in}S$ has both a left inverse $x_l^{-1}$ and a right inverse $x_r^{-1}$, then $x_l^{-1}=x_r^{-1}=x^{-1}$, and $x^{-1}$ is the unique inverse of $x$.

Proof: Since $x_l^{-1}$ and $x_r^{-1}$ are the left and right inverses of $x$ respectively, and by associativity:

\[x_l^{-1}=x_l^{-1}*e=x_l^{-1}*(x*x_r^{-1})\] \[=(x_l^{-1}*x)*x_r^{-1}=e*x_r^{-1}=x_r^{-1}\] Therefore $x_l^{-1}=x_r^{-1}=x^{-1}$ is an inverse of $x$.

Let $x^\prime$ be another inverse of $x$. Then:

\[x^{-1}=e*x^{-1}=(x^\prime*x)*x^{-1}\] \[=x^\prime*(x*x^{-1})=x^\prime*e=x^\prime\] Therefore, the inverse of $x$ is unique.

Let $*$ be a binary operation defined on a set $S$. For any $a,b,c{\in}A$:

If $a*b=a*c$ and $a{\neq}0$ implies $b=c$;
If $b*a=c*a$ and $a{\neq}0$ implies $b=c$;

then $*$ is said to be cancellative, or $*$ satisfies the cancellation law.

If only (1) holds, then $*$ is said to be left cancellative; if only (2) holds, then $*$ is said to be right cancellative.

Example: Ordinary addition $+$ and multiplication $\times$ on $R$ satisfy the cancellation law.

Example: The union and intersection operations on the power set $P(S)$ do not satisfy the cancellation law. Because for ${\forall}A,B,C{\in}P(S)$, $A{\cup}B=A{\cup}C$ does not imply $B=C$, and $A{\cap}B=A{\cap}C$ also does not imply $B=C$.

Example: On the set of rational numbers $Q$, define $*$ by: for any $x,y{\in}Q$, $x*y=x+y-xy$. Then $*$ is cancellative.

Proof: Clearly, the zero element of $*$ is $1$.

For any $x,y,z{\in}Q$, if $x*y=x*z$ and $x{\neq}1$, i.e., $x+y-xy=x+z-xz$, then $(x-1)(y-z)=0$, so $y=z$ (since $x{\neq}1$). Therefore $*$ is cancellative.

Theorem: Let $*$ be a binary operation defined on a set $S$ with $|S|>1$. If $*$ has both an identity element $e$ and a zero element $0$, then $e{\neq}0$.

Theorem: Let $*$ be a binary operation defined on a set $S$, and let $e$ be the identity element of $S$ with respect to $*$. If an element $x{\in}S$ has an inverse $x^{-1}$, then $x^{-1}$ is also invertible, and $(x^{-1})^{-1}=x$.

Theorem: The zero element has no inverse element.

Algebraic Systems

Definition: Let $A$ be a nonempty set, and let $*_1,*_2,\cdots,*_r$ be algebraic operations. The structure formed by the set $A$ together with the operations $*_1,*_2,\cdots,*_r$ is called an algebraic system, denoted \[U={\langle}A,\mathsf{*}_1,\mathsf{*}_2,\cdots,\mathsf{*}_r{\rangle},\] and the set $A$ is called the domain (Domain) of the algebraic system. When $A$ is a finite set, $U$ is called a finite algebraic system.

For example, ${\langle}Z,+{\rangle}$, ${\langle}Z,\times{\rangle}$, ${\langle}Z,+,\times{\rangle}$ are all algebraic systems.

Example: In the power set $P(S)$ of any set $S$, considering the complement “$\sim$”, union “$\cup$”, and intersection “$\cap$” operations, ${\langle}P(S),\sim,\cup,\cap{\rangle}$ constitutes an algebraic system called the set algebra.

Here, “complement” is a unary operation, while “union” and “intersection” are binary operations.

Example: ${\langle}N_6,\oplus_6{\rangle}$ is an algebraic system, where $N_6=\{0,1,2,3,4,5\}$. For any $a,b{\in}N_6$, $a{\oplus}_6b=(a+b)\,\mod\,6$.

Solution: Clearly for any $a,b{\in}N_6$, $a{\oplus}_6b=(a+b)\,\mod\,6{\in}N_6$. Hence $\oplus_6$ is an algebraic operation on $N_6$, and ${\langle}N_6,\oplus_6{\rangle}$ is an algebraic system.

\[ \begin{array}{ccccccc} \mathsf{\oplus}_6 & 0 & 1 & 2 & 3 & 4 & 5\\ 0 & 0 & 1 & 2 & 3 & 4 & 5\\ 1 & 1 & 2 & 3 & 4 & 5 & 0\\ 2 & 2 & 3 & 4 & 5 & 0 & 1\\ 3 & 3 & 4 & 5 & 0 & 1 & 2\\ 4 & 4 & 5 & 0 & 1 & 2 & 3\\ 5 & 5 & 0 & 1 & 2 & 3 & 4\\ \end{array} \]

Example: Let $S=\{0,1\}$. The $+$ and $*$ operations on $S$ are defined as follows:

\[ \begin{array}{ccc} + & 0 & 1\\ 0 & 0 & 1\\ 1 & 1 & 0\\ \end{array}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \begin{array}{ccc} * & 0 & 1\\ 0 & 0 & 0\\ 1 & 0 & 1\\ \end{array} \]

Then ${\langle}\{0,1\},+,*{\rangle}$ is an algebraic system.

Definition: Let $U={\langle}A,*_1,*_2,\cdots,*_r{\rangle}$ be an algebraic system, and let $X$ be a nonempty subset of $A$. If the operations $*_1,*_2,\cdots,*_r$ are all closed on $X$, then the algebraic system \[V={\langle}X,\mathsf{*}_1,\mathsf{*}_2,\cdots,\mathsf{*}_r{\rangle}\] is called a subalgebra of $U$, and $U$ is called an extension of $V$. If $X$ is a proper subset of $A$, then $V$ is a proper subalgebra of $U$.

For example, let $E$, $Z$, and $R$ denote the sets of even integers, integers, and real numbers respectively, with $+$ and $\times$ denoting ordinary addition and multiplication. Then:

${\langle}Z,+,\times{\rangle}$ is a subalgebra of ${\langle}R,+,\times{\rangle}$.

${\langle}E,+,\times{\rangle}$ is a subalgebra of ${\langle}Z,+,\times{\rangle}$.

Homomorphism and Isomorphism of Algebraic Systems

Definition: Let $U={\langle}X,*_1,*_2,\cdots,*_r{\rangle}$ and $V={\langle}Y,+_1,+_2,\cdots,+_r{\rangle}$ be two algebraic systems. If $*_i$ and $+_i$ are both $k_i$-ary operations for $i=1,2,\cdots,r$, then these two algebraic systems are said to be of the same type.

For example, let $N$ and $Z$ be the sets of natural numbers and integers respectively, with $+$, $\times$, and $\sim$ denoting ordinary addition, multiplication, and negation. Then ${\langle}N,+{\rangle}$ and ${\langle}Z,\times{\rangle}$ are two algebraic systems of the same type.

However: ${\langle}N,+,\times{\rangle}$ and ${\langle}Z,+{\rangle}$ are not of the same type. Nor are ${\langle}N,+{\rangle}$ and ${\langle}Z,\sim{\rangle}$.

For example, let $Z$ be the set of integers and $R^+$ the set of positive real numbers, with $\sim$ and $/$ denoting negation and reciprocal operations. Then ${\langle}Z,\sim{\rangle}$ and ${\langle}R^+,/{\rangle}$ are two algebraic systems of the same type.

Definition: Let $U={\langle}X,*{\rangle}$ and $V={\langle}Y,+{\rangle}$ be two algebraic systems of the same type, where $*$ and $+$ are both binary operations, and let $f$ be a function from $X$ to $Y$. If for any $x_1,x_2{\in}X$ we have \[f(x_1*x_2)=f(x_1)+f(x_2)\] then $f$ is called a homomorphism from the algebraic system $U$ to $V$, and $U$ and $V$ are said to be homomorphic.

When $f$ is injective, surjective, or bijective, $f$ is called a monomorphism, epimorphism (surjective homomorphism), or isomorphism, respectively.

Example: Let $U={\langle}M_n(R),*{\rangle}$ and $V={\langle}R,\times{\rangle}$, where $R$ is the set of real numbers, $M_n(R)$ is the set of real $n{\times}n$ matrices, and the operations $*$ in $U$ and $\times$ in $V$ are matrix multiplication and scalar multiplication respectively.

The function $f:M_n(R){\rightarrow}R$ is defined by: for ${\forall}A{\in}M_n(R)$, $f(A)=|A|$. Is $f$ a homomorphism from $U$ to $V$? What kind of homomorphism is it?

Solution: For any $A,B{\in}M_n(R)$: \[f(A*B)=|A*B|=|A|\times|B|=f(A){\times}f(B)\] So $f$ is a homomorphism.

$f$ is surjective but not injective, so $f$ is an epimorphism from $U$ to $V$.

Example: Let $U={\langle}R,+{\rangle}$ and $V={\langle}R,\times{\rangle}$, where $R$ is the set of real numbers and $+$, $\times$ are ordinary addition and multiplication. The function $f:R{\rightarrow}R$ is defined by: for ${\forall}x{\in}R$, \[f(x)=5^x\] Prove that $f$ is a homomorphism and is a monomorphism.

Proof: For any $x,y{\in}R$: \[f(x+y)=5^{x+y}=5^x{\times}5^y=f(x){\times}f(y)\] So $f$ is a homomorphism. Moreover, $f$ is a strictly monotone increasing function on $R$, so $f$ is injective. Therefore $f$ is a monomorphism from $U$ to $V$.

Example: Let $N$ be the set of natural numbers. Let $U={\langle}N,+{\rangle}$ and $V={\langle}N_4,+_4{\rangle}$. The function $f:N{\rightarrow}N_4$ is defined by: for ${\forall}x{\in}N$, \[f(x)=x\,\mod\,4\] Prove that $f$ is an epimorphism from $U$ to $V$.

Proof: For any $x,y{\in}N$: \[f(x+y)=(x+y)\,\mod\,4\] \[=(x\,\mod\,4+y\,\mod\,4)\,\mod\,4\] \[=x\,\mod\,4\mathsf{+}_4y\,\mod\,4\] \[=f(x)\mathsf{+}_4f(y)\] Clearly $f$ is surjective, so $f$ is an epimorphism from $U$ to $V$.

If there exists an isomorphism $f$ between algebraic systems $U$ and $V$, then $U$ and $V$ are said to be isomorphic, denoted $U{\cong}V$.

If $f$ is a homomorphism from an algebraic system $U={\langle}X,*{\rangle}$ to itself $U={\langle}X,*{\rangle}$, then $f$ is called an endomorphism.

If $f$ is an isomorphism from an algebraic system $U={\langle}X,*{\rangle}$ to itself $U={\langle}X,*{\rangle}$, then $f$ is called an automorphism.

For example, when $U={\langle}Z,+{\rangle}$, $f(x)=-x$ is an automorphism.

Example: Let $U={\langle}R^+,\times{\rangle}$ and $V={\langle}R,+{\rangle}$. Prove that $U{\cong}V$.

Proof: Define $f:R^+{\rightarrow}R$ by: for ${\forall}x{\in}R^+$, \[f(x)=\ln\,x\] Then for any $x,y{\in}R^+$: \[f(x{\times}y)=\ln(x{\times}y)=\ln\,x+\ln\,y=f(x)+f(y)\] So $f$ is a homomorphism from $U$ to $V$.

For any $x,y{\in}R^+$, if $x{\neq}y$ then $\ln\,x{\neq}\ln\,y$, so $f$ is injective.

Conversely, for any $y{\in}R$, there exists a unique $x=e^y{\in}R^+$ such that $y=f(x)=\ln\,x$, so $f$ is surjective.

Hence $f$ is bijective, and therefore $f$ is an isomorphism from $U$ to $V$, i.e., $U{\cong}V$.

Definition: Let $U={\langle}X,\circ,\vartriangle{\rangle}$ and $V={\langle}Y,\bullet,\blacktriangle{\rangle}$ be two algebraic systems of the same type, where $\circ$, $\vartriangle$, $\bullet$, $\blacktriangle$ are all binary operations, and let $f:X{\rightarrow}Y$. If for any $x_1,x_2{\in}X$: \[f(x_1{\circ}x_2)=f(x_1){\bullet}f(x_2),\,\,f(x_1{\vartriangle}x_2)=f(x_1){\blacktriangle}f(x_2)\] then $f$ is called a homomorphism from $U$ to $V$, and $U$ and $V$ are said to be homomorphic.

When $f$ is injective, surjective, or bijective, $f$ is called a monomorphism, epimorphism, or isomorphism, respectively.

Example: Given algebraic systems $U={\langle}Z,\times,+{\rangle}$ and $V={\langle}N_m,\times_m,+_m{\rangle}$. Here $N_m=\{0,1,2,\cdots,m-1\}$, and the operations on $N_m$ are modular arithmetic: for any $x_1,x_2{\in}Z$:

\[x_1\mathsf{+}_mx_2=(x_1+x_2)\,\mod\,m,\,\,x_1\mathsf{\times}_mx_2=(x_1{\times}x_2)\,\mod\,m\] Define $f:Z{\rightarrow}N_m$ by: for any $x{\in}Z$, $f(x)=x\,\mod\,m$.

Prove that $f$ is a homomorphism from $U$ to $V$.

Proof: For any $x_1,x_2{\in}Z$: \[f(x_1+x_2)=(x_1+x_2)\,\mod\,m=x_1\,\mod\,m{\mathsf{+}_m}x_2\,\mod\,m\] That is: \[f(x_1+x_2)=f(x_1){\mathsf{+}_m}f(x_2).\] \[f(x_1{\times}x_2)=(x_1{\times}x_2)\,\mod\,m=x_1\,\mod\,m{\mathsf{\times}_m}x_2\,\mod\,m\] That is: \[f(x_1{\times}x_2)=f(x_1){\mathsf{\times}_m}f(x_2).\]

Therefore $f$ is a homomorphism from $U$ to $V$.

Definition: Let $U={\langle}X,*_1,*_2,\cdots,*_r{\rangle}$ and $V={\langle}Y,+_1,+_2,\cdots,+_r{\rangle}$ be two algebraic systems of the same type, where $*_i$ and $+_i$ are both $k_i$-ary operations for $i=1,2,\cdots,r$, and let $f$ be a function from $X$ to $Y$. For each $k_i$-ary operation ($i=1,2,\cdots,r$), if for any $x_1,x_2,\cdots,x_{k_i}{\in}X$ we have

\[f(\mathsf{*}_i(x_1,x_2,\cdots,x_{k_i}))=\mathsf{+}_i(f(x_1),f(x_2),\cdots,f(x_{k_i}))\] then $f$ is called a homomorphism from $U$ to $V$, and $U$ and $V$ are said to be homomorphic.

Theorem: Given algebraic systems:

$U={\langle}X,+_1,+_2,\cdots,+_r{\rangle}$ and $V={\langle}Y,*_1,*_2,\cdots,*_r{\rangle}$, where $+_i$ and $*_i$ ($i=1,2,\cdots,n$) are all binary operations.

If there exists an isomorphism $f:X{\rightarrow}Y$ such that for any $a,b{\in}X$: \[f(a{\mathsf{+}_i}b)=f(a){\mathsf{*}_i}f(b)\,\,(i=1,2,\cdots,n)\] then:

If $+_i$ is commutative, then $*_i$ is also commutative.
If $+_i$ is associative, then $*_i$ is also associative.
If $+_i$ has an identity element $e_i$, then $*_i$ also has an identity element $f(e_i)$.
If $+_i$ has a zero element $\mathbf{0}_i$, then $*_i$ also has a zero element $f(\mathbf{0}_i)$.
For operation $+_i$, if $x{\in}X$ has an inverse $x^{-1}$, then for operation $*_i$, $f(x)$ also has an inverse $f(x^{-1})$.
If operation $+_i$ is distributive over operation $+_j$, then operation $*_i$ is also distributive over operation $*_j$. ($i,j{\in}\{1,2,\cdots,n\}$, $i{\neq}j$)

Theorem: If $f$ is a homomorphism from ${\langle}A,*{\rangle}$ to ${\langle}B,\circ{\rangle}$, and $g$ is a homomorphism from ${\langle}B,\circ{\rangle}$ to ${\langle}C,\odot{\rangle}$, then the composite function $f{\cdot}g$ is a homomorphism from ${\langle}A,*{\rangle}$ to ${\langle}C,\odot{\rangle}$, where $*$, $\circ$, $\odot$ are binary operations.

Proof: For any ${\forall}x,y{\in}A$:

\[f{\cdot}g(x*y)=g(f(x*y))=g(f(x){\circ}f(y))\] \[=g(f(x)){\odot}g(f(y))=(f{\cdot}g)(x){\odot}(f{\cdot}g)(y)\]

Therefore the composite function $f{\cdot}g$ is a homomorphism from ${\langle}A,*{\rangle}$ to ${\langle}C,\odot{\rangle}$.

Theorem: Given algebraic systems $U={\langle}X,*{\rangle}$ and $V={\langle}Y,\circ{\rangle}$, if the function $f:X{\rightarrow}Y$ is a homomorphism from $U$ to $V$, then the algebraic system $V^\prime={\langle}f(X),\circ{\rangle}$ is a subalgebra of $V$, and $V^\prime$ is called the homomorphic image of $U$ under $f$.

Congruence Relations and Quotient Algebraic Systems

Congruence Relations

Definition: Let $*$ be a binary operation defined on a set $A$, and let $R$ be an equivalence relation on $A$. If for any $x_1,x_2{\in}A$ and $y_1,y_2{\in}A$: \[{\langle}x_1,y_1{\rangle}{\in}R\,{\wedge}{\langle}x_2,y_2{\rangle}{\in}R\,{\Rightarrow}\,{\langle}x_1*x_2,y_1*y_2{\rangle}{\in}R\]

then the relation $R$ is said to satisfy the substitution property with respect to the binary operation $*$.

Definition: Let $U={\langle}A,*{\rangle}$ be an algebraic system, where $*$ is a binary operation on $A$, and let $R$ be an equivalence relation on $A$. If $R$ satisfies the substitution property with respect to $*$, then $R$ is called a congruence relation (Congruence relation) on $A$ with respect to $*$. In this case, the equivalence classes of $R$ are called congruence classes (Congruence classes).

Note: An equivalence relation with the substitution property is called a congruence relation.

Example: Let $U={\langle}Z,+{\rangle}$, where $Z$ is the set of integers and $+$ is ordinary addition. The equivalence relation $R$ on $Z$ is defined by: for any $x,y{\in}Z$, ${\langle}x,y{\rangle}{\in}R$ if and only if $x=y$. Prove that $R$ is a congruence relation.

Proof: For any $x_1,x_2{\in}Z$ and $y_1,y_2{\in}Z$:

If ${\langle}x_1,y_1{\rangle}{\in}R$ and ${\langle}x_2,y_2{\rangle}{\in}R$, then $x_1=y_1$ and $x_2=y_2$.

Thus $x_1+x_2,y_1+y_2{\in}Z$ and $x_1+x_2=y_1+y_2$.

Therefore ${\langle}x_1+x_2,y_1+y_2{\rangle}{\in}R$.

So $R$ is a congruence relation on $U$.

Example: Let $V={\langle}S,+{\rangle}$ with $S=\{a,b,c,d\}$. The $+$ operation is defined as follows:

\[ \begin{array}{ccccc} + & a & b & c & d \\ a & a & a & d & c \\ b & b & a & d & a \\ c & c & b & a & b \\ d & c & d & b & a \\ \end{array} \] For the equivalence relation on $S$: \[R=\{{\langle}a,a{\rangle},{\langle}b,b{\rangle},{\langle}c,c{\rangle},{\langle}d,d{\rangle}\] \[,{\langle}a,b{\rangle},{\langle}b,a{\rangle},{\langle}c,d{\rangle},{\langle}d,c{\rangle}\}\] Is $R$ a congruence relation on $V$?

Solution: For the $+$ operation, take \[{\langle}a,b{\rangle},{\langle}c,d{\rangle}{\in}R\] but \[{\langle}a+c,b+d{\rangle}={\langle}d,a{\rangle}{\notin}R\] So $R$ does not satisfy the substitution property with respect to $+$, and therefore $R$ is not a congruence relation on $V$.

A congruence relation is always an equivalence relation. But this example shows that an equivalence relation need not be a congruence relation.

Theorem: Let $f$ be a homomorphism from the algebraic system $U={\langle}A,*{\rangle}$ to $V={\langle}B,\#{\rangle}$, where $*$ and $\#$ are binary operations on $A$ and $B$. Define the binary relation $R$ on $A$ by: ${\langle}x,y{\rangle}{\in}R$ if and only if $f(x)=f(y)$. Then $R$ is a congruence relation on $A$.

$R$ is called the congruence relation induced by the homomorphism $f$.

Quotient Algebra

Definition: Let $R$ be a congruence relation on the algebraic system $U={\langle}X,*{\rangle}$, where $*$ is a binary operation on $X$. Define an algebraic system $V={\langle}X/R,\odot{\rangle}$ where:

$X/R=\{[x]_R|x{\in}X\}$
For any $[x]_R,[y]_R{\in}X/R$:

\[ [x]_R\odot[y]_R=[x*y]_R \]

The algebraic system $V$ is called the quotient algebra of $U$ with respect to $R$, denoted $U/R$.

Example: Let $U={\langle}Z,+{\rangle}$, where $Z$ is the set of integers and $+$ is ordinary addition. Let $R$ be the congruence modulo 4. Find the quotient algebra $U/R$.

Solution: Construct $U/R={\langle}Z/R,\odot{\rangle}$. \[R=\{{\langle}a,b{\rangle}{\in}Z,a{\equiv}b\,\mod\,4\}\] Quotient set: $Z/R=\{[0]_R,[1]_R,[2]_R,[3]_R\}$, where:

\[[0]_R=\{\cdots,-8,-4,0,4,8,\cdots\}\] \[[1]_R=\{\cdots,-7,-3,1,5,9,\cdots\}\] \[[2]_R=\{\cdots,-6,-2,2,6,10,\cdots\}\] \[[3]_R=\{\cdots,-5,-1,3,7,11,\cdots\}\]

Construct $U/R={\langle}Z/R,\odot{\rangle}$.

The $\odot$ operation is defined by: for any $[x]_R,[y]_R{\in}Z/R$:

\[[x]_R{\odot}[y]_R=[x+y]_R=[(x+y)\,\mod\,4]_R\] The resulting operation table for $\odot$:

\[ \begin{array}{ccccc} \odot & [0]_R & [1]_R & [2]_R & [3]_R\\ \,[0]_R & [0]_R & [1]_R & [2]_R & [3]_R\\ \,[1]_R & [1]_R & [2]_R & [3]_R & [0]_R\\ \,[2]_R & [2]_R & [3]_R & [0]_R & [1]_R\\ \,[3]_R & [3]_R & [0]_R & [1]_R & [2]_R\\ \end{array} \]

Thus the quotient algebra of $U$ with respect to $R$ is \[U/R={\langle}Z/R,\odot{\rangle}.\]

Definition: Let $R$ be an equivalence relation on a set $A$. Define the function $f:A{\rightarrow}A/R$ by: \[{\forall}x{\in}A,\,\,\,f(x)=[x]_R\] Then $f$ is called the canonical map (or natural map) from $A$ to the quotient set $A/R$.

Example: Let $A=\{a,b,c,d\}$, and let $R$ be an equivalence relation on $A$ with \[R=\{{\langle}a,a{\rangle},{\langle}a,b{\rangle},{\langle}b,a{\rangle},{\langle}b,b{\rangle} \]

\[{\langle}c,c{\rangle},{\langle}c,d{\rangle},{\langle}d,c{\rangle},{\langle}d,d{\rangle}\}\]

Find the canonical map $f$.

Solution: Since $[a]_R=[b]_R=\{a,b\}$ and $[c]_R=[d]_R=\{c,d\}$,

the quotient set is $A/R=\{\{a,b\},\{c,d\}\}$.

The canonical map is:

$f:A{\rightarrow}A/R$,

$f(a)=f(b)=\{a,b\}$,

$f(c)=f(d)=\{c,d\}$.

Theorem: If $R$ is a congruence relation on the algebraic system $U={\langle}A,*{\rangle}$, where $*$ is a binary operation, and the quotient algebra of $U$ with respect to $R$ is $U/R={\langle}A/R,\odot{\rangle}$, then the canonical map

\[f:A{\rightarrow}A/R\]

is a homomorphism from $U$ to $V$.

The map $f$ is called the homomorphism induced by the congruence relation $R$.

Theorem: If $f$ is a homomorphism from the algebraic system $U={\langle}A,*{\rangle}$ to $V={\langle}B,\circ{\rangle}$, and $R$ is the congruence relation on $U$ induced by $f$, where $*$ and $\circ$ are binary operations.

Then there exists an isomorphism between the quotient algebra $U/R={\langle}A/R,\odot{\rangle}$ and the homomorphic image $V^\prime={\langle}f(A),\circ{\rangle}$:

$g:A/R{\rightarrow}f(A)$,

that is, the algebraic system ${\langle}A/R,\odot{\rangle}$ is isomorphic to $V^\prime={\langle}f(A),\circ{\rangle}$.