0263: "Certainty"
Moderators: Moderators General, Prelates, Magistrates

 Posts: 139
 Joined: Tue Nov 07, 2006 6:36 pm UTC
 Location: Fremont, CA
Both incompleteness theorems only apply to logical systems strong enough to expess arithmatic. There's an interesting question here: why must a theory that can express multiplication and addition (along with the distributive property) be either incomplete or inconsistant while a theory that expresses only multiplication or addition may be complete and consistent.
I think I understood the answer to that question for about fifteen minutes when I was taking my second grad class in logic. And nicely toasted.
And I'm just going to assume that the alt text is a convulted reference to this fact.
I think I understood the answer to that question for about fifteen minutes when I was taking my second grad class in logic. And nicely toasted.
And I'm just going to assume that the alt text is a convulted reference to this fact.
 Yakk
 Poster with most posts but no title.
 Posts: 11078
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
oblivimous wrote:Both incompleteness theorems only apply to logical systems strong enough to expess arithmatic. There's an interesting question here: why must a theory that can express multiplication and addition (along with the distributive property) be either incomplete or inconsistant while a theory that expresses only multiplication or addition may be complete and consistent.
I think I understood the answer to that question for about fifteen minutes when I was taking my second grad class in logic. And nicely toasted.
And I'm just going to assume that the alt text is a convulted reference to this fact.
If you only have one of the two, you can't write a computer in equations.
If you have both, and some other tools, you can implement a full scale computer, proof system, etc.
Alternatively, see "Chinese Remainder Theorem".

 Posts: 139
 Joined: Tue Nov 07, 2006 6:36 pm UTC
 Location: Fremont, CA
 Yakk
 Poster with most posts but no title.
 Posts: 11078
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
With + and * and a few other tools, you can view an integer as a string and read the individual components of the string, and perform logic and mathematics on those components.
Ie, let T be our tapeinteger.
Suppose we want a character size of 1000 different values per character.
If we want to get the Nth character entry from T, we do the following:
Define T[N] := integer part of ( T / 1000^N ) mod 1000.
So now we can use an integer to store as much data as we want, extract it, and use it to run nearly arbitrary alogirthms. You can even do things like:
T[T[5]]
and use the values you store in T as pointers back into your integer T. Now all you have to do is write a FSM in logic, and you have a fullscale turing machine.
With only addition or multiplication, you can't pull this kind of thing off.
Godel's genius was to reencode the rules of logic itself into integers. Each axiom is an integer, each statement is an integer, and a proof is nothing more than a complex statement in which each step can be verified using relatively simple logic.
To do this, you need the ability to use an integer as a tape or an array.
To use an integer as a tape or array of arbitrary amounts of data, you need the chinese remainder theorem or something mostly equivilent.
To get the CRT, you need addition, multiplication, and some other proof rules (ie, a base logic).
Ie, let T be our tapeinteger.
Suppose we want a character size of 1000 different values per character.
If we want to get the Nth character entry from T, we do the following:
Define T[N] := integer part of ( T / 1000^N ) mod 1000.
So now we can use an integer to store as much data as we want, extract it, and use it to run nearly arbitrary alogirthms. You can even do things like:
T[T[5]]
and use the values you store in T as pointers back into your integer T. Now all you have to do is write a FSM in logic, and you have a fullscale turing machine.
With only addition or multiplication, you can't pull this kind of thing off.
Godel's genius was to reencode the rules of logic itself into integers. Each axiom is an integer, each statement is an integer, and a proof is nothing more than a complex statement in which each step can be verified using relatively simple logic.
To do this, you need the ability to use an integer as a tape or an array.
To use an integer as a tape or array of arbitrary amounts of data, you need the chinese remainder theorem or something mostly equivilent.
To get the CRT, you need addition, multiplication, and some other proof rules (ie, a base logic).
evilbeanfiend wrote:JoshuaZ wrote:UmbrageOfSnow wrote:Gelsamel wrote:Nothing can be proven universal, even math has it's axioms.
Sure, a(b+c) = (ab)+(ac) in our math systems, but it's based on axioms about multiplication and addition.
You could, in fact, set up a mathematical system where the above equation DOESN'T hold.
Yes Sir, Captain Godel.
This has nothing to do with Godel's theorem at all. ...
well goedel shows that if maths is consistent it can't be complete. a better and funny reference for showing there are always axioms (infinitely many hidden ones!) is http://www.ditext.com/carroll/tortoise.html
No. Godel's result shows that an axiomatic system which is sufficiently powerful cannot be both consistent and complete. That says nothing about Arithmetic in any neoplatonic or similar sense. Furthermore, Godel's theorem has nothing to do with whether or not we can reasonable acccept a given statement or set of axioms as "true" in any broader sense. As to the tortoise matter, I don't know how serious you were with that comment but the tortoise dialogue is an example of why we need to keep axioms and rules of inferrence separate and why informal axiomatization fails.
Barbie wrote:plams wrote:"a(bc)=(ab)+(ac). Politicize that, bitches." ... can we get that on a tshirt?
Haha, that would be so incredibly awesome. I would definitely wear it!
I would like to support the notion of this tshirt being created! Although it's quite similar to the 'Science' one. Not that that is a bad thing.
This was a great XKCD, my maths teacher enjoyed this a lot, I think shes put it on the wall now
But if anyone were ever to discover the meaning of life, all of space and time would collapse in on itself, and in the place that remained a large sign would appear saying:
Level 2.
Level 2.
a(b*c)=a*b+a*c
Death to distributivity! Rivers of vector spaces will flow red in the streets as we establish our set of all sets! InshaEuler!
McLurker wrote:OneLess wrote:Can a comic be written about using the word "maths" as a singular noun? It may or may not be correct as far as definition, but it sounds awful to hear a phrase like "Maths is great!" Bloody continentals, wot wot.
Would "Mathematics is great" also sound awful to you? Do you say "Mathematics are great"? (I would say the former).
I've always wanted to know this, but have kept on forgetting to ask.
"mathematics is great" sounds less awful than "maths is great" but it still has an odd ring to it. I would probably say "mathematics are great," though you'd have to catch me saying it without consciously thinking about the syntax to be sure
a note on mathematical proofs
God I love xkcd!
Today I just had to chime in about my own research experience with proofs. I used to be in grad school doing mathematics, we had it drilled into our heads what proofs are and aren't. Then I got interested in machine checkable proofs and switched to computer science.
The amazing thing is that standard "rigorous" mathematical proofs are usually full of holes! It sounds crazy, but if you learn a computerized proof assistant system like Coq and start doing machine checkable proofs, you realize how much more work it is to get all the details right.
For example, "paper proofs" might say something like "replace every X with Y in term T". In the machine checkable version, you have to define the replacement operator, then prove lots of properties about it. And it's hard to do! And lo and behold, if you go looking at the definitions of replacement in all the papers, lots of them get it wrong and "prove" false theorems.
I guess what I'm saying is that mathematicians have this attitude about "truth" as in the comic, but they are deluding themselves. We computer scientists working with proof formalization know all the shortcuts and intuitive leaps they're taking.
Today I just had to chime in about my own research experience with proofs. I used to be in grad school doing mathematics, we had it drilled into our heads what proofs are and aren't. Then I got interested in machine checkable proofs and switched to computer science.
The amazing thing is that standard "rigorous" mathematical proofs are usually full of holes! It sounds crazy, but if you learn a computerized proof assistant system like Coq and start doing machine checkable proofs, you realize how much more work it is to get all the details right.
For example, "paper proofs" might say something like "replace every X with Y in term T". In the machine checkable version, you have to define the replacement operator, then prove lots of properties about it. And it's hard to do! And lo and behold, if you go looking at the definitions of replacement in all the papers, lots of them get it wrong and "prove" false theorems.
I guess what I'm saying is that mathematicians have this attitude about "truth" as in the comic, but they are deluding themselves. We computer scientists working with proof formalization know all the shortcuts and intuitive leaps they're taking.
 gmalivuk
 GNU Terry Pratchett
 Posts: 26414
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: a note on mathematical proofs
nwhitehe wrote:For example, "paper proofs" might say something like "replace every X with Y in term T". In the machine checkable version, you have to define the replacement operator, then prove lots of properties about it.
I'd say that's more a limitation of computers than of paper proofs.
The step you quote is pretty basic in stuff dealing with formal logic. The thing is, once someone proves it can be done, the rest of us use it without reproving it. That doesn't mean we're all doing it wrong, it just means we're not reinventing the wheel every single time, because that would be, well, tedious and stupid.
 superiority
 Posts: 29
 Joined: Mon Dec 25, 2006 2:14 pm UTC
 Location: location is a social construct: rise up, throw off your geographical shackles!
 Contact:
