All posts by szymtor

Fraisse and Completeness from Baire Categoricity

In this post, we present the proofs of the following two theorems, using Baire’s categoricity theorem.

Theorem (Fraisse, 1954). Let \cal C be a countable class of relational structures over a finite relational signature, which is closed under induced substructures and under amalgamation. Then there is a homogeneous structure \str A with age \cal C.

We note that this is not the most general version of the theorem.

Theorem (Completeness; Godel, 1929). Let T be a theory such that T\not\vdash \bot. Then T has a countable model.

The standard proofs of these theorems involve some sort of constructions which proceed in stages, in each stage satisfying some requests which appeared in the previous stages. The proofs presented below rely on the following.

Theorem (Categoricity; Baire, 1899). Let X be a complete metric space, and let \cal U be a family of open and dense subsets of X. Then \bigcap \cal U is dense in X.

The first proof of Godel’s completeness theorem using Baire’s categoricity theorem appeared in Mathematics of Metamathematics (1963) by Helena Rasiowa (my great-great-phd-grand-mother) and Roman Sikorski. I don’t know who was the first to prove Fraisse’s result using Baire’s categoricity; definitely it is not new in this post (see e.g.  W. Kubiś, Fraisse sequences: category-theoretic approach to universal homogeneous structures). Other applications of Baire’s categoricity theorem in logic include the Omitting Type’s theorem and Forcing.

Continue reading

Least supports and weak elimination of imaginaries

We show that a property known from model theory as weak elimination of imaginaries corresponds to the property of admitting least algebraically closed supports, and is a generalization of admitting least supports in many contexts. In particular, we show that an ω-categorical structure admits least supports if and only if it has no algebraicity and has weak elimination of imaginaries.

Continue reading

The Rado graph admits only one oligomorphic action of its automorphism group

Let R denote the Rado graph and \aut R its automorphism group. We show that any action of \aut R on R by automorphisms which has finitely many orbits is isomorphic to the natural action. Therefore, in a sense, every interpretation of the Rado graph in itself without parameters is trivial. The proof uses a counting argument. As a corollary, every interpretation of the Rado graph in itself without parameters is definably isomorphic or anti-isomorphic to the Rado graph. Also, there is no interpretation of (R,c) – the Rado graph with a constant – in R which does not use parameters.

Continue reading

Least supports and non-interpretability

In this post, we give a proof that (\str Q,\le) does not interpret (without parameters) in the homogeneous poset P nor in the random graph R. The idea is to first show that every continuous action of \aut P  or \aut R on a set is faithful or trivial. We show this by using the fact that P and R have least supports. Since \aut P and \aut R have an automorphism of order two and \aut {\str Q,\le} does not, this proves that there is no nontrivial continuous action of \aut P nor \aut R on \str Q.

Continue reading

Automorphism groups of definable structures

We consider equality atoms \atoms, i.e., \atoms is a countable set with the equality relation. Recall that by definable set we mean a structure which can be defined (in a possibly nested fashion) from \atoms using finite unions, finite tuples, and set-builder expressions with first-order formulas ranging over \atoms, e.g. \set{(x,y):x,y\in\atoms, x\neq y}\cup\set{x:x\in\atoms, x\neq 5} is definable using the parameter 5. A definable relational structure is a relational structure (A,R_1,\ldots,R_n) where A and each relation R_i is a definable set. Up to isomorphism, definable structures are the same as structures which interpret in \atoms, using first-order interpretations (this correspondence preserves parameters), but sometimes using definable sets makes constructions easier.

The problem described in the previous post is to determine isomorphism between two definable structures. In this post, we describe this problem in terms of automorphism groups. This post is based on discussions with Manuel Bodirsky and Antoine Mottet.

Continue reading

Graph isomorphism

Fix an \omega-categorical structure \atoms. The simplest, and already interesting case is (\mathbb N,=), the pure countable set.

We consider the definable graph isomorphism problem for graphs which are definable (equivalently, interpret in) \atoms:

Problem: DefGraphIso

Input: Two definable graphs G,H

Output: Yes, if G and H are isomorphic, No otherwise.

Below we make some very basic observations concerning this problem.

Continue reading

Can orbit-finite semigroups be straightened?

A straight set is an equivariant set which is equivariantly isomorphic to a disjiont union of sets of the form \atoms^{(n)}. A straight semigroup is an equivariant semigroup whose universe is a straight set. We raise the following:

Question 1: is every equivariant, orbit-finite semigroup an image of some orbit-finite, straight semigroup under an equivariant mapping?

We show some simple preliminary observations towards the above question.

Continue reading