Products of systems
Products
Let L be a fixed relational language. For any two Lsystems
E and F, we define their product G = E×F
as the Lsystem 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):
∀s ∈L, s_{G} 
={((x_{0},y_{0}),...,
(x_{ns1}, y_{ns1}))
s_{E}(x_{0},..., x_{ns1})
∧s_{F}(y_{0},..., y_{ns1})} 

={(x×y)  x∈s_{E}
∧ y∈s_{F}} 

={z∈G^{ns}
 π_{0} ০ z ∈s_{E} ∧ π_{1}
০ z ∈s_{F}} 
This is the greatest interpretation letting both projections be morphisms: π_{0}
∈ Mor_{L}(G,E), π_{1}∈
Mor_{L}(G,F).
More generally, for any family of Lsystems (E_{i})_{i}_{∈}_{I}
with structures s_{i}⊂E_{i}^{ns}
for each s ∈L, their product P=∏_{i}_{∈}_{I}
E_{i} is an Lsystem interpreting L
by
∀s∈L, s_{P}
={∏x  x ∈ ∏_{i}_{∈}_{I}
s_{i}}={y∈P^{ns}
 ∀i∈I, π_{i} ০ y ∈ s_{i}
}
Again all projections are morphisms: π_{i} ∈ Mor_{L}(P,E_{i}).
Morphisms into products
For any Lsystem F and the product P=∏_{i}_{∈}_{I}
E_{i} of any family of Lsystems E_{i},
we have a canonical bijection ∏_{i}_{∈}_{I}
Mor_{L}(F,E_{i}) ≅ Mor_{L}(F,P)
defined by the product of functions (restriction of ∏_{i}_{∈}_{I}
E_{i}^{F} ≅ P^{F}).
Proof: for every f = ∏_{i}_{∈}_{I}
f_{i} ∈ P^{F}, i.e. ∀i∈I,
f_{i} = π_{i} ০ f ∈ E_{i}^{F},
f ∈ Mor_{L}(F,P)

⇔∀s∈L, ∀x∈s_{F}, f০x
∈ s_{P} 

⇔∀s∈L, ∀x∈s_{F},
∀i∈I, π_{i}০f ০x
∈ s_{i} 

⇔ ∀i∈I, ∀s∈L, ∀x∈s_{F},
f_{i} ০x ∈ s_{i} 

⇔ ∀i∈I, f_{i}
∈ Mor_{L}(F,E_{i}) 
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 Lalgebras
(E_{i})_{i}_{∈}_{I}
, their product P=∏_{i}_{∈}_{I}
E_{i} is an Lalgebra interpreting each
symbol s∈L on each tuple x=∏_{i∈I
}x_{i} ∈ P^{ns},
by
s_{P}(x) = (s_{i}(x_{i}))_{i∈I}
∈P.
This comes as a particular case of the product of relational
systems, obtained by replacing each nary operation s
by its graph, the (n+1)ary relation (y=s(x)):
∀x∈P^{n}, ∀y∈P, y=s_{P}(x)
⇔ (∀i∈I, y_{i}=s_{i}(x_{i})).
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 Lalgebras E, F, and any f
: E → F, f ∈ Mor_{L}(E,F)
⇔ Gr f ∈ Sub_{L} (E×F).
Proof 1: ∀s∈L, 
(∀x∈ E^{ns},
f(s_{E}(x)) = s_{F}(f০x))

⇔∀x∈E^{ns},∀y∈F^{ns},(y=f০x⇒
f(s_{E}(x))=s_{F}(y)) 


⇔ ∀(x×y)∈(Gr f)^{ns},
(s_{E}(x), s_{F}(y))∈
Gr f 


