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?
 A: 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.
