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.

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 -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 be sets and let be a function.

**Fact**. If is finite, and is infinite, then there is an infinite such that is constant.

In other words, on the function is so regular that it is in fact constant.

**Fact**. If is arbitrary, there is an infinite such that is one-to-one or constant.

**Definition**. For a set , we define to be the collection of all unordered subsets of of cardinality . The collection 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 by iff . 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 be a function, where is the usual order on these sets.

**Fact**. There is an infinite such that 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 be a function, where is a poset.

**Fact**. There is an infinite such that 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 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 .

**Exercise**.

- 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.

**Definition**. A canonical function induces a map , where is the collection of all types in .

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.

## -categorical structures

**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 .

**Proof**. The direction can be verified directly, without using -categoricity. The direction uses a back-and-forth argument. -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 -categorial structure can be described by one formula (Proof: You can always separate two types by some formula. Since in -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 be -categorical. A function is canonical if and only if such that .

### 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.

**Fact**. is a closed subgroup of .

**Proof**. Suppose that , we will show that . 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 , what closed supergroups does have?

**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 .

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

LikeLike

same as example 3

LikeLike

They are both fixed now. Thanks!

LikeLike