1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

On Collatz Problem

  1. Feb 21, 2004 #1
    Last edited: Feb 21, 2004
  2. jcsd
  3. Feb 21, 2004 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Comments1. k must be fixed one presumes or many things make no sense as we will see.

    2. The second line, starting 'A direct convergence', has an extraneous comma that makes it unclear what you mean


    3. the 4th paragraph implies that k is not fixed, since if it were 2^{k+1} would contradict that statement.

    4.of the 4 options you give one must conclude that k is fixed otherwise the assertion j is an even number >2^k is nonsense. It is bad maths anyway, as one should not use symbols when words are required.

    5. similarly don't use XOR like that, neither of the 'inputs' is a statement than can be true or false.

    are those contradictions about k being fixed or not enough for you? probably not.


    edit:

    there are also these:


    what does it mean 'to be out of the range'?


    why are you misusing decidability like this? godel states that something is undecidable if both it and its negation are consistent with the other axioms.


    i don't even want to touch the von neumann heirarchy stuff.
     
    Last edited: Feb 21, 2004
  4. Feb 21, 2004 #3

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    thinking about this for a while it just seems that you're saying: because of a couple of iterations of the rules of Collatz we see it can never be decided what happens. but that is obviously wrong.
     
    Last edited: Feb 21, 2004
  5. Feb 21, 2004 #4
    Hi Matt,

    Thank you for your reply.

    k is any positive integer ( 0 included).
    Thank you, you right (my English problems again), A direct convergence to 1 must start in one of the even numbers that belong to 2^k sequence.
    As i wrote, k is any positive integer ( 0 included).
    Please explain what do you mean by "k is fixed"?, again k is any positive integer ( 0 included).
    If i write "or" instead of "XOR" is it ok?
    If you look at the Binary Tree that stands in the base of Von Neumann Hierarchy, then you can see that this structure is the invariant symmetry of N members, therefore can be used to define rigorous proofs about N members.

    Collatz problem is also based on this invariant symmetry of the Binary Tree, and for any k we can find N members that are out of the range of 2^k (case 4 in page 1).

    Therefore it is non-decidable for any Binary Tree, which means non-decidable within N (for any n).
     
    Last edited: Feb 21, 2004
  6. Feb 21, 2004 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    I don't think you understand the subtlety of the word fixed.


    As you compare j to 2^k it cannot be that when you say 'examine 2^k' that you mean 'examine the set {2^k | k in N u{0}}'

    you are confusing sets and numbers again and the comparison j>2^k is meaningless without explanation.

    I really don't see what you are getting at, to be honest, at least beyond stating in a very confused fashion the obvious about what might happen when you apply the Collatz iteration.


    Anyway, that can be readily rectified, however you don't explain what you mean by 'out of the range' no matter what you may think. A simple statement will do, you know. Nor do you explain how your facile observations imply anything to do with decidability, which as I pointed out is quite an intricate issue - the continuum hypothesis is undecidable in ZFC for instance.


    or is better than xor, but you shouldnt write 'either >x or <x' in a sentence as that is deemed poor presentation.
     
  7. Feb 21, 2004 #6
    Dear Matt,

    Thank you very much for your help.

    I fixed some of the problems.

    Please read it again:

    http://www.geocities.com/complementarytheory/3n1proof.pdf

    and please tell me more about "fixed" if needed.

    Please be aware that i am using here a non-standard point of view on N members, which based on its fundamental symmetry of the Binary Tree.

    Yours,

    Organic
     
  8. Feb 21, 2004 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    changing the word range to the word scope doesn't make it any clearer. just state what you mean to be out of the scope of, or out of the range of
     
  9. Feb 21, 2004 #8
    Well, I used scope because "range" is already used by Math.

    By out of the scope I mean that we shall always find n's which are beyond any Binary Tree.

    Because this symmetry stands in the basis of N members, we can conclude that Collatz Problem is non-decidable for any n in N, because any n is nothing but a part of the Binary Tree invariant symmetry.

    I'm going to sleep, see you tomorrow.
     
  10. Feb 21, 2004 #9

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    so you assertion is that given any binary tree there is a number 'beyond' it. Care to explain what that means at any point?

    anyway, you've not proved that at no point in the future iteration of 47 does it not return to one. I'll put money on it doing so.

    Putting it in your language, you've omitted to consider things in the correct order, which is that given an n there is some k with n in the scope of the binary tree 2^k, and in fact in the scope of infinitely many of them. You're taking things in the wrong order again.

    Of course if you could prove that there is some n, such that for any k, there is some point in the Collatz iteration with i_r(n)>2^k, where i_r stands for the r'th iterate in the sequence, but that isn't what you've shown.


    The assertion that given any k there is an even integer, n, not a power of 2, with n>2^k does not prove anything interesting here.


    Let's repeat the main point. There is no number beyond the scope of any binary tree.

    Given any binary tree there is a number beyond its scope, but that is different for each tree. There is no number that is beyond the scope of EVERY tree.

    Not that I see what that would prove anyway.
     
    Last edited: Feb 21, 2004
  11. Feb 21, 2004 #10
  12. Feb 22, 2004 #11

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    The assertion that, given a k, 3*(2^k+1)+1 is not in *any* binary tree is wrong. It is in an infinite number of them. It is in the one corresponding to 2^r where r is any number greater than 3*(2^k+1)+1.

    When you say the first number after 2^k you are fixing k at some (arbitrary) value.

    because, once you've fixed this k, you can find a number iterated to some larger number is not important because it is dependent on k, only if it were independent would you even start to have something, but even then that is moot as you'd have to prove that no iteration at any point in the future would return you to 1

    example k=3, so we start with 9, the iterations are

    9,28,14,7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1



    It still wouldn't state it was undecidable:

    a statement is undecidable in some axiomatic theory if either the assumption of it or its negation is consistent with the axioms, example, the continuum hypothesis and ZFC.
     
  13. Feb 22, 2004 #12
    Hi Matt,

    But what I show is based on the invariant symmetry that stands in the base of any n in N.

    (2^k)+1 has a 1-1 and onto with {} that exists in the internal structure (The Von Neumann Hierarchy Binary Tree) of any n in N.

    Let current n be 2^(k+1).

    Any 3*((2^k)+1)+1(=3n+1) > 2^(k+1) where 3n+1 is beyond the internal Binary Tree structure of current n(=2^(k+1)) in N, which means that we always need to get n+1 for general and rigorous proof. Shortly speaking, if n then n+1 (the ZF axiom of infinity), therefore it is non-decidable for any n in N.
    Q.E.D

    Please see my updates:

    http://www.geocities.com/complementarytheory/3n1proof.pdf
     
    Last edited: Feb 22, 2004
  14. Feb 23, 2004 #13
    This self similarity of N members, which constructed by The Von Neumann Hierarchy Binary Tree can't be ignored.

    Maybe someone knows what is the Mathematical brunch that researches the symmetry of Mathematical objects like numbers?
     
  15. Feb 23, 2004 #14

    matt grime

    User Avatar
    Science Advisor
    Homework Helper



    Look, the number you pick for each k that is out of the 'scope' of the tree you are looking at is different for each tree, there is not universal number in those that you pick. Got it? Evidently not. You fix the k, then you say take 3*(2^k+1)+1, note that is different for each k and there is not one of them you can pick that works for all k.


    For pity's sake don't start using the axoim of infinity again, as this isn't what it states. It merely states the the set of integers must be a set in the model you are using.

    You are evidently using your own private defintion of undecidable which is not the mathematical one (again).


    In particular all it appears you are saying is that there is an odd number freater than 2^k. That number you chose is different for each k. The axiom of infinity that you seem obsessed with doesn't all ow you take the limit of this sequence and claim it is a meaningful number. This is just the same as the fundamental error in your cantor argument.

    What you've written down does not support any conclusions you've made.
     
  16. Feb 24, 2004 #15
    Matt,

    Again you ignore the invariant fundamental symmetry that stands in the basis of N.

    My proof is not about any fixed k value. It is about the "universal" (your word) structure that stands in the basis of N.

    What I show is that there is self similarity between this basic structure and the Binary Tree used in Collatz problem.

    Therefore if there is a general and rigorous proof to Collatz problem, it means that you also prove the ZF axiom of infinity ("if n exists then n+1 exists" is an axiom, therefore cannot be proved, otherwise it is not an axiom).

    Shortly speaking, a general and rigorous proof to Collatz problem is a contradiction of ZF axiom of infinity existence as an axiom.

    Because no proof of any Math system contradicts its axioms, Collatz problem is undecidable within N.

    Also sets R and C can't be used here because their existence depends on set N existence.

    My proof is "structured oriented", not "fixed k oriented".


    About |N| and Collatz problem

    If we look at this tree http://michael.cleverly.com/funstuff/3x+1/collatz2.jpg [Broken] we can see that there are some numbers which are the results of both 3n+1 and n/2, for example:

    Number 22 is the result of 3*7+1 and also the result of 44/2.

    Let K be the set off all natural numbers, which are a common result to both 3n+1 and n/2.

    |K|=|N| therefore transfinite system is too strong for Collatz problem.


    Arithmetic

    The arithmetic of Collatz problem is not importent, because we can use another arithmetic and get the same "Collatz tree" structure with different values instead of N members.

    Here is your example:
     
    Last edited by a moderator: May 1, 2017
  17. Feb 24, 2004 #16

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Oh, not again.


    I ignore the fundamental symmetry you claim is there because you've not demonstrated it proves anything.

    You have fixed k, because you say consider 3*(2^k+1)+1. That doesn't meant to say you've set k to be equal to some number. You then say that becase this isn't in the 'scope' of the binary tree for 2^k (still without defining scope) which I take to mean is bigger than something. However for each k you get a different thing. I've already shown you 2^k+1 goes to 1 for k=3, it does for 2 as well. It shouldn't be beyond you to check that it does for 4, 5 and 6 as well. So what's the point you're trying to make?


    The set N exists. It is in a model for ZF because of the axiom of infinity. If you wish to do a set theory omiting the axiom of infinity then N will not necessarily be a set in that theory.


    How have you concluded the Collatz problem contradicts ZF? How?


    The word universal was only used in an attempt to describe what it was you were claiming about these 2^k+1 things.

    You've misused the axiom of infinity again. DOes this mean you've finally accepted that the sentence

    If n then n+1

    makes no sense either mathematically or in English?

    If X then Y is a proposition, ther terms X and Y must be statements that are either true or false.

    I don't think there can be a 'self'-similarity between two different things, btw. And what boolean tree for Collatz? (I'm not sure I've ever heard the term boolean tree before) and even if there were these things you've not demonstrated anything. You'd think the fact that the numbers you're using to contradict the axiom of infinity using COollatz wouldn't so clearly reach 1 so quickyl for small k, but they do, don't they?

    So what that there the cardinality of the set of numbers that are obtained from more than one possible starting point are the same: Consider the itereation defined by n-->1 for all n

    every number ends up at 1 after one interation. By your logic it is undecidable in ZF if every number ends up at 1. After all, the set of elements which trivally get to 1 in COllatz is also uncountable too, the powers of 2 for instance.

    The quote you posted from me is irrelevant as it was answering an unrealted question you posed: are there other ways of defining the opertations that agree on a certain finite subset of the naturals with the COllatz seqence? The arithmetic of the Collatz sequence IS important as it must agree for all integers. I was also indicating there might be a way to extend it to a function of the complex plane that agreed with COllatz on the integers - like the gamma and factorial functions.
     
  18. Feb 24, 2004 #17
    Matt,

    A simple qeustion:

    Complex numbers existence, does it depends on N numbers existence?

    You use the words "agree with".

    Well this is exactly what I mean by saying that the important thing here is the invariant "Collatz Tree" and not its 'labels' that can be N, Q, R or C 'labels'.


    You CAN'T ignore the invariant fundamental symmetry of the Binary Tree that stands in the basis of set N members.

    What I show is that there is self similarity between this basic structure and the Binary Tree used in Collatz problem.

    Therefore if there is a general and rigorous proof to Collatz problem, it means that you also prove the ZF axiom of infinity ("if n exists then n+1 exists" is an axiom, therefore cannot be proved, otherwise it is not an axiom).

    Shortly speaking, a general and rigorous proof to Collatz problem is a contradiction of ZF axiom of infinity existence as an axiom.

    Because no proof of any Math system contradicts its axioms, Collatz problem is undecidable within N.

    Also sets R and C can't be used here because their existence depends on set N existence.

    My proof is "structured oriented" and if you don't get it you can't understand it.
     
    Last edited: Feb 24, 2004
  19. Feb 24, 2004 #18

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    You would have to demonstrate that this alleged fundamenetal symmetry has any bearing on the case in hand

    I don't think you understand what you're talking about here. The collection of elements of N exists, ZFC has an axiom that means that it constitutes a set, that's all. Or another way, it tells us there must be an inductive set in our model. The Naturals form this set in our model.

    It is very unclear what you are attempting to claim the contradiction is here. If one proves the Collatz conjecture one proves the naturals exist? They exist anyway, and happen to constiute a set in ZFC. So what?

    no it isn't

    I won't and don't use R or C here.

    Anyway, as you claim to have demonstrated the Collatz conjecture in itself contradicts the axioms of ZF, it is not that it is undecidable, but that it is false. Or at least it would be that if you assumed it true, then it contradicts ZFC hence it is false. So well, done you've disproved the Collatz conjecture, allegedly. Of course you haven't cos your proof is utterly wrong.

    Undecidable means that both it and its negation must be consistent with the axioms.
     
  20. Feb 24, 2004 #19
    Matt,

    Let us write it this way: A general and rigorous proof of Collatz problem is equivalence to the existence of ZF axiom of infinity, which tells us that there must be an inductive set in our model.

    Because no axiom can be proved, Collatz problem can't be proved.
     
  21. Feb 24, 2004 #20

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    How on earth is Collatz equivalent to the axiom of infinity?
     
  22. Feb 24, 2004 #21
    Dear Matt,

    Please look at page 1 and 2 in my proof, and see by yourself:

    http://www.geocities.com/complementarytheory/3n1proof.pdf

    How Collatz is tuned to the internal Binary Tree that stands in tha base of set N.

    After you got it, you can see that Collatz problem form this point of view is equivalence to: "if n exists then n+1 exists"(the ZF axiom of infinity).
     
  23. Feb 24, 2004 #22

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    I looked at the proof you offer and it doesn't prove anything that you are claiming. It may require the axiom of infinity, but only in the sense that N is infinite.

    All it does is show that given a number there is an odd number greater than it and that under the collatz iteration it gets sent to a larger number again. And?

    I really think you should learn about maths before you post stuff like this. Oh, I know you're just going to say that I don't understand your proof, and I should be more accepting, but really that isn't the case. That I can't understand your proof is because it is ill-written and makes completely substantiated deductions. It really would be benefical if you actually understood the axiom of infinity, that merely states the existence of an inductive set in our model is required for it to satisfy the ZF(C) axioms.
    It reads as though you think the only proofs are those that check every single case.

    Here is another trivial example which shows you are wrong:

    let I be the iteration given by I(n)=1 if n is even n+1 if n is odd

    given any r = 2^k+1, it is beyond the scope of the binary tree of base k as is r+1, therefore we see that it is undecidable (or contradicts the axiom of infinity, whatever) that repeated iterations of I send all numbers to 1 eventually. Clearly that is a false assertion but the logic is no different than your Collatz deductions.
     
  24. Feb 24, 2004 #23
    Matt,

    If you write:
    It means that you still don't understand my proof.

    Again, the main point is that I find 1-1 and unto between the internal structure of set N (given by The Von Neumann Hierarchy) and Collatz Binary Tree.

    The The Von Neumann Hierarchy Binary Tree is (as much as i know) a new structure that I have found and never used before by anyone.

    By this proof I connect between the micro level and the macro level of set N members, and only by this connection between micro and macro we can see that Collatz problem is equivalent to ZF axiom of infinity.

    Until know you are still see my proof only from macro level (where there is a meaning to odd or even) but again my proof can be understood only by the connection between this level and set N internal Binary Tree structure (where concepts like odd or even don't exist) that constructed by {} recursion.
     
    Last edited: Feb 24, 2004
  25. Feb 24, 2004 #24

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    I think the word your searching for is bijection.

    1. define the collatz binary tree.
    2. define what it means for this tree to be in bijection with the set of natural numbers
    3. is there some structure this bijection is preserving.
    4. for that matter define THE von neumann heirarchy tree, you have defined trees for each power of two, how does that define it for N? oh i know, that'll be the axiom of infinity induction.
    5. explain why this alleged bijection means collatz is false (it can't be undecidable in ZF by your reasoning becuase it contradicts something that is true, hence it must be false).
    6. prove it is actually a bijection, whatever it is.
    7. if the Collatz conjecture is equivalent to the axiom of infinity, then it is true in ZF, becuase the axiom of infinity is true in ZF. so you're contradicted yourself again and it isn't undecidable (perhaps you should actually look up the meaning of the words you use in a mathematical dictionary). It then won't be true in other set theories without the axiom of infinity. fine, but that's not what you've shown - in fact you are claiming to have proved two contradictory statements. there are results that are true depednding on the set theory you use - Shelah has some nice results on this and EXT groups infact. If you have shown it to be equivalent to the axiom of infinity then well done, you've proved it's true in ZF, and you didn't even realize it. Things like that make me wonder even more about your level of mathematical knowledge.


    And why didn't my counter example pass whatever criteria you have for these things? It is defined in the same manner as Collatz, so if my example doesn't make sense on the macro level because odd and even have no meaning, then neither does the Collatz iteration.
     
    Last edited: Feb 24, 2004
  26. Feb 24, 2004 #25

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Shall we presume that the COllatz tree is the one that has base node labelled by 1, from this is a branch to a node labelled by 2, from that to a branch labelled by 4, from that a branch to a node labelled by 8, there will then be one node out of 8 to 16, from 16 two branches to nodes labelled 5 and 32, and so on, each node labelled r having one or two branches out of it to nodes labelled 2r and, if applicable (r-1)/3.

    You claim this is in bijection (as a tree, or a toplogical space, or what?) to the infinite bi-leaved tree which I think is what you mean by the von Neumann tree. Clearly that is not an isomoprhism of trees. as the base node for one has only 1 branch out of it, and there are two branches out of the base node in the neumann case.


    If the collatz tree has only one component with labels for all the naturals, then collatz is true, by the way. but then you seem to think the collatz conjecture is undecidable in ZF and equivalent to the axiom of infinty....
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook