I think I have improved on my technique of explaining it.

1. Godel proved that some math statements are unprovable. (I am using that word rather than "undecidable" because I don't think number theory conjectures that involve finding a counterexample can be undecidable, since undecidable would seem to imply you can't find a counterexample so the conjecture would be true.)

2. Someone here said that it was proven that number theory conjectures have been proven to never be unprovable if they are indeed true. If he is right about all number theory conjectures there is no need to read further.

3. There are number theory conjectures that would likely have no counterexample if the numbers behaved like random numbers and you only took their sparseness into account. It wouldn't matter that there is an infinite number of opportunities to find a counterexample because it gets sufficiently harder and harder after each failure. I believe Goldbach's Conjecture meets this criteria. Call them Sparse conjectures.

4. There are also number theory conjectures where the density of the numbers involved would make the probability essentially 100% of finding a counterexample if those numbers behaved randomly. I believe Euler's (incorrect) conjecture that three cubes can't sum to a cube is an example. Call these Dense conjectures.

5. My contention is this: If there are actually any unprovable (but true) number theory conjectures, they will all be sparse. Conversely any true dense conjecture has an essentially zero probability of being unprovable.

What is the difference between "never be unprovable" and "be provable"?

Someone linked to a talk about Gödel's theorem recently where I thought I heard the guy say that proofs must exist for True statements but what Godel showed was that there is no algorithm which can generate proofs for all True statements. There is no algorithm which can decide the truth of all statements. In fact, there is no algorithm that can decide the truth of more than a finite number of statements.

If I understood him correctly then I guess I've misunderstood Godel before this - which may be the case anyway.


PairTheBoard

No difference.

I didn't read it particularly thoroughly, but I didn't see any conjectures.

His main conjecture is that if any true number theory conjectures are unprovable they will have this sparseness property.

This might be true but unprovable (and sparse of course if it can be expressed within number theory).

Here is the talk masque linked to in the Godel thread.

He starts talking about incompleteness around 9:00 minutes in. Around 16:20 a question is asked which can't be heard and he says,

"In general it is always possible to prove a sentence is true and unprovable but not in an algorithmic way."

However, I think this must be in the context where all true and unprovable sentences have been adjoined as axioms to the axiomatic system. He had just mentioned such a case.

In that interval he was asked what it means for an unprovable sentence to be "true". He said he would get to that in a minute but then he never did.




PairTheBoard

Is anything unprovable true in a meaningful sense?

Try this;

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

https://en.wikipedia.org/wiki/Second-order_arithmetic

and then after briefly seeing the above (promising yourself to revisit if not a mathematicians already lol) consider this;

https://en.wikipedia.org/wiki/Goodstein's_theorem

"In mathematical logic, Goodstein's theorem is a statement about the natural numbers, proved by Reuben Goodstein in 1944, which states that every Goodstein sequence eventually terminates at 0. Kirby and Paris[1] showed that it is unprovable in Peano arithmetic (but it can be proven in stronger systems, such as second order arithmetic). This was the third example of a true statement that is unprovable in Peano arithmetic, after Gödel's incompleteness theorem and Gerhard Gentzen's 1943 direct proof of the unprovability of ε0-induction in Peano arithmetic. The Paris–Harrington theorem was a later example.

Laurence Kirby and Jeff Paris introduced a graph theoretic hydra game with behavior similar to that of Goodstein sequences: the "Hydra" is a rooted tree, and a move consists of cutting off one of its "heads" (a branch of the tree), to which the hydra responds by growing a finite number of new heads according to certain rules. Kirby and Paris proved that the Hydra will eventually be killed, regardless of the strategy that Hercules uses to chop off its heads, though this may take a very long time."

For added conceptual/realization value also consider these links;

http://www.cs.tau.ac.il/~nachumd/term/Kirbyparis.pdf (the above Laurence Kirby and Jeff Paris / Hydra paper)

and discussions here may be interesting;

http://math.stackexchange.com/questi...able-statement

http://math.stackexchange.com/questi.../453764#453764

A book of interest also ;

https://books.google.com/books?id=G2...0Proof&f=false

Why do I need to read this? Does it specifically apply to the following two conjectures and my contention about them?

Conjecture 1. Staring with the googleth digit of e marked off two at a time there will never be a perfect square. I contend that if this is true there exists a proof. Since if it was random you have to hit a square eventually

