"truth=provability" principle — SophistiCat

Godel observed that truth =/= provability, for if it did, then he could have created a sentence in which "true" could be substituted for "provable." Meaning that instead of a sentence true but unprovable, you would have a sentence true and/but not true. - a real problem!

In a conversational way, that's an okay summary. But it actually describes Tarski's result pursuant to incompleteness.

To me, it's odd that Church's theorem (undecidability of the set of theorems of the pure predicate calculus) and Tarski's theorem (the inexpressiblity of a truth predicate in a consistent theory) came in 1936, six years after incompleteness, but those two results are pretty easy corollaries. Why did it take six years to publish the proofs?

Hmm, maybe they depend on Rosser's 1936 improvement of Godel's result? I don't know.

One of these days I need to refresh my knowledge of the proof details for Church and Tarski results.

At the end of the penultimate paragraph at the end of section 1 of Godel's paper, I find this;

"In the precise execution of the above [informal] proof, which now follows, we shall have the task (among others) of replacing the second of the assumptions just mentioned by a purely formal and much weaker assumption."

That assumption, "and, secondly, in which every provable formula is true."

My own encounter with Tarski's result was in secondary literature, I've no idea where. But it seems to me likely that Godel saw the problem, whether as a mouse in the kitchen or an elephant in the living room more than I know.

Why exactly he settled for provability over true would be interesting to know. Did he recognize that truth is a metamathematical notion, not part of the mathematics itself? He must have had a very clear reason, and I do not find it in the paper itself, implying it may have been too trivial to mention.

(1) That translation is different from the one in the van Heijenoort book, which, if I recall correctly is the only one approved by Godel. I don't mention that to discredit your quote or the translation it came from. Rather, just to say that in general and in principle, it may be better to refer to the approved translation.

(2) Indeed, Godel mentioned that his proof deploys the liar paradox but with 'provable' instead of 'true'. But that is not itself the observation that if we substituted 'true' for 'provable' then the system is inconsistent.

(3) Godel may have made that observation (I don't recall), and it would seem obvious anyway, but it was Tarski who put the formal cherry on top with Tarski's theorem.

Why exactly he settled for provability over true would be interesting to know. — tim wood

That is clear from the proof. It doesn't work with 'true' but it works with 'provable'.

Did he recognize that truth is a metamathematical notion, not part of the mathematics itself? — tim wood

I'm not sure to how summarize Godel's view on that at the time of the proof. But that's not the reason for using provability rather than truth. The reason for using provability is that it works.

It's interesting that Godel landed on the idea of incompleteness from his failure to proof the consistency of analysis. Before incompleteness was even a twinkle in his eye, he was unsuccessfully trying to prove the consistency of analysis, and he saw an opportunity in that failure that would possibly prove incompleteness (I don't know the details about that though).

Note that subsequent to incompleteness, Tarski did provide a framework for handling 'truth' as a formal mathematical notion. It is metamathematical, but metamathematics is also mathematics. Mathematical logic and model theory are mathematics.

That is clear from the proof. It doesn't work with 'true' but it works with 'provable'. — TonesInDeepFreeze

Not disagreeing, but rather following. "Doesn't work" seems about as meta-mathematical as it can get. Nowhere in the paper so far as I can understand it does he make clear either that or why it doesn't work with true. He dismissed true without making clear why. Hmm. True as not a formal concept?

Tarski did provide a framework for handling 'truth' as a formal mathematical notion. — TonesInDeepFreeze

Is the sense of this reproducible here, in a conversational way. in a non-onerous number of sentences?

"Doesn't work" seems about as meta-mathematical as it can get. — tim wood

It's merely an informal heuristic expression.

Nowhere in the paper so far as I can understand it does he make clear either that or why it doesn't work with true. — tim wood

