2.1. Algebraic structures¶

2.1.1. Introduction¶

An algebra is a set S (called the carrier) together with zero or more operations, each of which is a function from $S^k \rightarrow S$ for some k. The value k is the number of arguments to the operation and is called “arity” of the operation. Typical operations are unary (one argument) or binary (two arguments).

0-ary operations: identity element, etc.. Also called constants
unary operations: negation
binary operations: addition, multiplication etc.

Various standard algebras are abstractions which allow us to reason about different situations at the same time. They are like base classes in an object oriented type hierarchy that provide minimum features common to all classes that inherit from them without specifying any details.

Our proofs and algorithms don’t require the detailed structure of say $\mathbb{Q}$, $\mathbb{R}$, or $\mathbb{Z}$, but in fact can work in any algebra of the appropriate type.

Typical properties of operations

Closure: $x \in S \cap y \in S \Rightarrow x + y \in S$.
Associativity: $x+(y+z) = (x+y)+z$
Identity: $0+x=x+0=x$
Inverse: $x+(-x)=(-x)+x=0$
Commutativity: $x+y=y+x$
Distributivity: $x(y+z)=xy+xz; (y+z)x = yx+zx$
Multiplicative Associativity : $(xy)z = x(yz)$
Multiplicative Identity: $1x = x1 = x$
Multiplicative Commutativity: $xy=yx$
Multiplicative Inverse : $xx^{-1}=x^{-1}x=1$

Hierarchy of algebraic structures

