1.algebraic system

algebraic operation

A general expression of an operation

Addition operations in the set of natural numbers:

$$\mathbb{N}\times \mathbb{N}\to \mathbb{N}$$

Adding two natural numbers is still a natural number, it's a function.

The union and intersection operations on the power set P(A) of A are functions of:

$$P(A)\times P(A)\to P(A)$$

$P(A)$ refers to the family of sets composed of all subsets (including the total set and the empty set) of the original set $A$.

The essence of operations is functions.

Infix mode: $a+b=c$

function mode: $+(a,b)=c$

closure

Set $A$ is a nonempty set, function $f:A\times A\to A$ It's called an algebraic operation on $A$, then $A$ is closed to $f$, or the operation $f$​ is closed.

Subtraction and division on the set of natural numbers are not binary operations because the result of subtracting or dividing one natural number from another is not necessarily a natural number, which does not satisfy closure. But addition and multiplication are binary operations.

Defining binary operation

Expression

$$\mathrm{\forall }x,y\in \mathbb{R},x\circ y=max(x,y)$$

Table

$Z_n=\{0,1,2,...,n-1\},x\oplus y=(x+y)modn,x\otimes y=(x\cdot y)modn$​.

when $n=5$:

$\oplus$	0	1	2	3	4
0	0	1	2	3	4
1	1	2	3	4	0
2	2	3	4	0	1
3	3	4	0	1	2
4	4	0	1	2	3

$\otimes$	0	1	2	3	4
0	0	0	0	0	0
1	0	1	2	3	4
2	0	2	4	1	3
3	0	3	1	4	2
4	0	4	3	2	1

unary operation

Set $A$ is a nonempty set, function $f:A\to A$ is called a unary operation on $A$​.

Find the opposite number, conjugation, complement, negation, etc.

N-ary operation

Let $A_1,A_2,...,A_n$ be non-empty sets. If $\ast :A_1\times A_2\times ...\times A_n\to A$ is a function from $A_1\times A_2\times ...\times A_n$ to $A$, then $\ast$ is an n-ary operation on $A_1\times A_2\times ...\times A_n$​, abbreviated as n-ary operation.

When $A_1=A_2=...=A_n=A$, the operation $\ast$ is said to be closed on set $A$, or $\ast$ is called an n-ary operation on $A$.

Algebraic system and subalgebraic system

Let $A$ be a non-empty set, and ${\ast }_1,{\ast }_2,...,{\ast }_m$ be $m$-ary operations defined on $A$. If $k_1,k_2,...,k_m$ ($k_i\in {\mathbb{Z}}^{+},i=1,2,...,m$), then the system formed by the set $A$ and operations ${\ast }_1,{\ast }_2,...,{\ast }_m$ is called an algebraic system, abbreviated as Algebra, denoted by $<A,{\ast }_1,{\ast }_2,...,{\ast }_m>$.

$$<Set,operation1,operation2,...,operayionn>$$

If $A$​ is a finite set, the system is called a finite algebraic system; otherwise, it is called an infinite algebraic system.

Set algebra: $<P(A),\cup ,\cap ,\sim >$;

Proposition Algebra: $<S,\wedge ,\vee ,\mathrm{\neg }>$​.

Relationship between two algebra systems

Same Species

Let $<A,{\ast }_1,{\ast }_2,...,{\ast }_m>$ and $<B,{\circ }_1,{\circ }_2,...,{\circ }_m>$ be algebra systems, if ${\circ }_i$ and ${\ast }_i$ are $k_i$-ary operations ($i=1,2,...,m$​), then those algebra systems are same species.

In fact, the number of operations is the same and the number of elements corresponding to the operation is the same. For example, the following algebras are same species:

$$\begin{gathered} <\mathbb{N},+,\cdot >and<\mathbb{R},+,\cdot > \\ <P(A),\cap ,\cup ,\sim >and<S,\wedge ,\vee ,\mathrm{\neg }> \end{gathered}$$

Subalgebra

Let $<A,{\ast }_1,{\ast }_2,...,{\ast }_m>$ be an algebra system, if:

