3.2. Notion of algebra

Algebras. 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 on each set:

sE : EnsE
φE = ∐sL sE : LEE

This would be the case if the sE were the restrictions of a common ns-ary operator to each E, but this would not allow to interpret constant symbols r and s in algebras E and F with rE=sE but rFsF.
These form 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 the copy s'L' of each sL has increased arity ns' = ns+1, so that
L'E ≡ ∐sL Ens×E ≡ (LEE ≡ {(s,x,y) | sLxEnsyE}.
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 resulting condition for an fFE to be a morphism is equivalent :
(∀(x,y)∈E, (fL(x),f(y))∈F) ⇔ (∀xLE, φF(fL(x))= fE(x))).

Subalgebras. A subset AE of an L-algebra E is called stable by L or an L-subalgebra of E if φE[LA]⊂A. It is also an L-algebra, with structure φA restriction of φE to LA. The set of L-subalgebras of E is written SubL E = {AE | φE[LA]⊂A}.

If a formula of the form (∀(variables), formula without binder) is true in E, then it is true in each A∈SubLE.

Images of algebras. For any two L-algebras E,F, ∀f ∈MorL(E,F), Im f ∈ SubLF.

Proof : φF[L⋆Im f] = φF[Im fL] = Im (f০φE) ⊂ Im f

Let us generalize these concepts to categories of relational L'-systems (E,E) whose structure E ⊂ (LEE no more needs to be functional:

Stable subsets. The concept of stability of a subset A can be defined in any L'-system E beyond the case of algebras :

A ∈ SubL E ⇔ (E*(LA) ⊂A) ⇔ (∀(s,x,y)∈E, Im xAyA).

We have E ∈ SubL E. Stability is no more preserved by direct images by morphisms, but is still preserved by preimages:

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

Proof. Let A=f *B.
For L-algebras, ∀(s,x)∈LA, fxBnsf(sE(x)) = sF(fx) ∈BsE(x)∈A.
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) = sF(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, 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= ∩{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 or is a generating subset of E if 〈AL=E.

Minimal subalgebra. For any L'-system E, its minimal stable subset (or minimal subalgebra for an L-algebra) is defined as
MinLE = 〈∅〉L,E = ∩SubLE ∈ SubLE.

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

Proposition. For any L'-system E, ∀A∈SubLE, Proof: MinLE ⊂ MinLA because SubL A ⊂ SubL E;
MinL A ⊂ MinL E because ∀B∈SubLE, AB ∈ SubLA. ∎

Among subsets of E, other minimal L'-systems are included in MinL E but are not stable.
The stable subset generated by A is the minimal one for the extended language with A seen as a set of constants: 〈AL,E= MinLA E.

Injective, surjective algebras. An L-algebra (EE) will be called injective if φE is injective, and surjective if Im φE = E.

Proposition. For any L-algebras E, F,

  1. AE, Im φEAA∈SubLE.
  2. Any minimal L-algebra is surjective.
  3. MinLE = φE[L⋆MinLE] ⊂ Im φE
  4. AE, ⋃xA〈{x}〉L ⊂ 〈AL = A∪φE[L⋆〈AL] ⊂ A∪Im φE
  5. f ∈MorL(E,F), f [MinLE] = MinLF ∧ ∀AE, f [〈AL] = 〈f [A]〉L
Proofs:
  1. φE[LA] ⊂ Im φEAA∈SubLE
  2. Im φE ∈ SubLE
  3. MinLE is surjective
  4. A∪φE[L⋆〈AL] ∈ SubLAL
  5. B ∈ SubLF, f *(B)∈SubL E ∴ MinLEf*(B) ∴ f [MinLE]⊂B.∎

Injectivity lemma. If E is a surjective algebra and F is an injective one then ∀f ∈MorL(E,F),

  1. A= {xE | ∀yE, f(x) = f(y) ⇒ x=y} ∈ SubLE.
  2. For each uniqueness quantifier Q (either ∃! or !), B = {yF | QxE, y = f(x)} ∈ SubLF
They are essentially the same but let us write separate proofs:
  1. ∀(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.
  2. 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). ∎

Schröder–Bernstein theorem. If there exist injections f: EF and g: FE then there exists a bijection between E and F.

Proof : replacing F by the bijectively related set Im g, simplifies things to the case FE.
Then a bijection from E to F can be defined as x ↦ (x∈〈E\F{f} ? f(x) : x).∎

Set theory and foundations of mathematics
1. First foundations of mathematics
2. Set theory (continued)
3. Algebra 1
3.1. Relational systems and concrete categories
3.2. Algebras
3.3. Special morphisms
3.4. Monoids
3.5. Actions of monoids
3.6. Invertibility and groups
3.7. Categories
3.8. Algebraic terms and term algebras
3.9. Integers and recursion
3.10. Arithmetic with addition
4. Model Theory