s

@Banno, there's a problem with your proof. Firstly, it appears that any and all statements can be shown to be unprovable with your or Godel's method.

Suppose G = the mathematical statement with Godel number xyz is unprovable. Notice that the mathematical statement with Godel number xyz is essentially a free variable and ALL mathematical statements that have a Godel number, and that includes all of mathematics, can be assigned to it. Basically G = the X is unprovable, and X can take on values from the entirety of mathematics. That mean your argument "proves" all mathematical statements that can be reduced to a Godel number, and that's all of mathematics, are unprovable.

There has to be another constraint on the proof that restricts the variable X to those mathematical statements that actually are true but unprovable within a given axiomatic statement.

All this is on the fly so, bear with me. I'm hoping to stagger through this like a drunk and hopefully bump into the truth. If you have the patience, indulge me.

Nuh.

G (Godel sentence) = the mathematical statement with Godel number xyz is unprovable — TheMadFool

I ignored this error before, for the sake of getting to the main point. Each and every statement in mathematics has a Godel number. What you are calling a Godel statement is equivalent to one particular such number - to to all of them.

Last but not least, Godel admits that his method of proof has a connection with the Liar Paradox which, to me, should set the alarm bells ringing. — TheMadFool

Yet it isn't equivalent to Liar Paradox or perhaps in this case to Russell's paradox. This is something that some writers erroneously think. The self refence doens't fall into a vicious circle (as Russell put it), even if there's a statement / Gödel number referring to a Gödel number.

Ai-yi-yi! Here goes.

G-numbers are simply the unique numbers applied to expressions by the process of G-numbering. For example, suppose the G-number of (2+2=4) is 997. I can also have the expression Bew x, meaning that x is provable; of course x here is an undefined free variable . Bew x has its own G-number; suppose it to be 5280.

An important part of the machinery of the proof is rendering numerals into z-numbers. This is not difficult. It simple means starting with zero=0, one = 0s, two = 0ss, three = 0sss, and so forth.

Sb (x/z(x)) means substitute for the numeral x, replacing it with the z-number for x. Sb w y/z(x) reads, Substitute into the expression with the G-number w, in the place of y reading instead the z-number of x. This is just syntax.

Suppose I have the expressions 997 and 5280, as defined above. Also, for convenience, let's let 997 = a, and 5280 = b,

Let's start putting it together. Sb (b x/z(a). In English. Substitute into the expression 5280 (=Bew x), for the x, the z-number of 997 (2+2=4). That is, 0sss...sss is the (z-)number of a provable proposition. Whew!

1) Q(x,y) = ~(x B (sb (y, y/zy))). The function Q(x, y) is to be understood as x is not the G-number of a proof of the expression with the g-number y into which the z-number of the g-number for y is substituted.

2) Another part of the machinery of the proof is recursion, I think these days called primitive recursion. For present purpose that means you start at zero and work your way up one-by-one. Not efficient but exhaustive, and a guarantor of the grounds of conclusions reached within the limits of the grounds.

3) The g-number of Q(x,y) shall be q.

4) p = ((x) gen q). p is the g-number of the generalization of the x in Q. In English, for all x, x is not (the G-number of a proof of y in Q. That is, x is the g-number of a proof-schema and that it is not a proof of y. Generalized under recursion, it means that no x is a proof of y, hence y is unprovable. (Maybe y is the G-number of the proposition 2+2=6, or, 0ss + 0ss = 0ssssss). p is simply the g-number of this expression.

5) r = Sb (q, y/z(p)). r is the g-number for the expression on the right. The expression on the right in English: Substitute into q replacing the y with the z-number of the g-number p.

We have, then,

Q(x,y) = q

(x)gen(q) = p

Sb (q, y/z(p)) = r

6) Consider Sb (p, y/z(p)):

