Escaping Entropy @escapingentropy - Tumblr Blog

Can you prove godel's incompleteness theorem for the lambda Calculi?

The lambda calculus is a well-specified formal system capable of calculation, so it is subject to incompleteness for the same reasons as ZFC. There is no need for an additional proof.

An abridged English version of Gödel Incompleteness

Summary

Claiming “there’s an exception to every rule” is just a roundabout way of saying “this statement is false”.

Has anyone ever told you “there’s an exception to every rule”? Next time tell them, “There must be an exception to that rule, too.” And if they stop and think for a moment, they might start getting confused...wouldn’t that mean that there must be an exceptional rule that has no exceptions at all? But if there is, then the original thing they told you can’t be true at all! Because if you’ve found a rule without any exceptions, that directly contradicts the claim that all rules have an exception.

English-ified Proof

Assumption: There’s an exception to every rule.

1. Notice that our assumption is, itself, a rule. Therefore, it must have at least one exception.

2. From our assumption and (1) combined, it follows that there must be at least one rule that does not have an exception.

3. The result of (2) is a contradiction, as the assumption states that all rules have an exception, whereas (2) states there exists a rule without any exceptions. This directly implies that the initial assumption is false, and the opposite is true.

Discussion

In other words there is no way to state a (non-contradictory) rule that applies to all other rules. If you stop and think about it, that’s a pretty incredible (and correct!) conclusion to reach from very little starting material.

Mathematically, the theorem essentially says: “You can’t have a set that contains all other sets, as it would have to contain itself.” Kurt Gödel proved that such a set’s existence would violate the axioms he was working under (within a fundamental system in wide use).

The result was powerful. It placed limitations on the kinds of objects that could be constructed in a consistent manner. It showed that if you wanted to permit such objects to exist, you were in violation of your own laws and thus inconsistent (that is, your system is useless; anything can be proved true and/or false given enough time).

A few things I’d like to note:

When I write “...and the opposite is true”, be sure to understand what is meant by “opposite”.

This proof came from logic, but the same holds in English. What is the opposite of “every rule has an exception”? A few candidates you might be considering:

Every rule does not have an exception.

No rule has an exception.

Some rules have an exception.

Naturally I’m going to tell you what you already know, those choices are all terribly wrong. We need to apply negation to the statement as a whole, so the true opposite is:

“There’s an exception to every rule.” is not a rule.

Remember: the true assumption here was that our initial statement was actually a rule to begin with, since it’s content only applies to rules; not that it was itself a valid rule.

The result does not tell you which assumption was false.

“But we only had one assumption!”

Not true, and the following applies to both the mathematical treatments and this distilled English rendering: It may be that our notion of a “rule” is ill-defined, or simply not definable in a consistent manner, or the concept of proof systems is fundamentally incomplete as it must be explained and understood from one person to the next―at least initially―via a human language, which are prone to ambiguity.

You can find ways to circumvent the proof as written via English-based tactics, but you’d be missing the entire point, which is semantic.

There’s an exception to every rule except this.

Notice that “except one” includes the word “except”, a good tip-off that something is fishy. Also, it digs a deeper whole since the statement now directly admits to being a rule, something we inferred previously. In this case, the fatal flaw is that “except this” is, of course, an exception, which directly contradicts the claim in the first part of the sentence. It’s the equivalent of saying absolutely nothing meaningful. Let me state the same thing in a more obviously flawed way:

My name is always Stephen, except when it’s not.

Anyway, you get the idea. You can’t add exceptions for yourself if you aren’t supposed to have any! A more clever approach would be along the lines of what Bertrand Russel and Alfred North Whitehead attempted, but ultimately failed at:

The statement: ‘There’s an exception to every rule’ is always true.

See what I did there? I implicitly defined two ‘classes’ of things: ‘statements’ and ‘rules’, and then I used one to make a claim about the other. This might seem to avoid the issue, but as Russel and Whitehead discovered, the path is fraught with demons. Consider a small selection off the top of my head:

If statements are not rules and vice-versa, then why should we expect their claims about each other to be true?

What happens when I write: “The rule: ‘There’s an exception to every statement’ is always true,” or “all statements that apply to rules are always true”, headaches etc.

Most importantly: if new types of rules can be defined arbitrarily to side-step the issue, the underlying problem doesn’t go away; the fundamental issue of determining a system’s consistency from it’s axioms remains unaddressed.

And my final note for the evening:

Gödel produced other theorems and people often confuse them.

The words “incompleteness” and “inconsistent” can be easily interchanged, and he had multiple theorems with both. If this topic interests you, I highly recommend that you take an intro. to logic course and read Godel's Theorem: An Incomplete Guide to Its Use and Abuse, in that order. The book is very short, clear, well-written, and no, I have no financial interest in any of my recommendations; I also own other Gödel books of which I’m less fond.

The word “rule” as tossed around here is vague.

...hence the original theorem being written symbolically in the notation of fundamental mathematics rather than English. If you have a problem with that, remind yourself you’re once again missing the point, and that’s not something to be very ashamed of―this stuff gets pretty confusing. After all, it’s statements about rules that are about rules...no wonder Bertrand got lost.

Conclusion

I especially love when someone discovers something that applies to an entire proof system, or to systems in general, or to the very rules that govern how proofs are created, or interpreted, etc. Proofs like these stretch outside themselves a little and seem to touch the stuff entire universes are made of, if you’re inclined to think of our universe as obeying mathematical laws unerringly (as I am).

For whatever it’s worth, this is my best/only attempt to explain the core message of the fundamental incompleteness theorem for a general audience, compressed for minimum loss in translation.

#math #logic #proof #gödel #science

Leonard Susskind on his friendship with Richard Feynman

#math #physics #science

This article provides the best English explanation of P/NP and all its frustrations, conundrums, and naysayers I’ve read to date. Worth the few minutes! (And no, you don’t need to understand the few equations shown.)

#math #computerscience #science

Goodbye, Telemarketers

If you have Google Voice, press 4 and a female voice will say, “This call is being recorded.” Telemarketers hangup immediately.

#LifeHack

OF COURSE I'LL SUPPORT ENHANCING TED CRUZ' FACE BY REPLACING IT WITH KITTENS :DDDDDDDDDDDDDDDDDDD -IrrationalLiberal

Thank you! <3

I'm a believer (aka "I'm a liar") - italiano

#monkeys #italy #italia #language