Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I can prove this in ZFC, but don't know how to prove this in ZF.

Following is the argument of this in ZFC.
Fix $0<r\in \mathbb{R}$ and $x_0\in X$. Let $A_i = \{x\in X\mid d(x,x_j)\ge r,\, j<i\}$. Suppose $A_i≠\emptyset$ for every $i\in \omega$. Then by AC, we can choose $x_i$ for each $A_i$ to derive contradiction.

I want to prove this in ZF. Help.

Additional Question: Does infinite set have a countable subset in ZF? I guess it's true, but I only know the proof in ZFC. (If it is true, I think it would be really useful in many proofs in ZF.)

share|cite|improve this question
See this question; but I think both answers there use choice. – joriki Aug 8 '12 at 10:33
@joriki I guess it would be possible to prove this in ZF with that argumenet, since 'for every $x\in X, \{y\in X|d(x,y)≧r\}$ is finite', hence i can choose its least element. I'll try it again :) – Katlus Aug 8 '12 at 11:00
a) Why is that set finite? b) It least element with respect to which ordering? – joriki Aug 8 '12 at 11:05
@joriki Fix $x\in X$ and suppose $\{y\in X|d(x,y)≧r\}$ is infinite. Then a limit point of the set is an element of the set. It leads a contradiction. – Katlus Aug 8 '12 at 11:13
b) you are right.. I used AC$_\omega$. I didn't notice that. – Katlus Aug 8 '12 at 11:15
up vote 8 down vote accepted

Unfortunately, the claim is not provable in ZF.

It is relatively consistent with ZF that there is an infinite Dedekind-finite set of reals, an infinite set of reals $X$ with no countably infinite subset. This set of reals forms a metric space with the usual metric, and it cannot be separable, because it has no countably infinite subset (and no finite subset of an infinite metric space can be dense).

Meanwhile, such an $X$ has your limit point property. To see this, suppose $Y\subset X$ is infinite, but has no limit point in $X$. In particular, every point $y\in Y$ is isolated in $Y$, and therefore we may pick a rational interval neighborhood $(q_x,r_x)$ of $y$ containing no other points from $Y$ except for $y$ itself. We do not need AC to pick this interval, since we may enumerate the rational intervals and pick the first one with this property. Further, each $y\in Y$ gives rise to a distinct such interval. Thus, we have an injective map from $Y$ to the set of rational intervals, and from this it follows that $Y$ is countable, contradicting our assumption that $X$ has no countably infinite subset.

Note that $X$ also serves as a metric space that is limit-point compact but not compact. We've already shown that it is limit-point compact. But $X$ is not compact because we may simply pick any real $z\notin X$ that is a limit point of $X$, and then use the rational approximations to $z$ to produce an open cover of $X$ with no finite subcover, consisting of intervals straddling these approximations. Thus, ZF (if consistent) does not prove that limit-point-compact metric spaces must be compact.

share|cite|improve this answer
Thanks, I have now fixed it to give a metric space counterexample. – JDH Aug 8 '12 at 14:41
@JDH Nice answer. Thank you! Is 'Limit point compact⇒compact' also not provable in ZF? – Katlus Aug 8 '12 at 15:19
@Katlus: I think the same example shows that. A compact subset of reals is closed, and therefore is finite, countable, or of the cardinality $2^{\omega}$, so $X$ can't be compact. – tomasz Aug 8 '12 at 15:21
@tomasz This is the first time i face unprovable statements in ZF. Very impressing. Thank you! – Katlus Aug 8 '12 at 15:29
@Katlus: I think that I supplied you with a plethora of unprovable claims in some of your previous questions... – Asaf Karagila Aug 8 '12 at 15:50

About your second question: IIRC, a set $S$ is by definition infinite iff there is a bijection $f$ from $S$ to a proper subset $T$ of $S$. Now consider a point $x_0\in S\setminus T$, and define $x_n = f(x_{n-1})$. Now if for any $m<n$ we had $x_m=x_n$, then we could apply $f^{-1}$ $m$ times (because it's a bijection) and end up with $x_{n-m}=x_0$. However by construction $x_{n-m}\in T$ and $x_0\in S\setminus T$, thus $x_{n-m}\neq x_0$, and therefore no two $x_n$ are equal. Therefore the set $\{x_n:n\in\mathbb N\}$ is a countable subset of $S$.

share|cite|improve this answer
Why is $x_{m-1}\in T$ by construction? – joriki Aug 8 '12 at 10:57
Oops, should have been $x_{n-m}$ (both where I've written $x_{n-m}$ and $x_{m-1}$, sorry. Of course $x_{n-m}\in T$ because by assumption $n-m>0$ and thus $x_{n-m}=f(x_{n-m-1})\in f(S)=T$. – celtschk Aug 8 '12 at 11:05
A set is bijectable to a proper subset iff it has a countably infinite subset. These describe what are known as Dedekind-infinite sets. The OP is referring to Tarski-infinite sets--that is, sets that are not strictly injectable into $\Bbb N$. – Cameron Buie Aug 8 '12 at 14:43
@CameronBuie: Actually the OP only stated "infinite set" without qualification. Up to now I was unaware of the fact that there are several definitions of infinite sets which are inequivalent without choice (are there any others besides Dedekind and Tarski?), therefore I couldn't know that the definition I knew doesn't cover all infinite sets. – celtschk Aug 8 '12 at 14:52
There aren't any others that I know of. You (of course) couldn't have known which sort the OP was referring to, since you posted an hour before it was revealed in the comments. Just thought I'd let you know. Typically, in set-theoretic circles, one uses "infinite" to refer to Tarski-infinite sets, and "D-infinite" for Dedekind-infinite sets. – Cameron Buie Aug 8 '12 at 14:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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