Mathematical truth is not orderly but highly chaotic

TonesInDeepFreeze

You can't prove arithmetic from arithmetic because we created it. — Philosophim

Given a theory adequate for a certain amount of arithmetic, for example, PA, it's redundant to say that the theory proves all its theorems. But if the theory is formal and consistent, then there are truths of arithmetic that are not provable in the theory. This has nothing to do with who "created" the theory.

TonesInDeepFreeze

Do [we] have uncountably many interpretations? — fishfry

Given a particular countable language and meta-theory with a countable alphabet:

This is correct:

Given a countable set of symbols, there are exactly denumerably many finite sequences of symbols, thus exactly denumerably many sentences.

There are uncountably many subsets of the set of sentences. And any set of sentences can be a set of axioms. Therefore, there are uncountably many theories. But there are only countably many ways to state a theory, so there are theories that are not stable.

I'm pretty sure this is correct:

There are exactly denumerably many algorithms. And for every formal theory and set of axioms for that theory, there is an algorithm for whether a sentence is an axiom. So there are only countably many formal theories.

Given a language for a theory, trivially, there are uncountably many interpretations for the language, since any non-empty set can be the universe for an interpretation, and there are not just countably many sets. But there are only countably many ways to state an interpretation, so there are interpretations that are not statable.

Given any theory, there are uncountably many models of the theory, since there are uncountably many isomorphic models of the theory. But there are only countably many ways to state a model, so there are models that are not statable.

TonesInDeepFreeze

Provability, if I have understood it correctly, means that a truth of a statement/conjecture can be derived from some axiomatic system or logical rules. — ssu

Not in mathematical logic.

A sentence is provable from a set of axioms and set of inference rules if and only if there is a proof sequence (or tree, tableaux, etc.) resulting with the statement.

A sentence is true in an interpretation if and only if the sentence evaluates as true, per the inductive clauses, in the interpretation.

And we have the soundness theorem:

If the axioms used in a proof are all true in a given interpretation, then the proven sentence is true in that interpretation.

So, proving a sentence is not in and of itself proving the truth of a sentence. Rather, we have that if all the axioms used are true in a given interpretation, then the proven sentence is true in that interpretation.

TonesInDeepFreeze

With diagonalization, we get only an indirect proof. — ssu

No, diagonalization does not require indirect proof.

Is diagonalization a way to find mathematical statements that cannot be proven by a direct proof, but only can shown to be true by reductio ad absurdum? — ssu

No, diagonalization does not require indirect proof.

Proof of incompleteness is usually constructive. Given a system of a certain kind, we construct a sentence in the language for the system such that the sentence is true in the standard interpretation for the language (or, more informally, true of arithmetic) but not provable in the system.

Also, there are two kinds of proof by contradiction:

Assume P, derive a contradiction, infer not-P. That method is not generally controversial.

Assume not-P, derive a contradiction, infer P. That method is not accepted by intuitionists.

/

It seems people get false Internet memes in their head. I don't know where these memes originate from, but they ubiquitous and persistent in forums.

TonesInDeepFreeze

What the Turing Machine cannot compute is found exactly by using diagonalization (or negative self-reference) that we are talking in the first place. — ssu

I think the theorem you have in mind is that there is no algorithm that decides whether a program and input halt. The proof uses diagonalization. But, again, the proof is constructive. Given an algorithm, we construct a program and input such that the algorithm does not decide whether the program halts with that input.

TonesInDeepFreeze

"In particular, the consistency of P is unprovable in P, assuming that P is consistent. (in the contrary case, of course, every statement is provable)." - Godel (His proof of this being very slippery.) — tim wood

The second completeness theorem is:

If S is a formal, consistent theory that adequate for certain arithmetic, then S does not prove the consistency of S.

Godel doesn't give a full proof for the second incompleteness theorem in his famous paper. But the details are supplied in subsequent articles and textbooks by other authors.

TonesInDeepFreeze

For each element B in P(S0), form the sentence that is the coordinate conjunction of all the sentences in B. — The Vastness of Natural Language

Some of the elements of B are infinite. Those members of B that are infinite don't have a finite conjunction, but all natural language expressions are finite.

TonesInDeepFreeze

considering the first incompleteness theorem:

PA ⊢ ∃ A ( A ⇔ ¬Bew(ÍAÎ ) ) — Tarskian

Do you mean the diagonalization lemma applied to the negation of the provability predicate?

