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).

A more general form of recursion

Some useful sequences need recursive definitions where the term defining uSn uses not only un but also n itself. Somehow it would work all the same, but trying to directly adapt to this case the proof we gave would require to define some special generalizations of previous concepts, and specify their resulting properties. To simplify, let us proceed another way, similar to the argument in Halmos's Naive Set Theory, but generalized.
For any algebraic language L, let us introduce a general concept of "recursive condition" for functions u : EF, where, instead of a draft, E is first assumed to be an L-algebra (then a ground term algebra to conclude).
The version we saw was formalized by giving the term in the recursive definition as an L-algebra structure on F, φF: LFF, then expressing the request for u to satisfy this condition as u∈Mor(E,F), namely

∀(s,x)∈LE, u(sE(x)) = φF(s,ux).

Let us generalize this as u(sE(x)) = φ(s,x,ux) which by the canonical bijection Dom φ ≡ ∐sL Ens ×Fns ≡ ∐sL (E×F)ns = L⋆(E×F) can be written using h : L⋆(E×F) → F such that ∀(s,x,y)∈ Dom φ, φ(s,x,y) = h(s,x×y), as

u(sE(x)) = h(s,x×(ux)).

As ∀uFE, x×(ux) = (IdE×u)০x, this becomes the second component of the formula IdE×u ∈ Mor(E, E×F) when giving E×F the structure φE×F = (φE০πLh.
The first component (φE০πL) we give to φE×F, makes π∈ Mor(E×F, E) and makes tautological the first component of the formula IdE×u ∈ Mor(E, E×F), namely
IdE(sE(x)) = φE(s,x) = (φE০πL)(s,x×(ux)).
It is then possible to conclude by re-using the previous result of existence of interpretations:
If E is a closed term L-algebra then ∃!f ∈ Mor(E, E×F), which is of the form IdE×u because π০f ∈ Mor(E, E) ∴ π০f = IdE.
But one can do without it, based on the following property of this L-algebra E×F:

uFE, IdE×u ∈ MorL(E, E×F) ⇔ Gr u ∈ SubL(E×F)

Indeed the defining formulas of both sides coincide. To see it otherwise, This reduces the issue to the search of subalgebras of E×F which are graphs of functions from E to F.
Now if E is a ground term L-algebra then M = MinL(E×F) is one of them because π|M∈ MorL(M, E) from a surjective algebra to a ground term algebra must be bijective.
Any other subalgebra of E×F must include M, thus to stay functional it must equal M. ∎
Next : Varieties
More texts on algebra

Back to Set theory and foundations homepage