9

Does there exist a "valid" application of Gödel's incompleteness to "logical natural language statements"?

It can be found to sometimes be naively applied that way, even when the incompleteness theorems are a specific application.

But I find it reasonable, why couldn't one devise "incompleteness theorem" for natural language statements? That relies on e.g. "expectation of non-contradiction"?

  • Natural language does not seem to satisfy the assumptions of G's Th : consistent and with a decidable set of axioms. – Mauro ALLEGRANZA Jan 21 at 15:27
  • You may be interested in Tarski's Undefinability theorem, which is more applicable to languages rather than proofs. It is, however, only focused on formal languages, not natural. – Cort Ammon Jan 21 at 22:51
  • 1
    Also potentially of interest is how easy it is to sidestep Godel's theorems in a purely mathematical environment. Dan Willard demonstrated that just by not assuming multiplication was total (i.e. it is not provable that multiplying two numbers always yields a number), he was able to create self-referencing proof systems with all of the remaining rules of arithmetic without incompleteness rearing its head. If such a small thing can sidestep the issue, it suggests there's lots of room for natural langauges to sidestep it. – Cort Ammon Jan 21 at 22:53
  • @CortAmmon-ReinstateMonica That last comment is in my opinion somewhat misleading: it's very specific to Godel's second incompleteness theorem. There is really no way around the first incompleteness theorem, in the following sense: any computably axiomatized consistent theory which interprets Robinson arithmetic is incomplete. (It also underplays the weakness of Willard's systems - sacrificing totality of multiplication is expensive!) – Noah Schweber Jan 22 at 1:19
  • @Noah Schweber : How expensive? Can you assume totality fails at arbitrarily large minimum inputs and have that suffice? If so, you should be able to axiomatize "all arithmetic that is practically realizable", no? Kind of like a "soft finitism" (in that you are not explicitly disavowing infinities philosophically, but you are going to limit the scope of your mathematical axiomatization.). – The_Sympathizer Jan 22 at 4:01
9

Natural language is a very slippery thing; I don't know what one would hope for exactly here. You do clarify that you're looking at "logical natural language," but it's not at all clear what that is. That said, of course one of the roles of logic is to find and analyze well-behaved fragments of natural language, so it's not out of the question that something could be done here - but I still think it's too broad to really hope for too much.

In particular, I would say that hoping to apply a theorem to natural language is pie-in-the-sky. Rather, it's fruitful to look for analogues of constructions in natural language: so, don't try to apply incompleteness to natural language, but rather - motivated by incompleteness - look for an analogue of incompleteness in natural language. This is a subtle distinction but I think it's crucial.


Adopting that stance, we do get something rather interesting when we look at belief and assertion. Consider the following sentence (I believe more-or-less originally due to Hofstadter):

(X) Noah Schweber cannot honestly assert this sentence.

Here of course both "honestly" and "assert" are doing some heavy lifting, but I can confirm that (i) I do recognize that (X) is true but (ii) I can't assert (X) in any way which feels "honest" to me (including point (i) previously - sorry, but honesty on the internet is rare!). Of course, that latter point is subjective - others might experience the situation differently, or argue that there's something silly about invoking qualia here in the first place - but personally I think it's a reasonable point here.

Ultimately of course this leans on a couple assumptions about what's "built into" the relevant part of natural language:

  • An appropriate mechanism for talking about assertion, belief, honesty, etc.

  • Classical truth values and behavior, and some capacity for self-reference (at the cost of not being able to refer to truth itself inside a sentence per Tarski).

  • And an appropriate mechanism for referring to speakers (or "agents").

All of this though is reasonably tame from a mathematical perspective: we can in fact whip up formal "toy models" of this situation. And I would argue that this sentence and its analysis does in fact mirror some of Godel's argument.


But just as interesting as the parallels are the divergences.

An interesting additional feature of (X) is its interaction with universal instantiation. I would say reflexively that I can honestly assert

(Y) For every person P, the sentence "P cannot honestly assert this sentence" is true.

Basically, the point is that I do not consciously percieve all possible instantiations when I consider the universal statement above.

  • This recalls a key difference between belief and assertion: one is obviously aware of what one is asserting, but one is arguably not aware of the set of all one's beliefs at any given moment (and even worse, it's reasonable in my opinion to argue that people may have individual beliefs that they don't recognize).

Moreover, it's not clear that there's a habit I can adopt here which is guaranteed to prevent similar problems in the future: I can always make a point to check the specific instantiation "me," but why should that be the only source of problems for universal instantiations here? I'd ultimately argue that this is a point we simply can't avoid:

We can honestly assert universals while not being able to honestly assert - even not believing - some of its instantiations.

There is a family similarity between this situation and the existence on the formal logic side of consistent theories asserting their own inconsistency. However, in my opinion this family similarity doesn't stand up to too much scrutiny. One key point being that in the natural language context this situation is actually happening in the "intended situation," whereas on the mathematical side those self-defeating theories are only true in nonstandard models and in fact only happens as a consequence of a highly-nontrivial technical result (Godel's completeness theorem) whose interaction with natural language is in my opinion even more problematic and interesting (interestingly problematic? problematically interesting?). So there is a real difference in essences here, in my opinion.

I'd say that the final takeaway should be the following:

There are indeed "Godel-like" phenomena in natural language. Moreover, these need not be "cheats" (like "This statement is false" is usually (but not universally) argued to be) - they can coexist with logical tameness and formalizability in other ways. Moreover, further paralleling the mathematical situation at a very general level they lead to further surprises about even "fairly logically tame" natural language; however, these further surprises are not necessarily trivial parallels of ones arising in the classical setting, but should be construed in their own light.

|improve this answer|||||
  • Be careful. All of this talk of analogs of inherently ambiguous natural language might upset formalists. ; ) – J D Jan 21 at 15:59
  • 1
    @JD Well that's really their fault for perceiving meaning in the string of symbols I wrote :P. (I'm curious, though, in case that wasn't entirely a joke: why would formalists be upset by this? I consider myself a formalist, and I'm not ...) – Noah Schweber Jan 21 at 16:02
  • Good natured ribbing of those who confuse the map with the territory. I think there exists a general hubris among intellectuals to ordain symbols with a certain undeserved power and certainty in experience and thus the construction of the representation of reality. I've seen several posts here, for instance, that presume that the best path to understanding is to study the work of logicians and neglect linguistics. I'd call it Cartesian hubris, but the magical power of words and thoughts is far older. I upvoted because you caught the essence of the relation of formalisms to natural language. – J D Jan 21 at 16:23
  • Yes. The difficulty with natural languages is they're ambiguous, fuzzy and fluid. Because they're ultimately built to communicate stuff between similarly fluid, adaptable neural nets (our brains). That doesn't mean they're uncomputable, but they're not analyzable with the naive kind of formalism seen in mathematics. Which is why natural language processing on a computer is a difficult problem in artificial intelligence, too. But it's also one a lot of work has been done on. – The_Sympathizer Jan 22 at 4:03
  • Interestingly, accepting fuzziness and "imperfection" into things can actually render non-computable things computable, or intractable things tractable - e.g. you can find approximately optimal solutions to problems like TSP (NP-complete) in P- or at least subexp-time. "Perfect" is, indeed, "the enemy of good". – The_Sympathizer Jan 22 at 4:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.