Functions on Homogeneous Ramsey Structures 2 – Ramsey DocCourse Prague 2016

The following notes are from the Ramsey DocCourse in Prague 2016. The notes are taken by me and I have edited them. In the process I may have introduced some errors; email me or comment below and I will happily fix them.

Special thanks. Thank you to Michael Kompatscher for all his feedback and helpful comments.

Title: Functions on Homogeneous Ramsey Structures 2 (of 3).

Lecturer: Michael Pinsker.

Date: Friday October 7, 2016.

Main Topics: Equivalent notions of \omega -categorical, Proof of Cameron’s Theorem, Proof of canonical-Ramsey.

Definitions:No new ones.

Lecture 1 – Lecture 2 – Lecture 3

Playing around with \omega -categorical

Our definition of \omega -categorical said that for an \omega -categorical structure all other countable structures with the same theory were isomorphic. Here we present two more algebraic definitions.

Theorem (Ryll-Nardzewski, Engeler, Sveronus, 1959). For \Delta a countable structure TFAE

  1. \Delta is \omega -categorical.
  2. \forall n \geq 1 , \Delta has only finitely many types of n -tuples.
  3. \forall n \geq 1 , \text{Aut}(\Delta) \curvearrowright \Delta^n has only finitely many orbits.

Moreover, (2) and (3) are in correspondence. In any of these three equivalent cases, every orbit is first order definable in \Delta .

The assumption that \Delta is countable is to prevent counterexamples of other cardinalities from the Löwenheim–Skolem theorem.

In the case that \Delta is homogeneous this gives us a nice corollary. The proof is an exercise.

Corollary. If \Delta is homogeneous in a finite relational language, then \Delta is \omega -categorical.

In the previous lecture we started to examine closed supergroups of \text{Aut}(\Delta) . This is motivated by the following open conjecture.

Conjecture (S. Thomas, 1991). If \Delta is a homogeneous structure with a finite relational language then \text{Aut}(\Delta) has only finitely many closed supergroups.

One of the original motivations for this is the following theorem.

Proposition. Let \Gamma, \Gamma^\prime be \omega -categorical (relational) structures on the same domain.

\Gamma is first order definable in \Gamma^\prime if and only if \text{Aut}(\Gamma) \supseteq \text{Aut}(\Gamma^\prime) .

Note that in the Proposition you can drop the condition that \Gamma is \omega -categorical, since \text{Aut}(\Gamma) contains \text{Aut}(\Gamma^\prime) and therefore has fewer orbits in every arity that \text{Aut}(\Gamma^\prime) . (Comment by Michael Kompatscher.)

Proof. The \Rightarrow direction is straightforward. An automorphism of \Gamma^\prime will preserve statements in \Gamma^\prime so it preserves the structure of \Gamma (since it’s definable in \Gamma^\prime ). \omega -categorical is not needed here.

For the \Leftarrow direction, start with a relation R of \Gamma . By assumption it is preserved by \text{Aut}(\Gamma^\prime) . By \omega -categoricity, R is a union of finitely many orbits of \text{Aut}(\Gamma^\prime) . By assumption each orbit is definable, so R is definable (using Ryll-Nardzewski).

We can now prove a nice corollary.

Corollary. Let \Delta be \omega -categorical (relational) structure.
Closed supergroups of \text{Aut}(\Delta) are in one-to-one correspondence with structures that are first order definable in \Delta (up to interdefinability).

You might need the following exercise to prove the corollary.

Exercise. Every closed subgroup of \text{Sym}(\mathbb{N}) is the automorphism group of some structure.

In the case of (\mathbb{Q}, <) we looked at the the closed subgroups G[\leftrightarrow] = \langle \text{Aut}(\mathbb{Q}, <), \leftrightarrow \rangle , where \leftrightarrow is a reflection map, and G[\curvearrowright] = \langle \text{Aut}(\mathbb{Q}, <), \curvearrowright \rangle , where \curvearrowright is a cycling map (see lecture 1). In an abuse of notation we will assume that \langle A,B \rangle is the topological closure of the algebraic closure of A and B .

These correspond to the following structures:

G[\leftrightarrow] is given by the structure (\mathbb{Q}, <, \text{betw}(x,y,z)) where \text{betw}(x,y,z) if and only if x<y<z or z< y<x .

G[\curvearrowright] is given by the structure (\mathbb{Q}, <, \text{cycle}(x,y,z)) where \text{cycle}(x,y,z) if and only if x<y<z or z<x<y or y<z<x .

Cameron’s Theorem

As mentioned in the previous lecture, we want to characterize the closed supergroups of \text{Aut}(\mathbb{Q}, <) .

Theorem (Cameron). There are only three groups strictly between \text{Aut}(\mathbb{Q}, <) and \text{Sym}(\mathbb{Q}, <) .

