(ZF) Every nonempty perfect set in $\mathbb{R}^k$ is uncountable.

This is the part of proof in Rudin PMA p.41

Let $P(\subset \mathbb{R})$ be a perfect set. Since $P$ has limit points, $P$must be infinite. Suppose that $P$ is countable. Then, we can denote the points of $P$ by $x_1, x_2,...$. Let $V_1$ be any neighborhood of $x_1$.(i.e. open ball). Suppose $V_n$ is constructed. Since every point of $P$ is a limit point of $P$, there is a neighborhood $V_{n+1}$ of some point $x_m \in P$ such that (i) $\overline {V_{n+1}}$ $\subset V_n$ and (ii) $x_n \notin \overline {V_{n+1}}$ and (iii) $V_{n+1} \cap P ≠ \emptyset$. Then form a sequence $\{V_n \subset \mathbb{R}^k | n\in \omega \}$.

Here, Axiom Of dependent choice is used. I have tried some other ways, but ,informally speaking, proof by 'squeezing' region requires AC. (Forming a decreasing sequence)

I want a proof without AC. Help..

-
What are you asking? Are you looking for some way to prove the result without choice? –  KReiser Jul 30 '12 at 18:09
@KReiser Yes. I'll add it –  Katlus Jul 30 '12 at 18:11
You actually use DC since the choice of $V_n$ depends on $V_{n-1}$. DC is stronger than countable choice (it just happens that I am studying the proof of that... weird, huh?) –  Asaf Karagila Jul 30 '12 at 18:13
@Asaf Edited. It's off the topic, but it is hard to find where AC is used at the first time, then it is reallly hard to notice what kind of choice is used.. –  Katlus Jul 30 '12 at 18:17
@Katlus: Yes. It's not an easy task to see the precise form of choice used in a proof. It requires a lot of practice and knowledge on the various forms. Dependent choice is like the name suggests: the next choice depends on the previous ones. Essentially when defining by induction you often use DC. Sometimes this use is excessive, but this is not a big deal most of the time. –  Asaf Karagila Jul 30 '12 at 18:22

The trick is simple. Use the fact the $P$ is well-ordered and that the rationals are well-ordered.
In the induction step, instead of taking "some $x_m\in P$" take $x_m$ such that $m$ is the least $k$ for which $x_k$ has an open neighborhood etc. etc.
Also require that the open neighborhoods are open balls of rational radius. Well ordering the rationals we can require the radius to be of the least rational in a fixed enumeration such that a ball around $x_m$ with the wanted properties exists.
Now we have a canonical choice of the open neighborhoods, and we can show that their intersection is non-empty because it is equal to the intersection of the closures - which is compact (by a previous question of yours) and therefore contains a point. This point is not in $P$.
@Katlus: The rationals are countable, therefore they are well-ordered. Fix a bijection with $\omega$ and you have proved that. We use this to choose a rational for the radius of $V_{n+1}$, we simply take the least rational in this enumeration such that $B(x_m,q_j)$ has the properties we want from $V_{n+1}$. –  Asaf Karagila Jul 30 '12 at 19:07
Oh got it, it's a different ordering of $\mathbb{Q}$ from the usual. Thank you –  Katlus Jul 30 '12 at 19:13