# Truth and Justification in light of Godel

I was thinking about Godel's Incompleteness Theorem and was wondering if this is a fair conclusion: Godel seems to have demonstrated that within axiomatizations of arithmetic, that is of a sufficiently rich axiomatized system which could generate arithmetic, there are statements which can not be proven nor disproven as being theorems of the system in question but which are assumed nonetheless as being 'true.'
May I also conclude from this that as far as any notions of truth are concerned, Godel has effectively divorced the notion of justification (proof) from 'truth.?' If indeed there are statements which are true
but unprovable, then truth does not necessarily entail provability.

Does the assumption of truth for such theorems also maintain the logical consistency of those systems (ie. if we were to assume they were false, then that particular system would be inconsistent)?

Thanks and cheers, mrj

Last edited:

AKG
Homework Helper
These things aren't assumed to be true, they are true (in the standard model). The question is whether there are sentences in the language of number theory such that, given some recursive axiomatization of number theory, there is no proof for the sentence yet it is true in the standard model of number theory. Godel answers "yes". But that doesn't mean that these sentences aren't provable in second order logic, or aren't provable from set theory. But then we'd just ask the same questions about the completeness of set theory or second order logic. So yes, you could probably say that Godel showed given a reasonable set of axioms, there are some true statements that cannot be proven (note, however, that for every true statement, there is a reasonable set of axioms that proves the statement - there is just no single reasonable set that works for all true statements simultaneously). Mathematically speaking, this is an interesting result, but generally speaking, it is rather obvious. That is, there are things outside of math, for instance some facts about the past or about the physical world, that are true but that cannot be known or proven.

You have to be careful about what you mean by "systems". There is one standard interpretation of number theory. In any interpretation whatsoever, any given sentence is either true or false. Some of these statements which, when interpreted, are true are such that they cannot be proven from some given fixed set of axioms. It has nothing to do with maintaining consistency of the interpretations. If you're talking about consistency of the set of axioms, then again, no. If we required this sentences to be true to maintain the consistency of these axioms, then this set of axioms S, together with the negation of this sentence ~P, would form an inconsistent set S U {~P}. But if a set is inconsistent, we can derive a contradiction from it, so you could indeed prove S from P. The sentence P must be such that both S U {P} and S U {~P} are consistent for it to be true but unprovable from S.

Thanks for the clarification AKG.

mrj

It depends on how exactly you define "truth".

HallsofIvy
Homework Helper
semioticghost said:
It depends on how exactly you define "truth".
Which is why, in mathematics, it is better to talk about "validity" rather than "truth". Since every statement in mathematics is "if .... then....", often with the "if" part not explicitely stated, saying a statement is "true" may be incorrectly interpreted as saying the conclusion is false. It is better to say that an argument is "valid" rather than that a statement is "true".

AKG
Homework Helper
No, the whole of Godel's arguments are about truth and validity, and how they relate. Of course, it does depend on how you "define" truth, and I believe it is Tarski's definition of truth that the Godel theorems are based on. If we agree to a common interpretation of what symbols like "2", "<", and "3" mean, then "2 < 3" is a true statement. It may be the conclusion of some valid argument, but that's irrelevant, since it is true. "My speakers are black." This is more than just a conclusion of a valid argument (actually, it is not the conclusion of any argument), it is a true sentence. As long as you agree with the meaning of "my", "speakers," "are," and "black," and understand the structure of English sentences, then you must agree that it is true, period (or that we're all being deceived by some demon, but skepticism is irrelevant in this context). Likewise, if you adopt the standard interpretation of the language of number theory, then the truth of a sentence is an entirely meaningful, natural thing which can be understood in full independence from provability. That is precisely what Godel's incompleteness theorem is about. There are statements in the langauge of number theory which are true under the standard interpretation (true a la Tarski's definition, which is entirely natural), yet not provable from any consistent, recursive set of axioms (together with the logical axioms and logical rules of inference), where a consistent, recursive set of axioms is basically a "reasonable" set of axioms. For example, you could take your axioms to be the set of every true statement in the standard interpretation, and so, of course every true statement could be proved from these axioms, but this set is not-reasonable - techincally, it is not recursive.

