Functions on Homogeneous Ramsey Structures 1 – 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 helpful fixes and feedback.

Title: Functions on Homogeneous Ramsey Structures 1 (of 3)

Lecturer: Michael Pinsker

Date: Wednesday October 5, 2016.

Main Topics: Canonical functions, $\omega$ -categorical structures, Automorphisms vs preserving types.

Definitions: $[S]^n$ , type, theory, canonical function, $\omega$ -categorical structure, pointwise convergence.

Lecture 1 – Lecture 2 – Lecture 3

Introduction

We will look at functions between two structures each with some type of Ramsey property. From this we would like to show that the function must have some “regular behaviour”.

Applications of this include the Constraint Satisfaction Problem (CSP) and reducts of $\omega$ -categorical structures.

The 2011 article by Manuel Bodirsky and Michael Pinsker “Reducts of Ramsey structures” provides a good survey of the area.

Toy examples

We will work our way up to complicated examples by understanding some simple examples.

Example 1 – Sets

Let $S,T$ be sets and let $f: S \longrightarrow T$ be a function.

Fact. If $T$ is finite, and $S$ is infinite, then there is an infinite $S^\prime \subseteq S$ such that $f \upharpoonright S^\prime$ is constant.

In other words, on $S^\prime$ the function is so regular that it is in fact constant.

Fact. If $T$ is arbitrary, there is an infinite $S^\prime \subseteq S$ such that $f \upharpoonright S^\prime$ is one-to-one or constant.

Definition. For a set $S$ , $n \in \mathbb{N}$ we define $[S]^n$ to be the collection of all unordered subsets of $S$ of cardinality $n$ . The collection $[S]^\omega = [S]^\infty$ is defined similarly.

Proof. We present an overpowered proof using Ramsey’s Theorem. There is a more direct proof of this (Exercise).

Define a colouring $\chi: [S]^2 \longrightarrow \{\text{EQ}, \text{NEQ}\}$ by $\chi(\{a,b\}) = \text{EQ}$ iff $f(a)=f(b)$ . Ramsey’s theorem gives the desired conclusion (colour EQ gives a constant function and NEQ gives a one-to-one function).

High-level overview. We looked at the local behaviour of the function and saw that it can do one of two things to pairs of points (identify them, or distinguish them). Ramsey then tells us that the local behaviour can be global.

Example 2 – Linear orders

Let $f: (\mathbb{N}, \leq) \longrightarrow (\mathbb{Q}, \leq)$ be a function, where $\leq$ is the usual order on these sets.

Fact. There is an infinite $S^\prime \subseteq \mathbb{N}$ such that $f \upharpoonright S^\prime$ is one-to-one, strictly increasing or strictly decreasing.

This proof uses the same trick of looking at local behaviour, but this time there are three types of local behaviour.

Example 3 – Poset

Let $f: (\mathbb{Q}, \leq) \longrightarrow (P, \preceq)$ be a function, where $(P, \preceq)$ is a poset.

Fact. There is an infinite $S^\prime \subseteq \mathbb{Q}$ such that $f \upharpoonright S^\prime$ is one-to-one, strictly increasing, strictly decreasing, or an antichain (no two elements are comparable).

Note that the domain and codomain can have different signatures.

Functions with regular behaviour: Canonical functions

We would like to describe a function that captures the “sameness” of a structure. To do this we use the notion of types.

Definition. Let $\Delta$ be a relational structure in some signature $L$ . For $n \geq 1, \overline{a} \in \Delta^n$ we define type of an $n$ -tuple (in $\Delta)$ to be $\text{type}_\Delta \overline{a} = \{\phi(x_1, \ldots, x_n) : \phi \text{ is a first order formula over }\Delta, \Delta \models \phi(\overline{a})\}$ .

The type of an element is all formulas that are true about the element in the structure $\Delta$ .

For example, in $(\mathbb{Q}, \leq)$ there are three possibilities for the type of a pair $\{a,b\} \in \mathbb{Q}^2$ : either $a<b, b<a$ or $a=b$ .

Exercise.

For the structure $(\mathbb{Q}, \leq)$ , find how many types a triple ${a,b,c} \in \mathbb{Q}^3$ can have.
Show that any two one point sets in $(\mathbb{N}, \leq)$ have their own type. (Use quantifiers.)

To avoid the difficulties of Exercise $2$ , we will only look at structures that are completely determined by what relations hold on them. We will not need quantifiers.

Definition. Let $\Delta, \Lambda$ be structures in some signatures. We say that a function $f: \Delta \longrightarrow \Lambda$ is canonical if for all $n \geq 1$ , all $\overline{a}, \overline{b} \in \Delta^n$ , $\text{type}_\Delta \overline{a} = \text{type}_\Delta \overline{b} \Rightarrow \text{type}_\Lambda f\overline{a} = \text{type}_\Lambda f\overline{b}$ .

By $f\overline{a}$ we mean the componentwise application of the function. E.g. $f(x,y)= (f(x), f(y))$ .

A canonical function is one that sends “same” to “same”. We will see in a moment that this captures more functions than just automorphisms. We will also see equivalent definitions of canonical functions.

Definition. A canonical function $f: \Delta \longrightarrow \Lambda$ induces a map $\hat{f}: \text{Types}_\Delta \longrightarrow \text{Types}_\Lambda$ , where $\text{Types}_\Delta$ is the collection of all types in $\Delta$ .

For example, a canonical function $f : (\mathbb{Q}, \leq) \longrightarrow (\mathbb{Q}, \leq)$ must send the types $\{=, \}$ to the types $\{=, \}$ . An automorphism $f$ must induce the identity on these types, but a canonical function can permute them.