If that is the case (I don't recall all of that paper now), then it supports my point.

Anyway, his task was to prove the theorem, which he did. Explaining why it wouldn't work with 'true' is extra.

The proof works because 'provable' is arithmetizable while 'true' is not for a consistent theory. If 'true' were arithmetizable, then the theory would be inconsistent (Tarski).

True as not a formal concept? — tim wood

No. 'true' is formalized, though not in 1930. But the important thing for incompleteness is that 'true' is not arithmetizable in a consistent theory.

More exactly: a truth predicate cannot be defined in the language of a consistent theory. In other words, a predicate T such that Tn evaluates to true in the standard model if and only if n is the Godel-number of a sentence that evaluates to true in the standard model is not definable from the language of the theory. (I think I have that right.)

Is the sense of this reproducible here, in a conversational way. in a non-onerous number of sentences? — tim wood

I can't do it some justice without some technicalities, but I will have to skip some defintions and to fudge some technicalities that would be handled better in a textbook. And to be cogent in a short space, I'll put some things in my own terms.

As is famous, Tarski proposed a correspondence notion of truth. For example:

'1+1 = 2' is true if and only if one plus one is two. [Using numerals and '+' and '=' on the left of the biconditional but words on the right of the biconditional, only to emphasize a certain difference explained in the next paragraph.]

That is not circular, since the '1+1 =2' is purely syntactical. and "'1+1 =2' is true" is a statement about the syntactical object '1+1=2', while the right side expresses a state of affairs.

Now, how do we formalize the notion of a 'state of affairs'?

Answer: With formal models.


A model is a certain kind of function from the signature (and also the universal quantifier in Enderton's book) of the formal object language:

The universal quantifier maps to a non-empty set called 'the universe'

n-ary predicate symbols (including n=0) map to n-ary relations on the universe.

n-ary function symbols (including n=0) map to n-ary functions on the universe.


For example, with the language of arithmetic, the standard model is:

the universal quantifier maps to the set of natural numbers

'=' maps to the identity relation on the set of natural numbers (that is "hardwired" since we are in a context of first order logic with identity)

'S' maps to the successor function on the set of natural numbers

'+' maps to the addition function on the set of natural numbers

'*' maps to the multiplication function on the set of natural numbers


Then the 'truth value' for sentences is inductively (mathematical induction, not empirical induction) defined (too many details for me to mention here). First are clauses for the denotations of the terms (atomic terms, then inductively, compound terms), then satisfaction for atomic formulas, then the connectives, then the quantifier, then a move from satisfaction of formulas to truth of sentences.

I buy it. For me it contains an echo of a "conversational" description of the method for proving 1+1=2. That is, in even briefer form, devise a system, or model, in which 1+1=2 is provable; show the system is equivalent to the arithmetic in question, the proof carrying over, and done.

I made no argument for a philosophy regarding truth. — TonesInDeepFreeze

Then what would you call the following?

We are concerned not just with the object-language and a meta-language, but the object-theory and a meta-theory.

With a meta-theory, there a models of the object-theory. Per those models, sentences of the object-language have truth values. So the Godel-sentence is not provable in the object-language but it in a meta-theory, we prove that the Godel-sentence is true in the standard model for the language of arithmetic. Also, as you touched on, in the meta-theory, we prove the embedding of the Godel-sentence into the language of the meta-theory (which is tantamount to proving that the sentence is true in the standard model). That is a formal account of the matter. And in a more modern context than Godel's own context, if we want to be formal, then that is the account we most likely would adopt.

Godel himself did not refer to models. Godel's account is that the Godel-sentence is true per arithmetic, without having to specify a formal notion of 'truth'. And we should find this instructive. It seems to me that for sentences of arithmetic, especially ones for which a computation exists to determine whether it holds or not, we are on quite firm ground "epistemologically" to say, without quibbling about formality, that the sentence is true when we can compute that it does hold. — TonesInDeepFreeze

Mathematics is true a priori and so empirical validation isn't relevant. — Wayfarer

As Wigner once suggested, there's a deep connection between mathematics and science. Per Aristotle, mathematics is the abstraction of the sensible - taking that which does not exist in separation and considering it separately:

For if attributes do not exist apart from the substances (e.g. a 'mobile' or a pale'), pale is prior to the pale man in definition, but not in substantiality. For it cannot exist separately, but is always along with the concrete thing; and by the concrete thing I mean the pale man. Therefore it is plain that neither is the result of abstraction prior nor that which is produced by adding determinants posterior; for it is by adding a determinant to pale that we speak of the pale man.

It has, then, been sufficiently pointed out that the objects of mathematics are not substances in a higher degree than bodies are, and that they are not prior to sensibles in being, but only in definition, and that they cannot exist somewhere apart. But since it was not possible for them to exist in sensibles either, it is plain that they either do not exist at all or exist in a special sense and therefore do not 'exist' without qualification. For 'exist' has many senses.

...

The same account may be given of harmonics and optics; for neither considers its objects qua sight or qua voice, but qua lines and numbers; but the latter are attributes proper to the former. And mechanics too proceeds in the same way. Therefore if we suppose attributes separated from their fellow attributes and make any inquiry concerning them as such, we shall not for this reason be in error, any more than when one draws a line on the ground and calls it a foot long when it is not; for the error is not included in the premisses.

Each question will be best investigated in this way - by setting up by an act of separation what is not separate, as the arithmetician and the geometer do. — Aristotle's Metaphysics 13.1077b-1078a [Book XIII, Part 2 - Part 3]

t since it was not possible for them [mathematical objects] to exist in sensibles either, it is plain that they either do not exist at all or exist in a special sense and therefore do not 'exist' without qualification. For 'exist' has many senses.. — Aristotle's Metaphysics 13.1077b-1078a [Book XIII, Part 2 - Part 3]

So, does a number, say the number 7, exist? You will say - of course, you just wrote it. But that's a symbol, which denotes a quantity, a numerical value. Different symbols can refer to the same number, but the quantity or count is what the number is, and that is something that only can be grasped by a mind capable of counting; hence, it's an 'intelligible object'.

Here is a Platonic rejoinder, consisting of a passage about Augustine's view of intelligible objects.

Intelligible objects must be independent of particular minds, because they are common to all who think. In coming to grasp them, the individual mind does not alter them in any way, it cannot convert them into its exclusive possessions or transform them into parts of itself. Furthermore the mind discovers them rather than forming them or constructing them, and its grasp of them can be more or less adequate...

...certain intelligible objects - for example, the indivisible mathematical unit [i.e. prime numbers] - clearly cannot be found in the corporeal world (since all bodies are extended, and hence divisible.) These intelligible objects cannot therefore be perceived by means of the senses; they must be incorporeal and perceptible by reason alone.

...We refer to mathematical objects and truths to judge whether or not, and to what extent, our minds understand mathematics. We consult the rules of wisdom to judge whether or not, and to what extent, a person is wise. In light of these standards, we can judge whether our minds are as they should be. It makes no sense, however, to ask whether these normative intelligible objects as they should be; they simply are, and are normative for other things.

In virtue of their normative relation to reason, Augustine argues that these intelligible objects must be higher than it, as a judge is higher than what it judges. Moreover, he believes that apart from the special sort of relation they bear to reason, the intrinsic nature of these objects shows them to be higher than it. These sorts of intelligible objects are eternal and immutable; by contrast, the human mind is clearly mutable. Augustine holds that since it is evident to all who consider it that the immutable is clearly superior to the mutable (it is among the rules of wisdom he identifies), it follows that these objects are higher than reason. — Cambridge Companion to Augustine

That entire passage is merely a report of notions and terminology of mathematical logic. It's nowhere even close to a philosophical statement. Except the last sentence, which does have a philosophical aspect. And philosophically it is very little - certainly not a philosophical stance and certainly not "dogmatic".

In that last sentence, I merely say that it seems to me that when we make correct computations in arithmetic, we can take the results as true. To say this more fully: Such computations may be reduced to primitive manipulation of such things as, say, plain tally marks - the most simple, most direct mathematical reasoning that I personally can imagine. Put another way, this is merely clerical attention to mechanical procedures. Now, if someone wants to express extreme doubts of computational arithmetic, then I would say, "If you think we are not justified in accepting truth from even the most simple results of manipulation of tally marks, then what mathematical knowledge do you think is justified?" I don't even claim that the person would not have a satisfactory answer. I only say that I personally don't know of one.

That is quite on the exact opposite end of the spectrum from dogmatism.

The key statement in Gödel's argument is: This sentence is unprovable.

The "argument" A (Adele) proceeds as follows,

1. If this sentence is provable then this sentence is unprovable [Gödel's key premise]
2. This sentence is provable [assume for reductio ad absurdum]
3. This sentence is unprovable [1, 2 MP]
4. This sentence is provable and this sentence is unprovable [2, 3 Conj]
5. This sentence is unprovable [2 - 4 reductio ad absurdum]

However...

Gödel's key premise is problematic,

2. If this sentence is provable then this sentence is unprovable [Gödel's key premise]
7. This sentence is unprovable or this sentence is unprovable [2 Imp]
8. This sentence is unprovable [7 Taut]

I've used only equivalence rules of natural deduction which means that Gödel's key premise, 2. If this sentence is provable then this sentence is unprovable is logically equivalent to 8. This sentence is unprovable.

If so, "argument" A becomes,

1. Thus sentence is unprovable [Gödel's key premise via substitution of "if this sentence is provable then this sentence is unprovable" = " this sentence is unprovable"]
2. This sentence is provable [assume for reductio ad absurdum]
3. This sentence is provable and this sentence is unprovable [1, 2 Conj]
4. This sentence is unprovable [2 - 3 reductio ad absurdum]

Notice, the conclusion, line 5 appears in the premises, line 1 [Gödel's key premise]. In other words, Gödel's argument begs the question, is circular and therefore, fallacious.

That is is nothing like Godel's proof. On so many levels it is nonsensical.

What actual version of a Godel's proof have you read in a paper or book?

That is is nothing like Godel's proof. On so many levels it is nonsensical.

What actual version of a Godel's proof have you read in a paper or book? — TonesInDeepFreeze

Well, let's you tell us how Gödel's argument works. C'mon. Out with it!

I asked you what version of Godel's proof have you read in a paper or book. That is, what writing did you base your previous post on?

Thank you for your time. G'day.

I did start this thread, and I do think Tones asks a reasonable question. You’re continually entering these long sequences of symbolic code as if they mean something. So he’s saying, based on what? You’re claiming this is something Godel says, so, like, provide the citation.

I did start this thread, and I do think Tones asks a reasonable question. You’re continually entering these long sequences of symbolic code as if they mean something. So he’s saying, based on what? You’re claiming this is something Godel says, so, like, provide the citation. — Wayfarer

Well, good advice Wayfarer. Truth be told, the contents of my post is drawn in full from the video in your OP. It's all in the video.

Perhaps I’ll watch it again. :yikes:

Please do but only if you feel like it though. TonesInDeepFreeze seems intelligent and well-read but his playing style is more brute force like the Deep Blue supercomputer which, I have to admit, defeated the world chess champion, Garry Kasparov despite...everything I guess.

t since it was not possible for them [mathematical objects] to exist in sensibles either, it is plain that they either do not exist at all or exist in a special sense and therefore do not 'exist' without qualification. For 'exist' has many senses..
— Aristotle's Metaphysics 13.1077b-1078a [Book XIII, Part 2 - Part 3]

So, does a number, say the number 7, exist? You will say - of course, you just wrote it. — Wayfarer

No, that's not Aristotle's position. See below.

But that's a symbol, which denotes a quantity, a numerical value. Different symbols can refer to the same number, but the quantity or count is what the number is, and that is something that only can be grasped by a mind capable of counting; hence, it's an 'intelligible object'.

Here is a Platonic rejoinder, consisting of a passage about Augustine's view of intelligible objects. — Wayfarer

Augustine saw the divine mind as the ground for universals. Whereas for Aristotle, it's the concrete situations themselves, such as seven apples in a bowl, that ground the use of those terms.

I favour the Platonist view.

In that last sentence, I merely say that it seems to me that when we make correct computations in arithmetic, we can take the results as true. — TonesInDeepFreeze

Strictly speaking, when we make correct computations in arithmetic, the results are logically valid. Following correct procedure results in a valid conclusion. Do you recognize the commonly held distinction between true and valid? A valid conclusion is not necessarily true, because it requires also that the premises are true. If we hold that axioms (as premises) are neither true nor false, or that truth and falsity is not relevant to axioms, then we cannot claim that correct computations provide us with truth.

I favour the Platonist view. — Wayfarer

OK. But I just wanted to point out that there are other views, such as Aristotle's, where mathematics and logic aren't considered to be a priori or exempt from empirical validation. Instead, for Aristotle, mathematics and logic were sciences of quantity and reasoning respectively. The qualitative difference to other empirical investigations is just the degree of abstraction and generality employed.

Which reminds me of this:

:up: :lol:

Excellent! :clap: :up: :lol:

A picture is worth a thousand words. — An old adage

[...]complex and sometimes multiple ideas can be conveyed by a single still image, which conveys its meaning or essence more effectively than a mere verbal description. — Wikipedia

I came across a nice proof of Godel's Incompleteness Theorem that utilizes computability and Cantor's diagonal argument (UC Davis lecture: Part 1 and Part 2). My summary below.

Suppose we have a list of all possible computable functions (programs) in some language (say, Python) that each accept a positive integer as input and produce either 0 or 1 as output. A computable function is a finite string of symbols that, when executed, produces an output in a finite amount of time.

Now consider a table that lists all those computable functions vertically (ordered by string length and symbol index) and the function outputs for each positive integer horizontally.


The above table shows the first three programs and the fifteenth program, with positive integer inputs 1, 2, 3 and 15. As an example, the outputs might be:


Now we define a function f-diag (called f-bar in the lecture) as:


i is a positive integer that appears in three places in that definition - as the input to function f-diag, as the index to a function in the computable functions table (i.e., the i-th function), and as the input to that indexed function. Per the above table, the outputs for f-diag (calculated by inverting the diagonal elements in the table) would be:


Note that f-diag differs from every computable function by at least one input/output pair. So f-diag is not on the list of computable functions and therefore cannot itself be a computable function.

Now consider some statements about those functions.


S1 states that the output of function f2 with input 2 is 0. Per the table above, S1 is true. Furthermore, we can prove the statement by executing function f2 with input 2 and it will output 0 in a finite time. What "prove" means here is that there is a mechanical procedure for obtaining the output in a finite time which, in this case, is provided by function f2.


Per the table, S2 is false. We can prove the negation of S2 by executing function f1 with input 3 and it will output 1 in a finite time.


Per the f-diag table, S3 is true. But we lack a mechanical procedure for proving it since, as shown earlier, f-diag is not a computable function. Furthermore, any computable function is going to produce a different output to f-diag for at least one input (due to the diagonalization). So the proof system would either fail to derive a true statement about f-diag for such an input (and therefore would be incomplete) or else would derive a false statement about f-diag for such an input (and therefore would be inconsistent).

Which just is Gödel's First Incompleteness Theorem: In any rich-enough [*] formal proof system that proves only true statements there are true statements that can't be proved.

--

[*] A system is rich-enough if it can express f-diag statements such as S3 above. f-diag is a well-defined function and S3 is a statement about positive integers just as S1 and S2 are.