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 φ : LE →
E, sum of a family of interpretations of each symbol s∈L 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
(E,φE) can be designated in the short form of its underlying set E :
sE : Ens
→ E
φE = ∐s∈L
sE : LE → E
(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 rF ≠ sF).
Algebras form a concrete category with the following sets of morphisms.
For any L-algebras E, F,
MorL(E,F) = {f∈FE |
∀(s,x)∈LE, sF(f⚬x) =
f(sE(x))} = {f∈FE|
φF⚬Lf = f⚬φE}.
When c∈L 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 s∈L has
increased arity ns' = ns+1, so that
L'E ⇌ ∐s∈L
Ens×E ⇌
LE × E = {((s,x),y) | s∈L ∧
x∈Ens ∧ y∈E}.
∐s∈L Gr sE ⇌ Gr φE
⊂ LE × E
Let us call L-system any set E with a structure formalized
as E ⊂ LE × 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) as
- Functional or a partial algebra if E is functional
(graph of a function from a subset of LE);
- Serial if Dom E = LE;
- Algebraic if a serial partial algebra, i.e. essentially an algebra
(E, φE) by E = Gr φE ;
- Injective if tE is functional ;
- Surjective if Im E = E.
The concept of morphism between algebras (E, φE),
(F, φF) is the particular case of the one between
systems when they are algebraic :
∀f∈FE, (∀(x,y)∈Gr φE,
(Lf(x),f(y)) ∈ Gr φF) ⇔
(∀x∈LE, φF(Lf(x))
= f(φE(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) =
{f∈FE | Im f⚬φE ⊂ Dom ψF ∧
Lf|Dom φE =
ψF⚬f⚬φE}
MorL(F,E) =
{f∈EF | Im Lf⚬ψF
⊂ Dom φE ∧
φE⚬Lf⚬ψF = f|Dom
ψF}
If there exists a injective morphism from E to F then
- If F is functional then E is functional;
-
If F is injective then E is injective.
If there exists a surjective morphism from E to F then
- If E is serial then F is serial;
-
If E is surjective then F is surjective.
Stable subsets and subalgebras
Any subset A⊂E 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 = {A⊂E | E⋆(LA)
⊂ A} = {A⊂E | ∀((s,x),y)∈E,
Im x⊂A ⇒ y∈A}.
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.
Conversely, any algebraic subset of a partial algebra is stable.
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.
A very abstract and general formulation of this will come in 3.9.
Diverse properties of stability
Intersections of stable subsets. ∀X ⊂ SubLE,
⋂X ∈ SubL E where ⋂X ≝
{x∈E | ∀B∈X, x∈B}.
Proof:
∀(x,y)∈E, x∈L⋂X ⇒ (∀B∈X,
x∈LB ∴ y∈B) ⇒ y∈⋂X. ∎
Other way:
E⋆(L⋂X) =
E⋆(⋂B∈X LB)
⊂ ⋂B∈X
E⋆(LB) ⊂ ⋂X.
Stable set generated by a subset. ∀A⊂E, we denote
〈A〉L,E or simply 〈A〉L, the
smallest L-stable subset of E including A
(called L-subalgebra of E generated by A if E is an algebra):
〈A〉L =
{x∈E | ∀B∈ SubLE, A⊂B
⇒ x∈B} =
⋂{B∈ SubLE | A⊂B} ∈ SubLE
For fixed E and L, the function A↦〈A〉L is the
closure, with
image SubLE, from the relation ∈ between E and SubLE:
∀X⊂E, ∀Y⊂SubLE, X ⊂ ⋂Y
⇔ (∀B∈Y, X⊂B) ⇔ Y ⊂ {B∈ SubLE | X⊂B}.
We say that A generates E or is a generating subset of E if 〈A〉L = E.
Stability of equalizers. The equalizer Eq(f, g) = {x∈E | 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 |
f⚬x = g⚬x} = {x∈LE |
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 A⊂E,
- ∀B∈ SubLE, A ∩ B ∈ SubL A
- MinL A ⊂ MinL E
- A is minimal ⇒ A ⊂ MinL E
- A ∈ SubLE ⇒ E⋆(LA)
∈ SubLE ∩ ℘(A) = SubLA
- A ∈ SubLE ⇒
MinLA = MinLE
- A = MinLE ⇔ (A is minimal ∧ A∈ SubLE) ⇒ E⋆(LA) = A
In particular, any minimal system is surjective.
- 〈A〉L = MinL∪A E where A
is seen as a set of constants.
- A ∪ E⋆(LA) ⊂ 〈A〉L =
A ∪ E⋆(L〈A〉L)
- E⋆A ⊂ LA ⇒ MinL A = A ∩ MinL E
For the last property, we already know MinL A ⊂ A ∩ MinL E; for
the converse, using MinL A ∈ SubL A,
E⋆A ⊂ LA ⇒ 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: E ↪ F and
g: F ↪ E then there exists a bijection between E and F.
Proof. 〈∁E Im g〉{g⚬f} = A =
(∁E Im g) ∪ g[f[A]] ⇒ ∁E
A = g[∁F f[A]] ⇒ (E ∋ x ↦
x∈A ? f(x) : g-1(x)) : E ↔ F ∎
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