Conjecture 2. Starting with the googleth digit of e marked off 2 then four then six etc digits there will never be a perfect square. If statements like this are eligible to be unprovable then, even if the conjecture is true there doesn't have to be a proof. Because if the digits of e were merely random numbers this second statement would usually be true for no other reason than the sparseness of squares.

It relates to the concept of unprovable within an axiomatic system yet still true within a greater system. I was addressing the last few posts really not the original mostly.

I gave examples of this situation.

I am trying to see in what way you use the concept uprovable yet true in number theory. For example what do you have in mind that has been shown to be unprovable but we know is true about natural numbers.

At a practical level what i could find is

https://en.wikipedia.org/wiki/Hilbert's_tenth_problem

https://en.wikipedia.org/wiki/Diopha...ch.27s_theorem

" Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers.

It took many years for the problem to be solved with a negative answer. Today, it is known that no such algorithm exists in the general case because of the Matiyasevich/MDRP theorem that states that recursively enumerable sets are equivalent to diophantine sets. This result is the combined work of Martin Davis, Yuri Matiyasevich, Hilary Putnam and Julia Robinson[1] which spans 21 years, with Yuri Matiyasevich completing the theorem in 1970."


Again what examples of known truths about natural numbers you have that are shown to be unprovable?


As a physicist i could argue for example that we may never know what is the sum of the 10^(10^(10^(10^(10)))) twin prime pair decimal digits (is it an even or an odd number) even if we prove that there are infinite prime pairs (i think current gap bound is down to 246 so lets say its proven eventually that the minimum 2 appears infinite times) because we do not have the resources in this universe to answer this question.

Certain conjectures appear very tough and hopeless but which one do you have in mind that has already been proven true and unprovable (also within what system unprovable to be true? and within what true?)

Maybe we can also look at the term unknowable here.

Also what if it is shown that a counterexample if it appears it appears at some huge number and higher that cannot be tested again due to physical limitations (ie not enough memory for whatever Turing computer scheme etc). So the counterexample may exist and cannot be found.


Also because of density arguments one cannot be certain they carry to full proof eventually (they are not formally strengthening a rigorous proof unless properties for the numbers considered are proven that secure it on other levels). I mean i can define numbers that never have the properly that naive probability arguments would secure they have if randomness was assumed by precisely going against the tide in the definition of the number while still the number appears to be normal if you run tests and take their limits. Also i think we cannot in principle test all possible ideas of random in the digits of Pi for example. After all the digits are not random, they are the digits of Pi and not some other number. I mean technically a properly may be avoided systematically (that would have probability 1 to eventually be hit i mean based on high density arguments) and in such a way that all digits still tend to appear 10% of the time in the limit. I may think of an example to show that i can construct a number to never have a property that other naive probability arguments would have you believe it has and where each digit or sequence of digits in the limit does appear random.

I think you might just be too intelligent to get the simplistic point I am trying to make. Perhaps uke master or dessin d'enfant can explain it to you.