A teacher at my school takes the position that maths is a form of philosophy and inherently ambiguous. I've attempted to convince her that 0.(9) is equal to 1, using various proofs and exhortations to reason.
She tells me that my conviction is evidence that I'm adhering to a sort of mathematical dogmatic religion.
She says that one should never stop questioning received wisdom. As far as I can tell, this means she views her own willful ignorance and inability to accept basic logic as a form of critical thinking.
It's the oddest thing.
She tells me that my conviction is evidence that I'm adhering to a sort of mathematical dogmatic religion.
She says that one should never stop questioning received wisdom. As far as I can tell, this means she views her own willful ignorance and inability to accept basic logic as a form of critical thinking.
It's the oddest thing.
easy challenge
a(b+c)=(ab)+(ac) obviously, this is a biased liberal attempt at socalled 'real' algebra. if you wanted to portray both sides of the issue, you must also teach intellegent algebra, where a(b+c)=god.
 Gelsamel
 Lame and emo
 Posts: 8237
 Joined: Thu Oct 05, 2006 10:49 am UTC
 Location: Melbourne, Victoria, Australia
superiority wrote:A teacher at my school takes the position that maths is a form of philosophy and inherently ambiguous. I've attempted to convince her that 0.(9) is equal to 1, using various proofs and exhortations to reason.
She tells me that my conviction is evidence that I'm adhering to a sort of mathematical dogmatic religion.
She says that one should never stop questioning received wisdom. As far as I can tell, this means she views her own willful ignorance and inability to accept basic logic as a form of critical thinking.
It's the oddest thing.
Just sounds like she thinks nothing is provable, did she actively deny 0.999... = 1 or did she just say you were following dogma when you quoted proofs for 0.999... = 1 from off the net?
"Give up here?"
 > No
