[dwohnitmok]

The article plays a little fast and loose with language

> For example, Gödel himself helped establish that the continuum hypothesis, which concerns the sizes of infinity, is undecidable, as is the halting problem

The continuum hypothesis is definitely not "undecidable" in the same way that the halting problem is undecidable. Though there are deep connections behind the two, the two notions of "undecidability" (logical independence in the former and Turing machine computability in the latter) are very different.

Also,

> He also showed that no candidate set of axioms can ever prove its own consistency.

This is powerful as a limiting result, but it has little direct impact for philosophy, because you wouldn't trust the consistency result of a system you suspect might be inconsistent to begin with because inconsistent systems can prove anything. So saying "my axioms prove themselves consistent" shouldn't have increased your trust in those axioms to begin with in the absence of the incompleteness theorems.

I'm not really a fan of "true-but-unprovable" as short-hand the incompleteness theorems, because that hinges a lot on what kind of logic system you're in and how that logic system defines "truth" (taken at face value, how do we know that Godel's incompleteness theorem is "true?").

I prefer rather to pose two questions to reflect on that I think illuminate Godel's incompleteness theorems some more. Most modern logical systems (e.g. first-order logic and its various extensions and variants) equate unproveability with logical independence. So with that in mind, here's two questions.

First, Conway's Game of Life:

Conway's Game of Life seem like they should be subject to Godel's incompleteness theorems. It is after all powerful enough to be Turing-complete.

Yet its rules seem clearly complete (they unambiguously specify how to implement the Game of Life enough that different implementation of the Game of Life agree with each other).

So what part of Game of Life is incomplete? What new rule (i.e. axiom) can you add to Conway's Game of Life that is independent of its current rules? Given that, what does it mean when I say that "its rules seem clearly complete?" Is there a way of capturing that notion? And if there isn't, why haven't different implementations of the game diverged? If you don't think that the Game of Life should be subject to Godel's Incompleteness Theorems why? Given that it's Turing complete it seems obviously as powerful as any other system.

Second, again, in most logical systems, another way of stating that consistency is unproveable is that consistency of a system S is independent of the axioms of that system. However, that means that the addition of a new axiom asserting that S is either consistent or inconsistent are both consistent with S. In particular, the new system S' that consists of the axioms of S with the new axiom "S is inconsistent" is consistent if S is consistent.

What gives? Do we have some weird "superposition" of consistency and inconsistency?

Hints (don't read them until you've given these questions some thought!):

1. Consider questions of the form "eventually" or "never." Can those be turned into axioms? If you decide instead to tackle the question of applicability of the incompleteness theorems, what is the domain of discourse when I say "clearly complete?" What exactly is under consideration?

2. Consider carefully what Godel's arithmetization of proofs gives you. What does Godel's scheme actually give you when it says it's "found" a contradiction? Does this comport with what you would normally agree with? An equivalent way of phrasing this hint, is what is the actual statement in Godel's arithmetization scheme created when we informally say "S is inconsistent?"

At the end of the day, the philosophical implications of Godel's incompleteness theorems hinge on whether you believe that it is possible to unambiguously specify what the entirety of the natural numbers are and whether they exist as a separate entity (i.e. does "infinity" exist in a real sense? Is there a truly absolute standard model of the natural numbers?).

[braindongle]

Who cares about the philosophical implications of the theorems? Philosophers! The linked article is about how the theorems destroyed Whitehead et al's aspirations to find One Algebra To Rule Them All.

The literature on Gödel and philosophy is gargantuan, for some reason. Wasn't it summed up well by Wittgenstein? Paraphrasing: "Who cares about your contradictions?" Well said. Also not the topic Wolchover's article.

Math people can make the same move: "Who cares about your philosophizing?"

[dwohnitmok]

> The linked article is about how the theorems destroyed Whitehead et al's aspirations to find One Algebra To Rule Them All.

Sort of. Whitehead's contributions to universal algebra are still relevant and universal algebra is still a thriving field of study for mathematical logic. Although perhaps you mean "algebra" in a more informal sense?

Again, the conclusion of the article is a bit strong.

> Gödel’s proof killed the search for a consistent, complete mathematical system.

The consistency half doesn't make sense. (EDIT: I get it now, see the last sentence of this paragraph) There was never a search for a consistent mathematical system in the sense that Godel destroyed because again a system that can prove its own consistency has no positive value in evaluating the consistency of that system (Godel's big contribution here is contributing a strong negative result, if it could prove its own consistency you're pretty screwed). EDIT: On reflection I see that the sentence probably means to tie consistency to completeness rather than as a stand-alone quality. That makes more sense.

As for mathematicians, their reactions to Godel's incompleteness theorems overall are probably similar to "Who cares about your incompleteness theorems?" (there's a reason Russell and Whitehead are known primarily for being philosophers first and mathematicians second and why often times there is distinction between logicians like Godel and other mathematicians). Most mathematicians don't think about the foundations of mathematics because it is (perhaps surprisingly) largely irrelevant to the day-to-day work of mathematicians. Indeed the vast majority of mathematics is very resilient to changes in its underlying foundations.