Now I am nothing more than an ignorant country boy with an ancient Ph.D. in theoretical physics, but I think people make more of Godel's proof than is there. I am not suggesting that it is unimportant, but rather that it is not to be unexpected. I was very curious about Godel's incompleteness theorem back when I was young (as I firmly believed that everything which could be proved should make sense). So I made a careful examination of his proof (which is not easy as it is really quite abstract) and worked out representations of real situations reflecting all of the bothersome steps. Maybe I was wrong but I came to the conclusion that he had proved that every mathematical system was either incomplete or inconsistent; actually a rather straight forward and simple concept which everyone seems to muddy up. :yuck:

Everyone knows a/b is undefined in division if b happens to be zero. That makes division incomplete or, if you attempt to define it under the given axioms, inconsistent. However, you can define an expanded system of division (by adding the appropriate axioms) where a/b is consistently defined even if b is zero. I'll leave that to others as I am no longer the facile mind I once was, but what Godel proved was that the central problem, consistency vs completeness, will eventually crop up again and can not be avoided. And I see no reason to suspect it. Since mathematics must be consistent by definition, the only consistent conclusion is that mathematics is incomplete. That is, no matter how far out we go, there are are going to be true statements (things we can prove are true under an expanded set of axioms) which cannot be proved under the current axioms accepted. Mathematics itself is not a closed system and Bertrand Russell's life's dream is unachievable. I'm sorry Bertrand, but life is tough sometimes. :rofl:

Have fun -- Dick

Hurkyl
Staff Emeritus
Gold Member
Everyone knows a/b is undefined in division if b happens to be zero. That makes division incomplete or,
You misunderstand the technical meaning of the term "incomplete". The fact that division is defined on the domain Rx(R - {0}) has nothing to do with the term incomplete.

A theory is incomplete if and only if there exists a statement in the language of the theory that can neither be proven true nor false by the axioms of that theory.

Division by zero is not a logical statement. :tongue: The expression "1/0" is said to be undefined, because the arguments "(1, 0)" are not in the domain of the function "/". The expression "1/0" can never appear in any statement in the language of arithmetic.

There are, in fact, complete mathematical systems. For example, the (first-order) theory of the arithmetic of the real numbers is, in fact, a complete theory. This theory is "too weak" for Gödel's theorem to apply.

From a different angle, the axioms of theory of the arithmetic of integers can be extended to create a complete, consistent theory. The resulting theory has "too many" axioms for Gödel's theorem to apply.

Hurkyl said:
You misunderstand the technical meaning of the term "incomplete".
Well, my examination of the proof was a long long time ago so I won't argue with you; I examined the proof and obtained my interpretation. Let's just say we will agree to disagree and let it go at that.

Have fun -- Dick

Dichter
I suspect Godel's theorem is related to meaning and logic, which from my personal observation seem to be mutually exclusive. That is, the more logical an assertion, the less meaningful it is, and vice-versa. At one end of the spectrum you have tautologies, at the other you have poetry.

I'm still not sure why this seems so, but my guess is that in order to be meaningful a statement must refer to things we do not yet know.

matt grime
Homework Helper
Doctordick said:
Well, my examination of the proof was a long long time ago so I won't argue with you; I examined the proof and obtained my interpretation. Let's just say we will agree to disagree and let it go at that.

No,let's not. You are just plain wrong and should admit that.

Hurkyl
Staff Emeritus
Gold Member
I suspect Godel's theorem is related to meaning and logic, which from my personal observation seem to be mutually exclusive. That is, the more logical an assertion, the less meaningful it is, and vice-versa. At one end of the spectrum you have tautologies, at the other you have poetry.
This doesn't make any sense to me.

Dichter
Hurkyl said:
This doesn't make any sense to me.

If I understand the consequences of the theorem correctly, no language can be complete; even if you adhere strictly to the language's grammar and lexicon you can still formulate meaningful questions for which meaningful answers cannot be found within the same language.

What I said is that I suspect the problem is not with languages themselves but with the requirement that languages must be capable of expressing meaning. Now meaning is something that cannot be found within the language itself, hence all languages that can express meaning must be incomplete.

