counterexample to the omitting types in uncountable language

I bravely followed Chang & Keisler's reference to the 1962 paper Bemerkung zu Einer Arbeit E. Engelers by Gebhard Fuhrken, and I was able to extract the example there. I can't read German, so the details might not be exactly the same as Fuhrken's, but I believe the main idea is the same.

First some motivation: The idea in the example in Chang and Keisler, as presented in Levon's answer, is to have an uncountable set of constants $(c_i)_{i\in \aleph_1}$ which force a model to be uncountable, and a countable set of constants $(d_j)_{j\in \omega}$, to make sure the partial type $p(x) = \{x\neq d_j\mid j\in \omega\}$ (which is not omittable, thanks to the size of the model) is not equivalent to a single formula. But if we complete the theory, the non-omittable completions of $p$ are isolated by formulas of the form $x = c_i$. We can try to fix this by separating the $c_i$ and $d_j$: put the $c_i$ and $d_j$ in disjoint unary predicates $C$ and $D$, respectively, and add $D(x)$ to $p$, so that $x = c_i$ is inconsistent with $p$ for all $i$. But then $p$ might be omitted entirely, since the realization of $D$ might consist of just the constants. Ok, how can we force the realization of $D$ to be uncountable too? We could add a bijection $f$ between $C$ and $D$. But this is no good, because it recouples $C$ and $D$: in any completion, the non-omittable completions of $p$ are isolated by formulas of the form $x = f(c_i)$. The final fix is to add not just one bijection $f$ that we can refer to by name, but a whole parametrized family of bijections.


Consider the language with $3$ unary predicates $F$, $C$, and $D$ (or $3$ sorts with these names), a ternary relation $R$ (in the sorted context, $R$ has type $F\times C\times D$), and constant symbols $(c_i)_{i\in\aleph_1}$ (of type $C$) and $(d_j)_{j\in \omega}$ (of type $D$).

Let $M$ be a structure in which $C$ and $D$ are interpreted as disjoint sets of size $\aleph_1$ and $F$ is interpreted as the set of all bijections $C\to D$. We set $R(f,c,d)$ if and only if $f\in F$, $c\in C$, $d\in D$, and $f(c) = d$. We interpret the $c_i$ as any distinct elements of $C$ and the $d_j$ as any distinct elements of $D$. Let $T = \text{Th}(M)$.

Note that $T$ contains sentences asserting that for all $f\in F$, $R(f,-,-)$ is the graph of a bijection $C\to D$, and if $R(f,-,-) = R(g,-,-)$ then $f = g$. So, in any model, we can identify the elements of $F$ with the bijections $C\to D$ that they encode.

And $T$ also contains a sentence asserting that for any $d$ and $d'$ in $D$, and for any $f$ in $F$, there exists $f'$ in $F$ such that $f' = \sigma\circ f$, where $\sigma$ is the permutation of $D$ swapping $d$ and $d'$. Such an $f'$ is necessarily unique, by the previous observation.

What are the types in the single variable $x$, over the empty set, and consistent with $D(x)$? Certainly there are the ones isolated by $x = d_j$ for all $j$. I claim that (1) there is just one other such type: the partial type $p(x) = \{D(x)\}\cup \{x \neq d_j\mid j\in \omega\}$ is actually complete, and (2) $p$ is realized in every model of $T$. If we can show (1) and (2), we're done, since $p$ is not isolated (by compactness).

So let $N\models T$ be any model. We will show that $N$ realizes $p$ and any two realizations are conjugate by an automorphism of $N$ (when $N$ is sufficiently saturated, this shows that $p$ can't have multiple completions). Thanks to the constants, $C$ is uncountable, and $T$ says $F$ is nonempty and every element of $f$ encodes a bijection $C\to D$, so $D$ is uncountable, so it contains a realization of $p$. Let $d$ and $d'$ be distinct realizations of $p$ in $N$, let $\sigma$ be the permutation of $D$ swapping $d$ and $d'$, and define $\tau\colon N\to N$ so that $\tau$ acts as the identity on $C$, $\tau$ acts as $\sigma$ on $D$, and $\tau$ acts on $F$ by sending $f$ to $\sigma\circ f$. Then $\tau$ is an automorphism of $N$.


This is an example from Chang and Keisler's "Model Theory". Let $L$ be the language consisting of constant symbols $\{c_\alpha : \alpha < \aleph_1\} \cup \{d_n : n < \omega\}$, let $T = \{c_\alpha \neq c_\beta : \alpha \neq \beta\}$ let $p(x) = \{x \neq d_n : n < \omega\}$. Then $p$ is not isolated. However any model of $T$ is uncountable and therefore has a realisation of $p$.

Tags:

Model Theory