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 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: Feb 24, 2004
  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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: On Collatz Problem
  1. Buoyancy problem (Replies: 1)

  2. Kinematics problem (Replies: 10)

  3. A spring problem (Replies: 1)

  4. Problems in gravity (Replies: 1)

Loading...