You said a Turing machine cannot prove Goldbach. That is not true. If it's true in the standard axioms a TM can verify the proof, it's false it can verify the counterexample and if it's independent it can verify that the standard model cannot ever prove the existence of a counterexample. All of those resolve the conjecture, provided the standard axioms are consistent. ABC is different in the last case, as it being independent of the standard axioms does not guarantee it's truth, without an upper bound on possible exceptions. But that is another issue.

I should have said a Turing machine cannot necessarily prove Goldbach.

Are you disputing that Goldbach might be an example of an arithmetic statement that is true but not provable?

Oh okay, I get what you were saying now.

When you say not proveable, you have to mention with respect to what axioms. If you show that Goldbach is not provable in PA, that in itself is the proof of Goldbach. It's just not a proof in PA.

I think it's possible for "P is unprovable" to be both true and unprovable.


PairTheBoard

Don't you mean "decidable" rather than "provable". If Goldbach can't be decided than there must no counterexample so Goldbach would be right. However if you only can't prove that there is no counter example, then he may or may not be right. (UNLESS there is some theorem that says that every conjecture of this ilk that is indeed true, has a proof of such. I was under the impression that I was told that there is such a theorem.)

If Goldbach is false then it's provably false via exhibition of the counter example. But what if the statement "Goldbach is either true or false" is nonsense?


PairTheBoard

Then you will have discarded a Law of Thought.

https://en.wikipedia.org/wiki/Law_of_excluded_middle

Not all statements are allowed in that courtroom, e.g. Russell's Paradox.

On a Turning machine searching for a Goldbach counter-example; Consider the statement, "Either it halts or it doesn't". I think it's probably nonsense. It's equivalent to saying, "Either it halts or it runs forever". But running forever is impossible. So it's equivalent to saying, "Either it halts or it does something impossible". If the statement is true and since it can't do something impossible it must therefore halt by finding a counter-example. So claiming the statement is true amounts to claiming Goldbach is false. Yet claiming the statement is false means that both halting is false and doing something impossible is false. But halting is false means Goldbach is true. Thus, determining the Truth Value of the statement determines the Truth Value of Goldbach. I contend the statement is neither true nor false because it's nonsense or at least not allowed in the courtroom of excluded middle law.

Yet it seems generally accepted that appeal to the statement shows that the Goldbach property must either be a true or false property of the integers. I just find such an assumption suspect. I don't think the integers are real things with real properties. I think there may be different logical versions of the integers whose logical properties are dependent on the richness of the axioms on which the versions are based.


PairTheBoard

You'll be doubting the existence of non-computable functions next.

A Turing machine is a theoretical concept, and as such, it can. Of course a real Turing machine wouldn't run forever, but only because someone pulls the plug or it is consumed by the Sun going supernova or w/e. But that has nothing to do with the program the Turing machine is running.

I meant "not proveable" as in independent. PA cannot prove it. PA cannot produce a counter example.

Again, you have to specify "can't be decided" with respect to what axioms. The textbook model theory example is Goodstein's theorem. It is true for the standard integers, but independent of PA. So it is possible to construct a (nonstandard) model that satisfies the axioms of PA and produces a counterexample.

If this were the case for Goldbach, your statement "Goldbach would be right" is reasonable because Goldbach is a statement about the standard integers and not any model of PA. Of course for most "natural" conjectures" those are one in the same.

Sure. That's more or less the situation we are actually in.

Your impression certainly seems to be wrong. Unless "of this ilk" doesn't apply to certain Diophantine equations with no solutions but don't have proofs of this fact in ZF.

Of course. But It's actually even worse than that. By the compactness theorem there are different models of the integers based on the exact same Peano axioms. That's why when you want to talk about specifically the standard integers, you need some external logical system; ZF, true arithmetic, intuition etc. But if you honestly have doubts about the integers, I find it hard to believe that any set of axioms would satisfy you. These axioms were only chosen because the standard integers were a model.

How does a Turning machine's calculations differ according to whether it's working in the Standard Model or a Nonstandard Model?


