Welcome to MathOverflow

Question

5

2

Let X be an infinite set. Is it possible to show the existence of a countably infinite subset of X without using the Axiom of Choice?

flag	asked Jan 7 2011 at 17:21 tibet 125●5

You may also be interested in this question: mathoverflow.net/questions/51171/… – Andres Caicedo Jan 7 2011 at 18:01

Stefan Geschke · Accepted Answer · 2011-01-07 17:31:11Z UTC

15

Short answer: No.

By countably infinite subset you mean, I guess, that there is a 1-1 map from the natural numbers into the set.

If ZF is consistent, then it is consistent to have an amorphous set, i.e., a set whose subsets are all finite or have a finite complement. If you have an embedding of the natural numbers into a set, the image of the even numbers is infinite and has an infinite complement. So the set cannot be amorphous.

answered Jan 7 2011 at 17:31

Stefan Geschke
10.6k●1●14●37

How do you show that nice consistency result? I used to know, but it’s escaping me now — something with Frankel-Mostowski permutation models, is it? – Peter LeFanu Lumsdaine Jan 7 2011 at 17:46

1

@Peter: Yes, the set $A$ in the basic Fraenkel model is amorphous, see A. Levy, "The independence of various definitions of finiteness", Fund. Math. 46 (1958), 1–13. But you can also see this directly in the original Cohen model for not-AC. – Andres Caicedo Jan 7 2011 at 18:16

ansobol · Answer 2 · 2011-01-08 04:49:01Z UTC

The following (nicely written) paper might be relevant:

http://arxiv.org/abs/math.LO/0605779

Division by three

Peter G. Doyle, John Horton Conway

We prove without appeal to the Axiom of Choice that for any sets A and B, if there is a one-to-one correspondence between 3 cross A and 3 cross B then there is a one-to-one correspondence between A and B. The first such proof, due to Lindenbaum, was announced by Lindenbaum and Tarski in 1926, and subsequently `lost'; Tarski published an alternative proof in 1949. We argue that the proof presented here follows Lindenbaum's original.

Chris Eagle · Answer 3 · 2011-01-07 17:31:31Z UTC

6

No. A set which has a countably infinite subset is called Dedekind-infinite. Clearly every Dedekind-infinite set is infinite; the statement that every infinite set is Dedekind-infinite is not provable in ZF (assuming ZF is consistent, of course). You don't need full AC, though. In fact, the equivalence isn't even as strong as countable choice.

answered Jan 7 2011 at 17:31

Chris Eagle
689●1●5●7

It’s perhaps worth noting that this may not be the most familiar definition of Dedekind-infinite (“X is D-infinite if it is bijective to some proper subset of itself”), but that these two definitions are equivalent in ZF. – Peter LeFanu Lumsdaine Jan 7 2011 at 17:45

@Peter: If $X$ is amorphous (as defined by Stefan in his answer) is it not Dedekind-infinite with some bijection to a cofinite subset? – Asaf Karagila Jan 7 2011 at 18:09

1

@Asaf: Amorphous sets are Dedekind finite. The point is that if you remove a point $a$ from a set $X$, and the result has the same size as $X$, you can iterate, and get an injection of ${\mathbb N}$: Keep track of the orbit of $a$ as you iterate the bijection $X\to X\setminus\{a\}$ . – Andres Caicedo Jan 7 2011 at 18:19

Andres: So simple! Many thanks :-) – Asaf Karagila Jan 7 2011 at 19:39

Is it possible to show that an infinite set has a countable (infinite) subset, without using the Axiom of Choice?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

3 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.