# Prove that the set $A = \{k^\frac{1}{k}| k \neq 0, k \in \mathbb{Z}\}$ is countably infinite

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?

• 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 – J. W. Tanner Jun 16 '19 at 19:27
• If I were you I would ask my professor first. – uniquesolution Jun 16 '19 at 19:28
• Do you know that the set of algebraic numbers is countably infinite? – J. W. Tanner Jun 16 '19 at 19:38
• @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. – Yousousen Jun 16 '19 at 20:04
• 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. – 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.

• 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. – hmakholm left over Monica Jun 16 '19 at 19:52
• For $k=2$ and $4$ they're equal – J. W. Tanner Jun 16 '19 at 19:56
• @James Thank you very much! This cleared up a lot. – Yousousen Jun 16 '19 at 20:07
• @HenningMakholm You are correct, let me fix that. – James Jun 16 '19 at 20:09