Since the comments section to this post (proof that any infinite set has a countably infinite subset) has been closed, I reiterate my question, what's wrong with that proof? I will try to imagine what might go wrong if I don't assume any version of the Axiom of Choice. S is the infinite set (a set with an infinite number of elements)

The summary of the proof is that we let *x _{1}* be an element in S. Then assume

*x*...

_{1}*x*are distinct members of S, and let

_{n}*x*be a member of S with

_{n+1}*x*...

_{1}*x*removed;

_{n}*x*...

_{1}*x*become distinct members of S. By (strong) induction, for each positive integer

_{n+1}*n*,

*x*exists, and they all form a countably infinite set that's a subset of S.

_{n}So what's wrong here? The Proof-Wiki warning says that this works for any finite value of *n*, but repeating it an infinite number of times requires a version of the Axiom of choice. Here's a clue: *n* is finite. The fact that *n* can be any positive integer makes the set {*x _{n}*} countably infinite.

For this to fail, there has to be some (finite) value of *n* for which the choice of *x _{n+1}* fails. The warning appears to tell us that this method is valid for finite

*n*, but invalid as

*n*approaches infinity. Okay, let's define a validity function

*v*(

*n*), with

*v*(

*n*)=1 meaning valid, and

*v*(

*n*)=0 meaning invalid. We're being told that

*v*(

*n*)=1 for any finite

*n*, but approaches zero as

*n*approaches infinity -- increases without bound. No, "

*v*(

*n*)=1 for any finite

*n*" means that

*v*(

*n*) stays 1 as

*n*approaches infinity.

## Recent Comments

Mike40033:You asked a question about negative interest ra... | more »John M:I dont think that is really a difference, in th... | more »Blissex:No, that argument does not work. Because libert... | more »