# 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)) ⇔ ∀i∈I,(ri(xi)∧si(xi)) (rP(x)∨sP(x)) ⇒ ∀i∈I,(ri(xi)∨si(xi)) (rP(x) ⇒ sP(x)) ⇐ ∀i∈I,(ri(xi)⇒si(xi)) (∀y∈P, rP(x,y)) ⇐ ∀i∈I, ∀yi∈Ei, ri(xi,yi) (P≠ⵁ ∧ ∀y∈P, rP(x,y)) ⇒ ∀i∈I, ∀yi∈Ei, ri(xi, yi) (∃y∈P, rP(x,y,...)) ⇒ ∀i∈I, ∃yi∈Ei, ri(xi,yi) (∃y∈P, rP(x,y,...)) ⇐ (ACI∧∀i∈I, ∃yi∈Ei, ri(xi,yi))

The ⇒ cases (white and in green) can be understood as deduced from πi ∈ MorL(P,Ei) as seen in 3.1, 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:
• Substitutions : for the relation r' defined by a relation symbol r with a substitution map u from r's arguments list I to the variables list J, let f=∏iI πu(i) ∈Mor(EJ,EI).
Then r∈SubS(EI) ⇒ r'=f -1(r)∈SubS(EJ).
• ∃: the relation defined by (∃xE, r(x,y,...)) is the image of r by the morphism ∏i≠0 πi
• =: this relation is Gr IdE = Im (IdE⊓IdE) ∈ SubS(E×E)
• ∧: intersections of subalgebras are subalgebras.
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)).

#### Duality theories with structures

A duality theory is a theory describing duality systems. Let R be a relational language, that is interpreted in K. We may even see it as R⊂RelK.

For any set E, we have a Galois connection between interpretations of R in E and subsets E'KE, defined as follows:
• Any E'KE defines an interpretation of each n-ary rR in E as rE={(x1,..., xn)∈En|∀yE' , r(y(x1),...,y(xn))}. This is the only one making (∏yE' y) an embedding from E to KE'.
• Any interpretation of R in E gives a set E*= MorR(E,K) ⊂ KE.
Now let us consider duality theories, or kinds of K-duality systems (E,E',〈 , 〉), that interpret R in E as defined from E' in this way. (This forms a first-order theory, while the claim of using of E* would form a second order theory).

By the properties of closures of the above Galois connection we have:
• E' ⊂ E*
• As ∏yE' y is an embedding of E into KE' (injective as E is assumed to be separated by E'),
yE* y is also an embedding of E into KE* (which means that the used R-structure on E is closed), i.e. (E,E*) is another K-duality system giving the same R-structure on E.

Thus, as the system E is a subset of an exponentiation of K (namely KE'), every axiom of the form (∀ variables) (F1 ∧ ... ∧ Fn) ⇒ G (where (F1 ,..., Fn, G) are relation symbols applied to variables) that is true in K, is also true in E.

Theorem. For any two K-duality systems (E,E',〈 , 〉) and (F,F',〈 , 〉') interpreting R in E and F in this way,
• Mor((E,E'),(F,F')) ⊂ MorR(E,F)
• Mor((E,E*),(F,F')) = MorR(E,F)
Proof.
As (∏yF' y) is an R-embedding from F to KF', we have
 ∀f∈FE, f ∈ MorR(E,F) ⇔ (∏y∈F' y)०f ∈ MorR(E,KF') ⇔ ∀y∈F', y०f ∈ MorR(E,K)=E* ⇔ f ∈ Mor((E,E*),(F,F'))
As E'E*, the condition f∈Mor((E,E'),(F,F')), that is ∀yF', yfE', is more restrictive, thus the inclusion.
Now, let S ⊂ Pol R ⊂ OpK. As seen above, in any K-duality system (E,E') we have E* ∈ SubS(KE).
As the R-structure in E stays unchanged whether it is defined from E' or from E*, it remains also unchanged using any X such that E'XE*. This is the case for X = E'S = the S-algebra generated by E', that is the smallest sub-S-algebra of E* (or equivalently of KE) such that E'X.