Relational clones

This section is only a remark, not needed for the next ones.

Truth of formulas in products

Given a product P=∏iI Ei of any family of L-systems Ei, and any formula Φ with any number n of free variables, let us compare the truth of Φ(x) in P for some tuple xPn of values of free variables, with the value (∀iI, Φ(xi)) obtained as the product of the structures defined by the same formula in each Ei, where x=∏iI xi, i.e.
iI, xi = πixEin.
We will do it with elementary formulas, from which the behavior of some more complex formulas can eventually be deduced.

There is equivalence with the equality symbol: ∀x,yP, (x=y ⇔∀iIxi = yi), and also for a formula Φ made of a relation symbol s with a choice of substitution h of its arguments by free variables:
Φ(x) ⇔ sP(xh) ⇔ (∀iI,si(xh)) ⇔ (∀iI,Φ(xi))
which simplifies the remaining needed study, to cases without substitutions. Now let us see the effects of connectives and quantifiers (between relation symbols s interpreted in P as sP(x)⇔∀iIsi(xi)):
(rP(x) ∧sP(x)) ⇔ iI,(ri(xi)∧si(xi))
(rP(x)∨sP(x)) ⇒ iI,(ri(xi)∨si(xi))
(rP(x) ⇒ sP(x)) ⇐ iI,(ri(xi)⇒si(xi))
(∀yP, rP(x,y)) ⇐ iI, ∀yiEi, ri(xi,yi)
(P≠ⵁ ∧ ∀yP, rP(x,y)) ⇒ iI, ∀yiEi, ri(xi, yi)
(∃yP, rP(x,y,...)) ⇒ iI, ∃yiEi, ri(xi,yi)
(∃yP, rP(x,y,...)) ⇐ (ACI∧∀iI, ∃yiEi, ri(xi,yi))

The ⇒ cases (white and in green) can be understood as deduced from πi ∈ MorL(P,Ei) as seen in 3.3, plus the preservation of ∀ by surjective morphisms.
The converse implications (⇐, in white and yellow, where ACI is the axiom of choice over I, see 2.10), describe which properties are "preserved by taking the product of systems".
For example if each member of a product satisfies an axiom of the form (∀ variables) (F1 ∧ ... ∧ Fn) ⇒ G where F1,..., Fn and G are relation symbols applied to variables, then the product also satisfies this axiom.
For example, any product of ordered sets is an ordered set; but a product of totally ordered sets, is a set with an order that is usually not a total order.

Relational clones

For any set R ⊂ RelE of relations in E, the relational clone generated by R, is the set  Cl'(R)⊂ RelE of relations defined by formulas with symbols in R∪{∃,=,∧, variables}. This is also a closure, whose closed elements are the relational clones (or clones of relations).

For any system E and formula Φ, the truth of Φ in E is written E⊨Φ .

Theorem. The set of invariants Inv S of any S ⊂ OpE, is a relational clone. In other words, for any R ⊂ RelE we have Cl'(R) ⊂ Inv Pol R.

Proof 1:

Let R ⊂ RelE and s∈MorR(En,E)⊂Pol R.
Let m∈ℕ, and a formula Φ with symbols in R∪{∃,=,∧}, variables bound by ∃, and m free variables.
Let r ∈Cl'(R) the m-ary relation defined by Φ in E.
We saw that (∀i<n, E⊨Φ(πix)) ⇒ (En⊨Φ(x)) using the truth of the axiom of choice over finite sets.
Then, (s∈MorR(En,E) ∧ En⊨Φ(x)) ⇒ (E⊨Φ(sx)).
We conclude ∀x∈(En)m, (∀i<n, rix)) ⇒ r(sx), i.e. sr.

Proof 2:
For any S ⊂ OpE, let us verify that Inv S is a clone of relations, that is, ∀m∈ℕ, ∀rEm defined by a term with language in {∃,=,∧}∪Inv S, we have r∈SubS(Em). We can verify that we stay in Inv S in the following steps of building formulas:
Other ways to operate on subalgebras reflect formulas with these symbols: for example
A∈SubS(E) ⇒ (IdE×IdE)[A] = {(x,y)∈E2|xAx=y}

For each relational clone R, the set Gr*R is a clone of operations : for example, the graph of the term "x" with variables x,y, is {(x,y,z)|z=x};
if f,gEE we have (x,y)∈ Gr(gf) ⇔ (∃zE, (x,z)∈Gr(f) ∧ (z,y)∈Gr(g)).