| |
Sets with Operations: Algebras
|
Algebra aka. Algebraic Structure [wiki]
|
An algebra A consists of 1 set S + n mappings/functions fi on it, called "operations".
Formally, A = (S,f1,...,fn).
Of course there may be an infinite number of (n-ary) operations defined on S.
But only n of them are included in the algebraic structure.
«In case there are no ambiguities,
we usually identify the set with the algebraic structure.
For example, a group (G,*) is usually referred simply as a group G»
[wiki].
«But to be perfectly precise,
different operations on the same set define different groups»
[wiki].
Similarly, if functions h : G -> H are classified as
a homomorphism
between (sets) G and H because
h(a *G b) = h(a) *H h(b) for all a, b  G,
we should more precisely be talking about a homomorphism
between (magma) algebras (G,*G) and (H,*H).
And if homomorphism h is a bijection then it is an isomorphism
between G and H - or rather (G,*G) and (H,*H).
And if G = H and *G = *H
then homomophism h is called an endomorphism
"on G" - or rather on (G,*G).
We may call two sets G and H isomorphic
because there is an isomorphism between them.
But actually, isomorphism is a relation between algebras
two (G,g1,...,gn)
and (H,f1,...,fn)
with the same arity for corresponding operations gi and fi,
such that there is one homomorphism h with
h(fi(a1, ..., ak))
= gi(h(a1), ..., h(ak))
for every k-ary gi/fi.
|
Algebras could be classified by their set (all algebras over N, over finite sets, etc.).
In the abstract algebra field of mathematics,
algebras (algebraic structures)
are classified by the properties of their operations:
| 
| |
| |
| |
stack, R-module, vector space, ...
|
|
loop, group, ...
| |
lattice, ring, field, ...
| |
| ?
| | f1 and f2 are binary, f3 is unary
|
regular expressions, ...
|
|
|
| |
(G,*) - magma aka. groupoid [wiki]
|
exactly one binary operation, generically written "*".
("magma" introduced by Bourbaki. Previously, "groupoid" was common.)
|
CATEGORIES OF ALGEBRAS
X-categories.
For any subclass X of the class of magmas,
the magmas in X ("X-magmas")
together with the homomorphisms between them ("X-homomorphisms")
form a category
(because: if h : G -> H and k : H -> K are X-homomorphisms, then so is k o h : G -> K).
|
|
| |
| |
| |
quasigroup [wiki]
| |
magma with identity
| |
semigroup [wiki]
|
"division" (ie., inversion of "*") is always possible.
Formally: there are unique solutions x, y to a * x = b and y * a = b,
for all a, b S
=> cancellation property:
a * b = a * c => b = c, and
a * b = c * b => a = c.
| |
"*" has an identity element e in S: e * a = a = a * e.
| |
"*" is associative: (a * b) * c = a * (b * c).
|
| |
| |
| |
| |
loop [wiki]
| |
monoid [wiki]
|
quasigroup with identity element
=> there is a left inverse, and a right inverse for each a S.
Inverse: If a * b = e, then a is b's left inverse and b is a's right inverse.
If x * a = e and a * x = e then x is a's inverse, also written a-1.
|
semigroup with identity element
=> e is unique
(N,+) - e=0; (N,*) - e=1;
set of n×n matrices over a given (unitary) ring, with matrix addition/multiplication
set of all strings over a finite alphabet - identity is the empty string
| «It is possible to view categories as generalizations of monoids.» |
| |
| |
Moufang loop [wiki]
| |
(a * b) * (c * a) = (a * (b * c)) * a, for all a, b, c S.
| |
| |
| |
group (associative quasigroup) [wiki]
| |
To summarize: A group is an magma (G,*) with
- associativity: (a * b) * c = a * (b * c), for all a, b, c G.
- identity element:  eG: e * a = a = a * e, for all a G.
- inverse element: a-1G: a * a-1 = e = a-1 * a, for all a G.
=> A group has exactly one identity element.
Every element has exactly one inverse.
| |
|
multiplicative terminology
additive terminology
|
| |
| a*b
| product a·b
| sum a+b
|
| |
| e
| unit element 1
| zero element 0
|
| |
| a-1
| reciprocal a-1
| opposite -a
|
| |
| |
abelian group (commutative group) [wiki]
| |
(G,*) is a quasi group where "*" is commutative: a * b = b * a.
Additive terminology is used for abelian groups.
Eg. (S,+), (S-{0},x).
Closure. The category of abelian groups is closed under
subgroups, factor groups, products, direct sums, homomorphism:
The set Hom(G, H) of all (abelian) group homomorphisms from
is itself an abelian group with operation + defined by
(h + k)(a) = h(a) + k(a), for all a G.
OTOH, the set End(G) of endomorphisms on an abelian G forms a ring with the same +.
|
CATEGORIES OF ALGEBRAS
The category of abelian groups with their homomorphisms
is preadditive and abelian
|
| |
| |
cyclic group [wiki]
| |
all elements of the group are powers of (at least) one fixed element (the "generator" of the group).
Eg. (N,+) has generator 1
| | | | | | |
|
|
| |
(R,+,*)
|
algebraic structure with exactly two binary operations, usually written + and *,
on set called R.
Additive terminology is used for (R,+), multiplicative terminology for (R,*)
|
| |
| |
| |
ring, broad sense [ring theory]
[wiki, wiki]
| |
semiring [wiki]
| |
(R,v,^) lattice, algebraically defined [wiki]
|
(R,+) is an abelian group and * is distributive (left and right) over + :
a * (b+c) = (a*b) + (a*c)
(a+b) * c = (a*c) + (b*c)
| |
(R,+) commutative monoid;
(R,*) monoid, ie. * is associative and has identity;
* distributive over +.
| |
v (join) and ^ (meet) are
commutative, associative, idempotent, and satisfy
absorption:
a v (a ^ b) = a
and a ^ (a v b) = a
| | |
| |
|
| |
ring, narrow sense (unitary ring, associative ring) [wiki]
| |
(R,+) abelian, (R,*) monoid, * distributives over +.
Eg. (Z,+,·)
Eg. set of n×n matrices, with matrix addition and multiplication
| |
| |
|
| |
Field [field theory]
[wiki, wiki]
| |
Boolean ring [wiki]
|
(R-{0},*) is also an abelian group
= (R, +, *) is a commutative ring
with 1 0
and all xR-{0} have a multiplicative inverse "reciprocal" x-1.
Eg. (Q,+,*), (R,+,*), (C,+,*)
Eg. algebraic numbers (the algebraic closure of Q), computable numbers, definable numbers.
|
a2 = a, for all a R.
=> a + a = 0, and ab = ba (commutative)
powerset of a set S, with symmetric difference of sets as "+" and intersection as "*"
| | | |
|
|
| |
(A,+,·,*) - Kleene algebras [wiki]
| -- relative to order (A,<)
|
(A,+,·) is a semi-ring; + is idempotent (a+a=a); and unary * satisfies
1 + a·(a*) < a*
1 + (a*)·a < a*
a*x < x if a,xA with a·x < x
xa* < x if a,xA with x·a < x
where a < b iff there is an xA with a + x = b
Eg. (B,v,^,x|->1) - boolean extended by to-true mapping
|
| |
Regular expressions over any "alphabet" A
|
where "+" or "|" is the alternative,
"·" is concatenation,
"*" is Kleene closure,
and "<" is the prefix relation.
| |
|
|
| |
Multisorted algebras
|
|
| |
| |
|
Stack = (E S, push, top, pop)
| |
(RM,+,*) - Left R-Module [wiki]
| |
Right R-Module [wiki]
| |
and other models of algebraic datatypes
| |
(M,+M) is an abelian group
(R,+R,*R) is a ring "of scalars"
*M×R->M "scalar multiplication" satisfies
for all r,sR, a,bM:
(r*s) * a = r * (s*a) (associativity)
(r+s) * a = r*a + s*a (left-distributes over +R)
r * (a+b) = r*a + r*b (right-distributes over +M)
1 * a = a
|
(M,+M) abelian group
(R,+R,*R) ring
*M×R->M satisfies
for all r,sR, a,bM:
a * (r*s) = (a*r) * s
a * (r+s) = a*r + a*s
(a+b) * r= a*r + b*r
a * 1 = a
|
| |
| |
|
| |
(RM,+,*) - R-Module (M is module over R) [wiki]
| |
R is commutative: r+s = s+r, r*s = s*r
=> the left R-module is the same as the right R-module
|
|
| |
(FV,+,*) Vector space (V is vector space over F) [wiki]
| |
(FV,+,*,×) is a V-module
and (V,+,*) is a field.
+V: V × V -> V "vector addition"
*V: F × V -> V "scalar multiplication"
Subspace of V - any nonempty subset of V which is closed under addition and scalar multiplication.
... span, linearly independent, basis ...
|
CATEGORIES OF ALGEBRAS
Linear maps from vector V to vector space W over the same field,
are maps preserving sums and scalar products.
The vector spaces over a fixed field F,
together with the linear maps, form a category.
|
|
|
| |
Associative algebra [wiki]
| |
vector multiplication *V is associative and distributive over +V.
*V×V->V is F-bilinear
Eg. n×n matrices over F
C - 2-dim assoc. alg. over R;
quaternions - 4-dim assoc. alg. over R
Polynoms with real efficients - assoc. alg. over R;
|
|
| |
Commutative algebra [wiki]
| |
(vector) multiplication is commutative
| | | | | |
|
|
|
