3.2. 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 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 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. For any two L-algebras E,F, ∀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 preimages:

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. For any L-algebra (or other L'-system) E, its minimal subalgebra (or minimal stable subset) is MinLE = 〈∅〉L,E = ∩SubLE ∈ SubLE.

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

Proposition. For any L-algebra 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).
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.

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, 〈AL = A∪φE[L⋆〈AL] ⊂ A∪Im φE.
  5. f ∈MorL(E,F), f [MinLE] = MinLF ; more generally ∀AE, f [〈AL] = 〈f [A]〉L
  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.

Replacing F by the bijectively related set Im g, simplifies things to the case FEg=IdF.
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. Morphisms of 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