"Do you accept defeat?"
 > No
"Do you think games are silly little things?"
 > No
"Is it all pointless?"
 > No
"Do you admit there is no meaning to this world?"
 > No
 > No
"Do you accept defeat?"
 > No
"Do you think games are silly little things?"
 > No
"Is it all pointless?"
 > No
"Do you admit there is no meaning to this world?"
 > No
After reading through this thread, I'm surprised noone has brought up Girard's linear logic. Preservation of hypotheses precludes the distribution of one (in the given example, 'a') over two subterms. Specifically, we require that (in the tensorial case):
So that, in fact, a(b+c) = (ab)+c
Code: Select all
 init  init
a  a b  b
 xR  init
a , b  (a x b) c  c
 +L
a , (b + c)  (a x b) , c
 +R
a , (b + c)  (a x b) + c
 xL
a x (b + c)  (a x b) + c
So that, in fact, a(b+c) = (ab)+c

 Posts: 8
 Joined: Sat May 19, 2007 6:07 am UTC
Gelsamel wrote:Nothing can be proven universal, even math has it's axioms.
Sure, a(b+c) = (ab)+(ac) in our math systems, but it's based on axioms about multiplication and addition.
You could, in fact, set up a mathematical system where the above equation DOESN'T hold.
Wait a minute, it IS a universal truth in the context of those commonly held axioms. One can only work in pure math to a certain extent before it becomes ridiculous. What you're saying is just like claiming that the Declaration of independence could actually be a religious text telling us to rape our sisters as long as you don't use an English dictionary to define all the vocabulary. While sure, this could be true, it was written in the context of "normal" English vocabulary. The distributive law was also written in a specific context, and it was not meant to be applied and (dis)proven under other systems. Go ahead and argue that the context it was written in is not the best one to be using, but don't drag the distributive law into it. It wasn't meant to live in such conditions, but it holds strong under those which we use today.
 Gelsamel
 Lame and emo
 Posts: 8237
 Joined: Thu Oct 05, 2006 10:49 am UTC
 Location: Melbourne, Victoria, Australia