In particular, for \leftrightarrow a reflection map and \curvearrowright a cycle map, and G = \text{Aut}(\mathbb{Q}, <) we have G \leq \langle G, \leftrightarrow \rangle, \langle G, \curvearrowright \rangle \leq \langle G, \leftrightarrow, \curvearrowright \rangle \leq \text{Sym}(\mathbb{Q}, <) .

In order to prove a theorem like this, it is very useful to have someone provide the target groups. Our proof strategy will be to start with a closed proper supergroup G of \text{Aut}(\mathbb{Q}, <) . We want to show that G contains one of the maps \leftrightarrow or \curvearrowright .

Since G is proper, it contains an f that is not an automorphism. So there are a<b such that f(b) < f(a) . We will use Ramsey’s Theorem to ensure that the function (or really a related function) is well behaved on large sections of \mathbb{Q} . We will use the following Ramsey result (with \{a,b\} = \{c_1,c_2\}) .

Proposition. Let \Delta be an ordered, Ramsey, homogeneous, \omega -categorical structure, and assume that \Lambda is \omega -categorical.

Let f: \Delta \longrightarrow \Lambda . Fix finitely many constants c_1,\ldots, c_n \in \Delta .

There is a function g \in \overline{\{\beta f \alpha : \alpha \in \text{Aut}(\Delta), \beta \in \text{Aut}(\Lambda)\}} such that g \upharpoonright \{c_1, \ldots, c_n\} = f \upharpoonright \{c_1, \ldots, c_n\} and g is canonical (from (\Delta, c_1, \ldots, c_n) to \Lambda ).

Why do we have to enrich the language? The starting function f is usually not canonical. You might even be able to see this on the finite set of constants. For example, in (\mathbb{Q}, <) you might have f(1)=2, f(2)=1 and f(3)=3 .

We will prove the Ramsey proposition at the end of today’s lecture.

Proof of Cameron’s Theorem. Start with the f, a,b as discussed before the proposition. Find a g:(\mathbb{Q}, <, a,b) \longrightarrow (\mathbb{Q}, <) as in the proposition.

Let’s think about what this function does to the sets L = (-\infty, a), C = (a,b) and R = (b, \infty) . Notice that g swaps the order of p,q \in L if and only if it swaps the order of p^{\prime\prime}, q^{\prime\prime} \in L . This is because a is part of the (expanded) language so the structure can “see” that they are to the left of a . In particular, g must behave uniformly on each of L,C,R (although it may behave differently on different parts). This observation allows us to analyze cases based on what g does on each of these parts.

We will only investigate one case, but the rest are similar.

Case 1: g swaps the order of one of L,C,R .

Without loss of generality, assume that g swaps the order of L . That is, for all p<q \in L , g(q)<g(p) .

Let us show that the map s(x) = -x is in our closed proper supergroup G . We do this by showing that s \in \overline{G} = G .

Recall that f \in G was our starting map.

Start by fixing a finite set F in \mathbb{Q} . For technical reasons, find an m \in \mathbb{Q} such that F < m . Since (\mathbb{Q}, <) is homogeneous, find an automorphism \alpha such that \alpha sends m to a and F into L . Apply g to \alpha[F] , which will swap its order. Use homogeneity again and find an automorphism \beta of (\mathbb{Q}, <) that sends f\alpha[F] to F .

So then \beta f \alpha [F] = F , but the order is reversed. That is, for x \in F we have \beta f \alpha (x) = s(x) . So s \in \overline{G} = G .

Case 2: g puts C in front of L , but preserves the order on C , and the order on L . That is g[C] < g[L] .

This case has more subcases, but the argument is comparable to case 1.

Intuition: Where do the supergroups come from?

One of the major difficulties for these types of proofs is coming up with the supergroups. If you don’t know the groups, then the proof is much harder. So how do we come up with these groups?

One approach is to play around with canonical functions. These can give us hints as to what the groups are. Adding constants to the structure can also help, as in expanding (\mathbb{Q}, <) to (\mathbb{Q}, <, a, b) .

Michael Kompatscher’s intuition. Adding constants is useful, since on those finitely many constants you can witness that a relation is violated: In the example with reducts of (\mathbb{Q},<) , for every f that is not an automorphism \mathbb{Q} , there are elements a,b such that a<b but f(b) \leq f(a) : this was the basis of our analysis of the reducts of \mathbb{Q} . To continue the classification of reducts of \mathbb{Q} , you would proceed similarly:

"What if f is not generated by \text{Aut}(\mathbb{Q},<) and the 'reflections'?"

Then the Betweenness relation is violated, which can again be witnessed by a canonical function (\mathbb{Q},<,a,b,c) \longrightarrow (\mathbb{Q},<) , etc.