matt grime
Homework Helper
Nope, still doesn't make sense. You appear to be applying Goedel's theorem, which is about finitely recursively axiomatized systems that are strong enough to define arithmetic, to something else entirely.

honestrosewater
Gold Member
I think any reasonable definition of 'meaningful statement' would include logical statements. Perhaps it's that logical statements seem less valuable to you because they are so general. An instance of the logical statement ((p -> q) & ~q) -> ~p could be if it were raining, Bob's shirt would be wet, but Bob's shirt isn't wet, so it's not raining, which seems to me like a meaningful statement and potentially valuable piece of info.

You might be interested in The Analytic/Synthetic Distinction, e.g., All doctors that specialize on eyes are doctors / Some doctors that specialize on eyes are unmarried .
Dichter said:
If I understand the consequences of the theorem correctly, no language can be complete; even if you adhere strictly to the language's grammar and lexicon you can still formulate meaningful questions for which meaningful answers cannot be found within the same language.

What I said is that I suspect the problem is not with languages themselves but with the requirement that languages must be capable of expressing meaning. Now meaning is something that cannot be found within the language itself, hence all languages that can express meaning must be incomplete.
That isn't how people who study language use those terms. I wonder where you think you can find meaning if not in the language.? If you don't have language, what does 'meaning' even mean -- isn't meaning a property of linguistic units? (Or more generally, isn't meaning a property of signs and sign systems, of which linguistic units and languages are types?)

I could understand if you mean that meaning is not contained entirely within a language, i.e., that meaning is basically derived from a map or set of maps between linguistic units and other objects that may not be objects of the language (e.g., truth-values, objects in the real word). It might often be the case that at least some of those objects do lie outside of the language, but it's also possible for them to all be objects of the language.

Last edited:
Hurkyl
Staff Emeritus
Gold Member
If I understand the consequences of the theorem correctly, no language can be complete; even if you adhere strictly to the language's grammar and lexicon you can still formulate meaningful questions for which meaningful answers cannot be found within the same language.
All a language does is provide, well, a language in which questions can be asked and answered.

It is not the job of a language to answer anything, nor to provide "meaning" to anything -- it is simply supposed to act as a language.

This thread seems to be confused somewhat... can someone state clearly what Godel's theorem implicates for knowledge in mathematics, for knowledge in general and for philosophy?

Dichter
honestrosewater said:
I think any reasonable definition of 'meaningful statement' would include logical statements.

I agree, but I also think even logical statements are not fully devoid of some ambiguity.

Perhaps it's that logical statements seem less valuable to you because they are so general. An instance of the logical statement ((p -> q) & ~q) -> ~p could be if it were raining, Bob's shirt would be wet, but Bob's shirt isn't wet, so it's not raining, which seems to me like a meaningful statement and potentially valuable piece of info.

I find [((p -> q) & ~q) -> ~p] almost meaningless; it's really little more than a definition of its symbols. Notice that you had to provide an example of what it *means*.

On the other hand, [if it were raining, Bob's shirt would be wet, but Bob's shirt isn't wet, so it's not raining] is not necessarily true, since it makes an objective claim that "Bob's shirt would be wet if it were raining". That may or may not be true.

That isn't how people who study language use those terms.

Oh, I'm definitely not familiar with the jargon. My interest in language is mostly associated with my professional experience with computer languages.

I wonder where you think you can find meaning if not in the language.?

I concede I'm not using "meaning" in the most adequate sense - it's just that there is no word to convey what I have in mind.

What I think is that statements either refer to language or to things outside language. For instance, "fiancée is a French word" is a meaningful statement but does not provide you any knowledge about anything other than the language itself. Those are the kinds of statements that computers are able to "understand".

On the other hand, a statement like "this is my fiancée" refers to a real person. Unless you refine what "this" means, the statement cannot be understood by a computer, but is perfectly understandable by a human who's standing in front of me and my fiancée.

I don't know what this difference in "meaning" is called, or even if it's acknowledged. In any case, the fact that computers cannot understand this non-linguistic aspect of meaning is the reason they cannot do a lot of things, like translating between two human languages.

If you don't have language, what does 'meaning' even mean -- isn't meaning a property of linguistic units?

