5 ms·
This is an exceptionally good explanation of Gödel's incompleteness theorem for the general reader.
by Bud 6y ago
This is an exceptionally good explanation of Gödel's incompleteness theorem for the general reader.
- stopachka 6y agoThank you, glad you liked it :)
- drran 6y agoWell, I disliked it. I see proof that every valid formula can be converted into a Godel number. However, every invalid formula can also be converted into a Godel number. So, if we are able to construct a number, then it proves what?
- arc0 6y agoThe conversion of formulae to Gödel numbers is basically an implementation detail, the fact it can be done allows us to define theorems on the natural numbers that describe properties of the logical system. Encoding an invalid formula is of course possible, but I don't see why that would be a problem, it doesn't inherently 'prove' anything.
- drran 6y agoFor me, it looks like use a program in C to generate a C code, and then prove that a C program can generate an invalid C code, so the C compiler must be invalid. Compilation step is missed. Compiler will refuse to compile the invalid code. IMHO, the same situation is for Godel numbers. We can use math to generate numbers, which are equivalent to formulas, BUT why these formulas must be accepted? Initial set of axioms was carefully chosen by human, so it not an open set, where anybody can add anything.
- arc0 6y agoGödel's proof does not apply to any single axiomatic system, it applies to any computable set of axioms that can talk about numbers, quantifiers, addition and multiplication. This isn't arbitrary, it's a set of properties required for just about any interesting mathematics to take place. The formulae are accepted because Gödel gives us a mapping, he proves that we can convert any formula into a number without losing information.
- drran 6y agoOk, we converted formulas into unique numbers. Now, we can range these numbers, then we can remap these numbers back to natural numbers: 1 is first formula, 2 is second formula, and so on. We can produce these numbers with just «next» operator. However, some formulas are incorrect, so we filter out them and then remap remaining functions again: 1 is first correct formula, 2 is second correct formula, and so on. Now, we can produce correct formulas with just «next» operator. However, some formulas can contradict our system of rules, so we filter out them, and remap remaining functions again: 1 is the first correct formula which doesn't contradict the system of rules, and so on. Let's call them "Lisivka's numbers". So, Godel's numbers can contradict axiomatic system, while Lisivka's numbers cannot. Do you see the problem?
- stopachka 6y agoThe point of Godel’s idea, is that he proved “ Lisivka's numbers", has a formula that can’t be proven. Try going through the essay, and point out where the “incorrect” numbers were formed. You may be surprised to find that all statements were “correct” in the definition you are thinking of. The mathematical term is “primitive recursive” and “well-formed”
- drran 6y agoYou missed the point. Any "bad" Godel's number can be interpreted as "good" Lisivka's number. We have ambiguity here, because a number can refer to any formula in infinite number of sets. > We can go further. We can even construct PM-Lisp formulas in PM-Lisp! No, we cannot.
- ProfHewitt 6y agoThe Gödel number a proposition in Russell's Principia Mathematica does not correctly represent the proposition because it leaves out the order of the proposition.
- ProfHewitt 6y agoHi Bud! What is actually needed is a correct exposition (such as https://papers.ssrn.com/abstract=3603021 https://papers.ssrn.com/abstract=3603021) of how inferential incompleteness of Russell's Principia Mathematica follows from the computational undecidability of the Halting Problem. Prior to https://papers.ssrn.com/abstract=3603021, attempts to proof inferential incompleteness were *incorrect* for foundational theories because of the incorrect assumption that theorems of a foundational theory can be computationally enumerated.