(1) $B\subseteq A$ and $B\ne \varnothing$​

(2) ${\ast }_1,{\ast }_2,...,{\ast }_m$ are closure on $B$

Then $<B,{\ast }_1,{\ast }_2,...{\ast }_m>$ is subalgebra of $<A,{\ast }_1,{\ast }_2,...,{\ast }_m>$.

if $B\subset A$, then $<B,{\ast }_1,{\ast }_2,...{\ast }_m>$ is proper subalgebra of $<A,{\ast }_1,{\ast }_2,...,{\ast }_m>$​.

for example:

$<\mathbb{N},+,\cdot >$ is proper subalgebra of $<\mathbb{R},+,\cdot >$.

Because their operations are the same and the set of natural numbers is a proper subset of the set of real numbers.

The subalgebraic system of any algebraic system must exist, since every algebraic system is a subalgebra of itself (a set must be a subset of itself).

Binary operation law

Associative law and Commutative law

Let $<A,\ast >$ be a binary algebraic system.

(1) If for any $x,y,z\in A$:

$$(x\ast y)\ast z=x\ast (y\ast z)$$

Then operation $\ast$ is associable on $A$, or $\ast$ satisfies the Associative law on $A$.

(2) If for any $x,y\in A$:

$$x\ast y=y\ast x$$

Then operation $\ast$ is commutable on $A$, or $\ast$ satisfies the Commutative law on $A$.

Idempotent law and Cancellation law

(3) If for any $x\in A$:

$$x\ast x=x$$

Then $\ast$ is idempotent on $A$, or $\ast$​​ satisfies the Idempotent law,

if an element $a\in A$ satisfies $a\ast a=a$, then $a$ is an idempotent element of $A$ with respect to $\ast$.

(4) If for any $x,y,z\in A$:

$$\begin{array}{}\text{(i)}& x\ast y=x\ast z\Rightarrow y=z\end{array}$$$$\begin{array}{}\text{(ii)}& y\ast x=z\ast x\Rightarrow y=z\end{array}$$

Then $\ast$ is cancelable or satisfies idempotent law on $A$, $x$ is the cancelable element of $A$ with respect to $\ast$.

Which satisfies $(i)$ called satisfies Left idempotent law, satisfies $(ii)$ called satisfies Right idempotent law,

corresponding $x$​ called Left cancelable element and Right cancelable element.

Distributive law and Absorption law

Let $<A,\ast ,\circ >$ be an algebra system.

(1) If for any $x,y,z\in A$:

$$\begin{array}{}\text{(iii)}& x\ast (y\circ z)=(x\ast y)\circ (x\ast z)\end{array}$$$$\begin{array}{}\text{(iv)}& (y\circ z)\ast x=(y\ast x)\circ (z\ast x)\end{array}$$

Then $\ast$ is distributive towards $\circ$ on $A$.

Which satisfies $(iii)$ called: $\ast$ is Left distributive on $A$ with respect to $\circ$​ (The first distributive law),

satisfies $(iv)$ called: $\ast$ is Right distributive on $A$ with respect to $\circ$ (The second distributive law).

(2) If for any $x,y\in A$:

$$\begin{array}{}\text{(v)}& x\ast (x\circ y)=x\end{array}$$$$\begin{array}{}\text{(vi)}& x\circ (x\ast y)\end{array}$$

Then $\ast$ and $\circ$​ satisfy Absorption law.

Example: $<P(A),\cup ,\cap ,\sim >$, $\cap$ and $\cup$ satisfy Absorption law on $P(A)$.

Special element of binary operation

Overview

Consider algebra systems:

$$\begin{array}{c}<\mathbb{R},+>:\mathrm{\forall }x\in \mathbb{R},x+0=0+x=x,x+(-x)=0\\ <\mathbb{R},\cdot >:\mathrm{\forall }x\in \mathbb{R},x\cdot 1=1\cdot x=x,0\cdot x=x\cdot 0=0\end{array}$$

