# Existence of a prime model for a theory

Consider the language $$\mathcal{L} = \{P, f\}$$ with $$P$$ a unary predicate and $$f$$ a unary function. Let $$T$$ be the theory:

1. $$f$$ is a bijection
2. $$\forall x \, f^nx \neq x$$ for all $$n$$
3. $$\forall x \, (Px \to Pfx)$$
4. there are infinitely many elements not satisfying $$P$$ whose $$f$$-image does satisfy $$P$$.

• Show that $$T$$ has a prime model.
• Determine all complete 1-types and indicate which of these are isolated.

I am stuck on this exercise. In general I don't know how to approach an exercise like this.

With regard to the existence of a prime model, I can only think to show that $$T$$ is complete and its isolated types are dense. This in turn "reduces" to showing that $$T$$ has at most countably many types.

• First steps first: Do you understand what the models of this theory look like? Given that, do you have a conjecture which model is prime? Commented Jun 17, 2019 at 16:34
• Also, be careful: if $T$ has at most countably many types, then $T$ has a prime model. But the converse isn't true. For example, $\text{Th}(\mathbb{R};0,1,+,\times)$ has continuum-many types over the empty set, but it has a prime model. Commented Jun 17, 2019 at 16:37
• @AlexKruckman I really like your Socratic approach. I've spent several hours on this problem, but your question gave me an idea very quickly. Maybe this works: it is not hard to see that every model of $T$ contains (up to isomorphism) $\{\dots, -2, -1, 0, 1, 2, \dots\} \times \omega$. Here we consider $\{k\} \times \omega$ as the elements $x$ such that $P f^k x$ is true but $P f^{k-1} x$ is false. Furthermore, this is a countable model of $T$, and the candidate for being prime because it embeds in every other model. Commented Jun 17, 2019 at 19:49
• Call this model $M$. What is left is to show that all types of $M$ are isolated (i.e. $M$ is atomic). But without quantifier elimination I do not understand how to analyze the types. Commented Jun 17, 2019 at 19:52
• Good! So what remains is to prove quantifier elimination. If you don't want to do this, here's an alternative: For each tuple from $M$, identify a formula that you think should isolate its type. You can then prove that this formula isolates the type by showing that any two tuples which both satisfy the formula are conjugate by an automorphism (and hence realize the same type). Commented Jun 17, 2019 at 20:02

Your solution via QE outlined in the comments is essentially correct, except for the hitch that $$T$$ doesn't quite have QE in the given language: for example, the formula $$\exists y\, (P(y)\land f(y) = x)$$ isn't equivalent to a quantifier-free formula. The problem here is that $$f^{-1}$$ isn't in the language. This leads to a hole in your argument, since if $$m$$ is an element such that $$M\models P(m)$$ but $$M\not\models P(f^{-1}(m))$$, we could map $$m$$ by a local isomorphism to any element $$n$$ such that $$N\models P(n)$$, including one where $$N\models P(f^{-1}(n))$$ and $$N\not\models P(f^{-2}(n))$$ (since $$f^{-1}(m)$$ is not in the substructure of $$M$$ generated by $$m$$).

But we can fix this by a definitional expansion. Let $$\mathcal{L}' = \{P,f,g\}$$, and let $$T' = T\cup \{\forall x \forall y\, (g(x) = y \leftrightarrow f(y) = x)\}.$$ We say that $$T'$$ is a definitional expansion of $$T$$, because it is obtained by adding new symbols to the language (in this case just $$g$$) and new axioms explicitly defining these new symbols in terms of formulas in the original language.

In case you are not familiar with the concept of definitional expansion: It follows that every model $$M$$ of $$T$$ expands in a unique way to a model $$M'$$ of $$T'$$, every $$\mathcal{L'}$$-formula $$\varphi'(x)$$ has a corresponding $$\mathcal{L}$$-formula $$\varphi(x)$$ (obtained by replacing instances of the new symbols by their definitions in terms of the old symbols) such that $$M'\models \varphi'(a)$$ if and only if $$M\models \varphi(a)$$, and $$f\colon M\to N$$ is an $$\mathcal{L}$$-elementary embedding if and only if $$f\colon M'\to N'$$ is an $$\mathcal{L}'$$-elementary embedding. So the definitional expansion does not change the answers to your questions: $$M$$ is a prime model of $$T$$ if and only if $$M'$$ is a prime model of $$T'$$, restriction to formulas in $$\mathcal{L}$$ is a bijection from types relative to $$T'$$ to types relative to $$T$$, and a type relative to $$T'$$ is isolated (by $$\varphi'(x)$$) if and only if its restriction to $$\mathcal{L}$$ is isolated (by $$\varphi(x)$$).

Now you can prove that $$T'$$ has QE (as you outlined in the comments), use this to answer your questions, and then conclude by taking the reduct to $$\mathcal{L}$$.

• So then the quantifier free formulas using $m$ can be completely determined by knowing 1) if $m$ is inside the hierarchy; 2) if $P m$; 3) if not $P m$, the position of $m$ in the hierarchy, that is one of $1, 2, 3, \dots$. But I fail to see where my argument fails when considering these different descriptive powers of the quantifier free formulas; although I agree that $\exists y \, (Py \land f(y) = x)$ is not equivalent to a quantifier free formula. Commented Jun 18, 2019 at 18:24
• What do you mean with "since $f^{-1}(m)$ is not in the substructure of $M$ generated by $m$"? Commented Jun 18, 2019 at 18:28
• Ok, so I think of the "heirarchy" as a copy of $\mathbb{Z}$: $\{\dots,-1,0,1,\dots\}$, where $f$ acts as the successor function and $P$ is true of the non-negative integers. The map sending $1\mapsto 0$ extends to the substructure $\{1,2,3,\dots\}$ generated by $1$, by $n\mapsto (n-1)$. This is a local isomorphism, since all of these elements and their images satisfy $P$. But now let's say we want to extend the domain of this local isomorphism to include $0$. We would be forced to map $0\mapsto -1$, but we can't do this, since $P(0)$ is true while $P(-1)$ is false. So we can't extend. Commented Jun 18, 2019 at 18:38
• I am not quite sure what you are saying (I'm sorry; however your help is amazing!). But between the lines this is what I understand: take the $\omega$-saturated model $\mathbb{Z} \times \omega$, which has countably many elements in each level of the hierarchy. Let $\tilde{1} \in \{1\} \times \omega$ and $\tilde{0} \in \{0\} \times \omega$ such that $f(\tilde{0}) = \tilde{1}$, and define the local isomorphism $g(\tilde{1}) = \tilde{0}$. Now $g$ cannot be extended to $\tilde{0}$; otherwise $P g(\tilde{0})$ while $f(g(\tilde{0})) = g(\tilde{1}) = \tilde{0}$, contradicting the hierarchy. Commented Jun 18, 2019 at 21:15
• Yes, they are equivalent. And yes, your example makes sense. Commented Jun 19, 2019 at 16:23