Godel Incompleteness Theorem

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

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

Re: Godel Incompleteness Theorem

Postby BlackSails » Sun Mar 21, 2010 4:59 am UTC

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

Postby Suffusion of Yellow » Sun Mar 21, 2010 3:30 pm UTC

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.

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

Re: Godel Incompleteness Theorem

Postby TNorthover » Sun Mar 21, 2010 3:37 pm UTC

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.

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

Re: Godel Incompleteness Theorem

Postby Something Awesome » Sun Mar 21, 2010 5:20 pm UTC

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

Postby Black » Sun Mar 21, 2010 5:27 pm UTC

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.

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

Re: Godel Incompleteness Theorem

Postby TNorthover » Sun Mar 21, 2010 5:51 pm UTC

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.

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

Re: Godel Incompleteness Theorem

Postby GyRo567 » Mon Mar 22, 2010 12:40 am UTC

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

Postby Tirian » Mon Mar 22, 2010 4:03 pm UTC

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


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 13 guests