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, -categorical structures, Automorphisms vs preserving types.
Definitions:, type, theory, canonical function, -categorical structure, pointwise convergence.
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 -categorical structures.
We will work our way up to complicated examples by understanding some simple examples.
Example 1 – Sets
Let be sets and let be a function.
In other words, on the function is so regular that it is in fact constant.
Proof. We present an overpowered proof using Ramsey’s Theorem. There is a more direct proof of this (Exercise).
Define a colouring by iff . Ramsey’s theorem gives the desired conclusion (colour EQ gives a constant function and NEQ gives a one-to-one function).
Example 2 – Linear orders
Let be a function, where is the usual order on these sets.
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 be a function, where is a poset.
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 be a relational structure in some signature . For we define type of an -tuple (in to be .
The type of an element is all formulas that are true about the element in the structure .
For example, in there are three possibilities for the type of a pair : either or .
- For the structure , find how many types a triple can have.
- Show that any two one point sets in have their own type. (Use quantifiers.)
To avoid the difficulties of Exercise , we will only look at structures that are completely determined by what relations hold on them. We will not need quantifiers.
Definition. Let be structures in some signatures. We say that a function is canonical if for all , all , .
By we mean the componentwise application of the function. E.g. .
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.
For example, a canonical function must send the types to the types . An automorphism 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.
Definition. Let be a countable structure. We say that is -categorical if countable implies .
Here is the collection of all true sentences in .
For example, is -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 -categorical.
Lemma. Let be an -categorical structure, , .
if and only if .
The moral here is that being in the same orbit is equivalent to being the same type.
Examples of canonical functions
- Every automorphism is a (very trivial kind of) canonical example.
- For the map that sends to 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 to in an order preserving way, and maps to in an order preserving way. Call this a cycling map. This is not a canonical map from since it behaves differently on and , but it is canonical from
Closed subgroups of the symmetric group
We will use canonical functions to describe the (closed) groups such that . First we explain these concepts.
Definition. Let be sets. The product is the collection of all functions . The topology we use it pointwise convergence, where for and we say that iff for all finite such that .
In particular, a sequence if such that for all . This is where the name “pointwise convergence” comes from.
The group is the collection of all bijections on , where the operation is composition.
This gives us the following question
Theorem (Cameron). There are only three groups strictly between and .
In particular, for a reflection map and a cycle map, and we have .
We will prove this in the next lecture. To a certain extent this theorem says that only has two types of symmetries: and .