Came across this problem today in Marker's Model Theory: An Introduction (problem 3.4.3)

(a) Show that the theory of $(\mathbb Z,s)$ has quantifier elimination where $s(x) = x+1.$ Show that the theory is strongly minimal and that $\operatorname{acl}(A)$ is the set of elements "reachable" from $A.$

(b) Show that the theory of $(\mathbb N,s)$ does not have quantifier elimination.

I quote the problem in full mostly for reasons of context. I understand how to do every part except the last part about "reachable" elements. For reference, the definition of acl is:

Let $\mathcal M$ be an $\mathcal L$-structure and $A\subseteq M.$ Then $b\in \operatorname{acl}(A)$ if there is an $\mathcal L$-formula $\phi(v,\bar w)$ and $\bar a\in A$ such that $\mathcal M \models \phi(b,\bar a)$ and $\{y\in M:\mathcal M\models \phi(y,\bar a)\}$ is finite.

First off, there is no definition I can find of the term "reachable from $A$" in the book, although I suppose it probably means reachable via finite number applications of the successor function on some element of $A$ (i.e. not less than all the elements).

However, I don't see why it isn't the case that $\operatorname{acl}(A) = \mathbb Z$ for any nonempty $A.$ For instance if $A=\{10\}$ then $25 \in\operatorname{acl}(A)$ by the formula $x = s^{15}(10).$ And on the other side, $-120\in \operatorname{acl}(A)$ by the formula $s^{130}(x) = 10.$ Similarly for any integer and any nonempty set $A$ (we just pick some number in it and do what we did with $10$.)

What am I missing here? This part of the exercise is referenced again later on pg 208, so I'm less inclined to think it's an oversight than I otherwise would be.


1 Answer 1


Your definition of "reachable" is almost right, but you also want to allow taking predecessors.

Now on to the main point. You're right that algebraic closure in $\mathbb{Z}$ is boring - but the situation is more interesting with respect to arbitrary models of the theory. A model of the theory is really a bunch of disjoint copies of $(\mathbb{Z}, s)$. An element of one copy can reach all the other elements of that copy, but not any elements of other copies.

At this point, in the context of the exercise, it's a good reality check to see why this doesn't contradict the minimality of the theory. Take the model $M$ consisting of two copies of $(\mathbb{Z}, s)$ and fix some $a$ in one of the copies. Then $acl(\{a\})$ is bi-infinite. However, this isn't a problem, since $acl(\{a\})$ isn't definable but rather a union of definable sets, each of which is finite.


You must log in to answer this question.

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