Oligomorphic Magic

I hadn't planned on making a new post until after moving but here we go. It seems that there are a few people with a philosophical bent reading this, so I will try and make a philosophical post soon. Today, however, is mathematical.

A couple of days ago, I was chatting with some group theorists and they mentioned the strange notion of an oligomorphic group. From a purely permutation group perspective, it does not seem like a particularly interesting object, so why has there been such a hubbub of late? The answer lies in logic and, in particular, model theory.

To make this post a manageable length, I assume familiarity with the definition of a group. Given a set X, the symmetric group on X, denoted Sym(X), is the group of all bijections mapping X to itself with function composition as the group operation. A permutation group, G, is a subgroup of Sym(X) for some X. Given a point x in X, the orbit of x is the set of all images of x under maps in G. It is a standard result that X is partitioned by the set of all orbits of G on X. The flavour of this area of group theory is markedly different depending upon whether X is finite or infinite. We shall deal with the infinite case here.

Now, a model, M, is a tuple consisting of a set m called the domain, together with a collection of (possibly no) functions from M^n to M and another collection of (possibly no) n-ary relations on M as well as some (possibly none) elements of m that are distinguished as constants. An automorphism of M is a permutation of m that preserves all functions and relations in M. For example, if (N,+,=) denotes the natural numbers together with addition and equality symbols, then an automorphism of this structure is just a semigroup automorphism. The collection of all automorphisms of M form a group under composition, the automorphism group of M, denoted by Aut(M). Given two models M and N, we say that they are isomorphic if there is a bijection mapping the domain of one to the domain of the other, which preserves functions and relations.

Much like in the first post of this blog, the automorphism group is going to tell us something logically interesting. Except, instaead of loooking at automorphisms of formulae, we are going to look at automorphisms of models. A set of sentences (quantifier-free formulae), S, is omega-categorical if every model of S with a countably infinite (omega) domain is isomorphic. Given a model M, the theory of M, denoted Th(M), is the set of all sentences true in M. Can we find omega-categorical theories?

It turns out that we can use the information about Aut(M) in order to find such theories. It is a result of Engeler, Ryll-Nardzewski and Svenonius that the following are equivalent for a countably infinite model M with domain m over a countable language:

1. Th(M) is omega-categorical
2. For each natural number k, there are only finitely orbits of Aut(M) on the set of k-tuples of elements of m.

This second condition is what is meant by an "oligomorphic" group: it has only finitely many orbits on the k-tuples of its permutation domain. We can also go the other way. Given an oligomorphic group, we can construct the so-called "canonical model" and this is going to have an omega-categorical theory.

Interesting flows of results start to go between model theory and permtuation group theory at this stage. For instance, from some elementary model theory, it follows that if a group G is the automorphism group of a model of an omega-categorical theory and H is any subgroup of G, then there are only finitely many groups between H and G (that is groups K such that H < K < G)

All of this is the starting point of the following wonderful book, which I, sadly, do not have the time to browse through properly before jetting off on Saturday:
Automorphisms of First Order Structures