## Godel Incompleteness Theorem

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

RogerMurdock
Posts: 158
Joined: Mon Jul 27, 2009 10:35 pm UTC

### Godel Incompleteness Theorem

I'm reading Godel, Escher, Bach right now and it's very interesting (I'm not very far in yet though) but I think I grasp what they're saying with the Godel Incompleteness theorem. So a system cannot be both consistent and complete, this is a very cool fact and all, but how does this relate to modern mathematics? I did some reading and came up on the ZFC axioms, http://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory.

So let me see if I'm understanding things. The ZF axioms themselves are consistent and not complete, but by themselves cannot PROVE OR DISPROVE the axiom of choice. So you just kind of have to "accept" the axiom of choice and accept it's use in proofs? Is this an example of a "true statement that cannot be proven"? If not, what is?

Also, does the axiom of choice added to the ZF axioms make that entire system complete but not consistent? That is, is the axiom of choice the "tipping point" from consistency to inconsistency so to speak? Or is it just an additional theorem that is useful but not able to be proven.

Another question: Assuming you start with the ZFC axioms, could you go from basic arithmetic and work your way up to calculus and stuff eventually?

I'm in high school and have a good amount of calculus understand, but I do not have any knowledge of set theory so forgiven me if I made some basic assumption or grossly misunderstood what was going on. Thanks!

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

### Re: Godel Incompleteness Theorem

Systems can be both consistent and complete. Its just that you cant prove it from within the system.

RogerMurdock
Posts: 158
Joined: Mon Jul 27, 2009 10:35 pm UTC

### Re: Godel Incompleteness Theorem

BlackSails wrote:Systems can be both consistent and complete. Its just that you cant prove it from within the system.

Yeah but what is "outside" the system of mathematics? So how would you prove it?

skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

### Re: Godel Incompleteness Theorem

RogerMurdock wrote:I'm reading Godel, Escher, Bach right now and it's very interesting (I'm not very far in yet though) but I think I grasp what they're saying with the Godel Incompleteness theorem. So a system cannot be both consistent and complete, this is a very cool fact and all, but how does this relate to modern mathematics?

To be precise, a computably axiomatizable system which is powerful enough to prove basic facts of number theory cannot be both consistent and complete. Both ZF and ZFC are such systems, but there are other systems out there which are both consistent and complete, either because they aren't powerful enough to prove basic facts of number theory (e.g. the theory of algebraically closed fields) or because they are not computably axiomatizable (e.g. true number theory, which is the system of all true statements about the natural numbers which can be written using the standard logical symbols and the symbols +, *, 0, 1, and <).

I did some reading and came up on the ZFC axioms, http://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory.

So let me see if I'm understanding things. The ZF axioms themselves are consistent and not complete, but by themselves cannot PROVE OR DISPROVE the axiom of choice.

They are believed to be consistent, and if so are not complete. Gödel's second incompleteness theorem implies that, if ZF consistent, we can't prove that it is.

So you just kind of have to "accept" the axiom of choice and accept it's use in proofs? Is this an example of a "true statement that cannot be proven"? If not, what is?

You don't have to accept anything. However most mathematicians accept the axiom of choice just as they accept the other axioms of set theory. At the end of the day, whether or not you accept an axiom is not based on whether you think it is true, but really what you think a set is. You can think of the axioms of set theory as actually defining what we mean when we refer to sets. Then the question of whether the axioms are consistent is really a question of whether this definition is valid, i.e. whether there really are such objects as sets with all the properties we define them to have.

Also, does the axiom of choice added to the ZF axioms make that entire system complete but not consistent? That is, is the axiom of choice the "tipping point" from consistency to inconsistency so to speak? Or is it just an additional theorem that is useful but not able to be proven.

No. Just like ZF, ZFC is another system that we think is consistent and that most mathematicians accept as the background for mathematics. Again, assuming ZFC is consistent, it is also incomplete (again, this follows from the incompleteness theorem).

Another question: Assuming you start with the ZFC axioms, could you go from basic arithmetic and work your way up to calculus and stuff eventually?

Yes. Basically, all of ZFC sits in the background for all of mathematics. However, much of the time we leave it in the background and out of focus so that we can focus directly on the objects of study, such as real numbers and functions from the reals to the reals (as is the case for calculus).
Last edited by skeptical scientist on Wed Mar 17, 2010 8:12 am UTC, edited 1 time in total.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

RogerMurdock
Posts: 158
Joined: Mon Jul 27, 2009 10:35 pm UTC

### Re: Godel Incompleteness Theorem

Thank you very much for the explanation. Question though, if you can't prove if someone is inconsistent, then can you prove it's completeness? You know that a system is either complete or consistent, one or the other, not both. You know that you cannot show it is consistent or inconsistent from within.

The only way to show it is one or the other is to show it's completeness then. But...how would you provide a standard for completeness? People can't "know" every single truth about number theory can they? If they can't, then the only gold standard for completeness would be to compare our system to some bigger better system that we KNEW was complete and see if it checked out. The thing is though, if we have a system we know is complete, it cannot be consistent, and therefore it invalidates itself (because you can't trust an inconsistent system to provide truths). So would the conclusion be that you can never even show whether a system is one or the other!?!? Am I going in circles/being foolish?

majikthise
Posts: 155
Joined: Sun Jun 10, 2007 2:28 am UTC
Location: Bristol, UK

### Re: Godel Incompleteness Theorem

If you can prove a contradiction, you know it's inconsistent, and from a contradiction you can prove every possible thing you can think of so it must also be complete (just useless).

BlackSails wrote:Systems can be both consistent and complete. Its just that you cant prove it from within the system.

Assuming you are talking about computably axiomatizable systems stronger than PA, this is false- see skeptical's post.

The classic example of a first order theory which you can show to be complete would be real closed fields- you can find a decision procedure for checking whether any well formed sentence is satisfied, hence each has a truth value.
Last edited by majikthise on Wed Mar 17, 2010 1:40 am UTC, edited 1 time in total.
Is this a wok that you've shoved down my throat, or are you just pleased to see me?

RogerMurdock
Posts: 158
Joined: Mon Jul 27, 2009 10:35 pm UTC

### Re: Godel Incompleteness Theorem

I'm sitting here trying to formulate my thoughts/arguments into words and my mind is literally blowing itself to shit.

So you can show a system in inconsistent by showing a contradiction, but if you cannot find a contradiction wouldn't you therefore know that the system is consistent? So to prove a system in consistent all you need to do is check for contradictions and you could then prove it when you find there are none.

If I had to guess the problem with the previous statement it's "all you need to do is...", but I'm not really sure. In fact I'm not really sure about anything right now.

achan1058
Posts: 1783
Joined: Sun Nov 30, 2008 9:50 pm UTC

### Re: Godel Incompleteness Theorem

RogerMurdock wrote:So you can show a system in inconsistent by showing a contradiction, but if you cannot find a contradiction wouldn't you therefore know that the system is consistent? So to prove a system in consistent all you need to do is check for contradictions and you could then prove it when you find there are none.
But how do you check for such a contradiction? There are infinitely many statements on there in the world, you know.

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

### Re: Godel Incompleteness Theorem

RogerMurdock wrote:So let me see if I'm understanding things. The ZF axioms themselves are consistent and not complete, but by themselves cannot PROVE OR DISPROVE the axiom of choice. So you just kind of have to "accept" the axiom of choice and accept it's use in proofs? Is this an example of a "true statement that cannot be proven"? If not, what is?

This might be a bad analogy (especially if you're not American ), but let's call RB the traditional rules of baseball, and DH the designated hitter rule. Both RB and RB+DH are sensible "systems". We might argue (and many do) about whether one or the other is more applicable to the spirit of sporting as we wish to experience it, but the simple fact is that there is nothing in baseball that says that the pitchers have to take their turn at bat or that they should have a stand-in.

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.

So there's nothing wrong with ZF as a model except that it doesn't prove as many things as ZFC. If you're a mathematician who is interested in one of those things (and I suspect most are), then you "accept" AC for the purposes of studying that field. If you want to be really clean about it (as I was taught to be), then you recognize precisely where you are using AC in your proofs and see if there is a way around it, because proving something in ZF is more generally elegant.

Also, does the axiom of choice added to the ZF axioms make that entire system complete but not consistent? That is, is the axiom of choice the "tipping point" from consistency to inconsistency so to speak? Or is it just an additional theorem that is useful but not able to be proven.

I am 99.5% certain that ZF also satisfies the conditions of Godel's Incompleteness Theorem.

Another question: Assuming you start with the ZFC axioms, could you go from basic arithmetic and work your way up to calculus and stuff eventually?
[/quote]

Sure. In fact, that's pretty much the way we have done it. If you can make it through GEB, then you might try to chew on the Principia Mathematica, which derives arithmetic from first principles. In my opinion, it's in need of a good editor, but the program itself is solid.

Of course, ZFC is just set theory, so you need just a little more structure to define functions and relations between sets, but from ZFC you can define ordinal numbers, and jump from there to rational, real, and complex numbers in turn, and then start imaging abstract systems using these building blocks that analyze arithmetic (which is abstract algebra) and continuity and limits (which is abstract topology), and then you've pretty much got all the pieces for defining what you know of calculus.

RogerMurdock
Posts: 158
Joined: Mon Jul 27, 2009 10:35 pm UTC

### Re: Godel Incompleteness Theorem

achan1058 wrote:
RogerMurdock wrote:So you can show a system in inconsistent by showing a contradiction, but if you cannot find a contradiction wouldn't you therefore know that the system is consistent? So to prove a system in consistent all you need to do is check for contradictions and you could then prove it when you find there are none.
But how do you check for such a contradiction? There are infinitely many statements on there in the world, you know.

So the only reason you cannot prove consistency is because you don't have an infinite amount of time? I feel like that's some kind of cop-out answer. I'm pretty sure it was an issue brought up in the book though, so I'm going to re-read that section and see if it still feels wrong.

And Tirian thank you for the example, I am American and I got the baseball just fine. Although, your example of the parallel postulate was exactly the one used in GEB so that was still fresh in my mind as well (I'm assuming you knew this).

And also, does anyone else feel very...like upset that math is somehow either inconsistent or incomplete and doomed to be forever? I always thought of logic and math in particular as absolute truths that once founded could be built up to whatever heights, but this just kind of blows all that away.

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

### Re: Godel Incompleteness Theorem

RogerMurdock wrote:

So the only reason you cannot prove consistency is because you don't have an infinite amount of time? I feel like that's some kind of cop-out answer. [/quote]

Thats the only reason you cant prove most things.

Lets take the riemann hypothesis. With an infinite amount of time, its really easy to do. Just check all the zeroes. Or the goldbach conjecture. Check every even number. The collatz conjecture? Check every integer.

This is related to something called the halting problem.

skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

### Re: Godel Incompleteness Theorem

RogerMurdock wrote:And also, does anyone else feel very...like upset that math is somehow either inconsistent or incomplete and doomed to be forever?

Nah. There are only finitely many statements that we will ever see proven in our lifetimes anyways, so does it really matter whether we will never see some truths proven because they are independent from the axioms, given how many truths we will never see proven because nobody can figure out how? Besides, part of Hilbert's program which Gödel's theorem ended was the goal of producing an algorithm which could decide the truth or falsity of any mathematical statement. Thank Gödel for the incompleteness theorem, because imagine how boring mathematics would be if any time you had a mathematical question, you just fed it into that algorithm to get the answer.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

majikthise
Posts: 155
Joined: Sun Jun 10, 2007 2:28 am UTC
Location: Bristol, UK

### Re: Godel Incompleteness Theorem

On the other hand, it could lead to people devoting entire lifetimes to proving something without even knowing whether it's possible.
Is this a wok that you've shoved down my throat, or are you just pleased to see me?

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 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.

Again, meh. I recall at some point running into a layman's description of Godel's work that claimed that Fermat's Last Theorem might well be an example of an undecidable statement, since a proof or counterexample had already eluded us for several hundred years. That was a horribly incorrect worldview to take away from Godel, and in specific case we see how it didn't pan out. We've even got tools nowadays for positively determining that several important statements (including but not limited to AoC) are independent of the axioms of ZFC, so there's even progress possible on the undecidability front.

Also, just to be clear, people have devoted their lifetimes to tackling problems that remain unsolved but still have a lot to show for it. Scientific discovery isn't about seeing what you want, it's about understanding what you see.

Like Skeptical Scientist says, it heartens me to know that Hilbert was foiled in his vision to build a machine that could replace a mathematician.

achan1058
Posts: 1783
Joined: Sun Nov 30, 2008 9:50 pm UTC

### Re: Godel Incompleteness Theorem

Tirian wrote:Like Skeptical Scientist says, it heartens me to know that Hilbert was foiled in his vision to build a machine that could replace a mathematician.
I don't think one needs Godel to foil such a vision, though Godel does make it impossible. Presumably, even if such a machine exist, if it is in NEXP time or something horrible, it's the same as it not existing.

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

### Re: Godel Incompleteness Theorem

Tirian wrote:
Like Skeptical Scientist says, it heartens me to know that Hilbert was foiled in his vision to build a machine that could replace a mathematician.

If instead of asking the machine "is there a proof of X" you ask "is there a proof of X less than ten billion characters long", the problem is always solvable. Its just only solvable efficiently if P=NP

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

### Re: Godel Incompleteness Theorem

Tirian wrote:Like Skeptical Scientist says, it heartens me to know that Hilbert was foiled in his vision to build a machine that could replace a mathematician.

Well, until we get sentient machines. But then everyone's replaceable (we're doomed!).

fractalchaos
Posts: 10
Joined: Wed Mar 17, 2010 5:36 pm UTC
Location: Ohio

### Re: Godel Incompleteness Theorem

I'm not sure if this will help you at this point, but a book as been written all about Gödel, his life, and his incompleteness theorems. It's appropriately called Incompleteness: The Proof and Paradox of Kurt Gödel by Rebecca Goldstein. It goes through both of the theorems and their proofs. It's also a bit of a biography, but you could always skip those parts. The beginning also has some interesting stuff about Platonism and Formalism.

ATCG
Posts: 471
Joined: Sat Aug 18, 2007 3:44 am UTC
Location: Straight up the jω axis

### Re: Godel Incompleteness Theorem

fractalchaos wrote:I'm not sure if this will help you at this point, but a book as been written all about Gödel, his life, and his incompleteness theorems. It's appropriately called Incompleteness: The Proof and Paradox of Kurt Gödel by Rebecca Goldstein.

Solomon Feferman, the editor-in-chief of Kurt Gödel: Collected Works, has reviewed Goldstein's book for the London Review of Books. While he praises it as providing "a vivid biographical picture of Gödel", he finds much to fault it from a technical and a historical standpoint.

If I were to recommend a single book as a follow-on to GEB, it would be Torkel Franzén's Gödel's Theorem: An Incomplete Guide to Its Use and Abuse.
"The age of the universe is 100 billion, if the units are dog years." - Sean Carroll

RogerMurdock
Posts: 158
Joined: Mon Jul 27, 2009 10:35 pm UTC

### Re: Godel Incompleteness Theorem

How is a human mathematician different from a machine with an algorithm? As was mentioned, we're fine until we get "sentient" machines, but where is that line crossed? Whats the difference between a machine that operates on a algorithmic level and one that operates with many more layers and complexity, but still finds the correct answer (in this case, the appropriate theorems)? Humans are not gifted with any particular miraculous insight into the universe that non-humans lack.

Syrin
Posts: 290
Joined: Thu May 24, 2007 7:10 pm UTC

### Re: Godel Incompleteness Theorem

RogerMurdock wrote:Whats the difference between a machine that operates on a algorithmic level and one that operates with many more layers and complexity

One exists, and one is a problem for philosophers.

RogerMurdock wrote:Humans are not gifted with any particular miraculous insight into the universe that non-humans lack.

Care to back up that claim? You're skirting the edges of a debate on the validity of Artificial Intelligence. "Is the human mind Turing computable?", basically.

skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

### Re: Godel Incompleteness Theorem

RogerMurdock wrote:How is a human mathematician different from a machine with an algorithm? As was mentioned, we're fine until we get "sentient" machines, but where is that line crossed? Whats the difference between a machine that operates on a algorithmic level and one that operates with many more layers and complexity, but still finds the correct answer (in this case, the appropriate theorems)? Humans are not gifted with any particular miraculous insight into the universe that non-humans lack.

Perhaps, but the best mechanical theorem-proving devices may basically just be AI mathematicians, who solve problems the same way we do (brainstorming ideas, producing examples and counterexamples, observing why such and such an argument won't work, trying to think of a suitable way of modifying it, and so on - in short, trying to apply intelligence to the task). That would be a very different situation from a computer algebra system which computes integrals by performing a set sequence of steps for every integral.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

RogerMurdock
Posts: 158
Joined: Mon Jul 27, 2009 10:35 pm UTC

### Re: Godel Incompleteness Theorem

I realize my arguments are more philosophical in nature than I intended, but theoretically I don't see why the human brain is different from a giant computer. I guess we just don't have enough information, but it's my point of view that human intelligence is something that can be understood, modeled, and copied. At least eventually it will be.

skeptical scientist wrote:
RogerMurdock wrote:How is a human mathematician different from a machine with an algorithm? As was mentioned, we're fine until we get "sentient" machines, but where is that line crossed? Whats the difference between a machine that operates on a algorithmic level and one that operates with many more layers and complexity, but still finds the correct answer (in this case, the appropriate theorems)? Humans are not gifted with any particular miraculous insight into the universe that non-humans lack.

Perhaps, but the best mechanical theorem-proving devices may basically just be AI mathematicians, who solve problems the same way we do (brainstorming ideas, producing examples and counterexamples, observing why such and such an argument won't work, trying to think of a suitable way of modifying it, and so on - in short, trying to apply intelligence to the task). That would be a very different situation from a computer algebra system which computes integrals by performing a set sequence of steps for every integral.

In mind those are basically the same thing. The only reason we would ever have a AI mathematician doing such needless tasks as "brainstorming" and "observing" is because we modeled it after human minds which are inefficient. I'm sure you could simplify the decision making process down eventually to something that is as set in stone as a CAS sequence for solving integrals.

But I'm mostly talking out of my ass at this point since nobody really knows what true AI will look like or how/if it is possible. Thank you guys for humoring me by responding to my arguments, it certainly helps me wrap my head around all of this much easier.

Dason
Posts: 1311
Joined: Wed Dec 02, 2009 7:06 am UTC
Location: ~/

### Re: Godel Incompleteness Theorem

RogerMurdock wrote:Humans are not gifted with any particular miraculous insight into the universe that non-humans lack.

I spent an entire semester in a class where we debated this very issue. It was a fun class but yeah... Not sure if I'd be willing to say that humans are nothing more than very complex computers.
double epsilon = -.0000001;

skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

### Re: Godel Incompleteness Theorem

RogerMurdock wrote:The only reason we would ever have a AI mathematician doing such needless tasks as "brainstorming" and "observing" is because we modeled it after human minds which are inefficient.

And what makes you think that non-humans are gifted with any particular miraculous insight into mathematics that humans lack?
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

Pvt. Parts
Posts: 4
Joined: Fri Mar 19, 2010 6:41 am UTC

### Re: Godel Incompleteness Theorem

...I don't see why the human brain is different from a giant computer

Well firstly, there would be a giant size and power consumption difference, which says a lot about the efficiency of the brain. Also, it's important to remember that computers are modeled on the human brain, and not the other way around.

The only reason we would ever have a AI mathematician doing such needless tasks as "brainstorming" and "observing" is because we modeled it after human minds which are inefficient.

Human minds may not be able to compute the square root of Pi to a million digits very efficiently, but show me a computer that can play Clair de Lune on the piano with emotion. Or judge the speed and direction of an approaching tennis ball, move to the spot it's going to be and return it to the other player, then do it again, and again, in the space of a few seconds. Human minds can be breathtakingly efficient at those sorts of things.

Further more, without brainstorming or observing, there's no science, and certainly no computers.

skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

### Re: Godel Incompleteness Theorem

Pvt. Parts wrote:show me a computer that can play Clair de Lune on the piano with emotion.

my iPod.

In any case, we seem to have wandered rather off-topic. There are many other places to discuss whether computers can ever be as good as humans at certain tasks. My point was only that doing mathematics still requires creativity, and I'm rather glad that it is a creative process rather than merely feeding a question into a computer and getting the answer.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

Pvt. Parts
Posts: 4
Joined: Fri Mar 19, 2010 6:41 am UTC

### Re: Godel Incompleteness Theorem

Hahahahaha I should have seen that one coming.

gmalivuk
GNU Terry Pratchett
Posts: 26836
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

### Re: Godel Incompleteness Theorem

Syrin wrote:
RogerMurdock wrote:Humans are not gifted with any particular miraculous insight into the universe that non-humans lack.

Care to back up that claim?

It's the opposite claim that needs to be backed up, really, because we have still seen no evidence of what kind of mechanism might magically grant the human brain abilities that are in principle impossible for non-humans to have.

Pvt. Parts wrote:but show me a computer that can play Clair de Lune on the piano with emotion.

I'm sure if we fed computers with chemicals that made them just a bit irrational, they could eventually have emotions, too.

The fact that modern computers, which are not modeled on the brain at all, can't do something a brain can should not be a surprise to anyone.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

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

### Re: Godel Incompleteness Theorem

http://arxiv.org/abs/quant-ph/0604079

tldr: If people have free will, electrons do too.

Syrin
Posts: 290
Joined: Thu May 24, 2007 7:10 pm UTC

### Re: Godel Incompleteness Theorem

gmalivuk wrote:
Syrin wrote:
RogerMurdock wrote:Humans are not gifted with any particular miraculous insight into the universe that non-humans lack.

Care to back up that claim?

It's the opposite claim that needs to be backed up, really, because we have still seen no evidence of what kind of mechanism might magically grant the human brain abilities that are in principle impossible for non-humans to have.

Nor do we have evidence that a conscious, sentient human can be modeled by an inhuman machine. I, myself, believe that AI is possible, but that doesn't mean I will use it as an argument.

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

### Re: Godel Incompleteness Theorem

If you accept the Church-Turing thesis, then you accept that the human mind cannot solve the halting problem.

As an aside, IIRC, and I don't recall the details, but the unsolvability of the halting problem is weaker than the incompleteness theorem. Even with an oracle that gave you the answer to any halting problem as it is traditionally formulated, you could not decide the truth of all statements in the language of PA.

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

### Re: Godel Incompleteness Theorem

Syrin wrote:Nor do we have evidence that a conscious, sentient human can be modeled by an inhuman machine.

This position does not need evidence to make it the default position. Remind me what makes the configuration of molecules that makes up a human fundamentally and relevantly different from any other configuration of molecules?
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

### Re: Godel Incompleteness Theorem

Black wrote:As an aside, IIRC, and I don't recall the details, but the unsolvability of the halting problem is weaker than the incompleteness theorem. Even with an oracle that gave you the answer to any halting problem as it is traditionally formulated, you could not decide the truth of all statements in the language of PA.

This is true. The halting problem allows you to decide what are called $$\Sigma_1$$ sentences, which are sentences of the form $$\exists \bar{x} \phi(\bar{x})$$ where $$\phi$$ is a computable formula. (Here $$\bar{x}$$ can stand either for a single natural number, or else an n-tuple of natural numbers $$x_1, x_2, \ldots, x_n$$, in which case $$\exists \bar{x}$$ is shorthand for $$\exists x_1 \exists x_2 \cdots \exists x_n$$. A computable formula $$\phi$$ is one where it can be checked by an algorithm whether $$\phi$$ holds of some particular n-tuple.) The halting problem also allows you to decide what are called $$\Pi_1$$ sentences, which are just like $$\Sigma_1$$ sentences but with a universal instead of an existential quantifier.

One example of a $$\Sigma_1$$ sentence would be the statement $$\exists x \, \forall y<x \, \forall z<x [(y \in P \land z \in P) \longrightarrow y+z\neq x]$$ which asserts that there is some number x which is not the sum of two primes. (I'm using $$y \in P$$ as a shorthand for $$\forall y'<y \, \forall y''<y [y'\cdot y''\neq y],$$ in the interest of readability.) So an oracle for the halting problem would allow you, right away, to decide the Goldbach conjecture.

However, there are lots of sentences which are not $$\Sigma_1$$ or $$\Pi_1$$. Generally speaking, any sentence in PA can be written in a "normal form" which looks like $$Q_1 \bar{x_1} Q_2 \bar{x_2} \cdots Q_n\bar{x_n} \phi(\bar{x_1},\ldots,\bar{x_n})$$ with n blocks of quantifiers followed by a computable formula. The quantifier blocks alternate between existential and universal quantifiers. If there are n alternating blocks of quantifiers and they begin with an existential quantifier this is called a $$\Sigma_n$$ sentence, and if the first quantifier is universal it is called a $$\Pi_n$$ sentence. (You can check that the n=1 case agrees with our previous definition.) One example of a $$\Pi_2$$ sentence would be $$\forall x \exists y [y>x \land y\in P \land y+2 \in P].$$ In order to decide the truth of $$\Sigma_2$$ and $$\Pi_2$$ sentences in general you need something stronger than the halting problem; you would need to be able to determine whether an arbitrary algorithm which can call that halting problem as an oracle will halt. This is called the halting problem relative to the halting problem. So an oracle for the halting problem would not necessarily solve the twin primes conjecture right off the bat, but an oracle for the halting problem relative to the halting problem would.

(Of course, there may be a more clever way to use a halting oracle to settle the twin primes conjecture, such as by deciding the $$\Sigma_1$$ sentence which asserts the existence of a proof of the twin primes conjecture. This sentence must exist, using the proof of the incompleteness theorem. However, if you decide that that this sentence is false, that doesn't necessarily mean that the twin prime conjecture is false; it may be true but unprovable.)

The set of (Gödel numbers of) halting algorithms is sometimes written K. Given a set A of natural numbers, one can use that set as an "oracle" by allowing algorithms to not only perform the basic functions we are used to algorithms performing, but also "ask questions of the oracle", i.e. we allow as an atomic procedure call A(n) which returns 1 if n $$\in$$ A and 0 if n $$\notin$$ A. Then given an "oracle" (set of natural numbers) A, we write A' for the halting problem relative to A; i.e. the set of (Gödel numbers of) A-oracle-algorithms which halt. Just as the halting problem itself is not computable, the halting problem relative to A is not even A-oracle-computable, and one can show this by the same proof.

So K is morally equivalent to $$\emptyset'$$, the halting problem relative to the empty set. It's not quite the same, because an ordinary algorithm is slightly different from an algorithm which is allowed an extra procedure call $$\emptyset$$(n). But since this extra procedure call always returns 0, it is not hard to turn one into the other, so we could say that K and $$\emptyset'$$ contain the same information.

What does all this have to do with sentences of arithmetic? It turns out that with a K=$$\emptyset'$$ oracle, you can decide "one-quantifier questions", i.e. decide the truth of $$\Sigma_1$$ or $$\Pi_1$$ sentences, but you can't, in general, decide the truth of $$\Sigma_2$$ or $$\Pi_2$$ sentences. If you had a K'=$$(\emptyset')'$$ oracle, you could decide the same sentences as with K, and also $$\Sigma_2$$ and $$\Pi_2$$ sentences. Writing $$\emptyset^{(0)}$$ for the empty set and $$\emptyset^{(n)}$$ for $$(\emptyset^{(n-1)})'$$, i.e. the halting problem relative to the halting problem relative to ... to the halting problem, it turns out that with a $$\emptyset^{(n)}$$ oracle, you could decide anything up to a $$\Sigma_n$$ or $$\Pi_n$$ sentence, but can't in general decide the truth of $$\Sigma_{n+1}$$ or $$\Pi_{n+1}$$ sentences. So to decide the truth of every sentence in the language of PA is quite a lot harder than just solving the halting problem. Not only would one need to solve the halting problem, but also the halting problem relative to that, and the halting problem relative to that, and so on, ad infinitum.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

Pvt. Parts
Posts: 4
Joined: Fri Mar 19, 2010 6:41 am UTC

### Re: Godel Incompleteness Theorem

gmalivuk wrote:The fact that modern computers, which are not modeled on the brain at all...

I'm not sure what you mean, I'll concede that a modern computer is not similar to a brain in structure, but they are modeled on the brain for the simple reason that brains designed them. No computer solves any problem on it's own, a human solves the problem and writes the code that computes the answer.

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: Godel Incompleteness Theorem

Pvt. Parts wrote:I'll concede that a modern computer is not similar to a brain in structure, but they are modeled on the brain for the simple reason that brains designed them.

But, by the exact same token, you could argue that a car is also modeled on the brain, because brains designed them. One could, perhaps, make an argument about the similarity of the two classes of objects, but this is not it.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

gmalivuk
GNU Terry Pratchett
Posts: 26836
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

### Re: Godel Incompleteness Theorem

Yeah, made by the brain is a completely different thing from modeled on the brain.

We designed computers, and we designed them to do some tasks we ourselves were fairly slow at. But we didn't design them to do those tasks the same way we do, because we didn't actually know how we do them at that time (and still only have a hazy idea of a lot of the nitty gritty of how the brain processes stuff). Plus, the way we do those tasks is slow--that's why we made computers to do them.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

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

### Re: Godel Incompleteness Theorem

BlackSails wrote:tldr: If people have free will, electrons do too.

If there is a meaningful definition of "free will" I have not yet come across it

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

### Re: Godel Incompleteness Theorem

Suffusion of Yellow wrote:
BlackSails wrote:tldr: If people have free will, electrons do too.

If there is a meaningful definition of "free will" I have not yet come across it

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

skine
Posts: 61
Joined: Sat Feb 09, 2008 5:53 pm UTC

### Re: Godel Incompleteness Theorem

In essence, what Godel stated was that; pick two: (1) statements that are right are not wrong, (2) all statements are either right or wrong, (3) every possible statement can fit into the above two.

Basically, in Math, as in every science, we assume that what makes sense is true until it can be disproved. Until then, we find everything it implies. So we assume the system (generally ZF) is consistent, knowing that it is not complete. Knowing it's not complete, we add the Axiom of Choice, and again, most believe it is consistent and all know it is not complete.

One of the strange things about the system is that, assuming ZF, you can prove that you can't prove ZFC. The problem is that it makes sense, and yet what it implies doesn't quite.
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.

This is not to say that ZFC is false, but it is obviously incomplete. The biggest thing I deal with is category theory. For a simple example, the collection of all sets is not itself a set. It's just too damned big.

Here's the basic thought, in my mind: If the axioms of ZFC can be disproven, then my entire world view would be proven wrong. I know it seems a religious notion, but I feel it's a rational stance. ZF and mathematicians just seems to hold the same intrinsic absolute truth as do, for example, biologists and cell theory.