Functions on Homogeneous Ramsey Structures 2 – Ramsey DocCourse Prague 2016 – Mike Pawliuk

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

$\Delta$ is $\omega$ -categorical.
$\forall n \geq 1$ , $\Delta$ has only finitely many types of $n$ -tuples.
$\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$ .

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.

$g$ lives in the correct place.
$g$ is canonical
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”

Pingback: Functions on Homogeneous Ramsey Structures 1 – Ramsey DocCourse Prague 2016
Pingback: Functions on Homogeneous Ramsey Structures 3 – Ramsey DocCourse Prague 2016

Playing around with -categorical

Cameron’s Theorem

Intuition: Where do the supergroups come from?

Proof of the Ramsey proposition

Share this:

Like this:

Related

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

Leave a Reply Cancel reply

Playing around with $\omega$ -categorical