Re: Recursivity vs. Provability

Charlie-Boo <chvol@xxxxxxx> wrote:
>Assume that the set of provable statements is recursively enumerable.
>For any given statement, whether it is provable or not is the same as
>whether it is in this r.e. set.
>Now what does that tell us about the statements that we can prove?

Not much about individual statements, but the set is r.e.

>For example, does it imply that there must be a statement that is not
>provable and whose negation is also not provable?

Not necessarily.

>Or a statement that is not provable and which is true?

True where? The set of sentences true in all algebraically closed
fields is a recursive set. The set of sentences true in arithmetic
is *not* an r.e. set. So these two situations are *very* different.

--Herb Enderton


.

Relevant Pages

  • Re: Goedel incompl. theorems
    ... Enderton considers his first-order arithmetic theory, A_E, which ... deduction relation, and get to a fixed-point result. ... sentences true in all models of this 2nd-order arithmetic that are not ... because its axioms aren't recursive or even r.e. ...
    (sci.logic)
  • Re: An example of a complete but undecidable theory
    ... set of sentences true in ... Not under standard definitions of these words. ... axiomatization. ... --Herb Enderton ...
    (sci.logic)