In this post, we present the proofs of the following two theorems, using Baire’s categoricity theorem.
Theorem (Fraisse, 1954). Let 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 with age .
We note that this is not the most general version of the theorem.
Theorem (Completeness; Godel, 1929). Let be a theory such that . Then 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 be a complete metric space, and let be a family of open and dense subsets of . Then is dense in .
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.
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.
These are some short notes concerning model-complete cores, based on an exposition of Manuel Bodirsky. In particular, he proved that every -categorical structure has a unique (up to isomorphism) model-complete core. We pose the question whether the model-complete core of a definable structure (say, over the equality atoms) is again definable.
Fix an -categorical structure . The simplest, and already interesting case is , the pure countable set.
We consider the definable graph isomorphism problem for graphs which are definable (equivalently, interpret in) :
Input: Two definable graphs
Output: Yes, if and are isomorphic, No otherwise.
Below we make some very basic observations concerning this problem.
We ask the question of how the Rees-Suskevitch theorem should be generalised to provide representations of orbit-finite 0-simple semigroups. We believe that orbit-finite groupoids will be useful for this.
Orbit-finite groups are finite, and therefore not very interesting from the perspective of sets with atoms. It turns out that orbit-finite groupoids form interesting structures. They will be useful in the study of orbit-finite semigroups in the following post.
A straight set is an equivariant set which is equivariantly isomorphic to a disjiont union of sets of the form . 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.