[figure]

The Galois Connection

between

relations and automorphisms

Ferdinand Börner Martin Goldstern* Saharon Shelah

1/10

[figure]

Setup: A … an infinite set Rel_{k}(A) = 𝒫(A^{k}) = k-ary relations on A Rel(A) = ⋃_{k∈ℕ} Rel_{k}(A). Sym(A) = all permutations of A:

Every f ∈ SymA acts also on A^{k} (pointwise). For ρ ⊆ A^{k} we define f[ρ] naturally.

The Galois connection sInv-Aut For f ∈ SymA, ρ ∈ RelA we write

f ∈ Aut(ρ) or ρ ∈ sInv(f)

iff f[ρ] = ρ. We say

“f is an automorphism of ρ” “ρ is strongly invariant under f”

2/10

[figure]

Definition: f ∈ Aut(ρ) ⇔ ρ ∈ sInv(f) ⇔ f[ρ] = ρ.

For F ⊆ Sym(A) we let Aut(F) := ⋂_{f∈F} sInv(f) Dually: Aut(P) := ⋂_{ρ∈P} Aut(ρ) for P ⊆ Rel(A).

The Problem: Characterize the

Galois closed sets of relations.

in other words:

• Which subsets of Rel(A) are of the form sInv(F) for some F?

• (rephrased:) describe the closure operator

P ↦ sInvAut(P)

3/10

[figure]

Aside

The dual closure operator is easy to describe: For any set F ⊆ Sym(A), the set Aut sInv(F) is the smallest subset of Sym(A)

• containing F

• closed under the group operations (composition, inverse)

• closed under finite interpolability.

(= closed in the Tychonoff topology on A^{A}. “f ∉ Aut(ρ)” is an open=finitary property.)

Thus, for infinite sets A (of any cardinality) we have to combine an algebraic(=finitary) closure operator with a topological(=infinitary) closure operator. So we have to expect that the description of P ↦ sInv Aut(P) also involves finitary and infinitary closure.

4/10

[figure]

Closure properties of sInv(F)

Example 1: if ρ_{1}, ρ_{2} are both in sInv(F) (for some F), and are of the same arity k, then also ρ_{1} ∪ ρ_{2} and A^{k} \ ρ_{1} must be in sInv(F).

Example 2: if ρ ⊆ A × A is in sInv(F), then also the projection of ρ,

∃ρ := {x ∈ A : ∃y ∈ A (x, y) ∈ ρ}

is in sInv(F).

Conclusion: sInv(F) is closed under all logical operations. (=operations of first order logic). This is also called a “Krasner algebra” (of the second kind). Moreover, sInv(F) is closed under arbitrary intersections.

5/10

[figure]

Countable base sets

Theorem: If A is countable, P ⊆ Rel(A), then sInvAut(P) is the closure of P under logical operations and arbitrary intersections. However, this is not true for uncountable sets: E.g., if ρ ⊆ A × A, then the relation ∃^{>ℵ_{0}}ρ, defined as

{x : there are uncountably many y:(x, y) ∈ ρ}

is in sInvAut(ρ), but can in general not be obtained from ρ with logical operations and arbitrary intersections.

6/10

[figure]

Invariant operations

The problem is that first order logic cannot distinguish different infinite cardinalities. So we add all operations from all higher order logics.

Definition: A map h : Rel_{k_{1}}(A) × ⋯ × Rel_{k_{ℓ}}(A) → Rel(A) is called an invariant operation, if:

For all f ∈ Sym(A) and all ρ_{1} ∈ Rel_{k_{1}},
…, ρ_{ℓ} ∈ Rel_{k_{ℓ}} we have
h[f(ρ_{1}, …, ρ_{ℓ})] = f(h[ρ_{1}], …, h[ρ_{ℓ}])]

All logical operations, and all operations definable in higher order logic such as ∃^{>ℵ_{0}} are invariant.

7/10

[figure]

A plausible conjecture

We are looking for an internal description of the closure operator P ↦ Aut sInvP. In many cases — in particular if the base set A is at most countable, or if the set P is finite — we have:

Aut(sInv(P)) is the smallest set containing P which is closed under

– all invariant operations

– arbitrary intersections.

Is this true in general?

Answer: No!

8/10

[figure]

A counterexample

There is an uncountable structure 𝒜 = (A, ρ_{1}, ρ_{2}, …) such that, letting

P := the first order definable relations of 𝒜 (without parameters)

𝒜 ↾n := (A, ρ_{1}, …, ρ_{n})

we have

1. 𝒜 is ℵ_{0}-categorical. Hence:

– P is small (countable)

– P is closed under arbitrary ⋂

2. ∀n : 𝒜 ↾n is homogeneous (every finite partial automorphism extends)

This implies: P is closed under all invariant operations.

3. 𝒜 is rigid.

Hence, Aut(P) = {id}, and sInv AutP = Sym(A) is large .

9/10

[figure]

Characterization of sInv Aut

Definition: A map

h : ∏_{n∈ω} Rel_{k_{n}}(A) → Rel(A)

is called an σ-invariant operation, if:

For all f ∈ Sym(A) and all countable sequences (ρ_{1}, …) with ρ_{1} ∈ Rel_{k_{1}}, …, we have

h[f(ρ_{1}, …, ρ_{ℓ}, …)] = f(h[ρ_{1}], …, h[ρ_{ℓ}], …)]

Then we have for any (even uncountable) set A:

For any set P of relations on A, Aut sInvP is the smallest set containing P which is closed under all invariant operations, and arbitrary intersections.

10/10