The result of an operation between the identity element and other elements is equal to that element, the result of an operation between the zero element and other elements is equal to zero, and an operation between an element and its inverse is equal to zero.

For example, in addition to real numbers, 0 is the identity element, and $-x$ is the inverse element of $x$​; In real multiplication, 1 is the identity element and 0 is the zero element.

Identity element

Let $<A,\ast >$ be an algebra system. If there's $e\in A$, for any $x\in A$:

$$\begin{array}{}\text{(vii)}& e\ast x=x\end{array}$$$$\begin{array}{}\text{(viii)}& x\ast e=x\end{array}$$

Which satisfies $(vii)$, then $e$ is a Left identity element in $A$ with respect to operation $\ast$, denote as $e_l$​.

If satisfies $(viii)$, then $e$ is a Right identity element in $A$ with respect to operation $\ast$, denote as $e_r$​.

The identity elements must be idempotent and cancelable, and if an algebraic system has an identity element $e$, then $e$ must be both a left and right identity element. And it's the only identity element in the system.

Zero element

Let $<A,\ast >$ be an algebra system. If there's $\theta \in A$, for any $x\in A$:

$$\begin{array}{}\text{(ix)}& \theta \ast x=\theta \end{array}$$$$\begin{array}{}\text{(x)}& x\ast \theta =\theta \end{array}$$

Which satisfies $(ix)$, then $\theta$ is a Left zero element in $A$ with respect to operation $\ast$, denote as ${\theta }_l$​.

If satisfies $(x)$, then $\theta$ is a Right zero element in $A$ with respect to operation $\ast$, denote as ${\theta }_r$​.

The zero element must be an idempotent element, but it is not a cancelable element unless there is only one element in an algebraic system. If there are zero elements, then that zero element are both left zeros and right zeros. And it's the only zero element in the system.

Inverse element

Let $<A,\ast >$ be an algebra system. If $e$ is an identity element with respect to operation $\ast$, for any $a\in A$, if there's an element $b\in A$, which satisfies:

$$\begin{array}{}\text{(xi)}& b\ast a=e\end{array}$$$$\begin{array}{}\text{(xii)}& a\ast b=e\end{array}$$

Then $a$ is reversable, $b$ is an inverse of $a$, denote as $a^{-1}$. If satisfies$(xi)$, then $a$ is Left reversable, and $b$ is a Left inverse element of $a$, denote as $a_l^{-1}$​.

Let $<A,\ast >$ be a binary algebra system, $\ast$ is associative and there's an identity element $e$.

(1) For any $a\in A$, if $a$ has left and right inverses, then $a_l^{-1}=a_r^{-1}$, and $a^{-1}$ is the only reverse.

(2) If $a,b\in A$, and they have their inverses$a^{-1},b^{-1}$, then $(a\ast b{)}^{-1}=b^{-1}\ast a^{-1}$.

Homomorphism and Isomorphism

Overview

The properties of an algebraic system can be described in terms of operation laws and special elements, so how to describe the relationship or similarity between different algebraic systems?

Here's a simple example of isomorphism:

$\ast$	odd	even
odd	odd	even
even	even	even

is isomorphic to

$\circ$	1	0
1	1	0
0	0	0

We can define a function to establish a correspondence between two sets:

$$f:\{odd,even\}\to \{1,0\}$$

$f(odd)=1,f(even)=0$,

For any $x,y\in \{odd,even\}$, $f(x\ast y)=f(x)\circ f(y)$​.

With this expression, we establish the relationship between the operations.

Homomorphism

Let $<A,\ast >$ and $<B,\circ >$ be binary algebra systems, $f$ is a mapping from $A$ to $B$. For any $x,y\in A$, there's:

$$\begin{array}{}\text{(xiii,the Homomorphic equation)}& f(x\ast y)=f(x)\circ f(y)\end{array}$$

