4 ms·
Quoting from the article: "The young Austrian mathematician Kurt Gödel tackled the problem and found that Hilbert’s expectations where [sic] fulfil
by triska 5y ago
Quoting from the article:
"The young Austrian mathematician Kurt Gödel tackled the problem and found that Hilbert’s expectations where [sic] fulfilled for first-order logic."
This (i.e., "Hilbert's expectations were fulfilled for first-order logic") is a common misconception, but it is not the case. For instance, ZFC is an example of a first-order theory that does not satisfy Hilbert's expectations mentioned in the article (consistency, completeness and decidability). Notably, if ZFC is consistent, then it is incomplete. Another example of a first-order theory that is essentially incomplete and not decidable is Robinson arithmetic:
https://en.wikipedia.org/wiki/Robinson_arithmetic https://en.wikipedia.org/wiki/Robinson_arithmetic
The confusion likely stems from the fact that Gödel proved first-order logic to be semantically complete (Gödel's completeness theorem), i.e., all its valid formulae can be derived as theorems. This does not mean that all first-order theories are syntactically complete, i.e, for every statement S, either S or its negation ¬S is in the theory. This kind of incompleteness is what Gödel's incompleteness results are about, and this phenomenon already arises in first-order logic. The common independence results of ZFC are well-known examples of this kind of incompleteness: ZFC, if consistent, does not prove them, and also does not prove their negation. Gödel's first incompleteness theorem shows that every sufficiently powerful formal system exhibits this kind of incompleteness. Also first-order theories exhibit it if they are sufficiently powerful.
With today's terminology and models of computation, it is easy to show this, because first-order logic is sufficient to express a Turing machine as a theory, and if we let S be the (first-order) statement "The machine reaches a halting state", then, if we had a mechanism that always terminates and always correctly decides whether S or its negation ¬S is in the theory, then we would have an algorithm that solves the halting problem, which, however, is easily shown to be only semi-decidable, not decidable. Hence, not all first-order theories are consistent, complete and decidable.
- bsaul 5y agoNot a logician, but it’s the first time i’ve heard Gödel incompleteness being about trying to say something about syntactically invalid formulas.. Do you have more pointers on that ? it makes me curious.
- laszlokorte 5y ago„Valid“ does not mean syntactically valid but „true in any case“
- triska 5y agoEvery statement S has a negation ¬S, read as "not S". If S is well-formed, so is its negation. For example, if we take the continuum hypothesis, i.e.: "There is no set whose cardinality is strictly between that of the integers and the real numbers." and construct S to express this statement in the language of our theory (say ZFC), then the negated statement ¬S would correspond to: "There is a set whose cardinality is strictly between that of the integers and the real numbers." Famously, the continuum hypothesis is independent of ZFC. This means that (assuming consistency of ZFC), ZFC does not prove S, and also does not prove ¬S. From a consistent and syntactically complete theory, we expect that it contains exactly one of these statements. Is it the case or not? The fact that ZFC does not "tell" us which it is means that it is incomplete in this sense. Clearly, a question that is important to us is left unanswered by this theory, since neither the statement nor its negation is provable with the given axioms. A syntactically complete theory is also called deductively complete, or negation complete. An example of a first-order theory that is consistent, complete, and also decidable is Presburger arithmetic: https://en.wikipedia.org/wiki/Presburger_arithmetic https://en.wikipedia.org/wiki/Presburger_arithmetic Every question you have about its sentences will be answered by the theory one way or the other by either proving the statement or its negation.
- ProfHewitt 5y agoThe Continuum Hypothesis is still an open question in foundational mathematical theories that are more powerful than 1st-order ZFC such as the theory Ordinals. See the following: https://papers.ssrn.com/abstract=3457802 https://papers.ssrn.com/abstract=3457802 Someday, the Continuum Hypothesis might be proved or it might be disproved in foundational theories.
- contingencies 5y agohttps://en.wikipedia.org/wiki/When_a_White_Horse_is_Not_a_Horse https://en.wikipedia.org/wiki/When_a_White_Horse_is_Not_a_Ho...
- lr1970 5y agoTo clarify, abbreviation ZFC stays for Zermelo–Fraenkel set theory with the Axiom of Choice included [0]. [0] https://en.wikipedia.org/wiki/Zermelo–Fraenkel_set_theory https://en.wikipedia.org/wiki/Zermelo–Fraenkel_set_theory
- ProfHewitt 5y agoContrary to the article discussed in these postings, having true but unprovable propositions in foundational theories of mathematics does not place any practical limitations on scientific knowledge.