Proof of the Ramsey proposition

“The Ramsey Proposition”. Let \Delta be an ordered, Ramsey, homogeneous, \omega -categorical structure, and assume that \Lambda is \omega -categorical.

Let f: \Delta \longrightarrow \Lambda . Fix finitely many constants c_1,\ldots, c_n \in \Delta .

There is a function g \in \overline{\{\beta f \alpha : \alpha \in \text{Aut}(\Delta), \beta \in \text{Aut}(\Lambda)\}} such that g \upharpoonright \{c_1, \ldots, c_n\} = f \upharpoonright \{c_1, \ldots, c_n\} and g is canonical (from (\Delta, c_1, \ldots, c_n) to \Lambda ).

Note the condition that \Delta is \omega may be changed to \Delta is countable.

The strategy here will be to use Ramsey to get a function that is regular on each of the parts, then use homogeneity to glue the parts together.

Proof. We start out by making a claim that will be very useful, but we will prove in the next lecture.

Claim. \forall F \subseteq (\Delta, c_1, \ldots, c_n) finite, there is an F^\prime \subseteq (\Delta, c_1, \ldots, c_n) such that F^\prime \cong F such that f \upharpoonright F^\prime is canonical.

Assume the claim. Write \Delta as the increasing union of finite structures \bigcup_{i \in \omega} F_i . For each of the finite structures, find an F_i^\prime that is isomorphic to F_i such that f \upharpoonright F_i^\prime is canonical.

By thinning out, we may assume that the behaviour of f on all of the F_i^\prime is the same (we clarify this below).

Find an \alpha_i \in \text{Aut}(\Delta, c_1, \ldots, c_n) such that \alpha_i [F_i] = F_i^\prime . Note that f \alpha_i is canonical on F_i (because the automorphisms preserve structure).

Unfortunately, these F_i^\prime usually don’t form an increasing union in \Lambda , they might even be disjoint. So we fix that with automorphisms in \Lambda .

Claim. We may refine so that \forall j < i, \text{type}_\Lambda f\alpha_j[F_j] = \text{type}_\Lambda f\alpha_i[F_j] .

This is a “standard compactness argument”, which we will write out.

For i\in \omega , there are only finitely many choices for \text{type}_\Lambda f\alpha_i[F_0] , so let S_0 \subseteq \omega be a collection where are these types are the same. Let i_0 = \min S_0 .

For i \in S_0 , there are only finitely many choices for \text{type}_\Lambda f\alpha_i[F_1] , so let S_1 \subseteq \omega be a collection where are these types are the same. Let i_1 = \min S_1 \setminus \{i_0\} .

Repeat this argument to get the desired infinite S = \{i_n : n\in\omega\} . Without loss of generality we will assume that S = \omega .

Making an increasing union in \Lambda . We find \beta_i \in \text{Aut}(\Lambda) .

Start by taking \beta_0 = \text{id}_\Lambda , which will map F_0^\prime to F_0^\prime .

Then find a \beta_1 such that \beta_1 \beta_0 f \alpha_1 \upharpoonright F_0 = \beta_0 f \alpha_0 \upharpoonright F_0 . This can be done since \text{type}_\Lambda f\alpha_0[F_0] = \text{type}_\Lambda f\alpha_1[F_0] . Therefore such a \beta_1 exists by \omega -categoricity.

Inductively find \beta_{i+1} such that \beta_{i+1} \beta_i \ldots \beta_0 f \alpha_{i+1} \upharpoonright F_i = \beta_i \ldots \beta_0 f \alpha_i \upharpoonright F_i .

Thus the functions (\beta_i \ldots \beta_0 f \alpha_i)_{i \in \omega} agree on larger and larger finite sets whose union is \Delta . While the limit of these functions is canonical, it need not agree with f on \{c_1, \ldots, c_n\} . So we fix this again.

Making the limit agree with f .

Start with an automorphism \gamma \in \text{Aut}(\Lambda) that corrects where the limit (\beta_i \ldots \beta_0 f \alpha_i)_{i \in \omega} sends \{c_1, \ldots, c_n\} . Now the appropriate limit will be g = \text{lim}(\gamma\beta_i \ldots \beta_0 f \alpha_i) . Note that g \in \overline{\{\beta f \alpha : \alpha \in \text{Aut}(\Delta), \beta \in \text{Aut}(\Lambda)\}} and this will be the function we want in the theorem.

Exercise. Check the following.

  1. g lives in the correct place.
  2. g is canonical
  3. There aren’t any type errors. That is, the compositions of functions we use always makes sense.

2 thoughts on “Functions on Homogeneous Ramsey Structures 2 – Ramsey DocCourse Prague 2016”

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s