Question 6.12: Let (N,<) be the model with universe N and the “less than...
Let (N,<) be the model with universe N and the “less than” relation. Show that Th(N,<) is decidable.
Reduce Th(N,<) to Th(N,+), which we’ve already shown to be decidable. Show how to convert a sentence \phi _{1} over the language of (N,<) to a sentence \phi _{2} over
the language of (N,+) while preserving truth or falsity in the respective models.
Replace every occurrence of i < j in \phi _{1} with the formula ∃k [(i+k=j)∧(k+k≠k)] in \phi _{2} , where k is a different new variable each time.
Sentence \phi _{2} is equivalent to \phi _{1} because “i is less than j” means that we can add a nonzero value to i and obtain j. Putting \phi _{2} into prenex-normal form, as required by the algorithm for deciding Th(N,+), requires a bit of additional work.
The new existential quantifiers are brought to the front of the sentence.
To do so, these quantifiers must pass through Boolean operations that appear in the sentence.
Quantifiers can be brought through the operations of ∧ and ∨ without
change. Passing through ¬ changes ∃ to ∀ and vice versa. Thus, ¬∃k becomes the equivalent expression ∀k ¬ψ , and ¬∀kψ becomes ∃k ¬ψ .