If the axioms are false then so is the distributive law, since you cannot prove axioms you cannot prove the distributive law. However this doesn't require the absence of absolute truths (obviously), just states that anything is unprovable as absolute/universal.
Edit: And in the discussion of Absolutes and being pedantic and all that, saying that a(b+c) = (ab)+(ac) is universal under certain axioms is as useless as me saying that I'm the best person in the world under my opinion.
Edit: And in the discussion of Absolutes and being pedantic and all that, saying that a(b+c) = (ab)+(ac) is universal under certain axioms is as useless as me saying that I'm the best person in the world under my opinion.
"Give up here?"
 > No
"Do you accept defeat?"
 > No
"Do you think games are silly little things?"
 > No
"Is it all pointless?"
 > No
"Do you admit there is no meaning to this world?"
 > No
 > No
"Do you accept defeat?"
 > No
"Do you think games are silly little things?"
 > No
"Is it all pointless?"
 > No
"Do you admit there is no meaning to this world?"
 > No
 superiority
 Posts: 29
 Joined: Mon Dec 25, 2006 2:14 pm UTC
 Location: location is a social construct: rise up, throw off your geographical shackles!
 Contact:
Gelsamel wrote:Just sounds like she thinks nothing is provable, did she actively deny 0.999... = 1 or did she just say you were following dogma when you quoted proofs for 0.999... = 1 from off the net?
Well, actually, the first two I showed her (the completeness of the real numbers, and the algebraic proof) I came up with on my own, never having seen the problem before. And yes, she is actively denying, although as near as I can tell, her argument mainly consists of "maybe not, though".
superiority wrote:A teacher at my school takes the position that maths is a form of philosophy and inherently ambiguous. I've attempted to convince her that 0.(9) is equal to 1, using various proofs and exhortations to reason.
She tells me that my conviction is evidence that I'm adhering to a sort of mathematical dogmatic religion.
She says that one should never stop questioning received wisdom. As far as I can tell, this means she views her own willful ignorance and inability to accept basic logic as a form of critical thinking.
It's the oddest thing.
Your teacher sounds like an idiot. This sounds very similar to how many creationists like to claim that they are in fact the ones being "real skeptics" or something similar to that. Anecdotally, .99... =/= 1 people often suffer from many of the problems in in critical thinking as believers in various pseudoscientific or superstitious ideas. See this recent article in Science for related observations.

 Posts: 1
 Joined: Fri May 18, 2007 3:44 pm UTC
