In a practice test for my algorithms class I was asked to prove that the set $A = \{k^\frac{1}{k}| k \neq 0, k \in \mathbb{Z}\}$ is countably infinite. My professor provided me with the answer that we can create an image like the following

$$ 1 \rightarrow 1^\frac{1}{1}, 2 \rightarrow (-1)^{-\frac{1}{1}}, 3 \rightarrow 2^\frac{1}{2}, 4 \rightarrow (-2)^{-\frac{1}{2}} ..., k \rightarrow ((-1)^{k+1}\lfloor\frac{k-1}{2} + 1\rfloor)^{(-1)^{k+1}\cdot\frac{1}{\lfloor\frac{k-1}{2} + 1\rfloor}}$$

which shows that for every $k$ there is an unique value of $((-1)^{k+1}\lfloor\frac{k-1}{2} + 1\rfloor)^{(-1)^{k+1}\cdot \frac{1}{\lfloor\frac{k-1}{2} + 1\rfloor}}$, and thus the image is a bijection and the set is countable infinite.

I am familiar with the concept of how there has to be a bijection with the natural numbers for a set to be countably infinite, but I have no idea how my professor got to the expression after '$k \rightarrow$'. Can someone enlighten me on this? Or, perhaps, show a different way to proof that the set is countably infinite?

  • $\begingroup$ Welcome to Math Stack Exchange. I'd find it easier to find a bijection for $k>0$ and $k<0$ separately and then use the fact that the union of two countably infinite sets ($k>0$ and $k<0$) is countably infinite $\endgroup$ – J. W. Tanner Jun 16 '19 at 19:27
  • 1
    $\begingroup$ If I were you I would ask my professor first. $\endgroup$ – uniquesolution Jun 16 '19 at 19:28
  • $\begingroup$ Do you know that the set of algebraic numbers is countably infinite? $\endgroup$ – J. W. Tanner Jun 16 '19 at 19:38
  • 1
    $\begingroup$ @J.W.Tanner I was not aware that the set of algebraic numbers is countably inifinite. The answer on that question seems like useful information. $\endgroup$ – Yousousen Jun 16 '19 at 20:04
  • 1
    $\begingroup$ On the other hand, if the values in $A$ are all supposed to be real, then $k^{1/k}$ doesn't mean anything when $k=-2$, so the professor's claimed bijection fails to even be a function in that case. $\endgroup$ – hmakholm left over Monica Jun 16 '19 at 20:06

Your professor's expression is a (complicated way) of (attempting to) explicitly writing down a bijection. The strategy really has two pieces: firstly it shows that the positive integers is in bijection with all the non-zero integers, and then in turn that the non-zero integers are in bijection with the set $A$. The formula $$\left\lfloor \frac{k-1}{2}+1\right\rfloor = \left\lfloor \frac{k+1}{2}\right\rfloor = \left\lfloor \frac{k}{2}+\frac{1}{2}\right\rfloor$$ is a somewhat unhelpful way to say "Divide by two, and round up".

To see this, first suppose $k$ is even. Then $k/2$ is an integer, so adding a half to it and then taking the floor does not change its value. Hence the value of the expression for even $k$ is just $k/2$. On the other hand, if $k$ is odd, then $k/2$ is an integer plus $1/2$. Adding another half to this then taking the floor is the same as just adding the $1/2$, or, rounding up.

What this function does for us is that it matches each positive integers with two other positive integers, e.g. $1$ is matched with $1$ and $2$, $2$ is matched with $3$ and $4$, and so on.

Then the $(-1)^{k+1}$ part makes the sign of the output alternate, so now each positive integer is matched with one non-zero integer (as $2$ now goes to $-1$ instead of $1$, and $4$ goes to $-2$ instead of $2$, and so on).

Once we have a function that does this, you raise it to the power one over itself, which matched it up with elements of the set $A$.

Edit: It was pointed out to me that I have not actually shown that $A$ is infinite. What the above shows is that the map is surjective (or onto), but we would need to show that $A$ has infinitely many elements. This is slightly complicated by the fact that $A \subset \mathbb{C}$ but not $\mathbb{R}$. The first thing that occurs to me is to show that the function $f(x) = x^{1/x}$ for $x>0,x\in\mathbb{R}$ is decreasing for $x>e$ (as its derivative is negative there).

Edit: Note that in the definition of $A$, $k=2$ and $k=4$ give the same value: $\sqrt{2}$. Consequently, any map that tries to enumerate $A$ in the "obvious" way will not be injective.

  • $\begingroup$ I think we're missing an argument here that the $k^{1/k}$s are all different -- or at least different enough that $A$ avoids being finite. $\endgroup$ – hmakholm left over Monica Jun 16 '19 at 19:52
  • $\begingroup$ For $k=2$ and $4$ they're equal $\endgroup$ – J. W. Tanner Jun 16 '19 at 19:56
  • $\begingroup$ @James Thank you very much! This cleared up a lot. $\endgroup$ – Yousousen Jun 16 '19 at 20:07
  • $\begingroup$ @HenningMakholm You are correct, let me fix that. $\endgroup$ – James Jun 16 '19 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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