I am a realist-in-truth-value for recursively-enumerable statements

[gusl]

I am a realist-in-truth-value for recursively-enumerable statements. i.e. I believe that statements for which counterexamples could be found if they existed must be either true or false.

For example, the Goldbach conjecture must be either true or false (since if it were false, you could find a number >4 which is not a sum of two primes). Also, whether any Turing Machine halts is a recursively-enumerable problem.

Basically, it seems to me that any meaningful problem is recursively-enumerable.

A consequence of Gödel's Incompleteness:
If a set of axioms expressing PA is recursively-enumerable, there will be statements which are undecidable.

I believe there should be an algorithmic way of deciding all recursively-enumerable statements, i.e. an algorithmic way of proceeding in making mathematics prove more true things whenever you run into undecidabilities (i.e. whenever you correctly prove, using a meta-method, that a sentence G is true but not provable in the original system). But this seems not to be possible, for if there were any such algorithm, we could construct its halting problem, and *that* problem would be undecidable in the new system.

So I do think that Gödel's theorem is significant for the philosophy of mathematics. And it seems like Chaitin is onto something when he says that mathematics must be semi-empirical.


Again, thanks to Benedikt Löwe for reciting me the theorem above.

Comments

[easwaran.livejournal.com]

What about incompleteness phenomena that occur at a higher level, say with two or three alternating quantifiers, rather than just one?

And if you think that mathematics can be extended in rational ways to decide all Pi_1 sentences (as I think you're saying) then why not for higher sentences as well? Clearly, we can't get a recursive algorithm to do any of this, because the Incompleteness theorem always gives us something at the single-quantifier level (I'm pretty sure).

But I think you're right - mathematics must be semi-empirical (at least at the higher levels - I don't know if Harvey Friedman is right that this is true for ordinary practicing non-set theorist mathematicians as well).

[gustavolacerda.livejournal.com]

What about incompleteness phenomena that occur at a higher level, say with two or three alternating quantifiers, rather than just one?

Maybe my terminology is wrong, but when I say that I'm only interested in recursively-enumerable statements, I mean I'm interested in those statements which be either proven or refuted in finitely many computational steps (the rest smells too much like metaphysics). I'm not saying anything about quantifiers.

What's the correct terminology here?

I think that statements like forall x ( exists y, y > x ) are no longer about the real world, but only about our inductive definition of "integer".


What still troubles me is that the search for consistencies is r.e., which makes "T is consistent" a co-r.e. statement, so it doesn't follow that it is provable in T. In fact's Gödel's second incompleteness theorem say that it is not provable in T. I think I am a realist-in-truth-value for co-r.e. statements too, which is troubling.

Do we even know that PA is consistent? Or that PA + Cons(PA) is consistent?

Is it ok to say that "true in PA" is the same as "really true"? Isn't the truth in PA equivalent to truth in PA + Cons(PA) and so forth? i.e. the hierarchy is only about provability?

[gustavolacerda.livejournal.com]

And if you think that mathematics can be extended in rational ways to decide all Pi_1 sentences (as I think you're saying) then why not for higher sentences as well?

So you're asking why my ontology separates Pi_0_1 sentences from higher sentences.

While "PA is consistent" is meaningful to me, I don't know of any higher-than-Pi_0_1 sentences which are.