Re: a note on mathematical proofs
gmalivuk wrote:I'd say that's more a limitation of computers than of paper proofs.
The step you quote is pretty basic in stuff dealing with formal logic...
I didn't put any details in my example, but I was thinking of replacement in a term in some kind of calculus of terms, not replacement in the proof steps themselves. In any case, you're right that substitution and replacement is well understood and shouldn't need to be reproved every time; but mathematicians are much too cavalier about proof reuse in new contexts. The reason is that it's boring, but necessary. So I would say that is a limitation of humans rather than computers! Computers don't mind checking all the cases, even the boring ones.
JoshuaZ wrote:
No. Godel's result shows that an axiomatic system which is sufficiently powerful cannot be both consistent and complete. That says nothing about Arithmetic in any neoplatonic or similar sense.
No. Goedel's incompleteness theorem explicitly states that any theory rich enough to express Peano arithmetic is incomplete. And if there exists a proof of completeness of this theory then it's also inconsistent.
Actually, Goedel's proof is a rather complex method of formulating a selfreferring statement (via Goedel's numbers), something like: "This statement is false".
Re: "Certainty" Discussion
Iluvatar wrote:Edit: title text now reads: "a(b+c)=(ab)+(ac). Politicize that, bitches."
Well, this statement is blatantly false. This equality holds for rings and fields.
But it certainly doesn't hold for all algebraic structures.
For example, 10^9(10 + (9))=10^10 + (9*10^9) doesn't hold if we make calculations using signed 32bit integers.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Well, really it expresses the statement, "this statement is unprovable" rather than "this statement is false" as Peano Arithmetic (PA) can only reference its own syntax, not its own semantics, and provability is a syntactical property, whereas truth is a semantic one.
And its not true that any theory which can express addition and multiplication is incomplete; the theory of algebraically closed fields is a complete consistent theory that deals with both. It is also not true that any theory powerful enough to encode PA is incomplete; there are complete extensions of PA. What is incomplete, by Godel's theorem, is any consistent theory which can be axiomatized by a computably enumerable set of axioms and which is powerful enough to prove standard results about arithmetic.
There are a lot of misconceptions about Godel's incompleteness theorem out there. One book I've seen recommended is Torkel Franzen's book, Godel's theorem: an incomplete guide to its use and abuse which discusses many of the erroneous claims about its statement and implications. Unfortunately I haven't had a chance to look at it yet, but it would probably be a good way of finding out what Godel's theorems really mean, and what they do not.
And its not true that any theory which can express addition and multiplication is incomplete; the theory of algebraically closed fields is a complete consistent theory that deals with both. It is also not true that any theory powerful enough to encode PA is incomplete; there are complete extensions of PA. What is incomplete, by Godel's theorem, is any consistent theory which can be axiomatized by a computably enumerable set of axioms and which is powerful enough to prove standard results about arithmetic.
There are a lot of misconceptions about Godel's incompleteness theorem out there. One book I've seen recommended is Torkel Franzen's book, Godel's theorem: an incomplete guide to its use and abuse which discusses many of the erroneous claims about its statement and implications. Unfortunately I haven't had a chance to look at it yet, but it would probably be a good way of finding out what Godel's theorems really mean, and what they do not.
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
"With math, all things are possible." —Rebecca Watson
Cyberax wrote:JoshuaZ wrote:
No. Godel's result shows that an axiomatic system which is sufficiently powerful cannot be both consistent and complete. That says nothing about Arithmetic in any neoplatonic or similar sense.
No. Goedel's incompleteness theorem explicitly states that any theory rich enough to express Peano arithmetic is incomplete. And if there exists a proof of completeness of this theory then it's also inconsistent.
Actually, Goedel's proof is a rather complex method of formulating a selfreferring statement (via Goedel's numbers), something like: "This statement is false".
To the first paragraph not exactly. The second paragraph is also not exactly correct. There seems to be an issue here involving the fact that there are two theorems in question. The first theorem says roughly what you stated although not exactly (closer to what I stated where sufficiently powerful means can model Peano arithmetic (actually you don't even need all Peano arithmetic, you can do with slightly weaker than that)). But it definitely does not say that "any theory rich enough to express Peano arithmetic is incomplete" It says that that is the case if the theory is 1) axiomatizable (that is that statements in the theory are recursively enumerable) then it is either inconsistent or incomplete. (Inconsistent systems are trivially complete unless we weaken our rules of inferrence).
The second statement you made that" Goedel's proof is a rather complex method of formulating a selfreferring statement (via Goedel's numbers), something like: `This statement is false'" is also wrong. The relevant Godel sentence is much closer to being equivalent to "This sentence is unprovable in theory T".
There are number of good works to get a better handle on this subject. I've been told that Franzen's "GÃ¶del's Theorem: An Incomplete Guide to its Use and Abuse" is a good primer although I haven't read it myself.
Edit: Original post had "Inconsistent systems are trivially incomplete unless we weaken our rules of inferrence" should have been trivially complete.  Nov 11, 2007
Last edited by JoshuaZ on Mon Nov 12, 2007 3:17 am UTC, edited 1 time in total.
skeptical scientist wrote:Well, really it expresses the statement, "this statement is unprovable" rather than "this statement is false" as Peano Arithmetic (PA) can only reference its own syntax, not its own semantics, and provability is a syntactical property, whereas truth is a semantic one.
And its not true that any theory which can express addition and multiplication is incomplete; the theory of algebraically closed fields is a complete consistent theory that deals with both. It is also not true that any theory powerful enough to encode PA is incomplete; there are complete extensions of PA. What is incomplete, by Godel's theorem, is any consistent theory which can be axiomatized by a computably enumerable set of axioms and which is powerful enough to prove standard results about arithmetic.
There are a lot of misconceptions about Godel's incompleteness theorem out there. One book I've seen recommended is Torkel Franzen's book, Godel's theorem: an incomplete guide to its use and abuse which discusses many of the erroneous claims about its statement and implications. Unfortunately I haven't had a chance to look at it yet, but it would probably be a good way of finding out what Godel's theorems really mean, and what they do not.
Wow, I didn't see your post when I replied. That's scarily similar to what I had to say (even down to recommending the same book and not having read the book). Are you sure you aren't me?
 Gelsamel
 Lame and emo
 Posts: 8237
 Joined: Thu Oct 05, 2006 10:49 am UTC
 Location: Melbourne, Victoria, Australia
Cyberax wrote:JoshuaZ wrote:
No. Godel's result shows that an axiomatic system which is sufficiently powerful cannot be both consistent and complete. That says nothing about Arithmetic in any neoplatonic or similar sense.
No. Goedel's incompleteness theorem explicitly states that any theory rich enough to express Peano arithmetic is incomplete. And if there exists a proof of completeness of this theory then it's also inconsistent.
Actually, Goedel's proof is a rather complex method of formulating a selfreferring statement (via Goedel's numbers), something like: "This statement is false".
No Goedel's Proof is a POKEMAN!
"Give up here?"
 > No
"Do you accept defeat?"
 > No
"Do you think games are silly little things?"
 > No
"Is it all pointless?"
 > No
"Do you admit there is no meaning to this world?"
 > No
 > No
"Do you accept defeat?"
 > No
"Do you think games are silly little things?"
 > No
"Is it all pointless?"
 > No
"Do you admit there is no meaning to this world?"
 > No
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
JoshuaZ wrote:Wow, I didn't see your post when I replied. That's scarily similar to what I had to say (even down to recommending the same book and not having read the book). Are you sure you aren't me?
Did you just read the review in The Bulletin of Symbolic Logic? If so, that's probably why  after all, it just came out so it was probably on both of our minds.
Or maybe I'm secretly your evil twin.
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
"With math, all things are possible." —Rebecca Watson
 EradicateIV
 Posts: 361
 Joined: Mon Mar 19, 2007 7:33 pm UTC
 Location: Brownsville, PA
 Contact:
skeptical scientist wrote:JoshuaZ wrote:Wow, I didn't see your post when I replied. That's scarily similar to what I had to say (even down to recommending the same book and not having read the book). Are you sure you aren't me?
Did you just read the review in The Bulletin of Symbolic Logic? If so, that's probably why  after all, it just came out so it was probably on both of our minds.
Or maybe I'm secretly your evil twin.
No, I saw the recent review on mathscinet which praises with faint damnation. I already have a twin; you must be an evil triplet.
 Gelsamel
 Lame and emo
 Posts: 8237
 Joined: Thu Oct 05, 2006 10:49 am UTC
 Location: Melbourne, Victoria, Australia
EradicateIV wrote:There is truth.
Proof by Contradiction:
Let's assume there is no truth. This assumption can not be true because there is no truth. Thus, there is truth.
QED.
(Please, tear this apart, I thought of this in 5 seconds).
Prove the logic that you've used to come to this conclusion as a universal truth and I will accept that argument.
"Give up here?"
 > No
"Do you accept defeat?"
 > No
"Do you think games are silly little things?"
 > No
"Is it all pointless?"
 > No
"Do you admit there is no meaning to this world?"
 > No
 > No
"Do you accept defeat?"
 > No
"Do you think games are silly little things?"
 > No
"Is it all pointless?"
 > No
"Do you admit there is no meaning to this world?"
 > No

 Posts: 3
 Joined: Sat Jan 13, 2007 7:02 am UTC
skeptical scientist wrote:Well, really it expresses the statement, "this statement is unprovable" rather than "this statement is false" as Peano Arithmetic (PA) can only reference its own syntax, not its own semantics, and provability is a syntactical property, whereas truth is a semantic one.
Yes, thanks for correction. But I did say 'like'
And its not true that any theory which can express addition and multiplication is incomplete; the theory of algebraically closed fields is a complete consistent theory that deals with both.
Yes, I know.
Another interesting complete theories are geometry and firstorder logic.
It is also not true that any theory powerful enough to encode PA is incomplete; there are complete extensions of PA.
If you are referring to closed fields theory  it can't express PA, because we have no way to express integers (other than 0 and 1).
There are a lot of misconceptions about Godel's incompleteness theorem out there. One book I've seen recommended is Torkel Franzen's book, Godel's theorem: an incomplete guide to its use and abuse which discusses many of the erroneous claims about its statement and implications.
Yes, my university logic teacher liked to say that there should be the third Goedel theorem: "Any popular interpretation of Goedel theorem is provably incomplete and misleading".
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Cyberax wrote:It is also not true that any theory powerful enough to encode PA is incomplete; there are complete extensions of PA.
If you are referring to closed fields theory  it can't express PA, because we have no way to express integers (other than 0 and 1).
No, I'm referring to complete extensions of PA (assuming it's consistent)  i.e. you take the theory of PA, and add consistent statements to it until it is complete. Godel's theorem tells you this can't be done by adding a computable or even computably enumerable set of axioms, but it is theoretically possible. You just list all of the sentences of the language of arithmetic, and add each, or its negation, to your theory; at least one of the two must be consistent, so this can be done until every sentence or its negation is in your theory.
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
"With math, all things are possible." —Rebecca Watson
 rosethornn
 Posts: 2
 Joined: Sun May 20, 2007 1:57 pm UTC