Sb (p, y(z(p)) = Sb ((x) gen q), y/z(p)) = (x) gen (Sb (q, y/z(p)) = (x) gen r.

Let's see if we can get to (x) gen r into English.

q -> x doesn't prove y

p -> for all x, x doesn't prove y

r -> x doesn't prove p

Sb (p, y/z(p)) -> Substitute into the expression, p = y is unprovable, for y, p. That is, p = p is unprovable.

p, then, states, is the expression that, p is unprovable. The similarity to the liar paradox is immediately apparent, except Godel's expression is a rigorously constructed mathematical proposition. It it's true, then it's unprovable. If it's negation were provable, then an unprovable proposition would be provable, and in that case everything is trivially provable.

The usage here is very close to Godel's own.

Thanks for all your inputs. As of this moment my brain is completely fried so you guys will have to wait for a couple of weeks or more for all this to sink in. Thanks again.

I'm please that you did not follow the path that says "I don't understand it, so it's wrong".

It might have gotten lost in the shuffle, so I'll repeat my suggestions

First, get a hold of Godel, Escher and Bach by Douglas Hofstadter. Besides giving (in my opinion) one of the best explanations of Godel, it's a very entertaining read in of itself with all sorts of very cool insights.

Next, you might want to check this out: https://www.youtube.com/watch?v=GbtNQ7yzo9Y&feature=youtu.be

This explains the technique behind Godel in totally non-mathematical terms.

Things that may be true, but may not be provable:
1. There is a God
2. String theory

Thanks

Things that may be true, but may not be provable:
1. There is a God
2. String theory — jgill

Things that are true but aren't provable: { } or not?

@Banno@tim wood@EricH@sime@jgill

A simple scenario:

It's true that this roller coaster, the one you want to ride on, is safe but it's my duty as the one in charge of this roller coaster to inform you that no one has ever proved that this ride is, in fact, safe.

Would you ride this roller coaster?

Did the esteemed Kurt Godel prove the statement: this [mathematical] statement is true but unprovable?

There is a better proof of Gödel's theorems that considerably clarifies the situation. It relies on two other theorems: (1) Gödel's proof that the set of theorems of a recursively axiomatized theory is computably enumerable; (2) Tarski's theorem that truth is not arithmetically definable. Let us tackle each of these by turn.

(1) We say that a theory is recursively axiomatized if there is an algorithm which tells us whether or not a given formula is an axiom of the theory, i.e. you input a formula and the algorithm prints YES or NO if the formula is an axiom or is not an axiom, respectively. By a long, tedious process of coding, Gödel was able to show that in the case of such theories, whether or not a sequence of formulas is a proof is also checkable by an algorithm. This implies that all there is another algorithm which prints all the theorems of the theory in a sequence, i.e. there is an algorithm that enumerates the theorems of the theory (the algorithm in question is horrid, by the way). In other words, the theorems of such a theory are computably enumerable. Now, there is another theorem that roughly shows that computably enumerable predicates are definable in PA by a formula with just one existential quantifier. So, in particular, the predicate "x is a theorem of T" is definable in PA for any recursively axiomatized theory T.

(2) But Tarski also showed that being a true formula of PA is not definable in PA by any formula, let alone one with just one existential quantifier. The idea is very roughly as follows: if truth were definable in PA, since PA allows for self-referential predicates, a version of the liar paradox would be replicated inside PA. But then PA would be inconsistent. So truth is not so definable.

Putting these together, we obtain the following: (1) Being provable is definable in PA, but (2) being true is not definable in PA. On the other hand, we have (3) if something is provable, then it is true. Hence, since, by (1) and (2), being provable and being true are different, and, by (3), everything that is provable is true, we have that there must be something that is true without being provable. In other words, PA is incomplete.

This version is better than the one originally presented by Gödel because it deals directly with intrinsic properties of the predicates of being a theorem and being a true formula, i.e. properties that are not relative to any system (this stems from the rather astonishing fact that the notion of algorithm is system-independent). So it avoids retorts of the sort "but we just prove [whatever] in a higher system".

So it avoids retorts of the sort "but we just prove [whatever] in a higher system". — Nagase

It's not an interesting retort anyway, because if a formula is true but not provable, we can just make it an axiom in a higher system, so it would be trivially provable.

Putting these together, we obtain the following: (1) Being provable is definable in PA, but (2) being true is not definable in PA. On the other hand, we have (3) if something is provable, then it is true. Hence, since, by (1) and (2), being provable and being true are different, and, by (3), everything that is provable is true, we have that there must be something that is true without being provable. In other words, PA is incomplete. — Nagase

Thanks.

But, in deductive logic, math included, proof guarantees truth. Ergo, being true doesn't need to be defined separately - it's redundant. Also, proof of a proposition is necessary to claim that that proposition is true. In other words a proposition is true IFF that proposition has a proof unless the proposition is an axiom.

Also, proof of a proposition is necessary to claim that that proposition is true. — TheMadFool

You keep saying this as if it was self-evident. Now, if you'd never before encountered this problematic, never had anyone contradict you, it wouldn't be unreasonable to say this. But after ten months and four pages of discussion a thinking person would begin to suspect that the question might not be so straightforward...

question might not be so straightforward... — SophistiCat

Does this observation apply exclusively to TheMadFool or does it also range over others?

Also, no one answered my rollercoaster question.

Does this observation apply exclusively to TheMadFool or does it also range over others? — TheMadFool

Does it matter? Do you hold your intelligence contintgent on the intelligence of people you are arguing with?

Does it matter? Do you hold your intelligence contintgent on the intelligence of people you are arguing with? — SophistiCat

Ok. It shouldn't matter but I feel bad when people accuse me of something which they themselves are guilty of.

All the time!

For instance, if you substract a positive number from a larger positive number, you get a positive number. There is no proof for this, despite it ensuing from mathematical axioms. No proof, but then again, nobody can find a counter-example for it, either. — god must be atheist

The rules of math were designed by human beings, so don't we design the proof and the truth if we are the designers of the system? What is the proof and truth of how to spell the word, "cat"? Humans didn't design the universe therefore truth and proof of some state of the universe will be difficult to come by however humans did design the means to represent and communicate our experiences of the universe, so any truth or proof would be inherent in the rules we've dictated.

Unfortunately, from the fact that provability is sufficient for truth, it does not follow that it is necessary for truth (in general, being a sufficient condition is not, well, sufficient for being a necessary condition). But truth would be redundant only if provability were sufficient and necessary for truth. Gödel's theorem, in the particular form I mentioned in my previous post, shows, however, that provability is not necessary for truth. So you must revise your position (note that the form I mentioned in my previous post does not exhibit any particular sentence, and therefore avoids your roller-coaster dilemma).

Incidentally, the idea that truth is simply redundant, at least in its naive form, is untenable. We already know that simply adding a predicate T to PA with the axioms T(x) iff x is the code of a true sentence results in inconsistency, which is already surprising to a redundant theorist, since it shows that adding a truth predicate with this simple property already goes much beyond the original theory (indeed, the simple property is so powerful that it results in inconsistency! In a sense, it is too powerful). But even more surprisingly, suppressing that axiom and adding weaker ones invariably result in non-conservative extensions of the base theories, i.e. theories that are more powerful than the original (both Friedman-Sheard and Kripke-Feferman have this property, for instance). So truth cannot be redundant.

The lesson here is that truth is an exceedingly difficult subject. As Timothy Williamson puts it in "Must Do Better":

One clear lesson is that claims about truth need to be formulated with extreme precision, not out of knee-jerk pedantry but because in practice correct general claims about truth often turn out to differ so subtly from provably incorrect claims that arguing in impressionistic terms is a hopelessly unreliable method. Unfortunately, much philosophical discussion of truth is still conducted in a programmatic, vague, and technically uninformed spirit whose products inspire little confi dence.

Hence why we need formalization, as Williamson himself defends later in the essay:

Philosophy can never be reduced to mathematics. But we can often produce mathematical models of fragments of philosophy and, when we can, we should. No doubt the models usually involve wild idealizations. It is still progress if we can agree what consequences an idea has in one very simple case. Many ideas in philosophy do not withstand even that very elementary scrutiny, because the attempt to construct a non-trivial model reveals a hidden structural incoherence in the idea itself. By the same token, an idea that does not collapse in a toy model has at least something going for it. Once we have an unrealistic model, we can start worrying how to construct less unrealistic models.

I think the ideas that truth is provability or that truth is redundant, at least in the naive forms presented here, are precisely of the type that "differ subtly from provably incorrect claims" and "do not withstand even that very elementary scrutiny, because the attempt to construct a non-trivial model reveals a hidden structural incoherence in the idea itself".

I'm with the Madfool, paradoxically for reasons hinted at by nagese.

Godel sentences do not support the colloquial interpretation they receive, that is to say "G is true because G is unprovable, assuming Peano Arithmetic is consistent". This is because

i) Firstly, the hypothesis that PA is consistent is potentially falsifiable, but it can never be verified. Therefore it is irrational for logicians and philosophers to assume or even talk about PA's 'infinitely complete' hypothetical consistency. Instead, they should only talk about PA's consistency within a limited finite scope of derivations.