digraph G { graph[ overlap=false splines=true rankdir=BT ] compound=true; fontsize = 10; node [ fontsize = 10 shape = "record" color=gray fontcolor= blue ] edge [ fontsize = 8 ] subgraph{ Set [ label="{Set|no operations}" ] } subgraph cluster_one_op_one_set{ label="One set with one binary operation" node [ ] Magma[ label="{Magma|closure}" URL="http://en.wikipedia.org/wiki/Magma_(algebra)" ] Semigroup [ label="{Semigroup|associativity}" URL="http://en.wikipedia.org/wiki/Semigroup" ] Monoid [ label="{Monoid}" URL="http://en.wikipedia.org/wiki/Monoid" ] Group [ label="{Group|inverse}" URL="http://en.wikipedia.org/wiki/Group_(mathematics)" ] CommutativeGroup [ label="{Abelian Group|commutativity}" URL="http://en.wikipedia.org/wiki/Abelian_Group" ] Quasigroup [ label="{Quasigroup|inverse}" URL="http://en.wikipedia.org/wiki/Quasigroup" ] Unital [ label="{Unital|identity}" URL="http://en.wikipedia.org/wiki/Unital_algebra" ] Loop [ label="{Loop}" URL="http://en.wikipedia.org/wiki/Loop_(algebra)#Loop" ] Semicategory [ label="{Semicategory|associativity}" URL="http://en.wikipedia.org/wiki/Category_(mathematics)" ] Category [ label="{Category|identity}" URL="http://en.wikipedia.org/wiki/Category_(mathematics)" ] Groupoid [ label="{Groupoid|inverse}" URL="http://en.wikipedia.org/wiki/Groupoid" ] { rank=same; Magma;Semicategory; } Semigroup -> Magma; Quasigroup -> Magma; Unital -> Magma; Loop -> Unital; Loop -> Quasigroup; Monoid -> Semigroup; Monoid -> Unital; Group -> Monoid; Group -> Loop; CommutativeGroup -> Group; Category->Semicategory; Groupoid -> Category; Group -> Groupoid; } subgraph cluster_one_set_two_ops{ label="One set with two operations" Ring [ label="{Ring (S,+,*)|Abelian Group(+)\nMonoid(*)|distributivity}" URL="http://en.wikipedia.org/wiki/Ring_(mathematics)" ] CommutativeRing [ label="{Commutative Ring|commutative(*)}" URL="http://en.wikipedia.org/wiki/Commutative_ring" ] IntegralDomain [ label="{Integral Domain|no zero divisors}" URL="http://en.wikipedia.org/wiki/Integral_domain" ] Field [ label="{Field|S - \{0\}(Commutiative Group under *)}" URL="http://en.wikipedia.org/wiki/Field_(mathematics)" ] CommutativeRing->Ring; IntegralDomain->CommutativeRing; Field->IntegralDomain; } subgraph cluster_two_set_two_ops{ label="Two sets with two operations" VectorSpace[ label="{Vector Space\n(A over B)| Abelian Group (A)\n Field (B)}" URL="http://en.wikipedia.org/wiki/Vector_space" ] Module[ label="{Module\n(A over B)| Abelian Group (A)\n Ring (B)}" URL="http://en.wikipedia.org/wiki/Module_(mathematics)" ] RModule[ label="{R Module\n(A over B)| Abelian Group (A)\nCommutative Ring (B)}" URL="http://en.wikipedia.org/wiki/Module_(mathematics)" ] //GroupOps [ // label="{Group with operators\n(G with B))}" //] RModule->Module; VectorSpace->RModule; } subgraph cluster_two_set_three_ops{ label="Two sets with three ops" AlgebraOverRing [ label="{Algebra over ring\n(A over B)| bilinear product on A}" URL="http://en.wikipedia.org/wiki/Algebra_(ring_theory)" ] AlgebraOverField [ label="{Algebra over field\n(A over B)}" URL="http://en.wikipedia.org/wiki/Algebra_over_a_field" ] AlgebraOverField->AlgebraOverRing; AlgebraOverRing->RModule; AlgebraOverField->VectorSpace; } { edge [style = dotted, color=blue] Magma->Set; Semicategory->Set; Ring->CommutativeGroup; Ring->Monoid; Module->CommutativeGroup; VectorSpace->CommutativeGroup; //GroupOps->Group; //GroupOps->Set; } { // connections for 2nd sets edge [style=dotted, color=green] Module->Ring; RModule->CommutativeRing; VectorSpace->Field; } }

2.1.2. Single binary operation algebraic structures¶

Let S be a set and . be a binary operation defined over it.

2.1.2.1. Magma¶

S is closed under .

Magma is also known as groupoid at times. But category theory gives a different interpretation to the term groupoid.

Example: binary tree whose leaves are elements of some set A.

2.1.2.2. Semigroup¶

S is closed under .
Operator . is associative.

Examples:

Let A be a set, and S be a set of functions from A to A. Then (S, .) is a semigroup, where . is the composition operation defined by $(f . g)(x) = f(g(x))$.
Let $\mathbb{Z}^+$ be the positive integers. Then $(\mathbb{Z}^+, +)$ is a semigroup.

2.1.2.3. Monoid¶

A semigroup (S, .) is a monoid if it has an identity element.

$e.x = x.e = x$

If there is an identity element, then it is unique.

A semigroup can be turned into a monoid by adding a new identity element (if it doesn’t have one already).

2.1.2.4. Group¶

A monoid (S,.) is a group if for each a and b in S, there are solutions x and y to the equations $ax=b$ and $ya=b$. This implies existence of inverse. Also it can be shown that left inverse and right inverse are equal.

Examples

Let $S={x}$ and let $x*x=x$. Then $(S,*)$ is a group with identity x and $x^{-1}=x$.
$\mathbb{Q}$, $\mathbb{R}$, and $\mathbb{Z}$ are groups with the binary operation +, but not with the binary operation $*$.

2.1.2.5. Abelian Group¶

If a group is commutative which means that $xy=yx \forall x,y \in S$, then it is an abelian group.

2.1.3. Operations on algebras¶

2.1.3.1. Subalgebras¶

A subalgebra of an algebra A is obtained by taking a subset S’ of the carrier that is closed under all operations of the algebra. Any axioms satisfied by the parent algebra are inherited by its subalgebras.

A subalgebra generated by a particular element or a set of elements is the the smallest algebra of a given algebra that includes the specified elements. These elements are called generators.

2.1.3.2. Homomorphism¶

A function from the carrier of A to the carrier of B is a homomorphism written $f:A\rightarrow B$, if for any n-ary operation g, $g(f(x_1), ..., f(x_n)) = f(g(x_1, ..., x_n))$, where g on the left side is B’s version of g and g on the right side is A’s version of g. If the operation holds for a particular operation g, then f is said to preserve g. A homomorphism preserves all operations.

Image of f is defined as $f(A) = \{f(x) | x \in A\}$.
Let $f:A\rightarrow B$ be an algebra homomorphism. Then f(A) is a subalgebra of B.

2.1.4. Two operation algebraic structures¶

For more details see

Change log

Last Modified: $Id: overview.rst 249 2012-08-05 06:17:57Z shailesh $