Algebra: motivational examples

Non-formal introduction - just some motivational examples

Peano axioms

See Peano axioms for details. I will give simplified explanation:

1. $N=0$ - zero is a natural number
2. $N+1$ - is a natural number

So solution of this equation: $N=N+1\text{ | }0$ forms all natural numbers.

Solution in this case can refer to (either):

• minimal solution
• unique solution
• maximal solution

Result: $N=\{0,1,2\dots \}$

Kleene closure

Classically denoted as $a^{\ast }$. But also can be written in form of Chomsky rules:

1. $S\to ϵ$
2. $S\to S\cdot a$

So solution of this equation: $S=S\cdot a\text{ | }ϵ$ forms language for Kleene closure $a^{\ast }$.

Result: $S=\{\epsilon ,a,aa\dots \}$ e.g. empty string, string “a”, string “aa” etc.

ADT list

Type signature for linked list in terms of ADT

List(T) = T * List(T) + 1

Or the same in terms of TypeScript:

type List<T> = {
  value: T;
  next: List<T>;
} | null;

Result: $List(T)=\{1,T,T\ast T\dots \}$ e.g. empty list, list with one item of type T, list with two items of type T, etc.

Conclusion

As we can see it’s all the same principles, but symbols are a bit different

Numbers	Languages	Types	Sets
+	|	+	$\cup$
*	$\cdot$	*	$\times$
0	$\varnothing$	$\varnothing$	$\{\}$
1	$ϵ$	1, null, $()$	$\{\epsilon \}$

1. Algebra allows to describe “structures”
2. Algebra can be applied to different areas. I skipped all details, but there are formal definitions which allow to specify exactly how operations behave, which allows to find exact correspondence between different system
3. List is a graph (DAG), which brings us to idea that we can use algebra to specify graphs

Related subjects:

• Algebraic graphs
• Combinatorial species
• Algebraic property graphs
• Categorical query language

See also:

• The algebra (and calculus!) of algebraic data types