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

  • 6
    $\begingroup$ (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.) $\endgroup$ – 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$.

| cite | improve this answer | |
  • $\begingroup$ Thank you for providing a natural example that, inexplicably, is missing from all textbooks of model theory. $\endgroup$ – Primo Petri Sep 20 '17 at 8:25
  • $\begingroup$ Do you really need to note tat that $R(f,-,-) = R(g,-,-)$ implies $f=g$? $\endgroup$ – Primo Petri Sep 20 '17 at 8:26
  • $\begingroup$ 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. $\endgroup$ – Primo Petri Sep 20 '17 at 8:26
  • $\begingroup$ "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. $\endgroup$ – Primo Petri Sep 20 '17 at 8:30
  • $\begingroup$ @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$ $\endgroup$ – 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$.

| cite | improve this answer | |
  • $\begingroup$ +1, but can you think of an example relative to a complete theory? I'm sure I knew one at some point... $\endgroup$ – Alex Kruckman Sep 19 '17 at 1:03
  • $\begingroup$ Why is $p$ nonprincipal? (I do not understand Marker's explanation on this...) $\endgroup$ – Pteromys Sep 19 '17 at 1:13
  • 1
    $\begingroup$ @AlexKruckman, Chang and Keisler have a reference, but I haven't checked it out. $\endgroup$ – Levon Haykazyan Sep 19 '17 at 3:32
  • $\begingroup$ @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$. $\endgroup$ – Levon Haykazyan Sep 19 '17 at 3:34
  • $\begingroup$ I have edited the question and made explicit the requirement "complete". $\endgroup$ – Primo Petri Sep 19 '17 at 7:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.