Every infinite set contains an infinite, countable subset?

[divergentgrad]

Does every infinite set contain an infinite, countable subset?

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

 

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

 

[SW VandeCarr]

Does every infinite set contain an infinite, countable subset?

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

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.

 

[divergentgrad]

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.

It seems so obvious now. Thanks.

 

[micromass]

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

 

[mathman]

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

Why do you need the axiom of choice?

 

[micromass]

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

 

[mathman]

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

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.

 

[micromass]

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

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

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.

What we do here is to select an element x₀ from a set X, then an element x₁ 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.

 

[micromass]

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 y_n (and eliminiting duplicates) yields a countable infinite subset of X.

 

[Hurkyl]

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.

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.

 

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

 

[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?

 

[Hurkyl]

How do you choose one element from a set X in the set theoretical formal language?

Maybe we can't do more that say \exists x : x \subseteq X and the cardinality of x is 1.

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.

 

[disregardthat]

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.

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?

 

[Hurkyl]

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.

 

[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?

 

[disregardthat]

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

 

[micromass]

Well, the fact that a set X and the set X² 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?

 

[SteveL27]

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?

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.

 

[Hurkyl]

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.

It's not what you're choosing from -- it's how many choices you have to make. You can still have a problem even if every set you're choosing from has only two members.

 

[mathman]

It's not what you're choosing from -- it's how many choices you have to make. You can still have a problem even if every set you're choosing from has only two members.

I don't understand the objection. I am choosing one element from one non-empty set. Next, since the set had an infinite number of elements, I then can choose another element, etc. I am not trying to choose an infinite number of elements from an infinite number of sets (axiom of choice - as far as I understand it).

 

[Hurkyl]

I don't understand the objection. I am choosing one element from one non-empty set. Next, since the set had an infinite number of elements, I then can choose another element, etc.

That "etc." only gets you up to "I can make N choices from this set, where N is a natural number". It does not get you up to "I can make infinitely many choices from this set".

 

[micromass]

I don't understand the objection. I am choosing one element from one non-empty set. Next, since the set had an infinite number of elements, I then can choose another element, etc. I am not trying to choose an infinite number of elements from an infinite number of sets (axiom of choice - as far as I understand it).

You can choose a finite number of elements. And that finite number can be made as large as you want. But it can't be made infinite.

 

[SteveL27]

I don't understand the objection. I am choosing one element from one non-empty set. Next, since the set had an infinite number of elements, I then can choose another element, etc. I am not trying to choose an infinite number of elements from an infinite number of sets (axiom of choice - as far as I understand it).

Here's how I understand that. You have an infinite set X. X is certainly nonempty. So I can pick one element; call it x1.

Now X\{x2} is certainly nonempty, so I can pick x2.

Now X\{x1,x2} is certainly nonempty, so I can pic x3.

Dot dot dot ... but that's where the AC is needed. Because to complete this construction, I have to choose one element from each of an infinite collection of nonempty sets.

 

[mathman]

Without a formal background in Z-F theory, I could not see the need for an axiom of choice for countable collections, but it appears necessary.