superiority wrote:A teacher at my school takes the position that maths is a form of philosophy and inherently ambiguous. I've attempted to convince her that 0.(9) is equal to 1, using various proofs and exhortations to reason.
She tells me that my conviction is evidence that I'm adhering to a sort of mathematical dogmatic religion.
She says that one should never stop questioning received wisdom. As far as I can tell, this means she views her own willful ignorance and inability to accept basic logic as a form of critical thinking.
It's the oddest thing.
I think what she's trying to argue is that certainty is never an attainable quality for human beings, as the mind is all we have to perceive and analyse any statement we are presented with. It's a basic Cartesian arguement.
Even rational truths with no perceivable flaws still have a minute chance of being a product of hallucination or deception. Descartes gives the example of the "brain in a vat" (think "The Matrix" and you've pretty much got it). As we cannot be certain whether our world is indeed 'reality' or a deception from an outside source, we equally cannot be sure that our mind isn't being played upon. If your mind truly was in such a helpless state, it's easy to conclude that whoever is tricking it into belief in the world can also alter it's perceptions of a priori truths as well.

 Posts: 30
 Joined: Wed Feb 28, 2007 4:46 pm UTC
 Location: Trondheim, Norway
skeptical scientist wrote:No, I'm referring to complete extensions of PA (assuming it's consistent)  i.e. you take the theory of PA, and add consistent statements to it until it is complete. Godel's theorem tells you this can't be done by adding a computable or even computably enumerable set of axioms, but it is theoretically possible. You just list all of the sentences of the language of arithmetic, and add each, or its negation, to your theory; at least one of the two must be consistent, so this can be done until every sentence or its negation is in your theory.
The problem is that you have to choose between adding a sentence or its negation.
If you specify a method to make this choice, you are vulnerable to GÃ¶dels attack and your theory has to inconsistent (since it can't be incomplete)
On the other hand, if you don't specify a method to make this choice, you don't really have a theory.
Another reason to reject the Axiom of Choice.
This is not true.
Return to “Individual XKCD Comic Threads”
Who is online
Users browsing this forum: No registered users and 24 guests