# Every infinite set contains an infinite, countable subset?

1. Jul 16, 2011

Does every infinite set contain an infinite, countable subset?

If so, why? (I'm assuming this depends on the Axiom of Choice).

2. Jul 16, 2011

### mathman

If a set is infinite, you can pick a point and place it in the (to be) countable set. This process cannot stop after a finite number of steps, since the original set is infinite. Therefore the limit of the new set is countable.

3. Jul 16, 2011

### SW VandeCarr

Under the Continuum Hypothesis, an infinite set which has a one to one mapping into real numbers would contain the countable set of rational numbers. I believe the AC is necessary to define exactly what is meant by a one-to-one mapping into the real numbers and to prove that such a mapping exists. There are others in this forum that know more about Set Theory than I do who I'm sure will weigh in.

Note: I did not see mathman's post since I started mine before he posted.

Last edited: Jul 16, 2011
4. Jul 16, 2011

It seems so obvious now. Thanks.

5. Jul 16, 2011

### micromass

Staff Emeritus
This depens on the axiom of choice, of course. Without it, there might be infinite sets without a countable subset.

6. Jul 17, 2011

### mathman

Why do you need the axiom of choice?

7. Jul 17, 2011

### micromass

Staff Emeritus
Because you choose a countably infinite set. That requires the axiom of choice (or something similar).

8. Jul 18, 2011

### mathman

I believe you are not completely familiar with the axiom of choice.

Specifically it says: given an infinite collection of non-empty sets, there exists a set (the choice set) which has an element in common with each set of the collection.

In the problem at hand we are dealing with only one infinite set, so you don't need the axiom of choice to select an element.

9. Jul 18, 2011

### micromass

Staff Emeritus
I did my thesis on the axiom of choice. But that's besides the point.

What we do here is to select an element x0 from a set X, then an element x1 from a set $X\setminus \{x_0\}$, and so on. So we are working with an infinite colection of sets, since we must select distinct elements every time.

Sets which have a countable subset are called Dedekind-infinite. So without the axiom of choice, there might exist infinite Dedekind-finite sets.

However, what we're doing here does not require the full axiom of choice!! It is even weaker than the axiom of countable choice. But it is not derivable from ZF that every set has a countable subset. Some kind of choice is needed here (although a very light kind of choice!)

See http://en.wikipedia.org/wiki/Dedekind_infinite for more information, or check out the excellent book "Axiom of choice" by Horst Herrlich.

10. Jul 18, 2011

### micromass

Staff Emeritus
An explicit model of set theory in which there exists an infinite, Dedekind-finite set is model N2(2) is "Consequences of the axiom of choice" by Howard and Rubin.

Here is a proof that the axiom of countable choice implies that every set has a countable subset.
Take an infinite set X. Consider for each n

$$X_n=\{(x_1,...,x_n)~\vert~x_i\neq x_j~\text{forall i,j}\}$$

By countable choice, there exists an element $(y_n)_n\in \prod{X_n}$
Concatenation of the yn (and eliminiting duplicates) yields a countable infinite subset of X.

11. Jul 18, 2011

### Hurkyl

Staff Emeritus
How do you plan on making the infinitely many choices?

The axiom of choice tells you things you can do, not things you cannot do.

You cannot make the choices because ZF simply doesn't have the power to show that it's possible. But ZFC does have the power.

12. Jul 18, 2011

### disregardthat

If c : P(X) --> X is a choice function, let x be an element of X, and define A_n recursively: A_(n+1) = A_n U c(X-A_n) and A_1 = {x}. The size of A_n is n, so the union will be countable. I don't think this is provable in ZF.

Hurkyl, could you answer me this, it has been bothering me for a while: How do you choose one element from a set X in the set theoretical formal language? For example, if I want to define a singleton subset from X, how do we do this by set construction?

We know that $$\exists x : x \in X$$. But how do we "draw" one element from X so that we can define a singleton subset Y? Or is this even possible? Maybe we can't do more that say $$\exists x : x \subseteq X$$ and the cardinality of x is 1.

Last edited: Jul 18, 2011
13. Jul 19, 2011

### SW VandeCarr

It seems that any infinite set which has the cardinality of the (uncountable) real numbers must contain an infinite subset which has the cardinality of the (countable) rational numbers since the rational numbers are dense in the real numbers. No?

14. Jul 19, 2011

### Hurkyl

Staff Emeritus
I think your analysis is correct. In ZF, if all we know is that "X is a set", then that is more or less the best we can do.

15. Jul 19, 2011

### disregardthat

This kind of changes the semantics for these kinds of proofs. If we take the example of the choice function above, A_n isn't really a defined set. It isn't set theoretically correct (that is, there is no corresponding argument in ZFC) to say: "let x be an element of X. Define A = {x}." We have to be able to know more of X, to such a degree that we can specify an element x for us to be able to define a singleton set. By "define" I mean as in comparison to e.g. the trivial example "Define Y = X".

So I believe that if we work with general sets, it should be put more appropriately. If I take my example again, we would have to argue that "there exists a sequence of subsets $A_1,A_2,...,A_n$ such that $A_1 \subseteq A_2 \subseteq ... \subseteq A_n$ and the cardinality of A_k is k", and from that argue that "there exists a countable subset of X" which doesn't involve defining anything, but only using the mechanics of the existence quantifier. This could alternatively be seen as 'what our argument actually mean' (if we insist on it being expressible in ZFC). Or would someone disagree with that?

Last edited: Jul 19, 2011
16. Jul 19, 2011

### Hurkyl

Staff Emeritus
Upon some reflection, what you're doing in a proof like that is not actually defining x to be a specific object. Instead, what you're doing is defining x to be a variable that varies over elements of X. (a "general element")

Once you've introduced the variable x, a definition
A := {x}​
is a perfectly good way to define a new variable A. (and makes A and x dependent variables)

Then the challenge of the proof is to ensure that your generalized elements are drawn from non-empty sets.

For finitely many such variables, it is enough to show that each individual variable varies over a non-empty domain.

For infinitely such variables, we still need only ensure each individual variable ranges over a non-empty domain. Some variant of the notion of choice function ensures that the entire collection of variables jointly varies over a non-empty domain.

Without the axiom of choice, we are no longer guaranteed that the collection of all our variables varies over a non-empty domain even if each individual one does on its own. It becomes more difficult to make arguments of this form.

17. Jul 19, 2011

### mathman

Maybe I'm being naive, but I don't see the need for the axiom of choice if we want to choose a member of a set which has an infinite number of members.

As far as the etc. part (going from one at a time to countably infinite). Is this any different from the standard proof that the rationals are countable?

18. Jul 19, 2011

### disregardthat

You don't just need one element, you will have to pick each element in the countable subset.

19. Jul 19, 2011

### micromass

Staff Emeritus
Well, the fact that a set X and the set X2 have the same cardinality is equivalent to the axiom of choice. So that's not surprising.

Showing that $\mathbb{N}$ and $\mathbb{N}^2$ have the same cardinality can be done without choice since an explicit bijection can be found (otherwise, choice was necessary). But not all sets are as well-behaved as the naturals!!

Let's say I give you an infinite set X. Try to write down an explicit countable subset of X. Explicit in the sense that you can use unions, products (which can be empty), intersections, etc. What would that explicit subset look like? Can you write it down?

20. Jul 19, 2011

### SteveL27

Yes. Say you have a countable collection of arbitrary countable sets. You want to do the "diagonal snake" trick by laying out each countable set horizontally, one above the other, to form an infinite matrix.

For each of the countable sets, there is a bijection with N, so we can certainly write down its elements in a list a1, a2, a3, ...

But what we need to do is choose a particular bijection for each of the countably many countable sets. For that we need choice.

In other words each countable set has a bijection with N. But you need Choice to simultaneously choose a particular bijection for each set.

I know that won't convince an AC disbeliever (or agnostic, as the case may be), but that's the explanation as I understand it.

Last edited: Jul 19, 2011