"Consider the structure $\mathcal{N} = (\mathbb{N}, \leq)$: the natural numbers with the usual ordering (without $0$). Let $\Sigma$ be the set of sentences stating that $\leq$ is a discrete total (i.e., linear) order with an initial point but without a final point. Prove that for every sentence $\varphi$ we have: $\Sigma \vdash \varphi$ or $\Sigma \vdash \neg \varphi$."

Here's what I have so far: I think the set of sentences in $\Sigma$ are:

  • Transitive, reflexive, antisymmetric axioms
  • Linearity (i.e., $\forall x \forall y: x \leq y \vee y \leq x$)
  • There is a smallest element (i.e., $\exists x \forall y: x \leq y$)

My guess is to use Gödel's Completeness Theorem (that is, $\Sigma \vdash \varphi \iff \Sigma \models \varphi$), so we instead have to prove that $\Sigma \models \varphi$ or $\Sigma \models \neg \varphi$. But I'm not sure where to proceed from there.

Thanks in advance for any help!

  • $\begingroup$ Is "discrete total order" not defined in the book the problem is from? I wonder why we are asked to "consider" the structure $\mathcal N,$ which is not mentioned again in the question? I don't know but I'm going to guess that $\Sigma$ is supposed to be the theory of the structure $\mathcal N.$ Besides the axioms you listed, you need one saying that there is no greatest element ("without a final point"). And I guess "discrete" means that every element which is not the smallest has an immediate predecessor, and every element has an immediate successor. $\endgroup$ – bof Nov 2 '17 at 6:17
  • 1
    $\begingroup$ How would prove it would depend on what you already know, what tools you have available. Do you know what it means for two structures to be elementarily equivalent? Do you have some technique for proving that two structures are elementarily equivalent? If so, one way to prove that $\Sigma$ is complete would be to show that all models of $\Sigma$ are elementarily equivalent, by showing that every model of $\Sigma$ is elementarily equivalent to $\mathcal N.$ $\endgroup$ – bof Nov 2 '17 at 6:20
  • $\begingroup$ The question was directly quoted from a past exam. Unfortunately, I couldn't find a definition for "discrete total order" anywhere, but to my knowledge your guess is correct $\endgroup$ – Adrian Lee Nov 3 '17 at 1:07
  • $\begingroup$ I do know what elementary equivalence is. Your comment gave me an idea - can we use Ehrenfeucht-Fraisse games to prove elementary equivalence? $\endgroup$ – Adrian Lee Nov 3 '17 at 1:11
  • 1
    $\begingroup$ Personally, I'd try using Ehrenfeucht–Fraisse games. Elimination of quantifiers may also be a good method. $\endgroup$ – bof Nov 3 '17 at 2:53

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.