Even here you can see how "meaning" itself cannot be defined within the language, at least not in a logical way. If it could, we would be able to write an algorithm that evaluates the meaning of any sentence.

I could understand if you mean that meaning is not contained entirely within a language, i.e., that meaning is basically derived from a map or set of maps between linguistic units and other objects that may not be objects of the language (e.g., truth-values, objects in the real word).

Sure, but even those maps cannot be found in the language itself. I think the best I can say about meaning is that it is a creation of the human mind. So unless you consider the speaker and the listener as part of the language, meaning is not be found in it.

It might often be the case that at least some of those objects do lie outside of the language, but it's also possible for them to all be objects of the language.

The latter is the case with programming languages, and that illustrates my original point well: we can't communicate using computer languages. We couldn't possibly be having this conversation if we were forced to adopt the grammar and lexicon of, say, Fortran. Which is equivalent to saying I can't program my computer to have this conversation with me.

Now I wonder whether Gödel's theorem applies to computer languages. I strongly suspect not, as you can't write things like "this sentence is false" in any computer language. But I'm not the Gödel specialist around and would be interested to hear more knowledgeable opinions.

Staff Emeritus
Gold Member
Dearly Missed
Dichter said:
Now I wonder whether Gödel's theorem applies to computer languages. I strongly suspect not, as you can't write things like "this sentence is false" in any computer language. But I'm not the

Since you don't seem to know anything about Goedel's Theorem except its name you should stop talking about it, as Wittgenstein recommended.

matt grime
Homework Helper
Dichter said:
I find [((p -> q) & ~q) -> ~p] almost meaningless;

I find that odd given the comment that follows about being interested in this because of a professional experience with computer programming languages. All computer programming languages are just predicate logic like this.

Notice that you had to provide an example of what it *means*.

no, she did not. She did not have to provide an example to show what it means, she provided an example to illustrate what it means in a non-mathematical context.

My interest in language is mostly associated with my professional experience with computer languages.

On the other hand, a statement like "this is my fiancée" refers to a real person.

no it does not, if we apply your logic before hand about rain. How do we know you have a fiancee? it might not refer to any real person, at all.

Unless you refine what "this" means, the statement cannot be understood by a computer, but is perfectly understandable by a human who's standing in front of me and my fiancée.

Again, not necessarily.

Now I wonder whether Gödel's theorem applies to computer languages. I strongly suspect not, as you can't write things like "this sentence is false" in any computer language.

However, Goedel actually states 'this sentence is unprovable', so your point is moot. But there is certainly a programming analogue to 'this sentence is false'. One would need something like: while i=i+1 do.... which is a loop that no initialization of i will make valid, but you can still type it into a program as long as you never call it. many programs (badly written ones) feature functions that will if given certain inputs fall over and die without checking.

given that you have been told what Goedel applies to, and it isn't hard to google, why don;t you think about whether or not a statemetn about finitely recursively axiomatized logical systems strong enough to define arithmetic have any bearing at all on C, or Fortran.

Last edited:
Hurkyl
Staff Emeritus
Gold Member
Dichter said:
you can't write things like "this sentence is false" in any computer language.
Why not? The construction is the same:

Code:
// this_sentence_is_false.cpp

class predicate {
public:
virtual bool apply(void *arg) = 0;
};

class uhoh : public predicate {
public:
bool apply(void *arg) {
predicate *q = (predicate*) arg;
return q->apply(q) == false;
}
};

int main() {
uhoh *p = new uhoh();
return p->apply(p);
}

P, here, corresponds to the predicate:

P(Q) := Q(Q) is false

and in main, we compute the truth value of P(P), which is none other than the statement "P(P) is false".

