Could someone who knows what they are talking about list, in layman-ish terms, the various non-mathematical ways of expressing Godel's Theorum. I have some understanding of it so one-liners will do.

Many thank for any answers.

Given a system of axioms (math or logic), statements can be created within that system that can never be proven or disproven within that system. Enlarging the system may get rid of some, but will create others.
Here's a simple such statement:
This statement is false. Now prove it is true, or false, based on looking at it logically - it is both, which is a contradiction, so it is neither, which is also a contradiction. etc.
Aaron

Sorry Aaron, its a bit more complicated than that.

For one thing, the example you give would not be considered a "statement" since it contradicts itself. It would BE neither true nor false in any system of axioms.

It is actually quite easy to construct "axiom systems" in which any statement can be either proved or disproved (many "college geometry" texts include examples of finite geometries in which the axioms assert that "there exist exactly 3 points" in which every statement can be either proved or disproved).

What Goedel (it's actually "o umlaut" which, when you don't have an umlaut is normally shown as "oe") showed was that in any consistent system large enough to encompass the natural numbers, there exist statements (which ARE either true or false) such that it is impossible to PROVE which is true.

Thanks. But I've come across many derivations and I'm wondering how many others there are. For instance:

-No completely coherent axiomatic system can be complete.

-Every complete axiomatic system must contain an undecidable proposition.

-There are always true statements which cannot be shown to be true within the system in which they are expressed, whatever the system.

-In any (sufficently powerful) system there are true statements which must be false to be true.

Also the undecidable statements of Goedel seem to be interpreted as logical contradictions by some. Is this correct? Is it because an undecidable question must come in the form of a logical contradiction (in the terms of the system)?

If this is so it seems to suggest that every compete logical system must contain a contradiction, which seems a much stronger thing to say than that it should simply be incomplete.

How much of this really does follow from Goedel?

Originally posted by Canute
Thanks. But I've come across many derivations and I'm wondering how many others there are. For instance:

-No completely coherent axiomatic system can be complete.

-Every complete axiomatic system must contain an undecidable proposition.

-There are always true statements which cannot be shown to be true within the system in which they are expressed, whatever the system.

for any system which is complicated enough to contain the integers, these three statements are true, if you remove the word complete from the second statement. this is the incompleteness theorem. it is not true that there exists no complete axiomatic system, there are some simpler systems which are complete.

those three statement above are all equivalent, with the correction that you remove the word complete from the second statement. as it stands, the second statement is simply contradictory. since the definition of "complete" is an axiomatic system under which all statements are decidable, that statement makes no sense.




-In any (sufficently powerful) system there are true statements which must be false to be true.

gödel had a second theorem, the inconsistency theorem. it states that it is impossible to prove that the axiomatic system contains no contradictions.

note that this does not mean that the system must contain contradictory statements. only that you cannot prove that it does not.

and again this only applies to certain systems. there are simpler axiomatic systems that are complete and consistent.




Also the undecidable statements of Goedel seem to be interpreted as logical contradictions by some. Is this correct? Is it because an undecidable question must come in the form of a logical contradiction (in the terms of the system)?


No! an undecidable statement is not the same as a contradiction! an undecidable statement is one that is true, but does not follow from the axioms. a contradiction is a statement that is both true and false.



If this is so it seems to suggest that every compete logical system must contain a contradiction, which seems a much stronger thing to say than that it should simply be incomplete.

wrong. see above.


How much of this really does follow from Goedel?
all of it.

to recap: any system which is complicated enough to contain the infinite natural numbers must be incomplete. that means there are undecidable statements.

also, there can be no proof that the system if consistent. that means that there could be (but don t have to be) statements which are both true and false.

most of us believe that the modern mathematical axiomatic system is not consistent. it would be nice if there were a proof of this fact, but gödel tells us this is impossible. just because there can be no proof, does not mean it is not true. hopefully our system is consistent, and does not contain any statements that are simultaneously true and false. if any such statements are found, then the axioms will have to be modified.

on the other hand, if an undecidable statement is found (actually, a few are known already), this will not force us to change our axioms.

and, like hallsofivy mentioned, there are axiomatic systems which are both consistent and complete. one studies some examples in abstract geometry. gödel s theorems only apply to certain more complicated axiomatic systems.