ii) PA cannot talk about what isn't provable in PA, which is the central conclusion of Godel's first incompleteness theorem, and corresponds to both the Halting Problem and Tarski's undefinability of truth within PA. In general, for any sentence S of PA we have

a) PA |-- S <---> PA |-- Prov('S')

e.g. PA derives S if and only if PA derives Prov('S')

b) PA |-- G <--> ~Prov('G') For any Godel sentence G.

Therefore b substituted into a leads to the conclusion

c) PA |-- ~Prov('G') <--> Prov('G')

In other words,

PA |-- ~Prov('S') does not imply that PA does not derive S .

i.e. Peano arithmetic cannot enumerate the formulas that PA cannot derive (duh).

Therefore G does not say that "G isn't provable"

iii) The arithmetical theorems that PA cannot derive, e.g. Goodstein's Theorem, aren't constructively acceptable in any case, due to them appealing to the Axiom of Choice. These theorems cannot be computationally or otherwise empirically verified in principle without begging the question. Therefore they should not be considered as having a truth value.

In conclusion, an undecidable proposition of PA cannot be said to have a truth value, unless it is added as an additional axiom, in which case it is vacuously true due to now being provable as an axiom.

Unfortunately, Classical Logic and it's accomplice Model Theory, give this illusion that arithmetic is a meta-language for defining the truth of PA or vice versa from 'outside the system'. This isn't the case, due to the very ability of each system to encode each other. They are therefore one and the same theory, for formal purposes and are as equally undecided as each other.