Arent you saying in essence that once the original Fermat problem fails a few small n cases (x^n+y^n=z^n) , its destined to fail everything basically because eg when you have x^101+y^101=z^101 the numbers get so high ie for z^101 with z>=m (say m=10) that x, y that also have to be less than z give it basically less than z^2 opportunities to get there and represent such a huge number eg z=10 leads to 101 digit number that has to be matched now by some less than 10^2=100 (not even 1/3 or 1/4 of that really) combinations or x,y similarly large numbers (so far out odds right?) that have a tiny chance to make it and if you go and check z=11 next its even larger now without the range of xy having increased all that much in comparison and so if you go all the way to infinity in some probability integration sense you will get the chance to hit it is a very tiny number and if you go over all exponents above a certain high N that has been proven to be true all the way to infinity it wont amount to anything significant as probability ( eg before Wiles say by 1993, Fermat's Last Theorem had been proven for all primes less than four million).

So its like n >4 mil you have like z^4mil for example is such a large number than the x,y chances to hit it, eg if z is 10 ,x,y less than 100 combos say offer a tiny probability to match it that is astronomically small and all the way to infinity the overall probability will remain super-tiny as z grows for that exponent.

So you would be using these arguments like eg a probability less than 10^(-1mil) type things to claim that its almost a certainty there are no solutions for these high exponents.


What i need to do is create an elaborate counterexample where density arguments fail and the plausible conjecture holds (if you didnt know how i defined the number) moreover everything working against it if the numbers were truly random (which they arent even if they share properties with random numbers in some limits when tested in some usual sequence tests).


Until i do that consider this for example;

https://en.wikipedia.org/wiki/Skewes'_number

It would appear that if you have an estimate for prime number counting function using the https://en.wikipedia.org/wiki/Logari...egral_function that it would not fluctuate around it but it does and in fact it was proven that it does infinitely often, yet the first time it does cross the sign (imagine it like a random walk) hasnt been found yet with any computer (it happens higher than the number 10^17 ) and still we know its there!

You may also need to specify on your point 5 when you say unprovable (but true) how do you establish they are true (within what system of axioms) and where is the unprovable part (in what axioms). (This is why i asked specific examples and i can provide some of my own from prior links i posted here and that i found to be interesting - eg an Erdos color - 4 numbers problem that connects to continuum hypothesis - but they are not your typical big name unsolved problems)

And notice again what i said that it may be unprovable for technical reasons (not logical structure ones) that have to do with the fact that you need a universe to do math, its not all in your head, even in the head it is in neurons and emerging information processing chemical systems lol, and in order to actually have a Turing machine in needs matter to work with and the concept of infinity is bs.

I mean if some thing requires10^(10^(10^1000))) steps to be executed to render a critical to the problem detail, it wont ever happen in this universe the way physics looks now.


And by the way we have also these guys that would appear ok with physics reasons too

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

contrasted with the ones on the other side that think in various classes of infinity too lol.

Your father was taught by Edward Kasner, right?

https://en.wiktionary.org/wiki/googolth

Yes. And Norbert Weiner, Ernest Nagel, A Adrian Albert, Arthur Compton, Mortimer Adler, and Lise Meitner.

I don't know what the definition of unprovable is. But I think I know what provable is. And I am saying that true dense conjectures are provable. If a monkey can never type Shakespeare there has to be a reason why. But if there is no reason why a sparse conjecture never has a counterexample that doesn't mean that there will be a counterexample.

I give a three dimensional random walker instructions for eternity. I show you those instructions and you say there is no way to prove that he will never get back to the origin. I take your word for it because even though I don't understand your math I know there is unprovable stuff and I think this could be an example because if the instructions were random he might never return. But if it was a two dimensional random walk and my instructions never got him back to the origin, I wouldn't believe you if you claimed that there was no way to prove it.

Ok the random walk example is a good one for the point made because at 2 dimensions its almost surely destined to return and at d=3 is ~34%.

But we do have true random walk here not instructions that relate eg to prime numbers or something like that eg digits of Pi etc.

I mean yes most of the time the heuristic you imagine with probability calculations as if some things were truly random will offer a good hint about the real result. Its just that you can never be sure because in principle one can imagine a dense enough case that would appear to eventually hit the conjecture but the structure is designed in a such a way that it just about fails at the critical points by design (ie seemingly random but correlated) without compromising the overall sense of randomness.

I will try to find a very convincing example and i will return to this.

You want to essentially argue that the probability heuristic will always work in determining if something is provable.

The monkey may be able to write a novel but it may be operating semirandomply in a way that if it ever gets to finish 5 sentences that make sense some transition takes place to mess up the process and restart it and that transition is part of the original rules. Such rules may be known and so we know what to expect but they may not be known also. It is possible that the sequence looks random but it has a subtle correlation in it that without essentially messing the long term averages it prevents certain sequences and unless you check for them you may never reveal that deficiency from the ideal randomness that would reject such property. After all eg prime numbers are not random. They are where they are because of the properties of natural numbers and some of the properties may prevent a particular rare thing from happening if you know what to look for.

NO. I am saying that if the number theory conjecture that involves not finding a counterexample is dense, then if it true that you will never find a counterexample, there will be a proof for that. But I am not saying that if the conjecture is provable it is dense. Fermat triples for cubes is dense and thus I contend that it was provable if true. But seventh powers are sparse. And of course that turned out provable also. But if number theory problems that involve counterexamples are sometimes unprovable, I contend that seventh power addition of two numbers were originally eligible to be in that category, but third powers were eliminated from the git go.

( I should note a technical problem. An apparently dense conjecture might be able to turn into a sparse one with sufficient fiddling.)

