most recent 30 from http://mathoverflow.net 2013-06-19T04:23:47Z http://mathoverflow.net/feeds/question/22243 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/22243/what-is-the-smallest-cardinal-number-of-a-set-that-requires-the-axiom-of-choice-t Garabed Gulbenkian 2010-04-22T19:47:44Z 2010-04-24T10:51:20Z

<p>Let C(x) be a formula belonging to the language of ZFC in which the variable "x" and no other variable occurs free. Suppose that (a sentence of this language equivalent to) the following statement, is provable in ZFC but not in ZF.</p> <p>"There exists a non-empty set Q such that every element x of Q satisfies the formula C(x)"</p> <p>QUESTION: What is the smallest cardinal number that such a set Q can (be proved in ZFC) to have?</p> <p>I know of no examples of such a set Q having a cardinal number less than 2^(2^k) where k is the cardinal number of the contnuum. Examples of such sets Q are the set of all uncountable sets of real numbers that are non-measurable in the sense of Lebesgue or that contain no perfect subset. </p>

http://mathoverflow.net/questions/22243/what-is-the-smallest-cardinal-number-of-a-set-that-requires-the-axiom-of-choice-t/22246#22246 Joel David Hamkins 2010-04-22T19:58:28Z 2010-04-24T10:51:20Z

<p>You probably won't like this, but the answer is cardinality 1. </p> <p>Let C(x) be the statement, "x=0 and the Axiom of Choice holds". </p> <p>ZF doesn't prove that any x satisifes C(x), since it doesn't prove AC. If AC fails, then no x can have C(x). Thus, ZF+&not;AC proves that no x has C(x).</p> <p>But ZFC proves that C(0) holds, and so it proves that Q={0} is the desired set.</p> <hr> <p>Addendum: </p> <p>The set { x | C(x) } is an indicator set for AC, in the sense that it is either 0 or 1, depending exactly on whether AC holds. A similar trick works to construct indicator sets for any assertion. </p> <p>I have suggested that the question be focused on the possibility of projective statements C(x). A projective statement is one expressible in the language of second order number theory, with quantifiers over real numbers and natural numbers. Thus, the question would be whether there is a specific projective statement C(x) such that ZFC proves that Q = { x | C(x) } is nonempty, but ZF does not. </p> <p>This version of the question is exactly equivalent to the question of whether ZFC is not conservative over ZF for projective sentences, since if there is a counterexample C(X), then the assertion $\exists x C(x)$ is provable in ZFC but not ZF, and if $\sigma$ is provable in ZFC but not in ZF, then the set {x | $\sigma$} is ZFC provably all of the reals, but ZF is consistent with this set being empty. </p> <p>Therefore, the question amounts to: Is ZFC not conservative over ZF for projective statements?</p> <p>I think it is not, but I don't have a counterexample. </p> <p>Meanwhile, I can say that if one replaces ZF here with ZF+DC, looking at the difference between the full Axiom of Choice and the Axiom of Dependent Choices, rather than at the difference between full AC and no AC at all, then the answer is that it IS conservative. In <a href="http://mathoverflow.net/questions/8392" rel="nofollow">this MO answer</a>, I explained that ZFC is conservative over ZF+DC for projective sentences, and so if one replaces ZF with ZF+DC in the question, the answer would be no. But without DC, weird things can happen in the reals, and I'm not yet quite sure about it.</p>

http://mathoverflow.net/questions/22243/what-is-the-smallest-cardinal-number-of-a-set-that-requires-the-axiom-of-choice-t/22250#22250 Simon Thomas 2010-04-22T20:04:39Z 2010-04-22T20:13:10Z

<p>Wilfrid Hodges has shown that it is consistent with ZF that there is an algebraic closure $L$ of the rational field $\mathbb{Q}$ with no nontrivial automorphisms. Obviously $|Aut(L)\smallsetminus {1}| = 2^{\aleph_{0}}$.</p> <p>See: W. Hodges, Läuchli's algebraic closure of $\mathbb{Q}$. Math. Proc. Cambridge Philos. Soc. 79 (1976), no. 2, 289--297</p>

http://mathoverflow.net/questions/22243/what-is-the-smallest-cardinal-number-of-a-set-that-requires-the-axiom-of-choice-t/22251#22251 cooperback 2010-04-22T20:13:12Z 2010-04-22T20:13:12Z

<p>If you want to prove that the countable union of countable sets is countable you need the Axiom of choice. However you can replace it by the Axiom of Countable Choice. Which is weaker than the Axiom of Choice and more intuitive. Also, it isn't strong enough to prove Banach-Tarski paradox (A good book to read the relation between AC ACC and the paradoxes is The Banach-Tarski Paradox from Wagon)</p> <p><a href="http://en.wikipedia.org/wiki/Axiom_of_countable_choice" rel="nofollow">http://en.wikipedia.org/wiki/Axiom_of_countable_choice</a></p>