![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
guslI 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.
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.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
(no subject)
Date: 2005-04-15 08:33 am (UTC)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?