Axiom of choice required?

83 Views Asked by At

I have been attempting to prove that there exists an injective function from $P(\mathbb{N})$ to $ \mathbb{R}$. My idea has been to show that I can write any finite set in the powerset in order and just map it to the corresponding real number, however I struggle with doing so in the case of infinitely large subsets of $\mathbb{N}$. Suppose I have such a subset $A$ given, would I only be able to sort it and map it using the Axiom of Choice? My intuition says yes but I don't know whether this is actually true.

Example for finite set: $(1,2,49,688)$ would map to 1249688.

To summarize: Would this proof work, why or why not? If it works, do I need choice, yes or no? If yes, why?

EDIT: Has been easily solved, proof doesn't work. Didn't think of the cases in which different sets can actually map to the same element (see comments).

1

There are 1 best solutions below

0
On

Given a function $f:\mathbf{Z}^+\to\lbrace 0,1\rbrace$, one may define $P(f)$ to be the real number $$P(f)=\sum_{k=1}^\infty\frac{1+(-1)^{1+f(k)}}{3^k}.$$ If you accept the principle of the excluded middle, $P:\mathcal{P}(\mathbf{Z}^+)\to\mathbf{R}$, and $P$ is injective as intended. Of course, the domain of $P$ is really $2^{\mathbf{Z}^+}$, the set of functions from $\mathbf{Z}^+$ to $2=\lbrace 0,1\rbrace$, but this distinction from the set of subsets $\mathcal{P}(\mathbf{Z}^+)$ disappears under excluded middle.

The function $P$ is continuous in both directions, and in fact provides a description of the Cantor set $C\subseteq\mathbf{I}=[0,1]$ as a denumerable product of finite discrete spaces—the very representation is in fact why it is also referred to as the Cantor ternary set. As far as I am aware, this correspondence is entirely constructive, meaning no axiom of choice or the principle of the excluded middle is required for the function $P$ itself, given that one considers $P:2^{\mathbf{Z}^+}\to\mathbf{R}$ rather than $P:\mathcal{P}(\mathbf{Z}^+)\to\mathbf{R}$.