The diagonalization lemma doesn't have an existential quantifier like that. The diagonal lemma is:

If F(x) is a formula, then there exists a sentence S such that ('#' for 'the numeral for the Godel number of'):

PA |- S <-> F(#(S))

Applied to the negation of the provability predicate ('P' for the provability predicate):

There exists a sentence G such that:

PA |- G <-> ~P(#(G))

So the existence statement is in the meta-theory, not in PA.

TonesInDeepFreeze

Hilbert believed it so strongly that he insisted that all his colleagues should work on proving the above. — Tarskian

He proposed the project. But he insisted that all of them undertake it? Moreover, is there even one colleague to whom Hilbert insisted the colleague undertake it?

TonesInDeepFreeze

untested experimental vaccine shots — Tarskian

What untested vaccines? (Of course, they're untested for the people who are taking them in tests.)

ssu

Thanks for answering my ramblings, @TonesInDeepFreeze,

A sentence is provable from a set of axioms and set of inference rules if and only if there is a proof sequence (or tree, tableaux, etc.) resulting with the statement. — TonesInDeepFreeze

As an non-mathematician/logician, I'm not familiar with the terminology. So it is sentence - proof sequence - axioms? I still assume there is a link between sentence and the set of axioms.

No, diagonalization does not require indirect proof. — TonesInDeepFreeze

Diagonalization itself of course doesn't require an indirect proof. What I meant that it itself is an indirect proof: first is assumed that all reals, lets say on the range, (0 to 1) can be listed and from this list through diagonalization is a made a real that is cannot be on the list. Hence not all the reals can be listed and hence no 1-to-1 correspondence with natural numbers. Reductio ad absurdum.

Perhaps using the "negative self-reference" would be better if the reductio ad absurdum proof isn't exactly about changing something on a diagonal.

What the Turing Machine cannot compute is found exactly by using diagonalization (or negative self-reference) that we are talking in the first place. — ssu

I think the theorem you have in mind is that there is no algorithm that decides whether a program and input halt. The proof uses diagonalization. — TonesInDeepFreeze

Exactly.

But, again, the proof is constructive. Given an algorithm, we construct a program and input such that the algorithm does not decide whether the program halts with that input. — TonesInDeepFreeze

Yes. Obviously Turing constructed a quite important and remarkable proof for the uncomputability of the Entscheidungsproblem. But is that constructiveness a problem?

tim wood

↪TonesInDeepFreeze

I'm thinking he did - which I quoted from. In my ed. section 4, starting, "From the results of section 2 there follows a remarkable result concerning a consistency proof for the system P.... Theorem XI.... The proof is (in outline) the following...." The Undecidable, Davis, ed. pp. 35-36.

Tarskian

So the existence statement is in the meta-theory, not in PA. — TonesInDeepFreeze

So, according to your remark, the diagonal lemma should be phrased as:

∃ A ( PA ⊢  ( A ⇔ ¬Bew(ÍAÎ ) ) )

instead of :

PA ⊢ ∃ A ( A ⇔ ¬Bew(ÍAÎ ) )

This is an extremely subtle difference because A still needs to be phrased in the language of PA. Therefore, A must also be a sentence in PA.

Another problem is that PA is its own meta-theory in this case. That is the whole point of encoding ÍAÎ as a natural number. We thereby make use of the fact that PA is capable of self-reflection.

If PA is not its own meta-theory in this case, what theory is then the meta-theory?

Tarskian

What untested vaccines? (Of course, they're untested for the people who are taking them in tests.) — TonesInDeepFreeze

These vaccines were obviously not tested for long-term consequences.

https://www.cancerresearchuk.org/about-cancer/find-a-clinical-trial/how-clinical-trials-are-planned-and-organised/how-long-it-takes-for-a-new-drug-to-go-through-clinical-trials

Drug testing and licensing

All new drugs and treatments have to be thoroughly tested before they are licensed and available for patients.

A new drug is first studied in the laboratory. If it looks promising, it is carefully studied in people. It may be then licensed if the trial shows that it works well and doesn’t cause too many side effects. You may hear this process called ‘from bench to bedside’.

There is no typical length of time it takes for a drug to be tested and approved. It might take 10 to 15 years or more to complete all 3 phases of clinical trials before the licensing stage. But this time span varies a lot.

There are many factors that affect how long it takes for a drug to be licensed.

If the habitual length of time it takes, is 10 to 15 years, to test a new drug for long-term consequences, then I do not want to use a drug that was tested for at most 6 months.

Tarskian

He proposed the project. But he insisted that all of them undertake it? Moreover, is there even one colleague to whom Hilbert insisted the colleague undertake it? — TonesInDeepFreeze

David Hilbert had a habit of drawing the attention of the entire mathematical world to his agenda. He also successfully did that with his 23 problems:

https://en.wikipedia.org/wiki/Hilbert%27s_problems

Hilbert's problems are 23 problems in mathematics published by German mathematician David Hilbert in 1900. They were all unsolved at the time, and several proved to be very influential for 20th-century mathematics. Hilbert presented ten of the problems (1, 2, 6, 7, 8, 13, 16, 19, 21, and 22) at the Paris conference of the International Congress of Mathematicians, speaking on August 8 at the Sorbonne.

The other 21 problems have all received significant attention, and late into the 20th century work on these problems was still considered to be of the greatest importance.

Since 1900, mathematicians and mathematical organizations have announced problem lists but, with few exceptions, these have not had nearly as much influence nor generated as much work as Hilbert's problems.

Hilbert's list of 23 problems actually still had merit. There was no hidden agenda in them. His program, however, was about proving a falsehood, such as "mathematics is complete" (i.e. there is a proof for every truth). Hilbert wanted other mathematicians to find proof for his misguided ideology.

Philosophim

You can't prove arithmetic from arithmetic because we created it.
— Philosophim

Given a theory adequate for a certain amount of arithmetic, for example, PA, it's redundant to say that the theory proves all its theorems. But if the theory is formal and consistent, then there are truths of arithmetic that are not provable in the theory. This has nothing to do with who "created" the theory. — TonesInDeepFreeze

I should add a bit more to this. Arithmetic is a tool we've created from logic. It is logic which proves arithmetic, not arithmetic itself.

TonesInDeepFreeze

So it is sentence - proof sequence - axioms? — ssu

A proof is a sequence of sentences such that every sentence is either an axiom or follows by a rule of inference from previous sentences in the sequence.

What I meant that it itself is an indirect proof: first is assumed that all reals, lets say on the range, (0 to 1) can be listed — ssu

No, as I said, Cantor did not make that reductio assumption. Again:

Let g be an arbitrary list of denumerable binary sequences. (We do NOT need to ASSUME that this is a list of ALL the denumerable binary sequences). Then we show that g is not a list of all the denumerable binary sequences.

Turing constructed a quite important and remarkable proof for the uncomputability of the Entscheidungsproblem. But is that constructiveness a problem? — ssu

Church is the one who addressed the Entscheidungsproblem. Turing proved the unsolvability of the halting problem. My point was that Turing's proof is constructive.

TonesInDeepFreeze

↪tim wood

As I understand, we agree. Godel gave an outline that leaves out needed details. But you said he was "slippery". I don't see what is slippery about it.

Tarskian

It is logic which proves arithmetic, not arithmetic itself. — Philosophim

Arithmetic can be reduced entirely to logic. However, logic can also be entirely reduced to arithmetic. You only need to do it for one universal gate NAND (or NOR) because all other logic can be implemented with it:

NAND(x,y) = 1 - (x*y)

Therefore, logic and arithmetic are perfectly bi-interpretable. If you can do the one, you can automatically also do the other.

TonesInDeepFreeze

So, according to your remark, the diagonal lemma should be phrased as:

∃ A ( PA ⊢ ( A ⇔ ¬Bew(ÍAÎ ) ) ) — Tarskian

I would not write it that way. But, yes, my point is that the existential quantifier is in the meta-language and not in the scope of the turnstile.

A must also be a sentence in PA — Tarskian

What I wrote:

If F(x) is a formula, then there exists a sentence S such that ('#' for 'the numeral for the Godel number of'):

PA |- S <-> F(#(S))

Applied to the negation of the provability predicate ('P' for the provability predicate):

There exists a sentence G such that:

PA |- G <-> ~P(#(G)) — TonesInDeepFreeze

There is no mess up of what is in the meta-language and what is in the object language there. Look at virtually any article or textbook to see that they are, modulo stylistic and symbol choices, along those lines and not with the existential quantifier in the scope of the turnstile.

PA is its own meta-theory in this case — Tarskian

I don't know. It is a tricky point that I wish I understood better (especially I suspect we would need to be careful where the consistency assumption occurs?). Since it is not needed for PA to be the meta-theory, personally, I think of some other meta-theory. In any case, in ordinary expositions, the existential quantifier is not written after the turnstile. Doing so would mix up the meta-language and object theory, as otherwise would indeed cause get us embroiled in keeping straight what are the theorems of PA as opposed to what are the theorems about PA. Even if PA could be its own metatheory (I don't know whether it a can be while consistent) it is not good to write the meta-theorems such that they are both in the meta-theory and object theory, lest the exposition becomes quite confusing. Moreover, when we move on to mention 'truth', the language for PA cannot be its own meta-language.

If PA is not its own meta-theory in this case, what theory is then the meta-theory? — Tarskian

Whatever you choose that is adequate. Godel performed the proof in ordinary mathematics and reasoning in natural language. On the other hand, set theory works even though it is more than we need. And, though I don't know the details, PRA would serve as an admirably lean basis.

TonesInDeepFreeze

These vaccines were obviously not tested for long-term consequences. — Tarskian

Correct, of course.

TonesInDeepFreeze

David Hilbert had a habit of drawing the attention of the entire mathematical world to his agenda. — Tarskian

I don't know that it was a habit, but of course he made his agenda prominent. But that is a far cry from insisting that all his colleagues work on it.

His program, however, was about proving a falsehood, such as "mathematics is complete" (i.e. there is a proof for every truth). Hilbert wanted other mathematicians to find proof for his misguided ideology. — Tarskian

He wanted to prove something. He did not claim that it might not turn out to be untrue. He expected that it would be true, but that's hardly even a foible. And "ideology" suggests connotations that I don't see as warranted.

TonesInDeepFreeze

Arithmetic can be reduced entirely to logic — Tarskian

What specific reduction do you have in mind?

Tarskian

Look at virtually any article or textbook to see that they are, modulo stylistic and symbol choices, along those lines and not with the existential quantifier in the scope of the turnstile. — TonesInDeepFreeze

Yes, I have noticed. But then again, I have never understood it like that. In fact, I have just always ignored it. I have always seen it as PA talking about itself.

Of course, some other theory could talk about PA, but the textbooks or papers do not seem to elaborate any examples. ZFC would not be a good candidate because it is too much like PA. ZF-inf is even bi-interpretable with PA. I have only ever run into one such example, i.e. Goodstein's theorem, where the theorem is in PA while the proof is in ZFC.

Moreover, when we move on to mention 'truth', the language for PA cannot be its own meta-language. — TonesInDeepFreeze

Yes, agreed. The truth of PA is in ZFC. But then again, where is the truth of ZFC? The only answer that I have found to this question is the following nebulous explanation on math exchange:

https://math.stackexchange.com/questions/1717893/in-relatively-simple-words-what-could-be-a-model-of-sf-zfc

My question is: What does a model of ZFC look like?

The question seems to come down to a common confusion: how can a model of ZFC be a set, if we want to use ZFC to study sets?

The answer is, essentially, that things don't work that way. To study "models", we need to work in a metatheory that already has some concept of set or collection. The "metatheory" here is the theory that we use, as a tool, to study the object theory.

There are many options for such a metatheory. One option would be ZFC itself, except that (by the second incompleteness theorem), ZFC can't prove that there is a model of ZFC.

In my impression, model theory is only straightforward for the simple case of PA being interpreted by ZFC's truth. Everything else seems to be smoke and mirrors.

fishfry

That should read "countably infinite." We can think of endless permutations of language, but we could also spend and infinite amount of time saying the names of the reals between any two natural numbers. — Count Timothy von Icarus

Lost me. There are uncountably many reals between any two natural numbers.

Not sure what's being argued here. The cardinality of natural language is not relevant to the thread, it's a side topic. It is a fact that there are only countably many finite-length strings over an at most countably infinite alphabet. I think that addresses the issue, but perhaps there's some disagreement.

Tarskian

What specific reduction do you have in mind? — TonesInDeepFreeze

"How Computers Work: Arithmetic With Gates"
http://www.goodmath.org/blog/2022/12/26/how-computers-work-arithmetic-with-gates

sum = x XOR y
carry = x AND y

fishfry

Nicely phrase. Our new chum is propounding much more than is supported by the maths. Here and elsewhere. — Banno

Chumming the water, is our new chum. But actually I'd heard the same claim from Chaitin, and it wasn't till I read the paper referenced by the OP that I learned that this is a very trivial observation related to undefinable real numbers, and not a major insight. But perhaps Chaitin has taken it deeper.

Any readable proof of Cantor's Theorem will contain at most a finite number of characters. Yet it shows can be used to show* that there are numbers sets* with a cardinality greater than ℵ0. — Banno

Yes, a point made by the constructivists I believe. Math talks about the infinite but math itself consists of finite-length proofs.

And we are faced again with the difference between what is said and what is shown. — Banno

Moby Dick didn't really kill Ahab, even though we may have enjoyed the story. Moby and Ahab never existed. We can always use language to describe impossible things. "Fly me to the moon and let me play among the stars." What kind of pedant would complain about the illogic?

So will we count the number of grammatical strings a natural language can produce, and count that as limiting what can be - what word will we choose - rendered? That seems somehow insufficient. — Banno

Lost me here. Anyway I don't think I should get too involved in the question of natural language, even if I believe my countability argument applies. There are only countably many finite-length strings over a countable alphabet. I just don't see that there's any more to say; but again, I'd rather talk about Chaitin's idea than get tangled up in the complexities of natural language.

And here I might venture to use rendered as including both what can be said and what must instead be shown.
a
Somehow, despite consisting of a finite number of characters, both mathematics and English allow us to discuss transfinite issues. We understand more than is in the literal text; we understand from the ellipses that we are to carry on in the same way... And so on. — Banno

It's like a trip to the moon on gossamer wings. We have no trouble expressing the thought, even though it describes something that's not possible, even if we knew what gossamer wings are. Unless by gossamer wings we mean the hardware of the Apollo missions.

Symbolic language lets us express many fanciful ideas. Alice laughed. 'There's no use trying,' she said. 'One can't believe impossible things.'

I daresay you haven't had much practice,' said the Queen. 'When I was your age, I always did it for half-an-hour a day. Why, sometimes I've believed as many as six impossible things before breakfast.

Of course Lewis Carrol was a logician as well as a writer of children's stories, and perhaps he was making this very same point. That with language, we CAN believe, or at least express, impossible things.

But further, we have a way of taking the rules and turning them on their heads, as Davidson shows in "A nice derangement of epitaphs". Much of the development of maths happens by doing just that, breaking the conventions. — Banno

Yes. Math is all about believing impossible things! A point that I'm sure did not escape Carrol's notice.

Sometimes we follow the rules, sometimes we break them. No conclusion here, just a few notes. — Banno

Yes.

TonesInDeepFreeze

I never understood it like that. In fact, I just always ignored it. I always saw it as PA talking about itself. — Tarskian

They ordinary way of writing it up is quite understandable, in context of Godel's original paper and in context of just about any article or book on it. Your way though requires me to regard PA as the meta-theory, which is not a required assumption for the proof.

Yes, PA can "talk about itself" in a certain sense (though I don't know that it can formulate all of the proof when it is a proof about PA). But we don't ordinarily stipulate that the proof about PA is being given in PA. In an ordinary exposition of the proof, it seems to be it would be, at best, an invitation to a lot of confusion to presuppose that the proof is being given in PA.

where is the truth of ZFC? — Tarskian

In, for example, ZFC+"there exists and inaccessible cardinal".

But, yes, of course, that is not an epistemological basis. But that issue is aside the point that one does not ordinarily stipulate that PA itself is the meta-theory.

model theory is only straightforward for the simple case of PA being interpreted by ZFC's truth — Tarskian

I don't know your criteria for straightforwardness, but model theory is rigorously developed, though it does use infinitistic mathematics.

smoke and mirrors — Tarskian

What is an example?

Tarskian

I don't know your criteria for straightforwardness, but model theory is rigorously developed, though it does use infinitistic mathematics. — TonesInDeepFreeze

It works fine for me, as long as it talks about ZFC models of PA. Model theory also uses infinitistic mathematics in that context. I have no problem with that.

I only give up when it talks about the models of ZFC. At that point, it is no longer capable of cleanly separating provability and truth: "How can a model of ZFC be a set, if we want to use ZFC to study sets?"

Concerning "smoke and mirrors", well that is about models of ZFC, where the theory is essentially its own model.

TonesInDeepFreeze

↪Tarskian

As I only perused, there's a writeup there about carrying out arithmetic with logic gates.

But to say that arithmetic can be reduced to logic requires showing, for example, the derivation of the axioms of PA from only logical axioms, or even more basically to define the non-logical primitives of PA from logical primitives. And those ain't gonna happen.

Mathematical truth is not orderly but highly chaotic

Welcome to The Philosophy Forum!

Categories

More Discussions