Re: An example of a complete but undecidable theory
From: Herman Rubin (hrubin_at_odds.stat.purdue.edu)
Date: 07/05/04
- Next message: News Subsystem: "Math Tutoring Site"
- Previous message: Heiko Röglin: "conditional density"
- In reply to: Chris Menzel: "Re: An example of a complete but undecidable theory"
- Next in thread: George Greene: "Re: An example of a complete but undecidable theory"
- Messages sorted by: [ date ] [ thread ]
Date: 5 Jul 2004 11:41:53 -0500
In article <slrnceimn0.381.cmenzel@philebus.tamu.edu>,
Chris Menzel <cmenzel@remove-this.tamu.edu> wrote:
>On Mon, 05 Jul 2004 11:37:48 GMT, Humberto Jose Bortolossi
><hjbortol-ufes@pop.com.br> said:
>> I'm looking for an example of a complete but undecidable
>> theory.
>> [By] complete I mean that every sentence in the theory
>> may be proved to be true or to be false.
>This isn't quite right -- I assume you are interested in talking about
>the usual definition of completeness. A theory T is complete if, for
>any sentence A in the language of the theory, either A or ~A is a
>theorem of T, that is, either A or ~A is provable from the axioms of T.
>> By decidable I mean there is an algorithm that (in a finite number of
>> steps) says if every sentence in the theory is true or false.
>Again, this is not the usual definition. A theory T is decidable if
>there is an algorithm for determining, for any sentence A, whether or
>not A is a theorem of T.
I believe this is the case, at least for all theories
for which the proofs can be enumerated.
I seem to recall a theorem of recursive function theory
which does prove this. Suppose we provide a 1-1 mapping
of all sentences in the language of the theory with the
set of positive integers. Then the set of numbers which
correspond to a theorem of T forms a recursively enumerable
set, as the proofs can also be enumerated. Likewise, the
set of numbers which correspond to the negation of a theorem
is a recursively enumerable set. But if a set and its
complement are recursively enumerable, the set is recursive;
this means that there is a algorithm which will decide if a
point is an element.
-- This address is for information only. I do not claim that these views are those of the Statistics Department or of Purdue University. Herman Rubin, Department of Statistics, Purdue University hrubin@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558
- Next message: News Subsystem: "Math Tutoring Site"
- Previous message: Heiko Röglin: "conditional density"
- In reply to: Chris Menzel: "Re: An example of a complete but undecidable theory"
- Next in thread: George Greene: "Re: An example of a complete but undecidable theory"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
