Is a Complete System Necessarily Decidable?

[EvLer]

I don't have a clear idea of distinction between the two, to me the latter seems to be restatement of the former with added "procedure".

completeness: every statement in the system can be either proved or disproved in the system;

decidability: iff there exists an algorithm such that for every well-formed formula in that system there exists a maximum finite number N of steps such that the algorithm is capable of deciding in less than or equal to N algorithmic steps whether the formula is (semantically) valid or not valid;

So a system can be complete and undecidable, right? If system is incomplete, does that necessarily mean that it is also undecidable?
Could someone explain on a simple example?

Thanks in advance.

 

[gravenewworld]

Completeness: A set of sentences R is complete if every sentence A or ~A is a consequence of R.

Decidable: A set of sentences R is decidable if the set of sentences of its language that are consequences of R is recursive.

So a system can be complete and undecidable, right?

If T is an axiomatizable theory then no. If T is complete, it must be decidable.

 

[Hurkyl]

Your definition of decidability is odd, so I suspect some of your confusion may relate to that. All that stuff about "a maximum finite number N of steps" just means that the algorithm terminates. In other words, it either accepts or rejects every input.

I don't have a clear idea of distinction between the two, to me the latter seems to be restatement of the former with added "procedure".

That's somewhat correct...

Completeness means that either a proof or disproof exists.
Decidability means that there's an algorithm for finding a proof or disproof.


In nice cases, they are equivalent, since in a complete theory, you can just iterate over every possible proof until you find one that either proves or disproves the statement.

I'll pause here. That should give you a hint as to how a complete, but not decidable, theory should look, so I want to give you a chance to find it (or at least the basic idea).

 

[Hurkyl]

*frown*

I don't think my definition of "decidable" is equivalent to gravenworld's definition. I'll have to ponder this for a while.

 

[gravenewworld]

*frown*

I don't think my definition of "decidable" is equivalent to gravenworld's definition. I'll have to ponder this for a while.

What I wrote means the same thing as what you did. A set of sentences R is decidable if the set of sentences of its language that are consequences of R are proved by R.

 

[EvLer]

thank you both for the clarification

So a system can be complete and undecidable, right?

If T is an axiomatizable theory then no. If T is complete, it must be decidable.

the reason I said that is because, first order logic is complete, since there are models in it, but my book says that it is not decidable in a sense that if you run some sentence through a semantic tableax, it may not necessarily reach a closure. Does it mean it is just not axiomatizable then?

 

[neurocomp2003]

it means you can't tell when the algorithm/execution will terminate

 

[master_coda]

thank you both for the clarification


the reason I said that is because, first order logic is complete, since there are models in it, but my book says that it is not decidable in a sense that if you run some sentence through a semantic tableax, it may not necessarily reach a closure. Does it mean it is just not axiomatizable then?

First order logic is complete, but for a different definition of complete than the one referred to above.

The completeness of first order logic refers to the fact that:
- if I have a set of axioms
- and I have a sentance that is true in every model of those axioms
- then there exists a proof of that sentance from the axioms
so long as the sentances are all expressed using first order logic.

 

[EvLer]

it means you can't tell when the algorithm/execution will terminate

or that it will terminate at all, so there's no way to know whether it is a theorem or not, i.e. it may never terminate with either positive or negative result, in case if that set of sentences is undecidable.

ooops, should have said first order PREDICATE logic... since propositional is both decidable and complete. Semantic tableaux does close for propositional logic.

Thanks for your replies, i think I have a better idea now.

 

[Hurkyl]

What I wrote means the same thing as what you did. A set of sentences R is decidable if the set of sentences of its language that are consequences of R are proved by R.

I'd like to believe that! I'm having trouble making myself happy.

If we're dealing with a finite set of axioms, it's clear, since you can just enumerate the proofs.

If we're dealing with an infinite, but turing decidable^*, set of axioms, it's still clear, because we can still enumerate the proofs.


But what if my set of axioms is not turing decidable?


You can't just use the proof that the turing machine decides the theory, becuase:
(1) The proof might require methods that simply don't exist in the theory
(2) There might not be a proof! Whether the turing machine decides the theory could be independent of ZFC. (or whatever formal world in which you're living)


It's not obvious to me that this can be patched up... and I don't recall any fancy results that could be used to do it, since I don't know what does and does not apply to theories with infinitely many axioms.


*: means the same as "recursive", but I'm much more comfortable with this language

 

[gravenewworld]

Hmmm I'm not sure how to respond to your point. I never studied turing machines. But Church thesis states that a function is effectively computable iff it is recursive. A set of sentences is effectively decidable iff its characteristic function is effectively computable. I think my professor mentioned to me that if a set is effectively decidable it can be computed by a TM. Thus if TM can compute a characteristic function for a set, the characteristic function is recursive, i.e. the set of sentences is recursive and decidable. If a TM can't compute a set of sentences, then the set of sentences isn't recursive. (I may be wrong about what I vaguely recall about TMs though.)

 

[neurocomp2003]

how did you manage to study church thesis before turing machines? I thought any algorithm can be put on a turing machine...whether it be single tape or multitape.
isn't that why its related(can't remember if its called it) to the "universal machine"(been awhile...forgot that name too).

 

[gravenewworld]

I did an independent study on Mathematical logic. I never studied logic before, but I definitely wanted to learn enough machinery so I could go through and understand the proofs to Godel's incompleteness theorems. There simply wasn't enough time to learn about TMs an other topics in logic. Needless to say, after a lot of blood, sweat, and tears I got through Godel's theorems.

 

[Hurkyl]

My text says "Turing decidable" is synonymous with "Recursive", and "Turing recognizable" is synonymous with "Recursively enumerable", if that helps.

 

[EvLer]

Ummm...
I have a follow-up question.

According to Godel's theorem (i think it's 2nd one): within a sufficiently strong axiomatic system it is impossible to prove that system to be consistent. So then, if it(system_1) can proved to be consistent from within another system (system_2), does that system (system_2) have to be consistent?

I am not exactly sure how this works, I just read an article that talked about proving consistency of one system using another system. If you have a simple example to demonstrate this, it would be great.

Thanks again!

 

[Hurkyl]

According to Godel's theorem (i think it's 2nd one): within a sufficiently strong axiomatic system it is impossible to prove that system to be consistent.

Not quite: if a system satisfying his conditions is consistent, it cannot prove itself consistent.


As an example of relative consistency, you can use algebra to prove geometry consistent: you can define the words "point", "line", "incident", "between", and "congruent" algebraically, and then prove that these terms satisfy the axioms of Euclidean geometry.

 

[DrMatrix]

Ummm...
I have a follow-up question.

According to Godel's theorem (i think it's 2nd one): within a sufficiently strong axiomatic system it is impossible to prove that system to be consistent. So then, if it(system_1) can proved to be consistent from within another system (system_2), does that system (system_2) have to be consistent?

No. An inconsistent system can prove any statement. If (system_2) is inconsistent it can prove (system_1) is consistent. For what it's worth, if (system_2) is inconsistent, it can also prove (system_1) is inconsistent.