Now, our c++ predicate here actually has three truth values: true, false, and "infinite loop", and the value of P(P) is, in fact, "infinite loop". (Well, I guess there's also "crash", which is more likely, but anyways...)

We're spared from paradoxes in programming languages only by virtue of the fact that there is no way to represent "infinite loop" in the language.

Now, you should keep in mind that "programming language" means far more than just a language -- the specification for a programming language includes both a language and semantics for that language.

Dichter said:
The latter is the case with programming languages, and that illustrates my original point well: we can't communicate using computer languages. We couldn't possibly be having this conversation if we were forced to adopt the grammar and lexicon of, say, Fortran.
Actually, it's pretty easy. If you preface every line in our conversation with the four characters "rem ", then it's clear that the result would be syntactically valid Fortran.

Actually, it's semantically correct Fortran as well, since the resulting Fortran code doesn't instruct the computer to do anything, and our conversation doesn't as well.

(That is the syntax for a Fortran comment, right? I can't remember for sure. If I have it wrong, then substitute "C++" for "Fortran", and "// " for "rem ")

Dichter said:
Which is equivalent to saying I can't program my computer to have this conversation with me.
Just because you can't do it doesn't mean it cannot be done.

Dichter said:
In any case, the fact that computers cannot understand this non-linguistic aspect of meaning is the reason they cannot do a lot of things, like translating between two human languages.
Why do you think computers cannot understand such things? And that computers cannot translate between two human languages?

It's a hard problem, yes, but that's no reason to think it cannot be done.

Last edited:
matt grime
Homework Helper
Hurkyl said:
It's a hard problem, yes, but that's no reason to think it cannot be done.

And perhaps more importantly, there's no reason to suppose that any human being is capable of doing it better than every computer.

Hurkyl
Staff Emeritus
Gold Member
Oh bleh, I edited out my examples of computer understanding things other than pure linguistics. For example, my computer knows that "C:\" refers to a particular one of my hard drives, and that "COM3" refers to my modem... neither of which are linguistic units!

Unless you refine what "this" means, the statement cannot be understood by a computer, but is perfectly understandable by a human who's standing in front of me and my fiancée.

Why? There's nothing stopping a computer from making inferences based on context. It knows that "www.physicsforums.com" really means "https://www.physicsforums.com"... [Broken] and ironically, it knows exactly how to interpret the keyword this in the appropriate languages which has a similar linguistic role as in the natural language example. (I think)

Last edited by a moderator:
honestrosewater
Gold Member
Dichter said:
I agree, but I also think even logical statements are not fully devoid of some ambiguity.
Well, I was trying to meet you halfway so that we could maybe make some progress. But your concepts about meaning obviously need to be at least a little better defined. Normally, a statement is called ambiguous if it can be interpreted in more than one way, i.e., if it has more than one meaning. According to what you've said, logical statements are both meaningless and ambiguous, i.e., they have both no meaning and more than one meaning. Do you see a problem with that?

Perhaps you intended 'ambiguous' to be simply 'not one meaning', whether 'more than one meaning' or 'less than one meaning.' But normally, a statement that has less than one meaning is called 'meaningless', as you seem to know.

Even if you allow yourself some wiggle room with hazy qualifiers like 'almost' and 'little', explaining how a statement can have both a little ambiguity and almost no meaning isn't going to be straightforward. (Normally, having exactly one meaning lies between meaninglessness and ambiguity.) It might make sense to consider a statement that has some huge number or infinite set of meanings to be effectively meaningless, or 'almost meaningless', but 'huge' and 'infinite' aren't normally synonymous with 'little'.

So I'm really trying to make sense of what you're saying, and if you can explain it, please do. But maybe you just aren't sure what you mean by 'meaning'.? This seems to be the case from the rest of your post.
I find [((p -> q) & ~q) -> ~p] almost meaningless; it's really little more than a definition of its symbols. Notice that you had to provide an example of what it *means*.
Maybe it seems almost meaningless to you because you just don't know what it means. !?! (It doesn't seem like you do, since ((p -> q) & ~q) -> ~p doesn't claim that (p -> q) is true -- even if we forget that it technically doesn't claim anything at all.) Unless you speak Swahili, Japanese, and Malagasy, ninasoma, gakuseiga senseini hanasita, and namangy anay ny ankizy are probably also almost meaningless to you, but they are meaningful statements to others.

if it were raining, Bob's shirt would be wet, but Bob's shirt isn't wet, so it's not raining is a string of symbols that can be interpreted to have the same structure as ((p -> q) & ~q) -> ~p at some level.

What do you think of the idea that to know what a statement means is to know the conditions under which it is true under a given interpretation? If someone said Bob's shirt is wet when Bob's shirt wasn't wet, wouldn't you think that they don't know what Bob's shirt is wet means?

Last edited:
honestrosewater
Gold Member
Okay, I made up an incomplete, very simple, very mini minigrammar for English -- call it Pfenglish. It might seem like overkill, but I think it would help to see that natural languages aren't so spooky and mysterioso. Take it, leave it, delete it, whatever.

____
Phrase Structure Rules
S --> S C S
S --> DP VP
DP --> D NP
NP --> A NP
NP --> N (PP)
PP --> P DP
VP --> V (DP) (PP)

Lexicon
C = {and, implies, because}
D = {the, his, her, its}
A = {blue, slimy, virile, lackadaisical, sweet}
N = {frog, prince, princess, face, pond, castle}
P = {on, in, of}
V = {jumped, kicked, kissed, put}
____

Call the sets in the lexicon lexical categories. You generate phrase structures by starting with a phrase structure rule that has S on the LHS (of the arrow '-->') and applying other rules until your structure consists of only lexical categories. You apply the rules by simply replacing the LHS with the RHS. Letters in parentheses are optional. Here's an abbreviated derivation with the applied rule noted on the right:

(0) S
(1) DP VP [S --> DP VP]
(2) DP V DP PP [VP --> V (DP) (PP)]
(3) DP V DP P DP [PP --> P DP]
(4) D NP V D NP P D NP [DP --> D NP]
(5) D A NP V D A NP P D A NP [NP --> A NP]
(6) D A N PP V D A N P D A N [NP --> N (PP)]
(7) D A N P DP V D A N P D A N [PP --> P DP]
(8) D A N P D NP V D A N P D A N [PP --> D NP]
(9) D A N P D N V D A N P D A N [NP --> N (PP)]

Now we can select and insert members from the appropriate lexical categories, replacing a D with a member of the lexical category D, etc.

(10) The slimy prince of the castle kissed the blue frog in the slimy pond.

If a member of C appears in a sentence S, call S compound; otherwise, call S simple. Let m be a map from the set of simple sentences to {0, 1}. Extend m to include compound sentences like so:

m(S1 implies S2) = {0 iff m(S1) = 1 and m(S2) = 0; 1 otherwise}
m(S1 and S2) = {1 iff m(S1) = 1 and m(S2) = 1; 0 otherwise}
m(S1 because S2) = {1 iff m(S1) = 1 and m(S2) = 1 and m(S1b2) = 1; 0 otherwise}

where S1b2 is the simple sentence derived from S1 and S2 that says basically S2 caused S1, with the appropriate changes. Caused would be a member of V, but I didn't include it for the sake of simplicity because it needs more complex structures. Classical logic doesn't even use connectives like because for this very reason -- they are not truth-functional. (A connective C is truth-functional iff m(Sx C Sy) depends only on m(Sx) and m(Sy).) I included because just for this comparison. Pfenglish can't use because either since it doesn't have the rules and verb for deriving Sxby.

Anywho, now if anyone wants to, we can talk a little more clearly about the meaning of sentences in both logic and Pfenglish. I included some real and apparent lexical and structural ambiguities in (10).

One could argue that the 'meaning' of Pfenglish connectives is simply what they contribute to the m-values of the sentences in which they appear. That is, knowing what and means is simply knowing that

m(S1 and S2) = {1 iff m(S1) = 1 and m(S2) = 1; 0 otherwise}

i.e., knowing the conditions under which S1 and S2 is true under a given interpretation, if we interpret 1 to mean 'true'.

To assign meaning to simple S, you can make a world, say, Pfearth. Let Pfearth contain a set of entities.

E = {frog, prince, princess, pond, castle}

and so on. You can just build whatever you need in order to interpret any S in Pfenglish.

You'll probably notice that the current rules allow you to generate sentences such as

(11) The frog put the sweet princess.
(12) The castle jumped the frog in the prince.

To rule these out, you just have to add more rules:

____
Argument structures & selectional restrictions
jumped - 1: agent(animate)
kicked - 2: agent(animate), patient
kissed - 2: agent(animate), patient
put - 3: agent(animate), patient, locative
...
____

Maybe you don't care this much. I just don't see any reason to keep pussyfooting around about natural language, so I'm offering up Pfenglish.