1
$\begingroup$

It is easy to find a choice function on all finite subsets of $\mathbb R$, but without using the axiom of choice, not on all subsets. Is there an "explicit" choice function on the countable subsets of the real line? Can it be used to create paradoxical objects like, say, Vitali sets in the same way that a choice function on all subsets does?

Edit: Chris notes that the construction of the Vitali set only involves choosing from countable subsets, so there is no hope for such a function to be explicit. I revise my question, then: does the existence of a choice function on all countable subsets imply the existence of a global choice function? Is it consistent that there is a choice function on the countable subsets, but not on all subsets?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

The standard construction of a Vitali set only involves making choices from countable subsets of $\mathbb{R}$ (specifically, from sets of the form $(r+\mathbb{Q}) \cap [0,1]$). It is well known that ZF (assuming consistent) does not prove the existence of a non-measurable subset of $\mathbb{R}$, hence it doesn't prove the existence of a Vitali set, and thus doesn't prove your restricted choice principle.

Consequences of the Axiom of Choice is useful for this sort of thing. According to this, form 85 (every collection of countable sets has a choice function) is true while form 79 (every collection of sets of reals has a choice function) is false in model $\mathcal{M} 1$, which I believe is Cohen's original model of ~AC. Thus your countable choice principle for the reals does not imply full choice for the reals.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Moreover, I think constructing non measurable sets relies necessarily relies on the axiom of choice (meaning it cannot be done with the axioms of ZF alone). $\endgroup$
    – Joël Cohen
    Commented Mar 23, 2011 at 22:49
  • $\begingroup$ @Joël: yes, I suppose that should be in my answer. $\endgroup$
    – Chris Eagle
    Commented Mar 23, 2011 at 22:54
  • 1
    $\begingroup$ Solovay's model is a model of ZF where every set of reals is measurable. (Assuming the existence of an inaccessible cardinal.) Thus, ZF without choice does not allow you to build a non-measurable set. $\endgroup$
    – Apollo
    Commented Mar 23, 2011 at 23:09
  • $\begingroup$ OK... but I suppose you should say: ZF without choice does not allow you both to build a set and to prove that the set is non-measurable. $\endgroup$
    – Gerald Edgar
    Commented Mar 24, 2011 at 1:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .