## Godel Incompleteness Theorem

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

BlackSails
Posts: 5315
Joined: Thu Dec 20, 2007 5:48 am UTC

### Re: Godel Incompleteness Theorem

skine wrote: take the pieces and construct two spheres with the same radius as the first.

Two completely solid spheres.

Suffusion of Yellow
Posts: 42
Joined: Thu Jan 01, 2009 6:15 pm UTC

### Re: Godel Incompleteness Theorem

majikthise wrote:On the other hand, it could lead to people devoting entire lifetimes to proving something without even knowing whether it's possible.

Question: I read that Continuum Hypothesis was proved unprovable, but since you can always disprove it by just pointing to a set with cardinality between rationals and reals, doesn't its unprovability imply no such sets exist, proving the hypothesis and contradicting it being unprovable?

Am I misunderstanding undecidability or the Continuum Hypothesis here? (Or both?)

BlackSails wrote:If people make decisions not based upon physical data and not predictable from the physical data, then so do electrons

Definitely, but there's no reason to think people do.

TNorthover
Posts: 191
Joined: Wed May 06, 2009 7:11 am UTC
Location: Cambridge, UK

### Re: Godel Incompleteness Theorem

Suffusion of Yellow wrote:Question: I read that Continuum Hypothesis was proved unprovable, but since you can always disprove it by just pointing to a set with cardinality between rationals and reals, doesn't its unprovability imply no such sets exist, proving the hypothesis and contradicting it being unprovable?

Because of (or perhaps as part of) the undecidability result there's no set whose cardinality you can prove is between the integers and reals. That doesn't stop you guessing one -- in fact I think that if you drop the axiom of choice then it's consistent to posit that a countable union of countable sets suffices, but there'll be no proof that it's between the two in ZF.

Something Awesome
Posts: 47
Joined: Sun May 18, 2008 10:53 pm UTC
Location: NY

### Re: Godel Incompleteness Theorem

TNorthover wrote:
Suffusion of Yellow wrote:Question: I read that Continuum Hypothesis was proved unprovable, but since you can always disprove it by just pointing to a set with cardinality between rationals and reals, doesn't its unprovability imply no such sets exist, proving the hypothesis and contradicting it being unprovable?

Because of (or perhaps as part of) the undecidability result there's no set whose cardinality you can prove is between the integers and reals. That doesn't stop you guessing one -- in fact I think that if you drop the axiom of choice then it's consistent to posit that a countable union of countable sets suffices, but there'll be no proof that it's between the two in ZF.

A countable union of countable sets is countable, with or without Choice. Since countable sets have a bijection with the naturals by definition, you can easily put them each into an [imath]\omega[/imath]-sequence, and then use something like the proof of the countability of the rationals (which also doesn't depend on Choice).

Black
Posts: 81
Joined: Fri Sep 19, 2008 4:24 am UTC

### Re: Godel Incompleteness Theorem

There is a set that would lie between the naturals and the reals if you take the negation of CH to be true: The set of all countable ordinals.

Basically, the independence of CH is saying that the structure of these sets is so complicated that you cannot say anything about their relative sizes using only the axioms of ZFC. The reals happen to be an extremely complicated set.

Imagine the warehouse at the end of "Raiders of the Lost Arc," and assume every crate is not empty. Obviously, you can take something out of each crate. But if there are an infinite number of crates, you can't prove that "taking something out of each crate" quite makes sense (as a function). Even though this makes sense, it has been proven that , given this, you can take a sphere apart (not by individual points), take the pieces and construct two spheres with the same radius as the first.

IIRC, you need uncountable choice for the Banach-Tarski paradox, not simply countable choice. Correct me if I'm wrong.

Also, I think your reasoning about Godel's conclusion is incorrect. Every statement is either right or wrong, but not both in a consistent system. The incompleteness theorems state that you cannot prove a statement is right or wrong in PA in general. The set of true statements with proofs is a strict subset of true statements in PA.

One way of looking at independence theorems is that we can construct models that look the same from our point of view, but somewhere far off into infinity they have different structure, and our axioms don't say anything about what kind of structure is correct in this realm. It can be seen as a consequence of our finiteness. For example, if we could solve the halting problem, the set of provable statements in PA becomes larger. Our inability to solve the halting problem is a consequence of being finite beings.

TNorthover
Posts: 191
Joined: Wed May 06, 2009 7:11 am UTC
Location: Cambridge, UK

### Re: Godel Incompleteness Theorem

Something Awesome wrote:A countable union of countable sets is countable, with or without Choice. Since countable sets have a bijection with the naturals by definition, you can easily put them each into an [imath]\omega[/imath]-sequence, and then use something like the proof of the countability of the rationals (which also doesn't depend on Choice).

The thing is you need choice (or at least a restricted form: the axiom of countable choice) to put each in bijection with the naturals simultaneously. Without that you could probably prove that the countable union of certain countable sets are countable (for example the disjoint union of countably many copies of N), but not the general theorem.

GyRo567
Posts: 107
Joined: Sun Jun 01, 2008 4:59 am UTC
Location: Austin, TX
Contact:

### Re: Godel Incompleteness Theorem

I haven't seen it mentioned yet, so I thought I'd point out that the Nagel/Newman book Godel's Proof is what originally got Hofstadter interested in Godel enough to write Godel, Escher, Bach. The present edition (which is usually found in the philosophy section, not alongside the others in the mathematics section) has been revised by Hofstadter & includes his introduction.

Tirian wrote:A more mathematical example is the parallel postulate in plane geometry. People spent two thousand years trying to prove it from the other four axioms, until eventually it was discovered that if you assumed that you could draw more than one line through a given point parallel to a given line, you'd come up with a consistent system (called elliptical geometry), and if you assumed that you could never draw a line through a given point parallel to a given line, you'd come up with another one (called hyperbolic geometry). None of these systems are "better" than the others, just more or less applicable to whatever problem you're trying to solve. To give an example of that, people studying relativity from a mathematical perspective are greatly aided by considering that space-time conforms to the rules of hyperbolic geometry, but people who are building a house prefer Euclid's model.

I think you may have this backward. In elliptic geometries, any 'straight' line through a point not on another line must eventually intersect with that other line. Spherical geometry is easiest to picture here. Just look at the lines of longitude (which are the straight lines of spherical geometry) versus latitude, which consists of curves through that space, except at the equator. And hyperbolic geometries are just the opposite. There are multiple lines to be drawn through any point not on a line, which do not intersect with that line.
I came here to read a cool post, a witty dialogue, a fresh joke, but stumbled upon a "bump"...
Way to go, jerk...
~CordlessPen

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

### Re: Godel Incompleteness Theorem

GyRo567 wrote:
Tirian wrote:A more mathematical example is the parallel postulate in plane geometry. Blah blah blah

I think you may have this backward.

It's a fair cop. Take those, reverse it. /willywonka