Then $f$ is the homomorphic mapping from $<A,\ast >$ to $<B,\circ >$. $f(A)$ is Homomorphic image, which $f(A)=\{f(x)|x\in A\}$. If there's a Homomorphic mapping from $<A,\ast >$ to $<B,\circ >$, then $<A,\ast >$ and $<B,\circ >$ are homomorphic, denoted as $<A,\ast >\sim <B,\circ >$(This is actually a similar symbol that we learned in junior high). When $A=B$, it's called an endomorphism.

As shown in the figure, two homomorphic algebraic systems can go through the same mapping and still make the mapped elements equal after the operation.

Isomorphism

When the homomorphic maps are injective, surjective, and bijective respectively, f is said to be monomorphism, epimorphism, and isomorphism respectively. If there's a isomorphism from $<A,\ast >$ to $<B,\circ >$, then algebra system $<A,\ast >$ and $<B,\circ >$ are isomorphism, denoted as $<A,\ast >\cong <B,\circ >$​.

We can see that if two algebra systems are isomorphism, their inner logic are completely same.

Example:

$$<\mathbb{N},+>\sim <\mathbb{E},+>$$

Let $f:\mathbb{N}\to \mathbb{E},\mathrm{\forall }x\in \mathbb{N},f(x)=2x$,

$\mathrm{\forall }x,y\in \mathbb{N},f(x+y)=2(x+y)=2x+2y=f(x)+f(y)$, satisfies the homomorphic equation, and $f$ is obviously a bijection, so $<\mathbb{N},+>\cong <\mathbb{E},+>$​.

Extension

Let $<A,{\ast }_1,{\ast }_2,...,{\ast }_m>$ and $<B,{\circ }_1,{\circ }_2,...,{\circ }_m>$ are algebra system which have m binary operation, $f$ is a mapping form $A$ to $B$. For any $x,y\in A$:

$$\begin{array}{}\text{(xiii,the Homomorphic equation)}& f(x{\ast }_{i}y)=f(x){\circ }_{i}f(y),(i=1,2,...,m)\end{array}$$

Then $f$ is Homomorphic mapping from $<A,{\ast }_1,{\ast }_2,...{\ast }_m>$ to $<B,{\circ }_1,{\circ }_2,...,{\circ }_m>$​.

This theorem states that if there are multiple binary operations, there will be multiple homomorphic equations, which are not necessarily unique. They can only be said to be homomorphic if all of them satisfy the conditions.

Let $f$ be the Homomorphic mapping from $<A,\ast >$ to $<B,\circ >$, then $<f(A),\circ >$ is subalgebra of $<B,\circ >$.

Properties of homomorphism

1

Let $f$ is an epimorphism of binary algebra system $<A,\ast >$ to $<B,\circ >$, then:

If operation $\ast$ is commutative, then operation $\circ$ is commutative.

If operation $\ast$ is combinative, then operation $\circ$​ is combinative.

If $e$ is an identity of $<A,\ast >$, then $f(e)$ is identity of $<B,\circ >$​.

If $\theta$ is zero element of $<A,\ast >$, then $f(\theta )$ is zero element of $<B,\circ >$.

If $a$ is idempotent element of $<A,\ast >$, then $f(a)$ is idempotent element of $<B,\circ >$​.

If $x^{-1}$ is inverse of $x$ in $<A,\ast >$, then $f(x^{-1})$ is inverse of $f(x)$ in $<B,\circ >$.

If $a$ is cancelable element of $<A,\ast >$, then $f(a)$ is cancelable element of $<B,\circ >$​.

In other words, the properties mentioned above, as long as they are satisfied in $<A,\ast >$, will be satisfied in $<B,\circ >$.

2

Let $f$ is an epimorphism of binary algebra system $<A,{\ast }_1,{\ast }_2>$ to $<B,{\circ }_1,{\circ }_2>$, then:

If operation ${\ast }_1$ satisfies Distributive law in $A$ with respect to ${\ast }_2$, then operation ${\circ }_1$ also satisfies Distributive law in $B$ with respect to ${\circ }_2$.

The same is true for the absorption law.

Summary

It can be seen that if two algebraic systems are full homomorphic, they share many properties such as the operation laws and special elements, while if two algebraic systems are isomorphic, they can be considered exactly the same.