0
$\begingroup$

Let us define the two functions $F(n)$ and $G(n)$ as given:

$$ F(n) = \begin{cases} 3n+1 & \text{ and then dividing through by any powers of $2$} \end{cases} \\ G(n) = \begin{cases} 3n-1 & \text{ and then dividing through by any powers of $2$} \end{cases} $$

Assume for all $n$ we work with that $$G^{k}(n)=1 \qquad \text{ and } \qquad F^{k}(n)=1$$ for some $k$.

For example, $F^4(11) = 1$. Let us consider the set $\mathcal{O}(F) = \{n \in \mathbb{N} : F^k(n) = 1 \text{ for some k }\}$ and $\mathcal{O}(G)$ similarly.

Let's try to organize the sets as follows:

$$\mathcal{O}(F) \dashleftarrow\dashrightarrow \mathcal{O}(G)$$

For $$k=1$$ $1 \longleftrightarrow 1$

$5 \longleftrightarrow 11$

$21 \longleftrightarrow 43$

$\dots$ Notice these are all numbers which on their first iteration will go to $1$. For $$k=2$$

$3 \longleftrightarrow 15$

$227 \longleftrightarrow 911$

$909 \longleftrightarrow 3643$

$\dots$

For any $k$ we can write

$a_1 \longleftrightarrow b_1$

$a_2 \longleftrightarrow b_2$

$a_3 \longleftrightarrow b_3$

$\dots$

$a_i \longleftrightarrow b_i$

Question: If the set of $\mathcal{O}(F)$ is in one-to-one correspondence with the set $\mathcal{O}(G)$, can we say there is a counterexample for $F(n)$ ? Because, There is a counterexample for $G(n)$ which that, they are $(5,7,17)$ and $$\mathcal{O}(F) \dashleftarrow\dashrightarrow \mathcal{O}(G)$$

P.S: Please help me for improve my question.

Thank you!!

$\endgroup$
3
$\begingroup$

No; any two infinite sets of natural numbers are in bijection with each other. In particular, any infinite set of natural numbers is in bijection with $\mathbb{N}$, even though most (all but one, in fact) infinite sets of natural numbers don't contain every natural number. Just knowing that $\mathcal{O}(F)$ and $\mathcal{O}(G)$ are both infinite, and that $\mathcal{O}(G)\not=\mathbb{N}$, doesn't tell you anything about what $\mathcal{O}(F)$ could be.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Though, set of $\mathcal{O}(F)$ is in one-to-one correspondence with the set $\mathcal{O}(G)$ ?? $\endgroup$ – Soru Jun 26 '17 at 22:55
  • $\begingroup$ @Soru Yes. Any two infinite sets of natural numbers are in one-to-one correspondence with each other. ("In bijection with" is just another way of saying "in one-to-one correspondence with.") $\endgroup$ – Noah Schweber Jun 26 '17 at 23:07
  • $\begingroup$ Hmm...I understood thank you... $\endgroup$ – Soru Jun 26 '17 at 23:09
  • $\begingroup$ @Soru What does it mean for a function to be in one-to-one correspondence with another function? One-to-one correspondences are just for sets. And it is extremely easy to show that any two infinite sets of natural numbers are in one-to-one correspondence with each other (map the first element of the first to the first element of the second, the second element of the first to the second element of the second, ... , the $n$th element of the first to the $n$th element of the second, ...). $\endgroup$ – Noah Schweber Jun 26 '17 at 23:16
  • $\begingroup$ I understood 100% thank you so much! $\endgroup$ – Soru Jun 26 '17 at 23:19

Not the answer you're looking for? Browse other questions tagged or ask your own question.