Consider a language $L$ with $<0,1,S>$, where $S$ is the successor function.

Show that there are only $\aleph_0$ many countable models of Th$(\mathbb{N})$, under $L$.

This is one of the practice question in the book by Richard Kaye, Models of peano arithmetics.

Chapter 1, question 1.3.

I'm honestly quite stuck and do not know how to begin.

Any help or insight is deeply appreciated.


  • 1
    $\begingroup$ Think of the models as directed graphs, with vertices the elements of the model, and arcs $i\to Si$. Maybe scribble some pictures of possible models. Can a vertex have more than one arc going into it? $\endgroup$ – Dap Oct 3 '17 at 11:25
  • $\begingroup$ Some other questions to consider: can a vertex have no arc going out of it? How many vertices can have no arcs going into them? $\endgroup$ – Noah Schweber Oct 3 '17 at 19:06
  • 2
    $\begingroup$ If the graph thinking suggested above doesn't help, I think of models of $\mathrm{Th}$ as looking like $\Bbb{N} \ldots \Bbb{Z} \ldots \Bbb{Z} \ldots$. I.e., a copy of the natural numbers followed by lots of copies of the integers. $\mathrm{Th}(\Bbb{N})$ gives you all the properties of $0, 1$ and $S$ that imply a model must look like that ($S$ is one-to-one; only $0$ has no predecessor; any element that is not in $\Bbb{N}$ has a unique predecessor). If such a thing is countable there are only countably many copies of $\Bbb{Z}$ hence there are only countably many possibilities. $\endgroup$ – Rob Arthan Oct 3 '17 at 20:11

Your Answer

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

Browse other questions tagged or ask your own question.