Could a sequence in the Collatz conjecture actually increase without bound?

Question

If my understanding is correct, than the Collatz conjecture could only be false if there is at least two closed cycle in it or if there is a number which increases without bound.

$3x-1$

We know that in this case we have multiple loops!

Lets compare the 1->4->2->1 and the 5->7->5 loop.

For every odd number we can find every "previous" odd number that are goint to result in that number using the $\frac{x\cdot2^n+1}{3}$ formula.

Let A be the set of those numbers which are going to reach 1.

$\frac{1\cdot2^1+1}{3}=1$ //goes back to itself

$\frac{1\cdot2^3+1}{3}=3$ //multiple of 3 so it won't have any previous odd value

$\frac{1\cdot2^5+1}{3}=11$

$\frac{1\cdot2^7+1}{3}=43$

$\frac{1\cdot2^{9}+1}{3}=171$ //multiple of 3 so it won't have any previous odd value

$\frac{1\cdot2^{11}+1}{3}=683$

We can see that third of our numbers won't continue but the others would in the same way.

Let B be the set of those numbers that are going to reach 5.

$\frac{5\cdot2^2+1}{3}=7$

$\frac{5\cdot2^4+1}{3}=27$ //multiple of 3 so it won't have any previous odd value

$\frac{5\cdot2^6+1}{3}=107$

$\frac{5\cdot2^8+1}{3}=427$

$\frac{5\cdot2^{10}+1}{3}=1707$ //multiple of 3 so it won't have any previous odd value

$\frac{5\cdot2^{12}+1}{3}=5461$

We can see that third of our numbers won't continue but the others would in the same way.

We can see that A and B are quite simmilar but whilst in A after 1 we won't have any more previous elements in B we will have more elements after 7. So B is bigger than A with all the elements after 7.

$\frac{7\cdot2^1+1}{3}=5$

$\frac{7\cdot2^3+1}{3}=19$

$\frac{7\cdot2^5+1}{3}=75$ //multiple of 3 so it won't have any previous odd value

$\frac{7\cdot2^7+1}{3}=299$

$\frac{7\cdot2^{9}+1}{3}=1195$

$\frac{7\cdot2^{11}+1}{3}=4779$ //multiple of 3 so it won't have any previous odd value

We can see that third of our numbers won't continue but the others would in the same way.

For every element in A there will be 2 elements in B. That means that B is 2 times bigger than A. This is perfectly fine since the set of Natural numbers can have 2 infinite subsets where one is finitely bigger than the other.

$3x+1$

For every odd number we can find every "previous" odd number that are goint to result in that number using the $\frac{x\cdot2^n-1}{3}$ formula.

Let A be the set of those numbers which are going to reach 1.

$\frac{1\cdot2^2-1}{3}=3$ //goes back to itself $\color{red}{ \text{ this must be ... } =1 }$

$\frac{1\cdot2^4-1}{3}=5$

$\frac{1\cdot2^6-1}{3}=21$ //multiple of 3 so it won't have any previous odd value

$\frac{1\cdot2^8-1}{3}=85$

$\frac{1\cdot2^{10}-1}{3}=341$

$\frac{1\cdot2^{12}-1}{3}=1365$ //multiple of 3 so it won't have any previous odd value

Let B be the set of those numbers which are going to increase without bound.

As the 5->7->5 loop shows after each step the set B would become bigger than the set A.

After every step we would have a number and with those numbers previous elements B would be bigger than A.

After the first step B would be 2 times bigger than A.

After the second step B would be 3 times bigger than A.

When we say that our element increases without bound it means that it won't ever form a cycle or reach 1. But then that would mean that B would becomes infinite times bigger than A. We know that the set of Natural numbers cannot have two infinite subsets where one subset is infinite times bigger than the other.

I hope my logic and resoning makes sence. I would appriciate any comment or feedback even if my logic is wrong.

Answer 1

" After the first step B would be 2 times bigger than A.

After the second step B would be 3 times bigger than A.

When we say that our element increases without bound it means that it won't ever form a cycle or reach 1. But then that would mean that B would becomes infinite times bigger than A. We know that the set of Natural numbers cannot have two infinite subsets where one subset is infinite times bigger than the other."

This is mistaken. It isn't true that if we have two sequences of sets $\{A_n\} $ and $\{B_n\}$ where $\frac{|A_n|}{|B_n|}$ increases without bound that in the limit $A_\infty $ is 'infinitely bigger than' $B_\infty $. Consider instead of what you constructed the two sequences of sets $A_n$ = the first $n$ even numbers and $B_n$ = the first $n^2$ even numbers. At each step $|B_k|$ becomes larger than $|A_k|$ without bound, but in the limit they're the same set. In general ratios of cardinality/size aren't preserved in such an easy way when we move to the infinite world.

Answer 2

Considering two very simple cases, we either choose $x$ to be even or odd.

Case I: Odd

If $x$ is odd, then we are supposed to multiply it by 3 and then add 1, essentially giving us $3x+1$. However, this number is always even, thus we must divide it by 2, to get $$\frac{3x+1}{2}$$ Essentially, if $x\leq \frac{3x+1}{2}$ for some $x$ we are interested in, then there might exist a number that grows without bound in the Collatz Conjecture, but if all natural numbers obey this property, then the proof gets much simpler. Infact, this inequality can be solved to get $x\geq -1$ which every natural number obviously obeys.

Case II: Even

If we choose an $x$ that is even, then we divide by 2, which would make the number smaller. We either land at an even number or an odd number, even numbers decrease as we have just shown, and odd numbers tend to decrease too. Thus, the number will always tend to decrease implying there is no sequence that shoots off to infinity.

Note

The Collatz Conjecture is still a conjecture because, even though we have proved that no number shoots off to infinity, we cannot prove that there does not exist any seperate loop outside the 4-2-1 loop that we are unaware of.