0
$\begingroup$

Prove / disprove the following statements regarding the Collatz conjecture T

$(1) \forall n \in \mathbb{N} ((\exists k \in N_{0} \hspace{0.5cm} n=2^k ) \rightarrow T(n)=1)$

$(1) \forall n \in \mathbb{N} ((\exists k \in N_{0} \hspace{0.5cm} n=2^k ) \leftrightarrow T(n)=1)$

$T(n):=\begin{cases} 1 \hspace{0.5cm} if \hspace{0.5cm} n=1, \\ T(\frac{3n+1}{2})\hspace{0.5cm} if \hspace{0.5cm} n>0 \land n=1\hspace{0.1cm}\mathrm{mod}(2) \\ T(\frac{n}{2})\hspace{0.5cm} if \hspace{0.5cm} n>0 \land n=0 \hspace{0.1cm}\mathrm{mod}(2) \end{cases}$

So the second statement can be disproved very fast by taking $n=10 \neq 2^{k}$ , T(10)=T(5)=T(8)=T(4)=T(2)=T(1)

It is clear that the first one is true since $\forall k \in \mathbb{N} T(2^k) = 0\hspace{0.1cm}\mathrm{mod}(2)$ $T(n)=T(2^k)=T(2^{k-1})=...=T(2^{k-k})=T(2^{0})=T(1)$

However I think I can not write it down like this and I need formal argumentation (in the task it is written that induction over $k \in \mathbb{N_0}$ is suggested, and it should be argued why induction over $k \in \mathbb{N_0}$ is allowed)

For arguing why induction over k is allowed could I use the fact of predicate logic that $(1) \forall n \in \mathbb{N} ((\exists k \in N_{0} \hspace{0.5cm} n=2^k ) \rightarrow T(n)=1)$ equals $(1) \forall n \in \mathbb{N} \hspace{0.5cm} \forall k \in N_{0} ( n=2^k \rightarrow T(n)=1)$ ?

$\endgroup$
5
  • 1
    $\begingroup$ You asked this question before. It's hard for anyone here to guess what it means to argue that induction is allowed. Are you to recast the entire problem within some formal axiom system for the natural numbers? Can you assume the laws of arithmetic and exponentiation and such? I suggest seeking clarification from whomever set the problem. $\endgroup$
    – lulu
    May 23, 2020 at 10:02
  • $\begingroup$ @lulu: Yes I agree the whole question is weird, I think we can fully use the laws of exponentiation and everything. For me the closest I could get with the argumentation is with the laws of predicate logic. Was the quantor transformation correct? On the task sheet, the prof wrote induction over $k$ might be easier than over $n$, well of course, because induction over n would not make any sense since for $n=2^k$, $\nexists k_{1} : n+1 = 2^{k_1}$ $\endgroup$
    – M-xyz1
    May 23, 2020 at 10:10
  • 1
    $\begingroup$ I strongly doubt that this is meant to be a logic exercise. If it is, then it is necessary to specify precisely the axiom system you are using, To me, it looks like an entirely routine (and easy) exercise in induction. But, as I say, you should seek clarification from whomever set the problem. $\endgroup$
    – lulu
    May 23, 2020 at 10:18
  • 1
    $\begingroup$ For example: A priori one could object that there is an obvious halting problem here. $T(n)$ could well be undefined (that's the point of the Collatz conjecture after all). So you should say a word or two about why $T(n)$ is obviously well defined if $n=2^k$. But, again, it's hard to guess what the problem setter had in mind here. $\endgroup$
    – lulu
    May 23, 2020 at 10:19
  • $\begingroup$ @lulu: thank you so much for your help until now. It is very likely that it is a logic exercise since we did the predicate logic just before. Are these the logic axioms in regards of the quantors? For the induction, could I argue with the modulo? We know that $T(2^k) = T(1)$ since $2^k$ ist 0 mod (2)now for $(k \rightarrow k+1), T(2^{k+1})=T(2*2^{k})$ and we know $2^k = 0 mod(2)$ thus $2*2^{k} $ is also 0 mod (2)? $\endgroup$
    – M-xyz1
    May 23, 2020 at 10:52

1 Answer 1

1
$\begingroup$

Proof by induction that $\forall k \in \mathbb{N}: T^{{(k)}}(2^k) = 1$.

  • Base case, for $k=0$: $T^{(0)}(2^0) = T(1) = 1$.
  • Induction hypothesis, for $k$: We suppose that $T^{{(k)}}(2^k) = 1$.
  • Induction step, for $k+1$ : $T^{(k+1)}(2^{k+1}) = T^{(k)}(T(2^{k+1})) = T^{(k)}(2^k) = 1$ by induction hypothesis.

$\endgroup$
3
  • $\begingroup$ Thank you, my solution was very similar, but I thought it is too easy. What does $T^{k}$ mean in your notation? Does it just denote the power of 2 ? and how would you argue that the induction over $k$ is also possible and not just over $n$? $\endgroup$
    – M-xyz1
    May 23, 2020 at 19:48
  • 1
    $\begingroup$ $T^k$ was a typo. I corrected that. $T^{(k)}$ is the notation for the $k$th iteration of the function $T$. Yes, it's easy. In fact this problem is very easy. It's trivial case of the 3n+1 problem. I'm not sure to understand your problem. The proof is a justification that the induction works. Here $2^k$ is $n$. The proof use the fact that for $n$ equal to a power of 2, the number of divisions by 2 for $2^k$ to reach 1 is exactly $k$. And the induction step use the fact that $k+1$ iterations of $T$ is the same that 1 iteration followed by $k$ iterations. $\endgroup$ May 24, 2020 at 7:51
  • $\begingroup$ Thank you so much. $\endgroup$
    – M-xyz1
    May 24, 2020 at 10:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .