Craig Alan Feinstein explains why the Collatz Conjecture is unprovable. For more information about unprovable conjectures, click: arxiv.org/abs/m... arxiv.org/abs/c... arxiv.org/abs/m... arxiv.org/abs/m...
@@WWLinkMasterX Assume a statement A that is unprovable and true. Create a statement B such that B = NOT(A) A is unprovable and as such B is unprovable But A = true -> NOT(A) = false Thus B is false and is unprovable, which disproves your claim. More generally Goedel's theorem proves that there are unprovable theorems that are true, which is significative as it means that once you find that something in uprovable you cannot assume it to be false. However it does not prove that somethign to be true. Your statement as written reads as: A is unprovable -> A is true But if we know A to be unprovable we proved A. Thus we reach an absurdum and your statement is false (if we accept RAA in our logic, of course).
@@lucabattisti8107 In this case, proving the collatz conjecture unprovable does imply things about the problem. For instance the conjecture being unprovable means that you can not test wether it's true or not by iterating over the integers. Which means that there are no cycles apart from 1 2 4, as cycles can be tested with finite computing power and it would render the statement "the collatz conjecture is true" false by counter example. But there could still be an infinitely growing sequence and we wouldn't be able to know so it still doesn't prove the conjecture.
@@carlosarcia5714 The argument you make is indeed compelling it would be probably more correct to state that there are no finite cycles (because of how we reach that conclusion) but that's factually the same in our case. I have some doubts myself that the proof presented by Feinstein is entirely correct, I'm afraid that level of abstraction could be a fair bit beyond my grasp. Specifically the part where Feinstein claims that the existence of an injection from T^(k)(n) makes it necessary to specify T^(k-1)(n) in the proof looks like magic to me. I intuitively agree that it would prevent constructive proofs of the conjecture but it does not seem evident to me that all proofs need to specify the precedents that bring that number to 1 (see Th.2 of his paper "The Collatz 3n+1 Conjecture is Unprovable"). Essentially I agree that the fact that it is unprovable means that you cannot prove it by iterating over integers but I'm not sure that the fact that you cannot prove it by iterating over integers means that it is unprovable.
@@lucabattisti8107 yep, it is not the same argument, as iterating over integers only gives information of the numbers you have tested. Also, there is no point in proving something unprovable in a general manner, as things can only be not provable under an specific and closed axiomatic system. There could be a new axiom that could let us discover the truth, in this case in less than infinite lines since that is what Feinstein used as the argument. Furthermore, if i understood correctly, the definition of random proposed by feinstein falls apart since any vector can be simplified thanks to Theorem 1, but i might be wrong.
I never said that using 5 as the multiplier instead of 3 proves anything about the original problem. I was just using 5 as an example of how such a sequence can diverge to infinity.
Exactly! x^2+y^2= z^2 has infinite number of solutions over the integers. But that does not imply that exchanging 2 for an arbitrary integer n>2 yields the same.
It makes some sense, because 3 is the only number that will work for the multiplier. Anything greater including 5 will make the number multiply forever. I don't know why, but I would reason that as you keep multiplying and dividing down, you must eventually reach the original beginning of "3 * 1 + 1, /2 /2 = 1; only the answer an equivalent of the original equation in complex form. I don't know the actual formula though.
The reason the equations were chosen as 3n+1 and n/2 was because 1. the "+1" guarentees and even number as an output 2. because of this 3n+1 can only iterate one in quick succession while n/2 can iterate multiple times, and when it does it drops the number faster than the 3n+1 can make it grow. for 5n+1, it takes 3 iterations for n/2 to decrease the quatity faster than 5n+1 which is MUCH less likely. Essentially, the equations were chosen specifically for the reason to descend to 1. However, it must still be proven
Why people think the whole "is,not bigger than 1". If cycle above 2^60 exists, then the whole idea of descending quicker is not valid, a sit can descend all it can, but if it come i to a cycle then a counter example is found. I personally think Collatz Conjecture is somehow connected with Odd Golden number
Kam Last You are certainly right about the non 1 cycle. If we use division by 2 and multiplication by 3 into subtraction by 1, we get the cycle 7, 20, 10, 5, 14
I've read your previous arguments in maths forums and I'm not yet convinced by your conclusions. The problem is in discovering " why" the sequences always eventually iterate to 1->4->2->1. Just because we don't know 'why' yet does not preclude us from discovering it in the future.
But we do know why they always go to 1. It's because on average, the the iterates decrease by a multiplicative factor of sqrt(3/4), which is less than 1. But this is not a proof. This is only a heuristic probabilistic argument.
"Just because we don't know 'why' yet does not preclude us from discovering it in the future." Exactly... See Neil De Grasse Tyson's statement on religion. Same exact deal... "Does it mean, if you don’t understand something, and the community of physicists don’t understand it, that means God did it? Is that how you want to play this game? Because if it is, here’s a list of things in the past that the physicists at the time didn’t understand [and now we do understand] [...]. If that’s how you want to invoke your evidence for God, then God is an ever-receding pocket of scientific ignorance that’s getting smaller and smaller and smaller as time moves on - so just be ready for that to happen, if that’s how you want to come at the problem." Just 'cause we don't know now, doesn't mean we won't know in 5 years. And then nay-saying will look stupid in retrospect. I mean, why would anyone ever need more than 64kb of computer memory?? Honestly... :P
I worked on the CC for 11 months, stopping about four months ago. At least in one aspect, CC is perfectly balanced between convergence and divergence. Convergence is easy because it has an ending point, divergence doesn't. The CC may be a lot of things, but one thing is isn't, is chaotic.
Pasqualmie, the problem is there is nothing preventing most of the iterations from being (3n+1)/2, which would cause the sequence to diverge. That is why it is unprovable.
Rewrite the sequence steps as follows: - Dvivide n by 2^k for k=0,1,.. where k is the largest number for which the result is still an intege. That will be an odd number - Multiply n by 3 and add 1 In binary the procedure is even simpler: - Remove all trailing 0's. - Shift left 1 and add the orgininal number and add 1. Now remark that the number of times we divide by 2 (or the number of trailing 0's we remove) is (except for the first iteration in which it is 50%) 1 in 100% of cases, 2 in 50% of cases, 3 in 25% of cases, etc. The weighted average is: 1 + 1/2 + 1/4 + 1/8 + ... = 2. So on average each step (as defined above) will yield a result of multiplication by 3 and division by 4, which is 3/4 and smaller then 1. That is why we can see that in (almost all) cases, the sequence must come down. However, for the 5n+1 sequence, we multiply by 5 and divide by 4 which is 5/4 which is larger then 1. So that sequence should diverge to infinity in almost all cases.
Well, even if using 5n+1 would go to infinite for some numbers - what you would have to prove first - it does not prove anything for 3n+1. While 2(a)n+1 goes to infinite for example - for obvious reasons - 1n+1 goes to 1 instead - for obvious reasons, too. You explain, why you *think* it goes to infinity, but deliver *no prove* at all.
Here's my take on it, and I haven't really seen it approached from this angle. I don't think it should EVER diverge to infinity, as long as it's in the format an + 1 where a is odd. At some point it is bound to land on a power of 2. That is literally all that's needed to that it will divide and divide until you get down to 1. So it might be something insanely large like 2^500000, but it would appear that probability dictates that at some point a power of 2 must be reached. So in my mind there is not really the need to show that it doesn't diverge to infinity but rather to show that a) the numbers generated in the sequence are random or at least that every real number can be a value in the sequence for some starting number (which would guarantee via probability that it must reach a power of 2), and b) that there are no closed loops that just spit out the same string of numbers over and over again.
lo que dices sobre potencias de 2 siempre no es del todo cierto ahora que sea un multiplo de una de esas potencias es la segunda opción. En mi canal presento la demostración de la conjetura de collatz. pensar en complicar el problema pensando en ciclos infinitos es un mito por el hecho de que impar conduce a par y hay mas posibilidades de dividir que de multiplicar. igual es pensar en problemas 5x+1, 7x+1 y px+1. primero se debe resolver collatz sin evadir el tema. eso ha distraido el trabajo eficiente en relación a la demostración. saludos
What part of it is it that they are trying to prove? Is it the equation for the number of times a number will bounce around before it goes down to the loop? Is it whether or not all numbers used will go down to the loop?
You might disagree with Mr Feinstein, but honestly you *have* to admit that his arguments are *always* interesting. And you must read *all* his papers to fairly and properly judge his assertions. He has much more than just brief YT videos. ... Though he should be publishing more and more!
That something is improbable for you or you cannot prove it is not enough to assume that it is unlikely for everyone. That was Paul Erdös' big mistake in 1982. He assumed that if he couldn't, no one would do it and that is pride and believing himself more than all other people. In conclusion a big mistake.
If you thought like in the Mandelbrot-set, ther are pints, wher it does converge, and others, wher it does'nt, and choosing the factor is 3 arbitrary, than it makes some sense, yet it does'nt mean that the convergance of some points and divergance of others are random - in a philosophical sense - they have the reasons why do they convarge/diverge, it's also quiet intuitive and you can visualize it in the case of the real line how the properties of convergance cames from the properties of quadratic functions and iteration. You can basicli have a deeper understanding of ther proces and you feel it less "god given". It's rather bold and misleading to state such think like "it's unprovable because it's not reasonalbe". You can think of a philosophical question like "why 2+2=4 and not something else", and you culd say that we don't know the answer but that is a different kind of why. It is posible to show it from tha axioms that is true and that is why it's true, that's what we mean by logical jn mathematics. Ther are some cases when it is shown that something is a nondecideable problem in a Gödel sense, but they all requier their own proofs, simple becouse the problem is difficoult or seems arbitrary. It's arbitrary but not random - like the primes. I would be carefull whit such statements or be more precise with the terms as in mathematics even the statement of something is unprovable requiers a proof.
Uhh... Probability can prove things. For example: Imagine an algorithm r where you start with a value being 1. There is a 2^n chance that it will stop there, but otherwise it will keep growing, adding one and doing it again. Once it stops, that is the output. The function will ALWAYS terminate because there is ALWAYS SOME chance that it will. For the Collatz sequence, it will always go down because for an odd number and the sequence is OEO where O is odd and E is even, the number is multiplied by 1.5. That isn't 2, but there is a 50% chance that it will actually be OEE. Then there is a 25% chance of EEE. There is NO chance that OOE exists, or OOO, because in this sequence two odd numbers cannot exist together. The number is always decreasing.
Katakana! This is untrue, probability will tell you that it is almost guaranteed to terminate, but there will always be a situation where it’s possible that it can go on infinitely. Much like in this conjecture, where we only need one value to disprove , they’re only needs to be a single situation in your case where the program doesn’t terminate, then nothing is guaranteed
Wait, I don't understand what you mean by "multiplying by 5 and adding 1 for odd numbers... appears to diverge to infinity". Let's take 3 (odd number) for example: 3*5+1 = 16 -> 16/2 = 8 -> 8/2 = 4 -> 4/2 =2 -> 2/2 =1. Where does it diverge to infinity?
Which numbers exactly diverge to infinity using that procedure? Do you have proof? Because I watched a video somewhere saying that 27 using the 3n+1 process actually goes back to 1 after over 9000 steps. By using 5n+1, it may take more than that for many (small) numbers to converge to 1, but is there proof that it will diverge to infinity?
Hi Cafeinst, actually, I can tell you that using the 5x+1, the numbers 3, 15, 19, 51 will terminate to 1. The others either cycles, diverges or are too big to evaluate
3x+1 on the other hand is very interesting, for every odd number up to 111 (and possibly much higher than that), everything terminates to 1, no cycles no diverges to infinity just 1
not necessarily (3*n+1)/2 > n so if it went like this ( it's not guaranteed to admittedly) then the value made combining two steps is always greater than n and only if that is also even will it slip below n.
Hello, that is somewhat plausible. But the fun of the conjecture is that it is so easy to do at home. If you have any questions about it, I recommend you spend a couple of minutes and try to work out maybe the numbers one through 20. It is actually quite fun to try and uncover patterns
Actually I have a rough "probalistic" reason why they should.The argument is incomplete and is a bit hard to explain,because I use completey new terms but I'll try any ways. Let's use the (3x+1)/2 form. I define a string as any part of the sequence that only goes up. In the sequence: 7 11 17 13 5 1 It's clear that 7-11-17 is a string(according to my definition). I can demonstrate that the lengths of such string must be finite. In fact the length is equal to the amount of time n+1 can be divided by 2. Roughly speaking the length of the string on average will be greater than the amount of time you need to divide by 2(2ⁿ.Thus going lower than the initial value).This means that the sequence can go on for a very long while,but will not be bounded to infinity. And will always eventually lead to one. When you increase to 5n+1,the probability that a sequence is long gets higher because you need to divide by 2 more often. On average the string lengths are longer and get even longer at 7n+1 and 9n+1. So the sequence can bound to infinity.To add more, 1 isn't even the lowest cycle in 5n+1. If you use something lower like n+1,It is clear that it will always lead to 1 because string length is always 1.So the numbers will decrease. The argument isn't complete,but is enough to understand why 3n+1 behaves that way. I also like to think of 3n+1 as a sort of "average" between n+1 and 5n+1 in the sense that it inherits properties from both.
amigo pensar probabilisticamente ha demoprado mucho el trabajo. te invito a mi canal para que veas la demostración suscribete a MI CANAL Y ACTIVA LAS NOTIFICACIONES. mi explicación de esta conjetura es facil de entender aun para personas que no sean matemáticos. saludos
jajaja. De acuerdo contigo hay personas que se rinden y quieren que los demas hagan lo mismo. esta conjetura es demostrable eso lo presentaré en mi canal.
you can prove whole classes out of the need for searching (4^n-1)/3 always leads to 4^n for example which is a power of two so leads to one. at power of two times these numbers is also connected to one.
that's not to say it's not unprovable but you haven't made a convincing case in what I can see without downloading. there are types of prove that can prove infinitely many cases using mathematical induction.
there's different ways to view almost any conjecture even things like goldbach's conjecture can be restated in a new way like the fact that after a certain point all positive whole numbers are equidistant to two primes.
in fact you can prove only odd numbers need be tested as all pure even numbers are the powers of two and all impure even numbers are an odd number times a power of two. therefore they all fall to this odd number value.
in fact you can prove the odd numbers that hit the powers of two immediately are of specific form so you can break it down into do all odd numbers>1 lead to an odd numbers of this form > 1.
Prove it wrong and you can say that a number may diverge to the infinite. Changing values that aren't variables in an expression changes the outcome for an equation
Seriously? Thats the reason you think its unprovable? You know mathematicians could have thought Fermats last theorem is unprovable and gave up on it but they didnt and you can see after almost 350 years it was proven so its better not to discourage young mathematicians instead of encouraging them to prove the conjecture.
Vivek Veer, I see myself as doing a public service discouraging anyone from even attempting to prove the conjecture. Proving the Collatz conjecture is like trisecting an angle with only a straightedge and compass. Better to work on other math problems.
would not be more truthful to say "it can't be denied"? people tried using computers to find number that will disprove this, they failed. how then anyone can claim this is not provable? so weird... it's almost like religion. You lack proof and you are not able to deny it but still you claim it's unprovable.
Hello! I have independently studied the Conjecture for the past 7 months or so, including similar functions such as 3x+5 and 5x+1. I have a few explanations for what's going on, however I would like to keep studying, double check my work, and then have it peer reviewed before I release it by sometime next year. Ironically enough, I may have to default to using probability as one of the supporting reasons for why the Collatz Conjecture does not go to infinity. However, this is not because of the popular "every odd number becomes even" argument. I would like to keep studying because I am not sure if I can explain all of the problems with the function possibly diverging to infinity. Aside from infinity, I still struggle to understand how loops form the way they do. The best thing I found about loop formation is all of the loops of 3x+5 must have a multiple of 4 steps. While interesting, I can not use this for 3x+1. I do believe the Conjecture is provable, however this video does do a good job of pointing out some specific problems that the proof for the Conjecture would need an explanation for. If I am fortunate enough to have a good working proof, I will refer to this video to make sure I addressed all of the mentioned concerns. Good luck and stay curious!
In fairness it's impossible to prove that it's unprovable because if it was unprovable then that would be proof that it was true. The reason for this is that if it is false a counterexample could be found which disproves it, making it possible to prove it is false. So in order for it to be unprovable as true or false there must be no counterexamples and so it must be true.
Okay but it can't be proven as undecidable as that would be proof it was true which would make it decidable. Therefore, you also can't prove it's unprovable without disproving it - because by saying its unprovable and that you don't know if it's true, aren't you saying it's undecidable?
TheTree0fDeath if it is true, then it is unprovable. If it is false, it is unprovable too, assuming that ZFC is consistent, since ZFC could not prove a false statement.
Well of course if it's false it's unprovable but that doesn't mean it's unprovable if true. Why could you have not used the same logic to argue that Fermat's last theorem was unprovable?
Please take this down - it is complete and utter nonsense and will have a negative impact on people trying to learn about Collatz. I'm not trolling you, this is genuinely very, very bad.
Rob, on the contrary. I am trying to warn people not to try to prove this conjecture. Lots of people have already wasted lots of time on this conjecture, with nothing to show for it. Proving this conjecture is the modern version of angle trisection.
Mate, I think you should show those thumbs up and downs, lets see what people think about... oh oh.... I just saw that you published a video called a simple proof that P is not equal to NP. LOOOOOL Ok, you are a troll, I see. Good one!
Please do not waste your life trying to prove me wrong. Read my paper in the video description, try to understand it. Read Conway's 2013 paper on this subject. Erdos did not say math wasn't ready for these types of problems for no reason.
I proved very cool things in it like there is no any cycles except 1.2.4 and there are infinite number of odds can reach any number How i can stop now i am working like from 2 years in this and now stop
My theory is saying that all number have infinite numbers of odds if i know how pattern is this, i can prove that all number can came from the number 1 and then all number go to the 1 I hope i can or any one can!
I only want to prove that (3^x - 1)/(2^x - 1)=(a hole number) Have only one answer for x and it is (1) And i know that when x even it will never be hole but odds i dont know if you can help me in this you will help me so much!