Let us suppose that everything you say is true. This still does nothing to address two facts: (1) the set of true formulas is not arithmetically definable, but the set of provable formulas is, whence the two must be distinct; (2) truth is not conservative over PA, whence it can't be redundant. I sketched that argument in my first post here precisely so we did not get entangled in fruitless discussions about how we can know that G is true or about the Kirby-Paris theorem.

Obviously, that particular argument assumes the soundness of PA, which you have disputed (this is a minority position, but one that I respect, if only because in the case of Nelson it generated some interesting mathematics). But this is not necessary for the argument to go through: one can start with Q and argue that any recursively axiomatized theory that extends Q will fall into the same problem, namely truth will be arithmetically undefinable and theoremhood will be arithmetically definable. Since no one that I know of doubts the soundness of Q (not even Nelson), the argument should go through.

By the way, if your ii.c) is correct, then PA is inconsistent. In any case, that is not a valid substitution instance of ii.a): ii.a) says merely that (assuming soundness) PA |- S iff PA |- Prov('S'), not that PA |- S <-> Prov('S') (the latter is a reflection principle and is actually not provable in PA).

Godel sentences do not support the colloquial interpretation they receive, that is to say "G is true because G is unprovable, assuming Peano Arithmetic is consistent". This is because

i) Firstly, the hypothesis that PA is consistent is potentially falsifiable, but it can never be verified. Therefore it is irrational for logicians and philosophers to assume or even talk about PA's 'infinitely complete' hypothetical consistency. Instead, they should only talk about PA's consistency within a limited finite scope of derivations.

ii) PA cannot talk about what isn't provable in PA, which is the central conclusion of Godel's first incompleteness theorem, and corresponds to both the Halting Problem and Tarski's undefinability of truth within PA. In general, for any sentence S of PA we have — sime

No one (worth attending to) says "G is true because G is unprovable." G is proved true by a meta-mathematical argument.

i) Who talks about "PA's 'infinitely complete' hypothetical consistency."? Godel limited his claim to ω-consistency.

