News for hackers. Stuff that matters.
Re:Poincaré, Heisenberg, Gödel and the limits of scientific ... by triska on Sunday October 10, 2021 @05:26AM (#28817033)
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

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.

Re:Poincaré, Heisenberg, Gödel and the limits of scientific ... by bsaul on Sunday October 10, 2021 @06:05AM (#28817200)
Not 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.
Re:Poincaré, Heisenberg, Gödel and the limits of scientific ... by triska on Sunday October 10, 2021 @06:27AM (#28817286)
Every 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

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.

Re:Poincaré, Heisenberg, Gödel and the limits of scientific ... by ProfHewitt on Monday October 11, 2021 @09:29AM (#28828087)
The 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

Someday, the Continuum Hypothesis might be proved or it

might be disproved in foundational theories.

Re:Poincaré, Heisenberg, Gödel and the limits of scientific ... by laszlokorte on Sunday October 10, 2021 @06:16AM (#28817243)
„Valid“ does not mean syntactically valid but „true in any case“
Re:Poincaré, Heisenberg, Gödel and the limits of scientific ... by contingencies on Sunday October 10, 2021 @08:34AM (#28817923)
Re:Poincaré, Heisenberg, Gödel and the limits of scientific ... by lr1970 on Sunday October 10, 2021 @05:07PM (#28821989)
To 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

Re:Poincaré, Heisenberg, Gödel and the limits of scientific ... by ProfHewitt on Monday October 11, 2021 @09:37AM (#28828155)
Contrary 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.