0

I don't understand how a theory can be undecidable (there is no effective procedure for determining if a sentence of the language is a theorem) and also be complete. How do we know all sentences are provable when we don't have a procedure to determine if they are?

1
  • you are first making a false assumption. All languages do not have sentences. Sanskrit, for example, has 'stops', and where a stop is can alter the meaning of the idea or ideas. There are other languages without sentences. Commented Oct 7, 2019 at 5:39

1 Answer 1

2

Consider the following example: "Let x=0 if the Goldbach conjecture is true and let x=1 if the Goldbach conjecture is false." We know that x is either 0 or 1, but we don't know which (yet!).


That's exactly what's going on here. Given a structure S, let Th(S) be the set of sentences true in S. For each sentence p, either p is true in S and hence Th(S)-provable or p is false in S and hence Th(S)-disprovable (since ~p is in Th(S)). We've concluded this without knowing anything about the particulars of the structure S: any structure whatsoever is guaranteed to give rise to a complete theory. Note that in particular this tells us nothing about the complexity of Th(S), and indeed there are "perfectly concrete" structures whose theories we know to be undecidable - the standard example being the natural numbers (with addition and multiplication), as a consequence of Godel's incompleteness theorem.

  • Incidentally, this is the only way complete (consistent) theories arise at all: if T is a complete theory and S is a structure satisfying T then by completeness of T we have T=Th(S) - or rather, the deductive closure of T is equal to Th(S), if you use the weaker notion of "complete" here.

Now you might object that some epistemological violence is being done to the word "know" here; that's a reasonable response, and leads to the idea of intuitionistic logic. But in the classical situation, everything above is perfectly valid - if a bit weird.

2
  • Ah, I guess my confusion came from thinking one has to know whether P is true or not for the theory to be complete.
    – csp2018
    Commented Oct 6, 2019 at 23:36
  • 1
    @csp2018 Nope! The theory has to know, but we might not. (To hopefully make this all less slippery, note that there are many "levels" of undecidability, and once we know something is undecidable we don't have to throw up our hands but in fact have a bunch of new interesting questions. So I'd say that this isn't actually a cheap trick.) Commented Oct 6, 2019 at 23:38

You must log in to answer this question.

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