A couple of "corrections" to Lethe:


-Every complete axiomatic system must contain an undecidable proposition.

Every CONSISTENT axiomatic system (sufficiently powerful to include the natural numbers) must contain an undecidable proposition. I believe that "there are no undecidable propositions" is the definition of "complete". A system is "consistent" as long as it is not possible to both prove and disprove the same statement.

Being both consistent and complete (you can either prove or disprove any statement, you can't do both) is the "desiderata" for an axiom system: Goedel proved that for sufficiently powerful systems you CAN'T have both!

From the point of view of a "working mathematician", saying an axiom system is not complete is like saying it isn't perfect. Saying it is inconsistent is saying it is useless!

By the way, since it is impossible to define "true" and "false" for an abstract system independently of "proof" I prefer to say that "complete" means "every statement can be either proven or disproven" rather than "every true statement can be proven".

Originally posted by HallsofIvy
A couple of "corrections" to Lethe:



Every CONSISTENT axiomatic system (sufficiently powerful to include the natural numbers) must contain an undecidable proposition. I believe that "there are no undecidable propositions" is the definition of "complete". A system is "consistent" as long as it is not possible to both prove and disprove the same statement.


oops. yeah i missed that. thanks hallsofivy. i went back and fixed my mistake. as you say, in a complete axiomatic system, every statement is decidable, by definition.



Being both consistent and complete (you can either prove or disprove any statement, you can't do both) is the "desiderata" for an axiom system: Goedel proved that for sufficiently powerful systems you CAN'T have both!


now i would like to slightly modify your statement. gödel s theorem does not say that we can t have both completeness and consistency. in fact, gödel has little to say about what systems can be consistent. instead, he only talks about proofs of consistency.

completeness, you can never have.

consistency, you can have, but you can never know you have it.

so using your notions about axiomatic systems that you described above (i think that s a great way to think of these concepts), our axiomatic system can never be perfect. furthermore, it is probably not useful, but we can never know for sure that it is not completely useless.

I accept your corrections except for one thing:


completeness, you can never have.

If a system is in-consistent then you can prove ANYTHING (and its contradiction) so it IS complete.

A system is complete if and only if it is N0T consistent!

Of course, you can never prove which!

Originally posted by HallsofIvy
If a system is in-consistent then you can prove ANYTHING (and its contradiction) so it IS complete.

A system is complete if and only if it is N0T consistent!

Of course, you can never prove which!

ok, that s a good point, that ~ consistent --> complete. this does seem to be true. if the system is not consistent, then you can prove any statement, so every statement is true....


but if ~ consistent --> complete. this then by contraposition, ~ complete --> consistent. and since we know our system (say, ZFC, or peano) is not complete, we can then infer that it is then consistent? this seems to contradict gödel s inconsistence theorem, because here we have a proof of the consistency of the theorem, using gödel s completeness theorem, and the inconsistency theorem states that there can be no proof of consistency....

i was under the impression that the two theorem s were independent. am i wrong? or is there a mistake in the above reasoning?

To HallsOfIvy:
I agree with you in that "This is not true" is not a translation of Godel to english but a translation of Tarski to english and that "This is an unprovable sentence of number theory" is a much better way of talking about godel. I disagree with your conclusion that the sentence is 'meaningless'.

leaving aside your inconclusive arguments that “this sentence is false” is meaningless, let’s suppose that it is indeed meaningless. Does that really enable you to escape the Liar Paradox? At first sight, it does. However, there’s a related paradox – I think it’s been called the Strong Liar – that it does not escape. To wit:



“This sentence is false or meaningless.”



Plainly, this lands you back in exactly the same kind of problem. You can’t escape here by saying that the sentence is meaningless, because if it’s meaningless, then it’s true (and if true, then false or meaningless, and if false or meaningless, then not true).



In addition, the Strong Liar exemplifies a strategy that can be reiterated to deal with any response offered. Suppose you say that “this sentence is false or meaningless” is not true or false or meaningless, but is just a string of words that doesn’t manage to say anything. That succumbs to the Stronger Liar:

“This sentence is false or meaningless or is just a string of words that doesn’t manage to say anything.”



And so on.

“This sentence is false or meaningless.”

can u incorporate comment on the sentence itself into that very sentence..?

"This sentence is false" - logically invalid construction of sentence. i don't think in maths formulae any such expression is possible.. it is more of a problem of language. grammatically ok but logically immpossible.

Is it possible to turn all this on its head and say:

Using the terms and rules of any (complex etc.) consistent system it is possible to construct a proposition that is paradoxical within the system.

Or - In any (complex) dualistic system it is possible to construct questions which do not have yes or no answers.

I went back and reread my posts and I don't see anywhere that I said that the sentence "This sentence is false" was "meaningless". I did say that logic only deals with "statements" which are, by definition, sentences that can be assigned (at least theoretically) a true or false value.

Sorry I must have mis read your post... Anyway my argument still should work with what you did write because it is the same as saying it is meaningless with just more words. I will rephrase it as follows:

You wrote:
For one thing, the example you give would not be considered a "statement" since it contradicts itself. It would BE neither true nor false in any system of axioms.

Strengthened Liar Paradox:
"This sentence is either false or is neither true nor false"
If it is not true nor false then it is true (contradiction).
If it is false then it is true (contradiction).
If it is true then it is either false or meaningless (contradiction).

Anyway to try to prove I understand your point I will raise a question to you and attempt to answer it. What is causing the contradiction? It is either of two things: self reference or truth.
Sense Godel proved that self reference can occur in number theory, it can't be that. So it must be truth that is causing this problem. This does not mean that there is no truth of course, it only means that this system we are using can not define truth within the system. There may be a way to define truth outside the system. Tarski proved this happens in math and spent the rest of his life trying to create a way to define truth for math outside the context of number theory where the problem is created. If you don't believe me I can give you links to pdfs that explain tarskis proof in detail but I don't want to spam the whole group.

Originally posted by Cybermorphic
Strengthened Liar Paradox:
"This sentence is either false or is neither true nor false"
If it is not true nor false then it is true (contradiction).
If it is false then it is true (contradiction).
If it is true then it is either false or meaningless (contradiction).

Is it not possible that these problems arise simply because dualism is false? In other words that reality, the real reality, is not dualistic, and that therefore any logically consistent but epistemologically dual model of it must ultimately be found to be illogical. This would explain, for instance, the impotence of metaphysics to produce yes or no answers to deep questions about reality, because instead of accepting that we are asking the wrong kind of dualist questions we stubbornly fight for only one dualistic answer to be right. This is what Goedel's Theorums suggest to me anyway.

In this way the paradox above can be resolved, since the sentence may be either false or true.

Here is a feeble attempt to define truth in a system:
TRUTH=TRUTH

Where TRUTH is a correspondence with all of reality.
This system has one axiom: TRUTH=TRUTH.
This system has one rule: TRUTH=TRUTH is the only well formed theorem of the system.


So I think you can define truth... and there probably is a better way than this, but heh this works. If TRUTH does in fact equal TRUTH in reality it would be contained in truth. If TRUTH did not equal TRUTH then it would also be in TRUTH so this system is therefore true but posibly contradictory. So this in a way proves that truth does exist but does not prove if truth is a contradiction.

Sorry, you lost me there.

hallsofivy? no comment on my last post?

If you are referring to
[QUOTE]but if ~ consistent --> complete. this then by contraposition, ~ complete --> consistent. and since we know our system (say, ZFC, or peano) is not complete, we can then infer that it is then consistent? this seems to contradict gödel s inconsistence theorem, because here we have a proof of the consistency of the theorem, using gödel s completeness theorem, and the inconsistency theorem states that there can be no proof of consistency.... [QUOTE]

it is certainly true that ~complete-> consistent. Now how can we "know our system (say, ZFC, or peano) is not complete?
Essentially Goedel (How are you getting that umlaut) says that any system (always with the proviso "large enough to include the natural numbers) is EITHER inconsistent or complete and we cannot prove which.

OK, i see what you re saying. for some reason, i was under the impression that gödel had two theorems, that were independent.

apparently i was mistaken.

i thought that the incompleteness theorem said that it is known that the system is incomplete.


<hr>

i have a mac, so getting umlauts and such is pretty easy, it s just opt+u.

look at the mathworld (http://mathworld.wolfram.com/GoedelsIncompletenessTheorem.html) page.

it says:

<ol>
<li>all consistent axiomatic formulations of number theory include undecidable propositions</li>
<li>any formal system that is interesting enough to formulate its own consistency can prove its own consistency iff it is inconsistent.</li>
</ol>

<hr>

so the first theorem says "if the system is consistent, then in is incomplete", or in other words "consistent --> ~ complete"

the second says "there can be no proof of consistency"


but nowhere does it say that the inverse statement "~ consistent --> complete", which is what i used in my little proof above, to show that the system must be consistent.

in fact, as i think about it, i no longer agree with this statement. that is, i no longer agree with this claim:

Originally posted by HallsofIvy
If a system is in-consistent then you can prove ANYTHING (and its contradiction) so it IS complete.

i now believe that even an inconsistent system could be incomplete.

imagine that i take some incomplete consistent axiom system. i construct a new axiom system by adding to my system a new axiom which is the negation of one of the original axioms. immediately, this system is inconsistent, and now all my decidable statements can be proved along with their negations.

but the undecidable statements? it seems to me that they could remain undecidable. if the original axioms can never arrive at the undecidable statement (or its negation), then the negations of the axioms can also never arrive at the undecidable statement (or its negation).

the proof i gave above, that the system is consistent seems to be circular. so i will abandon it.

my point, i don t agree that any inconsistent system must be complete.

But it is a true statement, in any system, that, for any statements a and b,

(a and ~a)-> b

If it is possible to prove both a and ~a (not a) then it is possible to prove ANY statement. There can be no undecidable statements. That has been my point all along.

Lethe - You said earlier that "An undecidable statement is not the same as a contradiction! an undecidable statement is one that is true, but does not follow from the axioms. a contradiction is a statement that is both true and false."

This seems incorrect. An undecidable statement is not true within the system, only by reference to a further system or to intuition. Therefore it is surely a contradiction within the system, being either both true and false, or neither.

Originally posted by HallsofIvy
But it is a true statement, in any system, that, for any statements a and b,

(a and ~a)-> b

If it is possible to prove both a and ~a (not a) then it is possible to prove ANY statement. There can be no undecidable statements. That has been my point all along.

HallsOfIvy-

oh yeah. false implies everything. OK. got it. i guess i m in agreement now.

Canute-
No.

Lethe - I see that I phrased my previous point badly.

As an undecidable statement is not provable true of false within the system, only by reference to a further system or to intuition, it is surely a contradiction within the system, it being in principle impossible for it to be proved true or false. Is that not a contradiction? Is it not equivalent to saying that 'this sentence is true and false'?

Originally posted by Canute
Lethe - I see that I phrased my previous point badly.

As an undecidable statement is not provable true of false within the system, only by reference to a further system or to intuition, it is surely a contradiction within the system, it being in principle impossible for it to be proved true or false. Is that not a contradiction? Is it not equivalent to saying that 'this sentence is true and false'?

Canute -

no this is incorrect. i m not sure how to address this point. why do you think not decidable is "surely a contradiction". it s simply not true.

Originally posted by lethe
Canute - no this is incorrect. i m not sure how to address this point. why do you think not decidable is "surely a contradiction". it s simply not true.
I would have thought that it could be said that the sentence G is undecidable precisely because it contradicts itself, if it is true it is false, and if false them true. Is this not a self-contradiction?

a contradiction is a logical falacy, which is different than an undecidable statement

Is not a sentence that contradicts itself a logical fallacy? Isn't it precisely because G is a logical fallacy that we know it is true? How else could we know?

Originally posted by Canute
I would have thought that it could be said that the sentence G is undecidable precisely because it contradicts itself, if it is true it is false, and if false them true. Is this not a self-contradiction?
this is not the definition of undecidable. undecidable does not mean "both true and false". undecidable means "does not follow from the axioms".

for a statement to be a contradiction, i need to show that it follows from the axioms, and is therefore true. then i need to show that its negation also follows from the axioms, and therefore the statement is also false. now the statement is both true and false, and is a contradiction. note that i had to connect it to the axioms in two different ways.

an undecidable statement, on the other hand, does not have any connection to the axioms. it does not follow from the axioms, nor does it s negation. it is not a contradiction. it can be true, but it is not "both true and false" the way a contradiction is.

to recap: undecidable means doesn t follow from the axioms. contradiction means both the statement and it s negation follow from the axioms. you can see that the two words have very different meanings.

Sorry but I don't get this. I thought the whole point of a Goedel statement was that it DID follow from the axioms. If it did not then it wouldn't be a theorum of the system and would prove nothing about it.

Originally posted by Canute
Sorry but I don't get this. I thought the whole point of a Goedel statement was that it DID follow from the axioms. If it did not then it wouldn't be a theorum of the system and would prove nothing about it.

what is a goedel statement? do you mean undecidable statement? this is a pretty subtle subject so try to keep your terminology correct.

assuming you re talking about an undecidable statement, then you re correct. it doesn t follow from the axioms, so it is not a theorem. you ve got it.

Originally posted by lethe
what is a goedel statement? do you mean undecidable statement? this is a pretty subtle subject so try to keep your terminology correct.

assuming you re talking about an undecidable statement, then you re correct. it doesn t follow from the axioms, so it is not a theorem. you ve got it.
perhaps I should have said Goedel sentence, but this seems a bit picky, statement seems to mean the same thing.

As I understand it a Goedel sentence for any system must be derived from the axioms of that system. It is therefore a theorum of the system, albeit an undecidable or contradictory one.

If it was not a theorum of the system Goedel theorums wouldn't be worth discussing. Proof of the truth or falsity of G(F) lies outside of the F, but not G(F) itself, that's surely why it's called G(F), and not G(not F).

Originally posted by Canute
perhaps I should have said Goedel sentence, but this seems a bit picky, statement seems to mean the same thing.

As I understand it a Goedel sentence for any system must be derived from the axioms of that system. It is therefore a theorum of the system, albeit an undecidable or contradictory one.

If it was not a theorum of the system Goedel theorums wouldn't be worth discussing. Proof of the truth or falsity of G(F) lies outside of the F, but not G(F) itself, that's surely why it's called G(F), and not G(not F).

sentence, statement, whatever, i don t know what you mean. what is a goedel statement/sentence? do you mean an undecidable sentence?

Originally posted by lethe
sentence, statement, whatever, i don t know what you mean. what is a goedel statement/sentence? do you mean an undecidable sentence?
Yes. As in 'this statement is not true' or as signified by G(T) or
G(F) and so on.

Originally posted by Canute
Yes. As in 'this statement is not true' or as signified by G(T) or
G(F) and so on.

i have no idea what the G(T) G(F) notation means. if, when you say goedel statement, you mean a statement that is not true, then i don t know what exactly you re getting at.

here is a statement that is not true: 1 = 2. is that a goedel statement? you need to explain your notations a little better i think.

"This statement is not true" is definitely not a "Goedel" statement. What Goedel showed was that there must exist a statement which is CLEARLY either true of false: the fact of its being true or false does not raise a contradiction; but such that a PROOF that it is either true of false does raise a contradiction.

He did that by developing the "Goedel numbering": a way of assigning a unique number to every statement or string of statements (such as a proof) and then exhibiting a statement about the Goedel number of a statement such that if it were possible to prove it true, the Goedel number of the proof would contradict the statement itself.

I may be stating that last part wrong, its been a while since I read about the proof but the point is that the statement itself is clearly either true of false. It is the PROOF that the statement is true (or false) that raises the contradiction. (And such a statement is certainly not as trivial as "This statement is not true"!)

Originally posted by lethe
i have no idea what the G(T) G(F) notation means. if, when you say goedel statement, you mean a statement that is not true, then i don t know what exactly you re getting at.

here is a statement that is not true: 1 = 2. is that a goedel statement? you need to explain your notations a little better i think.

I mean what I thought everybody meant, namely a statement that is not provable true or false within the system. Eg. 'This system will never prove whether G is true or not'. 'G' stands for the Goedel sentence of the system and the system is any sufficiently complex axiomatic system of reasoning. G is neither true nor false within the system, but can be seen to be true by some larger system, including human intuition.

G is a provably a theorum of the system but provably undecidable within it since it is a contradiction, true if proved false and false if proved true.

I can't understand what I'm saying that is causing a problem.