most recent 30 from http://mathoverflow.net 2013-05-20T12:03:05Z http://mathoverflow.net/feeds/question/51415 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/51415/is-it-possible-to-show-that-an-infinite-set-has-a-countable-infinite-subset-wi tibet 2011-01-07T17:21:29Z 2011-01-08T04:49:01Z

<p>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?</p>

http://mathoverflow.net/questions/51415/is-it-possible-to-show-that-an-infinite-set-has-a-countable-infinite-subset-wi/51416#51416 Stefan Geschke 2011-01-07T17:31:11Z 2011-01-07T17:31:11Z

<p>Short answer: No.</p> <p>By countably infinite subset you mean, I guess, that there is a 1-1 map from the natural numbers into the set. </p> <p>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.</p>

http://mathoverflow.net/questions/51415/is-it-possible-to-show-that-an-infinite-set-has-a-countable-infinite-subset-wi/51417#51417 Chris Eagle 2011-01-07T17:31:31Z 2011-01-07T17:31:31Z

<p>No. A set which has a countably infinite subset is called <a href="http://en.wikipedia.org/wiki/Dedekind-infinite_set" rel="nofollow">Dedekind-infinite</a>. 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.</p>

http://mathoverflow.net/questions/51415/is-it-possible-to-show-that-an-infinite-set-has-a-countable-infinite-subset-wi/51462#51462 ansobol 2011-01-08T04:49:01Z 2011-01-08T04:49:01Z

<p>The following (nicely written) paper might be relevant:</p> <p><a href="http://arxiv.org/abs/math.LO/0605779%20%22Division%20by%20three%22" rel="nofollow">http://arxiv.org/abs/math.LO/0605779</a></p> <p><strong>Division by three</strong></p> <p>Peter G. Doyle, John Horton Conway</p> <p>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.</p>