The "essentially zero probability" clause is key imo. To be consistent you should include language indicating that in both cases. i.e.

"5. My contention is this: If there are actually any unprovable (but true) number theory conjectures, they will almost surely be sparse. Conversely any true dense conjecture has an essentially zero probability of being unprovable."



I think that's the best version of your conjecture. I believe Godel had a way of describing the set of all allowable statements. It would help if we had that in front of us. If there's a way of describing that subset consisting of "sparse" and "dense" type statements and there's in some sense a natural measure that could be applied to it, then your conjecture might be put into precise mathematical form. Once in precise form attempts could be made to prove or disprove it. Until then it's all hand waving.

I've always liked the idea.

PairTheBoard

There doesn’t seem to be any good reasons to think that any of the problems being talked about will ever end up being independent of logical systems strong enough to express them, regardless of whether they are sparse or dense.

Things that have been shown to be independent in number theory seem to involve either universality (halting problem, Diophantine equations), equivalence to the consistency of the logical system itself (Gödel’s Theorem, Ramsey theory results whose independence I don’t really get) or non-primitive recursive functions that grow too fast to be fully definable in 1st order logic (more Ramsey theory). And I’ll point out that in the Ramsey Theory cases the theorems are pretty straightforward to prove, in 2nd order arithmetic, it’s just that they are independent of PA.

You are talking about number theory statements that don’t seem to have any universality, don’t seem likely to be equivalent to the consistency of any natural set of axioms and don’t involve any super-fast growing non-primitive recursive functions. They are just problems that we don’t really have any idea how to prove, which are a dime a dozen….but have no reason to be independent.

"Almost surely" is implied from "essentially zero" but it can't hurt to say it. On the other hand they are both technicalities. A monkey WILL type Shakespeare if there isn't a logical reason that stops him, as far as I am concerned.

I am fairly certain that civilized Christian conjectures only involve true-false statements with no allowance for probability.

So you are saying they are all provable, if true? I have never contended otherwise you understand. I am only making contentions about their nature IF they are unprovable.

Yet the reason may exist in a higher logical system than the one the conjecture was first made.

For example you may be within ZFC and the proof may depend on continuum hypothesis that is independent.

That is for example it seems the case for this;

" Take a countably infinite paint box; this means that it has one color of paint for each positive integer; we can therefore call the colors C1,C2, and so on. Take the set of real numbers, and imagine that each real number is painted with one of the colors of paint.

Now ask the question: Are there four real numbers a,b,c,d, all painted the same color, and not all zero, such that
a+b=c+d?

It seems reasonable to imagine that the answer depends on how exactly the numbers have been colored. For example, if you were to color every real number with color C1, then obviously there are a,b,c,d satisfying the two desiderata. But one can at least entertain the possibility that if the real numbers were colored in a sufficiently complicated way, there would not be four numbers of the same color with a+b=c+d; perhaps a sufficiently clever painter could arrange that for any four numbers with a+b=c+d there would always be at least one of a different color than the rest.

So now you can ask the question: Must such a,b,c,d exist regardless of how cleverly the numbers are actually colored?

And the answer, proved by Erdős in 1943 is: yes, if and only if the continuum hypothesis is false, and is therefore independent of the usual foundational axioms for mathematics."





The result is mentioned in

Fox, Jacob “An infinite color analogue of Radó's theorem”, Journal of Combinatorial Theory Series A 114 (2007), 1456–1469.

Fox says that the result I described follows from a more general result of Erdős and Kakutani, that the continuum hypothesis is equivalent to there being a countable coloring of the reals such that each monochromatic subset is linearly independent over Q, which is proved in:

Erdős, P and S. Kakutani “On non-denumerable graphs”, Bull. Amer. Math. Soc. 49 (1943) 457–461.

http://math.stackexchange.com/questi...able-statement



So here is my idea; one can design an elaborate problem that appears to be dense but to also depend on something external like CH. You wont be able to decide it within ZFC so it will be unprovable. Yet it will be dense and there will be a reason indeed for it failing but the reasons wont be able to be identified within ZFC, it will require the extension.


Additionally the reason may be found in something that in order to understand you need to perform a very long calculation and collect data that is prohibitive within our current universe. That may make the reason unknowable within a certain system. That wouldnt be logically unprovable but pragmatically unknowable, hence the proof can never be performed in our universe by any machine of this universe even if the entire universe was used to do the proof.