3.3. Notion of algebra

Algebras. Given an algebraic language L, an L-algebra is a set E with an interpretation of each sL as an ns-ary operation in E.
Again, let us assume a fixed class of L-algebras E where each s is interpreted as the restriction sE of an ns-ary operator s independent of E,
sE = (Ensxs(x)).
These can be packed as one function

φE = ∐sL sE = ((s,x) ↦ s(x)) : LEE.

Such a class of algebras forms a concrete category with the following concept of morphism.

Morphisms of algebras. For any L-algebras E, F,

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

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

Such categories can be seen as particular categories of relational systems, as follows.

Let the relational language L' be a copy of L where to each sL corresponds s'L' with increased arity ns' = ns+1, so that
L'E ≡ ∐sL Ens×E ≡ (LEE
also expressible as the set of triples (s,x,y) such that sL, xEns and yE.
Each ns-ary operation sE defines an ns'-ary relation s'EGr sE. These are packed as an L'-structure
E = Gr φE ≡ ∐sL s'E.

The conditions for an fFE to be a morphism are equivalent :
(∀(x,y)∈E, (fL(x),f(y))∈F) ⇔ (∀xLE, φF(fL(x))= fE(x))).
Every injective morphism f between algebras is an embedding :

∀(s,x,y)∈L'E, f(y) = sF(fx) = f(sE(x)) ⇒ y=sE(x).

Any embedding f ∈ MorL(E,F), is injective as soon as Im φE = E or some sE is injective for one of its arguments.
Bijective morphisms of algebras are isomorphisms. This can be deduced from the fact they are embeddings, or by

φEfL-1 = f -1f০φEfL-1 = f -1০φFfLfL-1 = f -1০φF.

Singletons are the final objects in any category of algebras with a fixed language where they are admitted as objects.

Subalgebras. A subset AE of an L-algebra E will be called an L-subalgebra of E, if φE[LA]⊂A.
Then the restriction φA of φE to LA gives it a structure of L-algebra.
The set of all L-subalgebras of E will be denoted SubL E. It is nonempty as E ∈ SubL E.

For any formula of the form (∀(variables), some formula without any binder), its truth in E implies its truth in each A∈SubL E.

Images of algebras. f ∈MorL(E,F) ⇒ Im f ∈ SubLF.

The proof uses the finite choice theorem with (AC 1)⇒(6):
∀(s,y)∈ L⋆Im f, ∃xEns, fx = ysF(y) = f(sE(x)) ∈ Im f
Thus trying to exend this result to algebras with infinitary operations, would require the axiom of choice, otherwise it anyway still holds for injective morphisms.

Let us generalize the concept of algebra, to any L'-systems (E,E), where E ⊂ (LEE needs not be functional. They form the same kind of categories previously defined, with a different notation (through the canonical bijection depending on the choice of distinguished argument) by which more concepts can be introduced.

Stable subsets. The concept of subalgebra is generalized as that of stability of a subset A of E by L :
A ∈ SubL E ⇔ (E*(LA) ⊂A) ⇔ (∀(s,x,y)∈E, Im xAyA).
Stability is no more preserved by direct images by morphisms, but is still preserved by inverse images:

Preimages of stable subsets.f ∈ MorL(E,F), ∀B ∈ SubLF, f *(B)∈SubL E.

Let A=f *B. Proof for L-algebras:
∀(s,x)∈LA, fxBnsf(sE(x)) = sF(fx) ∈BsE(x)∈A.
Proof for L'-systems:
∀(x,y)∈E, (fL(x),f(y))∈F∴ (xLAfL(x)∈LBf(y)∈ByA).∎

Proposition. For any L'-system E and any L-algebra F,
f,g∈MorL(E,F), {xE|f(x)=g(x)}∈ SubLE.

Proof : ∀(s,x,y)∈E, fx=gxf(y) = s(fx) = g(y). ∎

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

Proof: ∀(x,y)∈E, xL⋆∩X ⇒ (∀BX, xLByB) ⇒ y∈∩X. ∎

Other way: E*(L⋆∩X) = E*(∩BX LB) ⊂∩BX E*(LB) ⊂∩X.

Subalgebra generated by a subset.AE, the L-subalgebra of E generated by A, written 〈AL,E or more simply 〈AL, is the smallest L-subalgebra of E including A:

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

For fixed E and L, this function of A is a closure with image SubLE.
We say that A generates E if 〈AL=E.

Minimal subalgebra. The minimal subalgebra of an algebra E, is its subalgebra MinLE =〈∅〉L,E = ∩SubLE. (This can also be used on stable subsets of algebraic systems which are not algebras)

An L-algebra E is minimal when E = MinL E, or equivalently SubLE = {E}. Then MinLE is the only subalgebra of E that is a minimal algebra.
We can redefine generated subalgebras in terms of minimal subalgebra with a different language: 〈AL,E= MinLA E where A is seen as a set of constants.

Proposition. For any L-algebra E,

Proofs:
φE[LA] ⊂ ImφEA
ImφEA∪ImφEA∪ImφE∈SubLE
B ∈ SubLF, f *(B)∈SubL E ∴ MinLEf*(B) ∴ f [MinLE]⊂B.∎

Injective, surjective algebras. An L-algebra (EE) will be called injective if φE is injective, and surjective if Im φE = E.
Any minimal L-algebra is surjective. Thus, the minimal sub-algebra of any algebra is also a surjective algebra.

Proposition. If E is a surjective algebra and F is an injective one then
f ∈MorL(E,F), A= {xE | ∀yE, f(x) = f(y) ⇒ x=y} ∈ SubLE.

Proof: ∀(s,x)∈LA, ∀yE,
f(sE(x)) = f(y) ⇒ (∃(t,z)∈φE(y), sF(fx) = f(sE(x)) = f(y) = f(tE(z)) = tF(fz) ∴ (s=tfx=fz) ∴ x=z)sE(x)=y.

Other view : under the same assumptions, for each uniqueness quantifier Q (either ∃! or !),
B = {yF | QxE, y = f(x)} ∈ SubLF

Proof: as φF is injective, ∀y∈φF[LB], ∃!: φF(y) ⊂ LBQzLE, φF(fL(z)) = y.
As φFfL = f০φE and φE is surjective, we conclude QxE, y = f(x). ∎

More texts on algebra

Back to homepage : Set theory and foundations of mathematics
1. First foundations of mathematics
2. Set theory (continued)
3. Algebra 1
3.1. Morphisms of relational systems and concrete categories
3.2. Special morphisms
3.3. Algebras
3.4. Algebraic terms and term algebras
3.5. Integers and recursion
3.6. Arithmetic with addition
4. Model Theory
4.1. Finiteness and countability
4.2. The Completeness Theorem
4.3. Infinity and the axiom of choice
4.4. Non-standard models of Arithmetic
4.5. How theories develop
4.6. The Incompleteness Theorem