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 (3n+1)

  1. Jan 29, 2004 #1

    I have 3 questions about 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.

    I made a mistake, instead of n/2 we have to read m/2 where m not= n.

    If we want to find a general and rigorous proof of Collatz problem it must be related to all Natural numbers.

    The cardinal of all Natural numbers is |N|=aleph0.

    Question 1: Can we say that |K|=aleph0 and therefore |K|=|N|?

    If the answer to question 1 is yes, then I have 2 more questions:

    Question 2: Is there some property that distinguish between |N| and |K| and can be used to define a general and rigorous proof of Collatz problem?

    Question 3: If the answer to Question 2 is no, can we come to the conclusion that Collatz problem is undecidable?

    Last edited: Jan 29, 2004
  2. jcsd
  3. Jan 29, 2004 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    You are implying 22 is in the set K, correct?

    Seeing as 22 = 7.3+1, and 22=44/2 means that the n's in your post are not equal, that is something, k say, is in K if there is an n with n/2=k, and an m with 3m+1=k, we must conclude that K is indeed infinite, because there are exactly aleph_0 numbers of the form 3n+1 each of them is half the number 6n+2.

    If we read K as being the set of all numbers n with 3n+1=n/2, then that is 6n+2=n, 5n=-2, which has no solutions in the naturals.

    If that was not what you wanted, then I suggest you rewrite the question so that it isn't trivial.
  4. Jan 29, 2004 #3
    Hi Matt,

    By the rusult 5n=-2 we can conclude that Collatz problem is undecidable within N,
    isn't it?
    Last edited: Jan 29, 2004
  5. Jan 29, 2004 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    No, that's not what collatz would appear to say. Please, can you clarify your original post so that we may see what it is that you are asking exactly.

    If it were that Collatz's decidability is equivalent to the statement above then I rather think Conway might have noticed.

    Please rewrite your question so that the same n's don't stand for different numbers.
  6. Jan 29, 2004 #5
    Dear Matt,

    Is 5n=-2 looks too simple not to be noticed by Conwey?

    Is this the problem?
  7. Jan 29, 2004 #6
    Through my point of view we can get this result (5n=-2) only because of the existence of aleph0 as something that related to ALL Natural numbers.
    Last edited: Jan 29, 2004
  8. Jan 29, 2004 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    The Collatz Conjecture is quite simple to understand, but I don't see what 5n=-2 has got to do with it, please explain. I mentioned Conway simply because this great mathematician has worked on the problem and you think he might have noticed that it was undecidable if -2/5 is not an integer.

    And why the hell are you citing aleph-0? Something you don't usually accept.

    You've still not cleared up the inconsistencies in the original question, please repost without the ambiguities about n.
  9. Jan 29, 2004 #8

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    To explain some of the original post by organic.

    The link to some external website (michael cleverly) is something that just states that there exist distinct numbers p and q such that eventually after repeating the collatz opertation then they become the same sequence. In particular, if we start with 25 or 18, then rapidly they reduce to the same case (and eventually become 1 thank goodness, or Collatz is trivially false).

    Ans 1.
    There are trivially infinitely many numbers which are of the form 3n+1 and m/2 simultaneously. This does not say anything about the decidability of the Collatz problem.

    As you've said the there are simultaneous solutions to something, it cannot be that you mean for there to be an integer n with 3n+1=n/2, so the rest of the posts are not relevant.

    If |K|=|N| then of course nothing can distinguish between |K| and |N| because they are equal.

    If you meant can anything distinguish between N and K, then of course the answer is equally trivially yes, no element of K is a multiple of 3.
  10. Jan 29, 2004 #9
    Dear Matt,

    Thank you very much for your corrections.

    You wrote: No element of K is a multiple of 3.

    Therefore I have another question:

    When |K|=|N| we have no choice but to distinguish between sets not by their cardinality, but by their unique arithmetic that define their members.

    How this uniqueness by arithmetic can be used to proof something on Collatz problem?

    For example:

    This tree http://michael.cleverly.com/funstuff/3x+1/collatz2.jpg is a unique product of Collatz arithmetic.
    Last edited: Jan 29, 2004
  11. Jan 30, 2004 #10

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    You can distinguish between the sets because they are not the same; it is trivial to demonstrate that there is an element of one not in the other. Obviously K is a subset of N, so it suffices to find something in N not in K. I think you are talking of arithmetic in a way that I wouldn't. It's the description of K that you use. I don't see any arthmetic on K. Perhaps you mean its arithmetical properties, which is not the same.

    As, for Collatz. This set doesn't help you do anything to solve the conjecture. At least not without saying something else.

    Here are some simple observations.

    Collatz is equivalent to the statement, eventually you reach a power of 2.

    It would be proved wrong if there were a non-trivial periodic sequence (non-trivial means not the sequene 4 - 2 -1).
    I leave it to you to formulate some boundedness type conjecture to accompany that.

    What do you mean by uniqueness of that diagram?
  12. Jan 30, 2004 #11
    Last edited: Jan 30, 2004
  13. Jan 30, 2004 #12

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Of course it can.

    Define the 'arithmetic' in anyway you choose that happens to agree with that specific example on those particular numbers. Eg, the Collatz rules except when a_n=1,000,000,000, and anything but division by two there.

    If you mean is there another way of defining a Collatz type relation which agrees on ALL values of a_n, then the answer is yes and no. There are equivalent constructions, but functionally they are the same. By that I mean

    sin(x) and cos(x-pi/2) are functionally the same, but have different 'labels'
    Last edited: Jan 30, 2004
  14. Jan 30, 2004 #13
    So we have a structure which is not depends on 'labels' nor arithmetic.

    My question is:

    Can the structure itself be used to define a general and rigorous proof to Collatz problem?
  15. Jan 30, 2004 #14

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    But your question is just a restatement of the Collatz problem. Which as far as I'm aware is still open.

    As for the first sentiment you express there, I don't know; I can't understand what you are saying.
  16. Jan 30, 2004 #15
    I think that any general and rigorous proof to some problem is connected to an invariant property which lays in the basis of the problem.

    In this case we can see that neither 'labels' nor arithmetic are invariant properties of Collatz problem, so now we examine the structure of the tree.

    My question is: Is the structure itself is the invariant property that can help us to define a general and rigorous proof to Collatz problem?

    ( By the way i have an answer to you here:
    https://www.physicsforums.com/showthread.php?s=&threadid=12942&perpage=12&pagenumber=3 )
  17. Jan 30, 2004 #16

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Ok, I think I see what you mean here now.

    More formally, we might call this a generalization. In this case, for example, suppose there were some function, f, defined on the whole of the complex numbers (or rationals, or reals) that is equivalent to the Collatz function on the positive integers. Does this more general function have the property that given any input f^n(x)=1 for some n. Perhaps by some juducious choice of this f we can prove Collatz. I don't think that this will help here, because it is too vague. But you might be able to find some other apparently unrelated thing that implies it. (For instance Perelman's so-called proof of the Poincare conjecture, doesn't prove that but something else that implies it.)

    In some sense, yes, when proving something you attempt to find what is essential to the statement. Sometimes generalizations are easier to prove than direct questions.

    For instance, there is something called Grothendieck Duality, which Grothendieck proved at length in some certain situation with messy direct calculations involving the inherent properties of the space on which he was working (we are talking morphisms of schemes here, but that isn't important). However Neeman has provided an abstract construction using some abstract theory, which gives the duality without getting your hands dirty with explicit calculations.

    Often there are direct calculations to demonstrate the existence of something in a specific case by constructing it, when there is a more general proof available that doesn't tell you what the thing is, merely that it exists. Look at finding highest common factors using Euclid's Algorithm directly or by defining an ideal and using the well ordering principle.
  18. Jan 30, 2004 #17
    Last edited: Feb 1, 2004
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: On Collatz problem (3n+1)
  1. Algebra 1 Problem. (Replies: 2)

  2. Collatz Problem (Replies: 9)