6
$\begingroup$

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 and $x_0\in X$. Let $A_i = \{x\in X\mid d(x,x_j)\ge r,\, j. 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.)

  • 0
    See [this question](http://math.stackexchange.com/questions/83876); but I think both answers there use choice.2012-08-08
  • 0
    @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 :)2012-08-08
  • 0
    a) Why is that set finite? b) It least element with respect to which ordering?2012-08-08
  • 0
    @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.2012-08-08
  • 0
    b) you are right.. I used AC$_\omega$. I didn't notice that.2012-08-08
  • 0
    Your additional question: There are two definitions of [finite](http://en.wikipedia.org/wiki/Finite_set#Set-theoretic_definitions_of_finiteness)/infinite sets, which are not equivalent in ZF, see [Section 4.1](http://books.google.com/books?id=JXIiGGmq4ZAC&pg=PA43) in H. Herrlich: Axiom of Choice. They are called Dedekind infinite sets and Tarski infinite (or simply infinite) set. A set $X$ is D-infinite $\Leftrightarrow$ $\aleph_0\le|X|$. A set $X$ is T-infinite $\Leftrightarrow$ $|X|\not<\aleph_0$. You'll find more if you search for these terms on MSE and on the Internet.2012-08-08
  • 0
    @joriki a) is neither true. I used some wrong inequalities / Martin I'm referring to T-infinite which is strictly weaker than D-infinite!2012-08-08
  • 0
    @Katlus: If you've said yourself that they are not equivalent, which answers your additional question. :) $\aleph_0\leq \lvert X\rvert$ is pretty much what you asked for.2012-08-08
  • 0
    @tomasz I knew the difference, but couldn't prove that T-infinite implies D-infinite..2012-08-08
  • 0
    @Katlus: It seems to me that the proof you give yields something (strictly) stronger than separability (at least assuming choice), namely total boundedness. Is that what you want, or is separability enough?2012-08-08
  • 0
    @tomasz separability is enough. Help2012-08-08

2 Answers 2

9

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.

  • 0
    Thanks, I have now fixed it to give a metric space counterexample.2012-08-08
  • 0
    @JDH Nice answer. Thank you! Is 'Limit point compact⇒compact' also not provable in ZF?2012-08-08
  • 0
    @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.2012-08-08
  • 0
    @tomasz This is the first time i face unprovable statements in ZF. Very impressing. Thank you!2012-08-08
  • 0
    @Katlus: What about CH? ;) Or T-infinite $\Rightarrow$ D-infinite?2012-08-08
  • 0
    @tomasz Let me rephrase it to 'first example 'almost' directly related to calculus'.. I dunno2012-08-08
  • 0
    Tomasz, I added a remark about that.2012-08-08
  • 1
    @Katlus: I think that I supplied you with a plethora of unprovable claims in some of your previous questions...2012-08-08
  • 0
    @Asaf you're absolutely right. I see there is a difference between 'looking' at examples and 'touching' examples.. I have no idea how to explain this.. Never mind what i just said.2012-08-08
  • 0
    BTW *limit-point-compact* is called *Weierstrass compact* in [Herrlich's book](http://books.google.com/books?id=JXIiGGmq4ZAC&pg=PA38). (I am not sure whether this name is widespread.)2012-08-09
1

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 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$.

  • 0
    Why is $x_{m-1}\in T$ by construction?2012-08-08
  • 0
    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$.2012-08-08
  • 0
    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$.2012-08-08
  • 0
    @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.2012-08-08
  • 0
    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.2012-08-08
  • 0
    @CameronBuie: Looking at the comment by Martin Sleziak, it is obvious that Dedekind-infinite implies Tarski-infinite, so if there are no other definitions of infinite (esp. none which apply to non-Tarski-infinite sets), then the most obvious definition of unqualified "infinite" (namely "either Dedekind-infinite or Tarski-infinite") is equivalent to Tarski-infinite, so it's no surprise that it is used that way.2012-08-08
  • 0
    Precisely! ^_^ I'm not sure why people are downvoting you without giving you a reason.... I've upvoted to compensate.2012-08-08
  • 0
    @CameronBuie: Thank you.2012-08-08
  • 0
    The usual definition of "infinite" is simply "not finite", and so I find the definition given in this answer to be wrong, especially in a context without AC. (A set is finite when it can be placed in bijection with the predecessors of a natural number.) Although this usual notion is the same as what Cameron called "Tarski infinite," it seems to me that the concept considerably pre-dates Tarski...2012-08-08