Products of systems


Let L be a fixed relational language. For any two L-systems E and F, we define their product G = E×F as the L-system made of the ordinary product G of E and F (seen in 2.3), interpreting L as follows (using the product of families from 2.8):
sL, sG ={((x0,y0),..., (xns-1, yns-1))| sE(x0,..., xns-1) ∧sF(y0,..., yns-1)}

={(x×y) | xsEysF}

={zGns | π0z sE ∧ π1zsF}
This is the greatest interpretation letting both projections be morphisms: π0 ∈ MorL(G,E), π1∈ MorL(G,F).

More generally, for any family of L-systems (Ei)iI with structures siEins for each sL, their product P=∏iI Ei is an L-system interpreting L by
sL, sP ={∏x | x ∈ ∏iI si}={yPns | ∀iI, πiy si }
Again all projections are morphisms: πi ∈ MorL(P,Ei).

Morphisms into products

For any L-system F and the product P=∏iI Ei of any family of L-systems Ei, we have a canonical bijection ∏iI MorL(F,Ei) ≅ MorL(F,P) defined by the product of functions (restriction of ∏iI EiFPF).

Proof: for every f = ∏iI fiPF, i.e. ∀iI, fi = πifEiF,
f ∈ MorL(F,P) ⇔∀sL,xsFfxsP

⇔∀sL,xsF, ∀iI, πifxsi

⇔ ∀iI, ∀sL,xsF, fixsi

⇔ ∀iI, fi ∈ MorL(F,Ei)

Products of algebras

Now let us define the product of algebras, taking as L an algebraic language (set of operation symbols): for any family of L-algebras (Ei)iI , their product P=∏iI Ei is an L-algebra interpreting each symbol sL on each tuple x=∏iI xiPns, by

sP(x) = (si(xi))iIP.

This comes as a particular case of the product of relational systems, obtained by replacing each n-ary operation s by its graph, the (n+1)-ary relation (y=s(x)):

xPn, ∀yP, y=sP(x) ⇔ (∀iI, yi=si(xi)).

An operation defined by a term in a product of algebras, coincides with the product of operations defined by the same term in all component algebras.

Morphisms as subalgebras

For any L-algebras E, F, and any f : EF,     f ∈ MorL(E,F) ⇔ Gr f ∈ SubL (E×F).

Proof 1: ∀sL, (∀xEns, f(sE(x)) = sF(fx)) ⇔∀xEns,∀yFns,(y=fxf(sE(x))=sF(y))

⇔ ∀(x×y)∈(Gr f)ns, (sE(x), sF(y))∈ Gr f

⇔ ∀z∈ (Gr f)ns, sE×F(z) ∈ Gr f

Proof 2:
f∈ MorL(E,F) ⇒ IdE×f ∈ MorL(E,E×F) ⇒ Im(IdE×f )=Gr f ∈ SubL (E×F).
If Gr f ∈ SubL (E×F) then π0|Gr f is a bijective morphism from Gr f to E, thus its inverse is a morphism: IdE×f ∈ MorL(E,E×F) thus f ∈ MorL(E,F).∎

Another proof of uniqueness of morphisms from minimal algebras

For any L-algebras E, F, if E is minimal then !: MorL(E,F)
Proof: ∀f,g∈MorL(E,F), {xE|f(x)=g(x)} = π0 [Grf ⋂ Grg] ∈ SubL E because (Grf ⋂ Grg) ∈ SubL (E×F).

Another proof of recursion

By seeing morphisms as subalgebras, we can write another construction of recursive sequences u∈Mor(0,S)(ℕ,(E,a,f)), as follows.

Let M be the minimal subalgebra of ℕ×Ea,f, and let A={n∈ℕ | ∃!xE, (n,x)∈M}.
As M is a minimal (0,S)-algebra, M = {(0,a)}∪ Im SM.
Substituting this into the definition of A we get
p∈ℕ, pA ⇔ (∃!yE, (p=0 ∧ y=a)∨∃(n,x)∈M, (p=Sny=f(x))).
From 0 ∉ Im S we get 0∈A, and
n∈ℕ, SnA ⇔ ∃!yE, ∃(n',x)∈M, (Sn=Sn'y=f(x)).
From the injectivity of S we get
n∈ℕ, SnA ⇔ ∃!yE, ∃xE, (n,x)∈My=f(x).
Thus (∀nA, SnA), so that A = ℕ, i.e. M is the graph of a function uE. As M ∈ Sub(ℕ×Ea,f), we conclude u ∈ Mor(0,S)(ℕ,Ea,f).

Next : Varieties
More texts on algebra

Back to Set theory and foundations homepage