5
$\begingroup$

The famous Ehrenfeucht's omitting types theorem states that for any countable set of nonisolated types (without parameters), there is a (countable) model such that it does not realize any of them.

A similiar theorem, which so far as I know is due to Shelah states that for any complete theory $T$ with infinite models, you can omit any set of COMPLETE nonisolated types of cardinality less than $2^{\lvert T\rvert}$ -- he announces the result in the introduction to Classification Theory and the Number of Non-Isomorphic Models, but the book is quite hard to read and I did not even manage to find the actual proof, however, an accessible sketch for the countable case can be found in Wilfrid Hodges' Model Theory.

This, however, provokes the following conjecture, generalizing the above result for countable theories:

For any complete, countable theory $T$ with infinite models, and any subset of $S_1(\emptyset)$ with empty interior, there exists a model of $T$ omitting all the types in the set.

It would be a generalization, since the space of complete types in a countable theory is a Polish space (through its natural embedding into the Cantor set, for instance), so in particular any open subset contains an isolated point or its cardinality is $2^{\aleph_0}$.

On the other hand, I haven't heard about such a conjecture or theorem, even though it seems very natural, as it would give complete characterization of sets of types that can be omitted (it is easy to see that emptiness of interior is a necessary condition), so my guess is that there are known counterexamples, or it is independent from ZFC.

Am I right? If yes, are there simple counterexamples? If I'm not, was there ever any promising research in that direction, or maybe it is even a theorem?

$\endgroup$
4
  • $\begingroup$ I may be getting this wrong, but since $\{p\}$ is open for isolated $p$, any set with empty interior must consist of non-isolated types. So your conjecture is weakening rather than strengthening of Ehrenfeucht's result. $\endgroup$ Commented Oct 27, 2012 at 11:00
  • $\begingroup$ @LevonHaykazyan: Ehrenfeucht's theorem states that nonisolated types can be omitted. Furthermore, it is not hard to see that no isolated type can be omitted, so you're probably getting it wrong. $\endgroup$
    – tomasz
    Commented Oct 27, 2012 at 11:08
  • $\begingroup$ Right sorry, I missed the point that a set of types with empty interior may be uncountable. $\endgroup$ Commented Oct 27, 2012 at 19:36
  • 1
    $\begingroup$ The following is an exercise (4.2.2 b) in the book "A course in model theory" by Tent and Ziegler. Let $T$ be a countable and consistent. Then any meagre subset $X$ of $S_n(T)$ can be omitted. I have no idea how to prove it. $\endgroup$ Commented Nov 8, 2012 at 22:32

1 Answer 1

7
$\begingroup$

The proposed generalization is false. The hypothesis of empty interior is too weak, but, as indicated by Levon Haykazyan's comment from the book of Tent and Ziegler, the statement would become correct if one required that the closure of the set of types to be omitted has empty interior.

Here's a counterexample to the generalization in the question. Let the language consist of countably many unary predicate symbols $U_n$ (one for each natural number $n$) and a unary function symbol $f$. Let the theory $T$ say that $f(x)\neq x$ and $f(f(x))=x$ for all $x$ (so $f$ serves to pair up the elements of the universe of any model of $T$), that $U_n(x)\iff U_n(f(x))$ for all $x$ for each $n\neq0$, but $U_0(x)\iff\neg U_0(f(x))$ (so paired elements satisfy the same $U_n$'s except that they disagree about $U_0$), and, for any distinct subscripts $n_i,\dots,n_k,m_1,\dots,m_l$, the formula saying that there is an element $x$ satisfying all of $U_{n_1},\dots,U_{n_k}$ and none of $U_{m_1},\dots,U_{m_l}$ (so the $U$ predicates are combinatorially independent). Unless I've made a stupid (and easily repaired) mistake, this $T$ is a complete theory.

For each infinite sequence $a=(a_0,a_1,\dots)$ of zeros and ones, there is a type $t_a$ consisting of the formulas $U_n(x)$ for those $n$ with $a_n=1$ and $\neg U_n(x)$ for those $n$ with $a_n=0$ (and the $T$-consequences of these, if your definition of "type" requires closure under consequences). Note that the topology of the space $S_1$ of types (in one variable) for $T$ matches the usual product topology on the space of sequences $a$.

Partition the set of sequences $(a_1,a_2,\dots)$ [intentionally starting with subscript 1, not 0] into two pieces $Y$ and $Z$ both with empty interior. For example, $Y$ could consist of those sequences that have infinitely many zeros and $Z$ those with only finitely many. Let $X$ consist of those sequences $a=(a_0,a_1,\dots)$ such that either $a_0=0$ and $(a_1,a_2,\dots)\in Y$ or $a_0=1$ and $(a_1,a_2,\dots)\in Z$. This $X$ has empty interior, but I claim no model can omit all the types $t_a$ for all $a\in X$.

To verify the claim, suppose, toward a contradiction, that we had such a model, and consider some element $q$ of it. Suppose $U_0(q)$ holds (in this model). (The case where it doesn't hold is treated symmetrically.) Define $(a_1,a_2,\dots)$ by setting $a_n$ equal to 0 if $U_n(q)$ holds and equal to 1 if it doesn't hold. So $q$ realizes the type $t_a$ where $a=(0,a_1,a_2,\dots)$. If $(a_1,a_2,\dots)\in Y$ then $a\in X$ and we have the claimed contradiction. If, on the other hand, $(a_1,a_2,\dots)\in Z$ then $f(q)$ realizes $t_b$ where $b=(1,a_1,a_2,\dots)\in X$, so we again have a contradiction.

$\endgroup$
1
  • $\begingroup$ Nice example! It looks very natural (so convincing) to me, for what it's worth. $\endgroup$
    – tomasz
    Commented Nov 10, 2012 at 13:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .