Live data from Hacker News

What Gödel Discovered

stopa.io

91–100 of 271 posts

Re: What Gödel Discovered

#91
post #34

Just to be clear. This implies that it's possible to write some specific statement (using PM axioms) that contradicts itself? Is there a readable example of this statement without using Gödel numbers but instead just with the axiom statements?

I don't think PM itself had any contradictions inside of it, rather there are statements composed of the PM langauge that aren't reached from the axioms selected by PM -- that is one of the sentences Godel demonstrates in his proof where he gets one that basically says "this statement has no proof in this system" (so if it does have a proof it is a contradiction, but if it doesn't have a proof then PM is an incomplet…

The continuum hypothesis is more like Euclid's parallel postulate than a Gödel sentence - assuming ZFC consistent there are models with CH true and CH false (the cardinality of the continuum doesn't have to be the first uncountable cardinal).

Everything gets qualified with "assuming ZFC consistent" or "assuming Peano consistent" because any inconsistent theory proves any statement. More of a proof technicality than anything too profound.

There is a construction of a model of Peano arithmetic, so it is consistent, as long as you accept the system used in the proof: https://en.wikipedia.org/wiki/Gentzen%27s_consistency_proof

Not sure if this sheds light on the parent commentator's question ... the terminology can be quite tricky.

Re: What Gödel Discovered

#92
post #68

Earlier quoted context omitted.

In light of current circumstances this story has actually been on my mind! Has there ever been any more detail revealed about Godel's scheme?

There is some more information at https://jeffreykegler.github.io/personal/morgenstern.html There's also an article about this question at https://papers.ssrn.com/sol3/papers.cfm?abstract_id=2010183

Thanks the second one finally answered the question:

In summary, Gödel’s loophole is that the amendment procedures set forth in Article V self-apply to the constitutional statements in Article V themselves, including the entrenchment clauses in Article V. Furthermore, not only may Article V itself be amended, but it may also be amended in a downward direction (i.e., through an “anti-entrenchment” amendment making it easier to amend the Constitution). Lastly, the Gödelian problem of self-amendment or anti-entrenchment is unsolvable. In addition, the author identifies some “non-Gödelian” flaws or “design defects” in the Constitution and explains why most of these miscellaneous design defects are non-Gödelian or non-logical flaws.

Re: What Gödel Discovered

#93
post #72
post #43

Earlier quoted context omitted.

> being able to prove the CH is an incompleteness in ZFC. It's only incompleteness if the CH is true or false at the semantic level, "outside" of the logic system under discussion. But the CH may be neither true or false, semantically, if the meaning of "existence of a set whose cardinality is strictly between that of the integers and the real numbers" strictly depends on the axioms and logic used to define sets and…

Hm? I thought (in)completeness was just about whether or not , for each well-formed-formula, either there is a proof of it, or a proof of its negation. The CH is a syntactically valid statement in ZFC. So, shouldn't the fact that ZFC cannot prove or disprove CH, be an example of ZFC being incomplete, regardless of whether CH is in fact true, false, or not-a-proposition-that-has-a-truth-value ?

Ok. If we are being careful, there are different kinds of completeness and we should specify which one we're talking about.

Here's a good list: https://en.wikipedia.org/wiki/Completeness_(logic)#Forms_of_...

The existence of a proof within the logic system for every well-formed formula or its negation is "syntactical completeness".

Re: What Gödel Discovered

#94
post #68

Earlier quoted context omitted.

In light of current circumstances this story has actually been on my mind! Has there ever been any more detail revealed about Godel's scheme?

There is some more information at https://jeffreykegler.github.io/personal/morgenstern.html There's also an article about this question at https://papers.ssrn.com/sol3/papers.cfm?abstract_id=2010183

I'm sad that there isn't an explanation of Godel's proof!

But, given that we can amend the constitution, it does seems fairly straightforward that a dictator could come to power, if there was approval of a super majority of the people.

Re: What Gödel Discovered

#95

I thought I replied to this post, but I guess not and my reply ended up being a top-level reply, which is just as well. I will just mention my main two quibbles to this otherwise excellent post and others like it so that other people who embark on introductory posts to Godel's results don't fall into the same trap. 1. Please don't bring the notion of truth into an introductory explanation (such as in the section "Pow…

"I will just mention my main two quibbles" -- Poking through your history, why do you quibble on the word truth so often? Do we not agree there are statements that are true? Do we not agree there are provable true statements ? If there are unprovable statements in any consistent set of axioms, might we also conclude there also be an unprovable but true statements?

It's because it's a huge can of worms that leads to really grandiose claims that aren't supported by Godel's statements, of the sort the article is already beginning to make.

It also shifts the conversation into becoming fundamentally a philosophical question rather than a logical or mathematical one, which is okay, but considerably changes the table stakes of what background knowledge we need.

> If there are unprovable statements in any consistent set of axioms, might we also conclude there also be an unprovable but true statements?

That is one potential philosophical position. Another philosophical position is that there are no "true" axioms schemes, but rather that axiom schemes are always indefinitely extendable. Truth lies instead in how we choose to apply the axiom schema to the external world, which is outside the purview of Godel's Incompleteness Theorem. Both positions are supported by Godel's Incompleteness Theorem.

For example, do you believe that the Continuum Hypothesis (CH) is true? That is, although it is independent of ZFC, do you believe that objectively we are only allowed to use CH as an axiom or Not(CH) as an axiom. One of those must be objectively wrong. Some people do some people don't.

Likewise, do you believe that the imaginary numbers are "true?" That is the axioms that make them up are not artificial statements that somebody can up in pursuit of an abstract theory, but are immutable truths of the universe and that in fact you cannot choose an alternative axiomatization because it would be "wrong?" Some people some people don't.

What about the natural numbers?

There are many philosophical positions you can take on the notion of mathematical truth and the crucial thing is describing Godel's theorems with reference to truth suggests that Godel's theorems help decide among these notions of mathematical truth, when in fact what happens is that Godel's theorems stretch and shrink to accommodate different philosophical frameworks. The former is why I think a lot of people accord Godel's theorems a mystical status that makes it very difficult to have coherent discussions about them.

To pedagogically illustrate why the notion of truth can be confusing, I'll repeat two questions I've listed elsewhere which I think are good things to meditate on for first-time readers of Godel's Incompleteness theorems and explore why the often grandiose philosophical proclamations arising from Godel's theorems require very careful footing.

I answer them in my post history, but I would recommend you don't look at those before you've come up with answers yourself.

------Repost-----

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?).

Re: What Gödel Discovered

#96
post #81

I thought I replied to this post, but I guess not and my reply ended up being a top-level reply, which is just as well. I will just mention my main two quibbles to this otherwise excellent post and others like it so that other people who embark on introductory posts to Godel's results don't fall into the same trap. 1. Please don't bring the notion of truth into an introductory explanation (such as in the section "Pow…

> It makes it very confusing, especially in light of Godel's other landmark result, i.e Godel's Completeness Theorem which simultaneously applies to many of the same logical systems and can be very very vaguely described as "all true things are provable." If people want to understand how to reconcile this very vague statement with Goedel incompleteness theorem that appears to say that some "true" statements are in fa…

I am trying to follow, but I feel I am hanging

Goedel incompleteness theorem -> apply this to "theories"

Goedel completeness theorem -> apply this to a specific "model", of the theory

So there can be "something true but not provable" in the theory, and "we cannot describe all true things about specific models", but ....what?

Re: What Gödel Discovered

#97
Minor formatting gripe: the first inline citation (superscript 1) looks like an exponent given that it's right after a numeric constant in an equation.

It made me re-parse the sentence a few times before realizing it.

Re: What Gödel Discovered

#98
post #93
post #72

Earlier quoted context omitted.

Hm? I thought (in)completeness was just about whether or not , for each well-formed-formula, either there is a proof of it, or a proof of its negation. The CH is a syntactically valid statement in ZFC. So, shouldn't the fact that ZFC cannot prove or disprove CH, be an example of ZFC being incomplete, regardless of whether CH is in fact true, false, or not-a-proposition-that-has-a-truth-value ?

Ok. If we are being careful, there are different kinds of completeness and we should specify which one we're talking about. Here's a good list: https://en.wikipedia.org/wiki/Completeness_(logic)#Forms_of_... The existence of a proof within the logic system for every well-formed formula or its negation is "syntactical completeness".

Oh cool, I was (at least partially) wrong. (Or, I was missing something important at least.) I appreciate the correction/elaboration.

Re: What Gödel Discovered

#99

Very off-topic, but long ago when Albert Einstein went for a car ride with Mr. Gödel to become U.S. citizens, Einstein was trying very hard to think of ways to shut him up about a Constitution loophole he discovered. Things didn't go exactly as planned, and in front of the naturalization examiner, Mr. Gödel started blabbing about how he had found a way the U.S could be transformed into a fascist regime... Sources: ht…

The constitution is BS anyway.

For example, Article I, section 10 says "No state shall...coin money, emit bills of credit, make any thing but gold and silver a tender in payment of debts..."

And look what the US has today; fiat money. No only is it not gold or silver, but it's not event backed by it.

Based on this definition, nobody in the US earns any money so nobody should have to pay any income tax since basically everyone's income is 0 ounces of gold and 0 ounces of silver. Yet this argument would not stand in court even though it's 100% logical.

We're all just a bunch of monkeys. The implementation of the law always comes down to what the most popular monkeys think it is.

If the most popular monkeys think that the definition of 'gold' actually means 'feces', then before you know it, we will all start throwing feces at each other as a means of payment.

What's the point of defining the law using words if people will later distort the meaning of those words to suit their purpose? you may as well rely on gut feelings and majority rule to decide what is right or wrong.

Re: What Gödel Discovered

#100
post #81

Earlier quoted context omitted.

> It makes it very confusing, especially in light of Godel's other landmark result, i.e Godel's Completeness Theorem which simultaneously applies to many of the same logical systems and can be very very vaguely described as "all true things are provable." If people want to understand how to reconcile this very vague statement with Goedel incompleteness theorem that appears to say that some "true" statements are in fa…

I am trying to follow, but I feel I am hanging Goedel incompleteness theorem -> apply this to "theories" Goedel completeness theorem -> apply this to a specific "model", of the theory So there can be "something true but not provable" in the theory, and "we cannot describe all true things about specific models", but ....what?

Another example of why I don't like the word "truth" because I think it does more to muddy the situation than clarify it.

Let's drop "truth" for a sec.

Let's say I come up with a series of axioms about cows. They describe spots on cows, how many legs cows have, etc.

Now I come up with a sentence "all cows have spots." There are two ways of proving this sentence. One is a "semantic proof." That is I go and round up every cow and examine it and make sure they all have spots. Another way of proving this sentence is a "syntactic proof." I list out a series of axioms defining what cows are. Then I do a series of string manipulations on my axioms about cows according to an allowed ruleset to arrive at the statement "all cows have spots."

Semantic proofs are hard. They're annoying for finite groups of things and impossible to do for infinite groups of things. If possible we would like to use syntactic proofs. But syntactic proofs face two hurdles. The first is how to know we've applied our axioms correctly. For example, maybe one of my axiom is "all cows have 4 legs," and then I just conveniently define the symbol "4" to mean three. You can't really get around that problem. You kind of just have to tell people, don't mess around with the meaning of words.

The second hurdle though concerns our ruleset. That is string manipulations can be of an arbitrary form. How do I know, even if I've applied my axioms correctly, that my ruleset isn't crazy? Something like, anytime you see a sentence S, you're allowed to replace it with Not(S) if you want.

Godel's completeness theorem says for a lot of reasonable rulesets (including most of the ones we use for mathematics), semantic proofs and syntactic proofs coincide. You can decide to either go out and look at every cow or you can use your axioms about cows to move symbols on a sheet of paper around. As long as your axioms about cows capture enough information about whether cows have spots, with certain popular rulesets, you'll get the same result.

Put another way, as long as the result you're looking for is relevant to the axioms you've listed, either a semantic proof or a syntactic proof is valid.

Okay, but what about statements that aren't relevant to the axioms I've listed? Things like the weight of a cow? Or what about statements that are under-specified? For example if I just say as an axiom "some cows have spots," does that mean all cows have spots or that some don't?

Through the lens of Godel's completeness theorem this just means that our list of axioms is applicable to a lot more situations than we're giving it credit for. Our axioms don't talk about the weight of a cow? Well then they could be used for situations where cows are weightless or when they have weight. Our axioms don't specify whether all cows have spots? Well they can be used in situations where all cows have spots as well as situations where some cows don't have spots.

No biggie. That just means the only things relevant to our axioms are those properties in common across all the situations we could apply our axioms. And anything that can be semantically proved in all of these situations is also something that can be syntactically proved.

Okay so that concludes Godel's completeness theorem. Let's start going into his incompleteness theorems through the same lens.

Cows are really complicated things. They have tons and tons of different properties, so it's no surprise that our list of axioms will probably always under-specify them.

What if we strip things down to really really simple things. For example the natural numbers? Can we have a list of axioms that apply to the natural numbers and pin down every property about them?

The answer is no. Any list of axioms we come up with will always be "too broad." There are things other than the usual natural numbers (that's already a bit of a minefield to privilege one of them as being the "usual", but we'll ignore it for now) that I can present to you that also fulfill those axioms. In the same way that "some cows have spots" is mum on the issue of whether a certain cow doesn't have spots, and so can be used to describe either a herd of cows that all have spots or a herd of cows split half-and-half with spots and without spots, any system of logic that simultaneously fulfills both Godel's completeness theorem and incompleteness theorem means that it can be applied to more than one unique situation. Moreover those things that the system cannot syntactically prove are exactly those things that have different semantic proofs in different situations. For example, because I can't have a series of string manipulation steps that result in the sentence "all cows have spots" (Godel's incompleteness thereoms) there's gotta be some situations where all my axioms apply and all cows have spots and other situations where at least one cow doesn't have a spot (Godel's completeness theorem).

Hence through this lens Godel's incompleteness theorems aren't really about capital-T Truth so much as they are about our ability to completely specify infinite objects. If you and a friend decide to start listing out axioms to try to describe something like the natural numbers, no matter how many axioms you list out there is always something left unspecified.

Post reply on HN