⇔ ∀z∈ (Gr f)^{ns},
s_{E×F}(z) ∈ Gr f 
Proof 2:
f∈ Mor_{L}(E,F)
⇒ Id_{E}×f ∈ Mor_{L}(E,E×F)
⇒ Im(Id_{E}×f )=Gr f ∈ Sub_{L}
(E×F).
If Gr f ∈ Sub_{L} (E×F)
then π_{0Gr }_{f} is a bijective morphism
from Gr f to E, thus its inverse is a morphism: Id_{E}×f
∈ Mor_{L}(E,E×F) thus f
∈ Mor_{L}(E,F).∎
Another proof of uniqueness of morphisms from minimal algebras
For any Lalgebras E, F, if E is
minimal then !: Mor_{L}(E,F)
Proof: ∀f,g∈Mor_{L}(E,F),
{x∈Ef(x)=g(x)} = π_{0}
[Grf ⋂ Grg] ∈ Sub_{L} E
because (Grf ⋂ Grg) ∈ Sub_{L} (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 ℕ×E_{a,f},
and let A={n∈ℕ  ∃!x∈E, (n,x)∈M}.
As M is a minimal (0,S)algebra, M = {(0,a)}∪
Im S_{M}.
Substituting this into the definition of A we get
∀p∈ℕ, p∈A ⇔ (∃!y∈E,
(p=0 ∧ y=a)∨∃(n,x)∈M,
(p=Sn ∧ y=f(x))).
From 0 ∉ Im S we get 0∈A, and
∀n∈ℕ, Sn∈A ⇔ ∃!y∈E,
∃(n',x)∈M, (Sn=Sn' ∧ y=f(x)).
From the injectivity of S we get
∀n∈ℕ, Sn∈A ⇔ ∃!y∈E,
∃x∈E, (n,x)∈M∧ y=f(x).
Thus (∀n∈A, Sn∈A), so that A
= ℕ, i.e. M is the graph of a function u ∈ E^{ℕ}.
As M ∈ Sub(ℕ×E_{a,f}), we
conclude u ∈ Mor_{(0,S)}(ℕ,E_{a,f}).
A more general form of recursion
Some useful sequences need recursive definitions where the term defining
u_{Sn} uses not only u_{n} 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 : E → F, where, instead of a draft, E is first
assumed to be an Lalgebra (then a ground term algebra to conclude).
The version we saw was formalized by giving the term in the recursive definition as an
Lalgebra structure on F, φ_{F}: L⋆F → F,
then expressing the request for u to satisfy this condition as u∈Mor(E,F),
namely ∀(s,x)∈L⋆E,
u(s_{E}(x)) = φ_{F}(s,u০x).
Let us generalize this as u(s_{E}(x))
= φ(s,x,u০x) which by the canonical bijection
Dom φ ≡ ∐_{s∈L} E^{ns
}×F^{ns} ≡ ∐_{s∈L}
(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), asu(s_{E}(x))
= h(s,x×(u০x)).
As ∀u∈F^{E}, x×(u০x)
= (Id_{E}×u)০x, this becomes
the second component of the formula Id_{E}×u ∈ Mor(E, E×F)
when giving E×F the structure φ_{E×F} =
(φ_{E}০π_{L})×h.
The first component (φ_{E}০π_{L}) we give to φ_{E×F},
makes π∈ Mor(E×F, E) and makes tautological the first component
of the formula Id_{E}×u
∈ Mor(E, E×F), namely
Id_{E}(s_{E}(x)) = φ_{E}(s,x)
= (φ_{E}০π_{L})(s,x×(u০x)).
It is then possible to conclude by reusing the previous result of existence of interpretations:
If E is a closed term Lalgebra then
∃!f ∈ Mor(E, E×F), which is
of the form Id_{E}×u because
π০f ∈ Mor(E, E) ∴ π০f = Id_{E}.
But one can do without it, based on the following property of this Lalgebra E×F:
∀u∈F^{E}, Id_{E}×u
∈ Mor_{L}(E, E×F) ⇔ Gr u
∈ Sub_{L}(E×F)
Indeed the defining formulas of both sides coincide. To see it otherwise,
 ⇒ is a case of image of an algebra by a
morphism, Gr u = Im (Id_{E}×u).

For the converse, the inverse of the bijective morphism π_{Gr u}
∈ Mor_{L}(Gr u, E)
is a morphism Id_{E}×u ∈ Mor_{L}(E, Gr u)
⊂ Mor_{L}(E, E×F).
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 Lalgebra then M =
Min_{L}(E×F) is one of them because
π_{M}∈ Mor_{L}(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