To interpret Godel's incompleteness theorems requires a healthy dose of at least mathematical logic that can start veering quite close to mathematical philosophy.

An example from the article:

> However, although G is undecidable, it’s clearly true. G says, “The formula with Gödel number sub(n, n, 17) cannot be proved,” and that’s exactly what we’ve found to be the case!

Well no, that's not true in certain senses. Indeed in a larger axiomatic system subsuming the current system that corresponds to G, it is completely consistent to state that G is provable and that its statement is provable (see my example of S'), i.e. there are Godel numbers that correspond to both a proof of G and to a proof of its content. To interpret that statement that way requires certain philosophical commitments to the correspondence between a Godel number and truth, which not everyone would accept (do you accept the truth of the new axiom introduced by S'? Why then do you accept the truth of the statement "S is consistent?" and vice versa).

"In striving for a complete mathematical system, you can never catch your own tail." This on the other hand I think is a very good informal description of what's on with Godel's incompleteness theorems. Focus on the incompleteness not on truth.

That's why I'm not a fan of using the word "truth" when talking about Godel's incompleteness theorems. I am in fact deeply sympathetic to your desire to separate philosophy from Godel's incompleteness theorems.

I prefer to clearly delineate between its logical properties in mathematical logic and its philosophical implications and using the word "truth" by necessity muddles the two.

FINAL EDIT: I am being perhaps a bit too harsh on the article. I think it does a fine job of describing the arithmetization of the incompleteness theorems. But if someone else reading this also decides to create an informal guide to Godel's incompleteness theorems, please please please don't use the word "truth" and "true" or at least separate it out into its own section on philosophy.

[pdonis]

> that's not true in certain senses

I think it's not true in a very clear sense: you can construct semantic models of the axioms of arithmetic in which it is false. In other words, you can construct semantic models of the axioms of arithmetic (more precisely, of the axioms of arithmetic using first-order logic, which is what the article is about) in which there is a "number" that is the Godel number of a proof of the Godel sentence G! Godel's Theorem just ensures that in any such model, the "number" that is the Godel number of such a proof will not be a "standard" natural number, i.e., one that you can obtain from zero via the application of the successor operation.

So another way of viewing this whole issue of "truth" is that it is always relative to some semantic model. If your chosen semantic model of the axioms of arithmetic is the "standard" natural numbers, and only those numbers, then the Godel sentence G for that system will be true--there will indeed be no number in your model that is the Godel number of a proof of G. But if you pick instead a non-standard model that includes "numbers" other than the standard natural numbers, but still satisfies the axioms, then the Godel sentence G can be false in that model, since there can exist a "number" (just not a standard one) in that model that is the Godel number of a proof of G.

[dwohnitmok]

What you are saying is true (as you allude to with first-order logic) in any context in which Godel's completeness (not incompleteness) theorem holds. Not all logics have versions of Godel's completeness theorem (e.g. second order logic with full semantics). You can argue that philosophically in systems where Godel's completeness theorem fails that the article's statement is valid. But yes that's why it's only true in "certain senses."

More generally the philosophical question of truth revolves around whether there is a single, true set of standard natural numbers that corresponds to reality, and therefore all nonstandard natural numbers are "artificial" in some sense, or whether even standard natural numbers exist only in a relative sense.

[krick]

You seem like somebody who I could ask some (2) questions on the topic.

1. First of, I'm still not sure what to make of Gödel's theorems philosophically. In the "pop-culture", so to speak, there seems to be a notion that Gödel's theorems are, in essence, some grand, weighty statement about fundamental "inaccessibility of truth". That since Peano's arithmetic exemplifies very simple (compared to our general needs) mathematical system, no matter how we further develop math, one day there will be a useful, meaningful statement which cannot be proved or disproved.

What's perhaps even worse, some people, even some with names I feel uncomfortable to argue against (Penrose, for example, seems to be of this opinion) try to use it as a transition to the idea that "human mind is more than a computer", which I always implicitly assumed to be just a manifestation of anthropocentric hubris. The key to their reasoning is the observation, that some expressions unprovable within some formal system are "obviously true" (and they often kinda are, and they are provable within a higher-order formal system). So, the story goes, since the Turing machine couldn't see it (because of Gödel's), but we see it, we are more than a Turing machine.

And since that informal version of Gödel's findings was familiar to me long before I was acquainted with a formal version of it, I'm kinda used to the idea that "it must be right".

However, when I'm looking at the formal explanation of Gödel's theorems, or even perhaps more interesting "applied" findings, based on them (like Goodstein's theorem), they all seem to be surprisingly "boring" and non-consequential clever tricks based on self-referencing. I mean, it's sure a very interesting finding about formal systems as such, but if we take a step back into the realms of common sense: isn't it rather quite intuitive, that a system cannot be proven to be consistent by the means of the same system? So it must be of no surprise that any formal system powerful enough to be able to express statements about consistency of itself must be "incomplete".

So, my question is, am I missing something? Is there any truth to that pop-cultural image of Gödel's theorems? Because to me it seems like there actually isn't, just more of an "urban myth".

2. Continuum hypothesis. As I understand it, it is a matter of axiom, if 2^Aleph₀ ?= Aleph₁ and |R| could be as well Aleph₅ or whatever. Of course, we have most natural axiomatic system (with axiom of determinacy) where the former is true. But are there, like it was with Euclid's fifth postulate, any alternative, but still "interesting" constructs? Is there any use whatsoever in the assertion that continuum hypothesis is false?

[dwohnitmok]

I'll give brief statements with lots of hand-waving since I'm low on time. These are long questions.

1. In short, this is a deeply philosophical question. My personal inclination follows yours that the incompleteness theorems are overhyped. I don't buy Penrose's argument. Like most other formal limiting results philosophically I view those results as representing fundamental limits of both human and machine reasoning. While a single unproveable but "obviously true" result generally point to an inadequacy of the formal system, if every formal system suffers from some inadequacy that is indicative of a limitation in the fundamental human faculties of comprehension rather than a limitation of formal systems per se (the assumption e.g. that our formal systems must use finitistic methods is one born of human limitations and, depending on one's thoughts about the universe, potentially fundamental physical ones).

There are philosophically defensible positions that try to claim the incompleteness theorems have implications for truth in the real world, but I go back and forth on whether I believe them and more to the point they are far more subtle than the usual pop culture presentations of Godel's incompleteness theorems.

2. The mathematical Platonists I've come across believe that the continuum hypothesis is in fact false. (As an aside it's interesting that you find the axiom of determinacy natural as it contradicts the axiom of choice.) This mainly hinges on your opinion of the reality of large cardinals (which perhaps count as your "interesting" constructs), which many Platonists for a variety of reasons believe to be real.

[unknown_apostle]

Very interesting remarks... never looked at it in this way. Thx!

Care to write a short but more explicit wrap up of how you see your two questions yourself?

[dwohnitmok]

Don't read this without thinking about the questions first!

I tried to be short... there's a considerable amount of handwaving. I'll present two components to each of my answers. One that stays within mathematical logic and then one that expands a bit into philosophy.

1. Strictly mathematical logic: Godel's incompleteness theorems can be viewed as a limiting result on the absoluteness of mathematical induction (this is not strictly true, in fact we lose even more than absoluteness of induction, see e.g. Robinson's Q, but I'll leave that aside for now). Conway's Game of Life rules are complete in the context of a single step. That is for any step n, Conway's Game of Life rules completely determine step n + 1. The assumption that given a fixed starting state, this means that Conway's Game of Life is completely determined for all steps is exactly a statement of mathematical induction. In particular, we are piggy-backing off of the induction axiom of Peano arithmetic here. That's where Godel's incompleteness theorems get you.

One way of thinking about Godel's incompleteness theorems is that they attack the assumption that because we have defined every step transition we have defined the whole process. Hence certain "global" statements about potentially unbounded processes remain up in the air. Even if we rule by fiat with an induction axiom (or axiom schema) that this must be true, some ambiguity remains. "After a certain point once this square turns white it never turns black again" or "this square will never turn white" are both statements that are independent of Conway's Game of Life rules for certain squares and starting configurations.

Now this ambiguity is not observable because while we have ambiguity for unbounded questions, as soon as we place any bound, no matter how large the n (e.g. for the next 1000000 steps this square will not turn black), there is no ambiguity. Incompleteness hinges essentially on the ability to make unbounded statements which involve the words "eventually," "always," "never," etc.

Now the philosophical implications of this are interesting. This question is why I'm skeptical of naive attempts to talk about the incompleteness theorems' consequences for physical theories of the universe. Intuitively I view physicists as trying to find the "Game of Life" rules for the universe, and that if they did, that would be as good a candidate as any for a "theory of everything." In particular these rules would be local and finite, rather than global, infinite statements of the sort I outlined above. If you're willing to accept Conway's Game of Life as being complete enough for your purposes, I would argue you should accept a similar "theory of everything" as being "complete enough."

Now there's no reason why Mother Nature must be kind enough to furnish us with such a theory, but that's a different story.

Another interesting philosophical component here is whether this implies Godel's incompleteness theorems have any meaningful physical manifestation. I don't have the time at the moment to get into that discussion, but suffice it to say I generally think that these discussions usually go off the rails really really quickly without a deep understanding of the incompleteness theorems rather than informal overviews of them. In the philosophical context of Conway's Game of Life, you'd expect to find deviations in different implementations of the the rules "after an infinite amount of steps have passed." Whether you find that a coherent statement or not has implications for the applicability of Godel's incompleteness theorems to the physical universe.

EDIT: To tie this to the hints I gave, unbounded statements involving words like "eventually" or "never" are precisely those statements that can be independent of the "axioms" of the Game of Life. When we talk about the completeness of the Game of Life we are talking about it only at a per-step level.

2. Godel's incompleteness theorems are ultimately statements about natural numbers, or at least what the current logical system in question thinks is a natural number. The interpretation that this natural number represents some logical statement is a metalogical one and unjustified within the logical system itself. We can only make this interpretation as an outside observer. So S' produces a "number" according to the algorithm we use to represent the statement of inconsistency of S. However, within S' this is just a number. It doesn't know how to turn that number into a logical contradiction that it can then produce and use to prove things. As an outside observer then we are either free to agree with S' that indeed yes what you've produced is a number and then use that number to deduce the inconsistency of S or we can disagree with S' that this number represents an inconsistency of S (informally, you can imagine that S' is "hallucinating" a number that while might be a natural number according to the axioms of S', is not a natural number according to ours as an outside observer).

If we have a notion of what the "true" natural numbers are, as opposed to natural numbers are "hallucinated," we can talk about whether S' is right about the consistency of S. The assumption that S' is not "hallucinating" natural numbers is known as omega-consistency (https://en.wikipedia.org/wiki/%CE%A9-consistent_theory). Whether "true" natural numbers exist... well that brings me to the philosophical ramifications.

If you believe that there is one true set of natural numbers then it's easy to dismiss S' as a trick, useful for proofs and exploration, but ultimately simply an interesting tool rather than reflective of reality. If you believe that there is no such thing as "one true set of natural numbers" then consistency is simply a relative statement.

EDIT: To tie this to the hints I gave, Godel's arithmetization scheme only gives you numbers. It's up to you the reader to interpret those as proofs and logical statements. Within certain bounds, you are free to disagree that in your interpretation that this number represents a valid proof (or in equivalent phrasing that this "number" is truly a number).

[unknown_apostle]

Thanks! I'm bookmarking this to come back to for a while :-)