# counterexample to the omitting types in uncountable language

Could anyone remind me of an example of an uncountable non-isolated complete type that cannot be omitted?

• (I see this has two votes to close as "not mathematics." This post is, however, mathematics; the field is model theory, and this question would be answered in a graduate level course in the subject.) – user231101 Sep 18 '17 at 20:46

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$.

• Thank you for providing a natural example that, inexplicably, is missing from all textbooks of model theory. – Primo Petri Sep 20 '17 at 8:25
• Do you really need to note tat that $R(f,-,-) = R(g,-,-)$ implies $f=g$? – Primo Petri Sep 20 '17 at 8:26
• Do you rally need that $T$ contains a sentence asserting that you can swap $d$ and $d'$ in $D$? You could have started with $M'$ right from the beginning and skip this remark. – Primo Petri Sep 20 '17 at 8:26
• "If so, we can conclude by compactness that" should be "By compactness p(x) is not isolated." Your sentence seems to imply that the fact the $p(x)$ is the only other type is relevant for non-isolation. – Primo Petri Sep 20 '17 at 8:30
• @PrimoPetri Thanks for the comments. In order: 1. Yes, I was surprised by how simple the example is. 2. You could probably get away without this, but I use it to make sure that for any $f\in F$ and any swap $\sigma$, there is a unique $f'\in F$ encoding $\sigma\circ f$ when defining the automorphism $\tau$. Otherwise, you might worry that $\tau$ was not surjective. 3. I don't understand this comment. Certainly we need to know that every model of $T'$ satisfies this property, so it bears pointing out that it's a first-order property and is consistent with the other facts we're using about $T$ – Alex Kruckman Sep 20 '17 at 12:34

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$.

• +1, but can you think of an example relative to a complete theory? I'm sure I knew one at some point... – Alex Kruckman Sep 19 '17 at 1:03
• Why is $p$ nonprincipal? (I do not understand Marker's explanation on this...) – Pteromys Sep 19 '17 at 1:13
• @AlexKruckman, Chang and Keisler have a reference, but I haven't checked it out. – Levon Haykazyan Sep 19 '17 at 3:32
• @Pteromys, It is left as an exercise. Hint: if $\phi(x)$ is a formula, then there is $n$ such that $\phi$ does not contain $d_n$. – Levon Haykazyan Sep 19 '17 at 3:34
• I have edited the question and made explicit the requirement "complete". – Primo Petri Sep 19 '17 at 7:46