This is exactly what we mean by “regular behaviour” of a function.

$\omega$ -categorical structures

Definition. Let $\Delta$ be a countable structure. We say that $\Delta$ is $\omega$ -categorical if $\forall$ countable $\Lambda^\prime, \text{Theory}(\Delta^\prime) = \text{Theory}(\Lambda)$ implies $\Delta^\prime \cong \Delta$ .

Here $\text{Theory}(\Lambda)$ is the collection of all true sentences in $\Lambda$ .

For example, $(\mathbb{Q}, \leq)$ is $\omega$ -categorical because of the classical theorem that it is the unique countable dense-in-itself linear order without endpoints.

In the second lecture we will see equivalent definitions of $\omega$ -categorical.

Lemma. Let $\Delta$ be an $\omega$ -categorical structure, $n > 1$ , $\overline{a}, \overline{b} \in \Delta^n$ .

$\text{type}_\Delta \overline{a} = \text{type}_\Delta \overline{b}$ if and only if $\exists \alpha \in \text{Aut}(\Delta), \alpha \overline{a} = \overline{b}$ .

Proof. The $\Leftarrow$ direction can be verified directly, without using $\omega$ -categoricity. The $\Rightarrow$ direction uses a back-and-forth argument. $\omega$ -categoricity is used to capture the information of each type with only finitely much structure. This is a vague sketch only.

Michael Kompatscher’s comment. If you use Ryll-Nardzeswski it is not so hard. Note that every type in an $\omega$ -categorial structure can be described by one formula (Proof: You can always separate two types by some formula. Since in $\omega$ -categorical structures there are only finitely many types in every arity, you can describe a type by the conjunction of the formulas that separate it from the other types of same arity). Then the statement follows from a back-and-forth argument.

The moral here is that being in the same orbit is equivalent to being the same type.

Proposition. Let $\Delta, \Lambda$ be $\omega$ -categorical. A function $f: \Delta \longrightarrow \Lambda$ is canonical if and only if $\forall n \geq 1, \forall \overline{a} \in \Delta^n, \forall \alpha \in \text{Aut}(\Delta), \exists \beta \in \text{Aut}(\Lambda)$ such that $\beta f \alpha \overline{a} = f \overline{a}$ .

Examples of canonical functions

Every automorphism is a (very trivial kind of) canonical example.
For $(\mathbb{Q}, <)$ the map that sends $x$ to $-x$ is canonical. It is not an automorphism, because it actually destroys all of the relations.
All constant functions.
Take the function that maps the positive rationals $(\pi,\infty)$ to $(-\infty, e)$ in an order preserving way, and maps $(-\infty, \pi)$ to $(e, \infty)$ in an order preserving way. Call this a cycling map. This is not a canonical map from $(\mathbb{Q}, <) \longrightarrow (\mathbb{Q}, <)$ since it behaves differently on $\{3,4\}$ and $\{5,6\}$ , but it is canonical from $(\mathbb{Q}, <, \pi) \longrightarrow (\mathbb{Q}, <)$

Closed subgroups of the symmetric group

We will use canonical functions to describe the (closed) groups such that $\text{Aut}(\mathbb{Q}, <) \leq G \leq \text{Sym}(\mathbb{Q})$ . First we explain these concepts.

Definition. Let $X,Y$ be sets. The product $Y^X$ is the collection of all functions $f:X \longrightarrow Y$ . The topology we use it pointwise convergence, where for $S \subseteq Y^X$ and $g \in Y^X$ we say that $g \in \overline{S}$ iff for all finite $F \subseteq X, \exists f \in S$ such that $g \upharpoonright F = f \upharpoonright F$ .

In particular, a sequence $(f_n)_{n \in \omega} \longrightarrow f$ if $\forall a \in X, \exists i \in \omega$ such that $f_j(a)=f(a)$ for all $j>i$ . This is where the name “pointwise convergence” comes from.

The group $\text{Sym}(\Delta)$ is the collection of all bijections on $\Delta$ , where the operation is composition.

Fact. $\text{Aut}(\Delta)$ is a closed subgroup of $\text{Sym}(\Delta)$ .

Proof. Suppose that $g \in \overline{\text{Aut}(\Delta)} \subset \text{Sym}(\Delta)$ , we will show that $g \in \text{Aut}(\Delta)$ . If it wasn’t, you could witness this on a finite set. Any automorphism will preserve relations and negations on a finite set.

This gives us the following question

Question. For a fixed structure $\Delta$ , what closed supergroups does $\text{Aut}(\Delta)$ have?

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}, <)$ .

We will prove this in the next lecture. To a certain extent this theorem says that $\mathbb{Q}$ only has two types of symmetries: $\leftrightarrow$ and $\curvearrowright$ .

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

Yangjing says:

October 9, 2016 at 4:59 am

Hi, Mike, in the fact after example 2, an infinite S′⊆S maybe better S′⊆N. Yangjing

LikeLike

1. Yangjing says:
  
  October 9, 2016 at 4:59 am
  
  same as example 3
  
  LikeLike
  
2. Micheal Pawliuk says:
  
  October 9, 2016 at 6:21 am
  
  They are both fixed now. Thanks!
  
  LikeLike
  
Pingback: Functions on Homogeneous Ramsey Structures 2 – Ramsey DocCourse Prague 2016
Pingback: Functions on Homogeneous Ramsey Structures 2 – Ramsey DocCourse Prague 2016
Pingback: Functions on Homogeneous Ramsey Structures 3 – Ramsey DocCourse Prague 2016