PairTheBoard

Some basics:

TuringMachine.html

wolfram.com/HaltingProblem

GoldbachConjecturel


Additional Info from SEP:

stanford.edu/entries/turing-machine/

It depends on how you construct the model. That's what so great about the standard integers. You rarely if ever have to worry about any of this model theory stuff because every human learns about the integers and can prove theorems about them well before they study model theory. On the contrast, nonstandard models are studied exclusively by mathematicians and for most only once as an undergrad in logic 101. It's not something that really impacts other areas of math strongly.

Did someone say Gödel?

https://en.wikipedia.org/wiki/Peano_axioms#Arithmetic
------------------------------
The Peano axioms can be augmented with the operations of addition and multiplication and the usual total (linear) ordering on N. The respective functions and relations are constructed in set theory or second-order logic, and can be shown to be unique using the Peano axioms.
================

So the Peano axioms have to be "augmented" by second-order logic to get arithmetic? I did not know that. But then Gödel's theorem about "any system rich enough to contain arithmetic is something or other" wouldn't apply to the simple system of Peano axioms would it? If that's the case that's also news to me.

So in the non-standard model in which Goodstein's theorem has a counter example the Peano axioms must be augmented by some other kind of logic than "second-order logic" to get an arithmetic in which actual arithmetic calculations are different than in standard arithmetic. Can they actually produce that system of logic or do they just prove that some such alternative model exists?


PairTheBoard

Not necessarily by 2nd order logic. Arithmetic is fully definable in first order logic and incompleteness applies to PA. Quoting from later in that article

It's pretty straightforward to produce, but probably a but much for here. See this for details.

From your link above:
------------------------
A second point is that you may find that there are no specific "natural" models of PA at all other than the standard model. For example, Tennenbaum proved that there are no computable nonstandard models of PA; that is, one cannot exhibit a nonstandard model of PA so explicitly that the addition and multiplication of the model are computable functions. (See this related MO question.) But I do not rule out that there could be natural nonstandard models in other senses.
=============

So even if you exhibit an "explicit" non-standard model where Goodstein is false, you could never run two parallel Turing machines calculating the non-standard's counter-example Goodstein sequence to see where the arithmetic calculations differ. Reason being that the Turing machine could not do the arithmetic calculations in the non-standard model.

If PA with first order logic defines standard arithmetic then the Goodstein counter-example non-standard model must work according to some other logic? I'm gathering that logic cannot be finitely expressed? Do mathematicians have any ideas on whether an alien intelligence could work via such logic? Maybe doing their arithmetic via some unknown non-computable means? Would this make them too dumb to survive? Or are we the ones working with a logic making us too dumb to survive?


PairTheBoard

Does publishing it make it more available to the best mathematicians around the world? If so, why would he do that if he knew he had he had made an error?

Ego. He likely thinks the proof is correct. Publishing it wouldn't make it more available now; he already announced he has a proof of the abc conjecture and everyone knows about it. Publishing would just be a formality.

His options are a) retract the paper, admitting it's wrong, or b) continue claiming it is correct and push to have it published. Japan has a strong culture of saving face, so a) is off the table. He's going with b.

I think Scholze (at least at one point) said there is perhaps some subtlety in the argument he is missing. Which is what Mochizuki is clinging to, so maybe he's convinced himself there is some magical way to save the proof. But the fact that he can't explain the corollary in some alternative way that makes sense to someone of the caliber of Scholze (or anyone else), means it is ~0% to be correct.

In any case his conclusion is generally considered correct, right? It is only the logic that people think is wrong.

That seems to be the confusion. First order logic does not define standard arithmetic. Standard arithmetic is a model that obeys PA plus some first order extensions, but there will always be additional properties that the standard integers have that cannot be understood true by just looking at the Peano Axioms. Goodstein's theorem and Godel statements are two well known examples.

So it's not correct to say that a model where Goodstein's theorem is false works under some other logic. It obeys PA exactly as much as the standard integers. The new model just does not have some additional properties not required by PA that the standard integers have.