ii) "PA cannot talk about what isn't provable in PA." In Godel, sure it can, and does. G is unprovable in PA, and the consistency of PA is unprovable within PA. Seems a lot like talking about it to me.

Let us suppose that everything you say is true. This still does nothing to address two facts: (1) the set of true formulas is not arithmetically definable, but the set of provable formulas is, whence the two must be distinct; — Nagase

Correct me if i'm wrong, but aren't we both referring to the fact that the negation of PA's provability predicate doesn't actually enumerate what isn't derivable in PA?

(2) truth is not conservative over PA, whence it can't be redundant. I sketched that argument in my first post here precisely so we did not get entangled in fruitless discussions about how we can know that G is true or about the Kirby-Paris theorem. — Nagase

If by truth not being redundant, you are merely referring to the difference between

PA |-\- S (i.e. the event that PA doesn't derive S) versus PA |-- ~Prov('S')

then I think we're in agreement. But in this event, the notion of truth is redundant in the sense that it doesn't transcend the notion of derivability within PA, which is what I took the OP's point to be.

As for G's "truth" value, I can only recognise it as having undefined truth value, both in the sense of it's unknown status as a derivable theorem of PA, and also in the sense of it's decoded arithmetical interpretation pertaining to the undecidable solutions of Diophantine equations. As an aside, i don't recognize the truth of Goodstein's Theorem, due to it's proof relying on non-constructive notions pertaining to transfinite induction.

Obviously, that particular argument assumes the soundness of PA, which you have disputed (this is a minority position, but one that I respect, if only because in the case of Nelson it generated some interesting mathematics). But this is not necessary for the argument to go through: one can start with Q and argue that any recursively axiomatized theory that extends Q will fall into the same problem, namely truth will be arithmetically undefinable and theoremhood will be arithmetically definable. Since no one that I know of doubts the soundness of Q (not even Nelson), the argument should go through. — Nagase

I'm not so much of the view that PA will turn out to be inconsistent within my life time, but rather of the view that talk of the consistency of PA is meaningless in both demanding infinite evidence and also in being logically inexpressible, as demonstrated formally by Godel's second incompleteness theorem.

By the way, if your ii.c) is correct, then PA is inconsistent. In any case, that is not a valid substitution instance of ii.a): ii.a) says merely that (assuming soundness) PA |- S iff PA |- Prov('S'), not that PA |- S <-> Prov('S') (the latter is a reflection principle and is actually not provable in PA). — Nagase

ii a) doesn't express soundness in the sense of begging an external notion of arithmetic truth, rather it expresses the ability of Prov to enumerate what is derivable within PA:

PA |-- S <---> PA |-- Prov('S')

this is a provable equivalence, because Prov(''S') merely enumerates what can be derived in PA and it doesn't lead to false derivations, because it directly encodes PA's axioms and rules of inference.

ii c): By itself ii c doesn't imply inconsistency, because it is specifically stated with reference to the Godel sentence G that diagonalizes the negative provability predicate:

PA |-- ~Prov('G') <--> Prov('G')

Only if PA |-- G is derivable does ii c lead to inconsistency.

ii c) is equivalent to Tarksi's undefineability of truth applied to PA, in which PA's derivability predicate, Prov, is taken to be it's "truth predicate" . It also implies the constructive content of Godel's first incompleteness theorem, namely that ~Prov is a misnomer in not being able to enumerate what PA cannot derive.

That's why i said i agreed with Mad fool, for reasons you hinted at. Truth, as far as mathematical logic is concerned, IS derivability , for mathematical logic cannot be partitioned into a metalanguage talking about an independent object language, for both languages are isomorphic to one another and suffer from the same undecidability.

Sixty years ago I took a course entitled "Introduction the Graduate Mathematics" using Halmos' book on naive set theory plus handouts and lectures on the Peano Axioms and PA. I don't recall any critiques of PA, only using them to construct some elementary mathematics. I think our assignments got us up to the exponential function. We discussed Gödel, but only in passing. I wonder what students are required to study nowadays. Perhaps the math in math programs and the supporting logic in philosophy programs, with not a lot of overlap.

