4
$\begingroup$

There are two things I would like to prove.

  1. DLO - Dense linear order is complete, that means that when $\psi$ is a sentence of the language $\{<\}$ then $DLO\vDash\psi$ or $DLO\vDash\neg\psi$
  2. When $S$ is recurisvely enumerable and a complete set of axioms then $M:=\{\phi: S\vDash\phi\}$ is recursiv (i.e decidable=computable)

For 1. I do not have an idea. For 2. I use the fact that $M$ is recursively enumerable. Then I would like to argue (using the Church-Turing thesis) that in the case of complete theories the complement of $M$ is also recursively enumerable. Then I want to use the theorem that a set is recurisv if and only if the set and its complement are recursively enumerable.

$\endgroup$
5
$\begingroup$

DLO is not complete: The intervals $[0,1]$, $(0,1)$, $[0,1)$, and $(0,1]$ are all models of this theory and are not elementarily equivalent. On the other hand, these $4$ theories are the only possibilities:

It is a well-known theorem of Cantor that all countable models of DLO without end-points are isomorphic. This is typically proved using the back-and-forth technique. With this, it follows that if to DLO you add the sentence that says that there are no end-points, then you get a complete theory (using Lowenheim-Skolem, for example. One can think of this as a particular case of the fact that if $T$ is a countable theory that is $\kappa$-categorical for some infinite $\kappa$, and $T$ has no finite models, then $T$ is complete).

You can similarly see that the other three extensions of DLO (adding both endpoints, or only one) are complete. For example, any countable model of DLO+ "There are endpoints" looks like $\bullet+\mathbb Q+\bullet$, so any two countable models are isomorphic.


As for question 2, you have an algorithm for enumerating $S$. Using it, you can easily enumerate all consequences of $S$. The point is that if $\phi$ is provable from $S$, then for some $n$, $\phi$ is provable from the first $n$ axioms of $S$ with a proof that uses at most $n$ steps. Since $S$ is complete, eventually either $\phi$ or $\lnot\phi$ will appear listed this way. So you have a way of deciding whether $\phi$ is provable from $S$ or not (just wait until one of $\phi,\lnot\phi$ appears in your list of consequences). I agree this is a highly inefficient algorithm in practice.

$\endgroup$
  • $\begingroup$ Thanks, what exactly do you mean with the notation $\bullet+\mathbb Q+\bullet$ ? $\endgroup$ – Alexander Jun 11 '13 at 22:02
  • $\begingroup$ The same as "isomorphic to $[0,1]\cap\mathbb Q$". That is: A point, followed by a countable dense linear order without end-points, followed by a point. $\endgroup$ – Andrés E. Caicedo Jun 11 '13 at 22:08
2
$\begingroup$

Dense linear order is not complete. But it is close to complete. The four theories (i) DLO with no first or last element, (ii) DLO with first and no last, (iii) last and no first, (iv) last and first are each complete.

One way to prove it is (say for (i)) is to show that DLO with no first or last $\omega$-categorical, that is, that any two models of cardinality $\omega$ are order-isomorphic. This is a much stronger property than completeness.

The proof goes back to Cantor. The method is usually called the back-and-forth method, and will be easy to track down.

$\endgroup$
  • $\begingroup$ I already proved that any two models from DLO are isomorphic, so I am done now? $\endgroup$ – Alexander Jun 11 '13 at 21:54
  • 1
    $\begingroup$ Yes. For if $\varphi$ is neither provable nor refutable from a theory $T$ (over a countable language) then there are models $M$ and $M'$ in which $\varphi$ is respectively false and true. But our two theories (i) DLO, no first last, plus $\varphi$, (ii) same, but $\lnot\varphi$ and theory have only infinite models. So by Downward Lowenheim Skolem they each have a countable model. But the models are isomorphic, so $\varphi$ must be true in both or false in both, contradiction. $\endgroup$ – André Nicolas Jun 11 '13 at 22:03
1
$\begingroup$

Your general idea for proving (2) seems sound except that I don't see what the Church-Turing thesis has to do with it. You can use the completeness theorem to rewrite $S \models \phi$ to $S \vdash \phi$, and then use that fact that the set of valid proofs is recursively enumerable if the set of axioms is. This gives you that $M$ is recursively enumerable. Since $S$ is complete, $S \models \phi$ or $S \models \lnot\phi$ for every $\phi$ and hence the same argument shows that $M^C$ (i.e. the complement) is recursively enumerable. Then, as you said, it follows that $M$ is recursive.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.