more ignorant logic speculation
Oct. 19th, 2004 08:54 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
guslSo, I've been thinking, how significan't should Gödel's Incompleteness be anyway? It seems those example sentences are always pretty contrived, whereas I only really care about "concrete" statements.
Give me an example of a concrete-looking undecidable statement in number theory.
Should we replace the ideal of static axiomatization with a dynamic one? Can there be an algorithmic way of picking new axioms? Would this create a logic on its own, which also suffers from Gödel's Incompleteness?
Chaitin views Gödel's incompleteness as an information-theoretic necessity.
Does the undecidability of FOL imply that there are no bounds on proof size?
Give me an example of a concrete-looking undecidable statement in number theory.
Should we replace the ideal of static axiomatization with a dynamic one? Can there be an algorithmic way of picking new axioms? Would this create a logic on its own, which also suffers from Gödel's Incompleteness?
Chaitin views Gödel's incompleteness as an information-theoretic necessity.
Does the undecidability of FOL imply that there are no bounds on proof size?
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
(no subject)
Date: 2004-10-20 10:53 pm (UTC)(no subject)
Date: 2004-10-22 12:23 am (UTC)But in any case, I consider some existential statements, for example, the Goldbach conjecture as concrete enough: if there exists a counterexample, then a finite number theoretical fact holds. If there exists no counterexample, then the conjecture is true.
Whereas the existence of a set of intermediate cardinality sounds very abstract, and it's not the kind of result I would demand out of a theory arithmetic.
I feel like we should find a complete axiomatization for all statements like the Goldbach conjecture. Yet, I know it's likely that this is impossible.
(no subject)
Date: 2004-10-22 09:37 am (UTC)So Hilbert dreamed that you could prove anything, even if it had to do with the infinite, even if it had a "there exists" that could only be verified by checking an infinite number of cases, by a finite proof.
If arithmetic could be proved to be consistent and complete, any proposition could be proved or its converse could be proved in a finite number of steps, and the infinite would not be needed.
That's what Godel demolished and that's why I think what he did is important.
"Statements like the Goldbach conjecture"-->what do you mean precisely? Simple statements? Statements shorter than a certain length in symbols?
(no subject)
Date: 2004-10-23 01:34 am (UTC)I consider Goldbach concrete because there either there exists a counterexample or there doesn't (even though there are an infinite number of cases), and if it does it's simple to check it. In other words, either it is true or it isn't, independent of which foundational system you choose. And I would expect any foundational system to decide all statements like this.
Statements like CH, though, talk about much more abstract objects, whose "existence" I consider doubtful, for example the set of the so-called "real" numbers.
By "existence", I don't mean actual existence, but rather "concreteness". My definitions are circular, since my ideas on this are still philosophical.
I guess what I want to find is a "decidable fragment" of arithmetic, which would include concrete things like Goldbach, but not necessarily things like CH.
Do you see what I'm getting at?
(no subject)
Date: 2004-10-23 10:40 am (UTC)(no subject)
Date: 2004-10-23 11:31 am (UTC)My hope is that there exists a decidable arithmetic which can express statements of the form of the Goldbach Conjecture.
(no subject)
Date: 2004-10-23 11:32 am (UTC)(no subject)
Date: 2004-10-24 12:58 am (UTC)