Unfortunately, from the fact that provability is sufficient for truth, it does not follow that it is necessary for truth (in general, being a sufficient condition is not, well, sufficient for being a necessary condition) — Nagase

So you would call the cops if someone accused me of a felony crime but didn't have a shred of evidence against me?

By the way, justified true belief (JTB) theory of knowledge, in stating truth as a separate condition, lends support to your claim that proving a proposition and the truth of that proposition are two different things but, in my humble opinion, this proof-truth gap exists only in inductive logic as opposed to deductive logic where a sound argument gaurantees the truth of the conclusion and mathematics is exclusively deductive in character. That's why I think truth is redundant.

Just to inquire, did Godel prove the Godel sentence "this mathematical statement is true but unprovable"?

Let me put it this way. Suppose truth were equal to provability (or even just extensionally equivalent). Then any algorithm for enumerating all the theorems would ipso facto enumerate all the truths. But, in fact, we have an algorithm for enumerating all the theorems (they are computably enumerable) and none for enumerating all the truths (truth is not even arithmetically definable, let alone definable by a Sigma_1 formula). Therefore, they truth is not equal to provability.

So no, I'm not merely claiming that theoremhood is not fully capturable in PA. I'm claiming that whereas theoremhood is weakly capturable, truth is not capturable at all, and therefore these are different concepts.

As for the supposed redundancy of truth, again, I'm not referring just to the fact that theoremhood is only weakly capturable in PA. Rather, I'm referring to the fact that (i) if truth were redundant, the addition of a truth predicate to PA would result in a conservative extension of PA and (ii) the addition of a truth predicate to PA does not result in a conservative expression of PA. Hence, truth is not redundant.

As for your ii.c), you're saying that PA proves a formula of the type ~P <--> P. But then we have: ~P <--> P is equivalent to (P -> ~P) & (~P -> P), which is equivalent to (~P v ~P) & (~~P v P), which is equivalent to ~P & P. Hence, if PA proves ~Prov('G') <--> Prov('G'), PA proves a contradiction. Here's another way of seeing the matter. PA is built on classical logic, whence it proves every instance of P v ~P. So suppose PA proves ~Prov('G') <--> Prov('G'). Suppose then ~Prov('G'). Then, by this equivalence, Prov('G'), whence by conjunction introduction ~Prov('G') & Prov('G). On the other hand, suppose Prov('G'). Then, again by the equivalence, ~Prov('G'), so ~Prov('G') & Prov('G'). Thus, ~Prov('G') v Prov('G') -> (~Prov('G') & Prov('G')). But the antecedent is an instance of the excluded middle, so we can detach the consequent (again, remember that PA is classical) and obtain ~Prov('G') & Prov('G'), which is a contradiction.

As I said, the problem is that you're passing from PA |- S iff PA |- Prov('S') to PA |- S <--> Prov('S'). The former is ok, but the latter is not true; we only have PA |- S --> Prov('S') (that's one of the derivability conditions), whereas Prov('S') --> S is a reflection principle (soundness). In fact, by Löb's theorem, we have that, for any S, PA |- Prov('S') --> S implies PA |- S (cf. section 4.1 of this paper for a sketch of the proof).

(Interestingly, Boolos comments on this theorem on pp. 54ff of The Logic of Provability as follows: "Löb's theorem is utterly astonishing (...). In the first place, it is often hard to understand how vast the mathematical gap is between truth and provability. And to one who lacks that understanding and does not distinguish between truth and provability, [Prov('S') --> S], which the hypothesis of Löb's theorem asserts to be provable, might appear to be trivially true in all cases, whether S is true or false, provable or unprovable.")

Refer to my reply to for a clearer sketch of why truth is not provability, and which has nothing to do with G or whatever. And, again, you're evading my point that, if you want to reduce A to B, the mere fact that B is sufficient to A is not enough: you must also show that B is necessary for A. But this is just what Gödel's theorems deny.

Your juridical reasoning may be convincing in the intuitive level, but, as Williamson has said, in these matters it is not enough to argue impressionistically. As counter-intuitive as it might be, it is demonstrable that truth (on most reasonable axiomatizations of the notion, anyway) is not redundant and is not the same as provability.