3.3. Algebras

Algebras and their morphisms

Given an algebraic language L, an L-algebra is the data (E,φ) of a set E with an L-algebraic structure φ : LEE, sum of a family of interpretations of each symbol sL as an operation φ⃗(s) ∈ OpE(ns).
Again, we shall usually consider a class of L-algebras with only one choice of algebraic structure φE on each set E, so that an algebra (EE) can be designated in the short form of its underlying set E :

sE : EnsE
φE = ∐sL sE : LEE

(but these sE cannot be the restrictions of a common ns-ary operator to each E, if we want to let constant symbols r and s interpreted in algebras E and F such that rE = sE but rFsF).
Algebras form a concrete category with the following sets of morphisms. For any L-algebras E, F,

MorL(E,F) = {fFE | ∀(s,x)∈LE, sF(fx) = f(sE(x))} = {fFE| φFLf = f⚬φE}.

When cL is a constant symbol (nc = 0), this condition on f says f(cE) = cF.

Algebras as relational systems

Any category of algebras is identifiable with a category of relational systems with functional structure, as follows.

Let L' be the copy of L as a relational language, where the copy s'L' of each sL has increased arity ns' = ns+1, so that

L'E ⇌ ∐sL Ens×ELE × E = {((s,x),y) | sLxEnsyE}.
sL Gr sE ⇌ Gr φELE × E

Let us call L-system any set E with a structure formalized as ELE × E.
All concepts defined for relational systems are equally applicable through this canonical bijection.

Qualities of systems with algebraic languages

Further properties of L-systems (E, E) will be named after the qualities of the relation E: let us qualify (E, E) asThe concept of morphism between algebras (E, φE), (F, φF) is the particular case of the one between systems when they are algebraic :

fFE, (∀(x,y)∈Gr φE, (Lf(x),f(y)) ∈ Gr φF) ⇔ (∀xLE, φF(Lf(x)) = fE(x))).

Similarly, between a partial algebra (E, Gr φE) and an injective system (F, tGr ψF), sets of morphisms are defined by

MorL(E,F) = {fFE | Im f⚬φE ⊂ Dom ψFLf|Dom φE = ψFf⚬φE}
MorL(F,E) = {fEF | Im Lf⚬ψF ⊂ Dom φE ∧ φELf⚬ψF = f|Dom ψF}

If there exists a injective morphism from E to F then If there exists a surjective morphism from E to F then

Stable subsets and subalgebras

Any subset AE of an L-system (E, E), forms a system with structure A = E ∩ (LA × A). If E is functional or injective then A has the same property.
We shall say that A is L-stable, if E(LA) ⊂ A. The set of stable subsets of E is written SubL E:

SubL E = {AE | E(LA) ⊂ A} = {AE | ∀((s,x),y)∈E, Im xAyA}.

We have E ∈ SubL E.
If E is serial and A is L-stable then A is serial.
If E is algebraic and A is L-stable then A is algebraic, thus called an L-subalgebra of E. As an L-algebra, its structure is φA = φE|LA.
If a formula of the form (∀(variables), formula without binder) is true in an L-algebra, then it is true in each of its L-subalgebras.

Diverse properties of stability

Intersections of stable subsets.X ⊂ SubLE, ⋂X ∈ SubL E where ⋂X {xE | ∀BX, xB}.

Proof: ∀(x,y)∈E, xLX ⇒ (∀BX, xLByB) ⇒ y∈⋂X. ∎

Other way: E(LX) = E(⋂BX LB) ⊂ ⋂BX E(LB) ⊂ ⋂X.

Stable set generated by a subset.AE, we denote 〈AL,E or simply 〈AL, the smallest L-stable subset of E including A (called L-subalgebra of E generated by A if E is an algebra):

AL = {xE | ∀B∈ SubLE, ABxB} = ⋂{B∈ SubLE | AB} ∈ SubLE

For fixed E and L, the function A↦〈AL is the closure, with image SubLE, from the relation ∈ between E and SubLE:

XE, ∀Y⊂SubLE, X ⊂ ⋂Y ⇔ (∀BY, XB) ⇔ Y ⊂ {B∈ SubLE | XB}.

We say that A generates E or is a generating subset of E if 〈AL = E.

Stability of equalizers. The equalizer Eq(f, g) = {xE | f(x) = g(x)} of any two L-morphisms f,g∈MorL(E,F) from an L-system E to a partial L-algebra F, is L-stable.

Proof : LEq(f, g) = {(s,x)∈LE | fx = gx} = {xLE | Lf(x) = Lg(x)}
∀(x,y)∈E, (Lf(x) = Lg(x) ∧ (Lf(x), f(y)) ∈ F ∧ (Lg(x), g(y)) ∈ F) ⇒ f(y) = g(y). ∎
Proof when F is an algebra : ∀(x,y)∈E, Lf(x) = Lg(x) ⇒ f(y) = φF(Lf(x)) = g(y).

Minimal systems

For any L-system E, its minimal stable subset is defined as

MinLE = 〈∅〉L,E = ⋂ SubL E ∈ SubL E.

It is called minimal subalgebra if E is an L-algebra.

An L-system E is minimal when E = MinL E, or equivalently SubLE = {E}.

For any minimal L-system E and any partial L-algebra F, !: MorL(E,F).

For any L-system E and any AE,

For the last property, we already know MinL AA ∩ MinL E; for the converse, using MinL A ∈ SubL A,
EALA ⇒ MinL A ∪ (E\A) ∈ SubL E ⇒ MinL E ⊂ MinL A ∪ (E\A) ⇒ A ∩ MinL E ⊂ MinL A.∎

Cantor-Bernstein theorem

If there exist injections f: EF and g: FE then there exists a bijection between E and F.

Proof. 〈∁E Im g{gf} = A = (∁E Im g) ∪ g[f[A]] ⇒ ∁E A = g[∁F f[A]] ⇒ (ExxA ? f(x) : g-1(x)) : EF


Set theory and foundations of mathematics
1. First foundations of mathematics
2. Set theory
3. Algebra 1
4. Arithmetic and first-order foundations
5. Second-order foundations
6. Foundations of Geometry

Other languages:
FR : Algèbres