6
$\begingroup$

Prove that the following statement implies the Axiom of Choice:

Let $ C $ is a set (of sets) and $ B $ is a set such that for all $ c \in C $, there exists a $ b \in B $ such that $ b \not\in c $. Then there is a function $ F: C \to B $ such that $ F(c) \not\in c $.

In other words, we're given an "anti-choice" function that gives us elements not in each set.

Any "usual" formulation of the Axiom of Choice (choice function, non-empty Cartesian product, Zorn's, etc.) is fine.


Attempt at solution: The usual formulations of the AC involve picking out elements out of sets. However, here we are given a way of picking out things not in a set.

My first attempt was to show the existence of a choice function. So let $ A $ be a set (of sets). Applying $ F $ to this domain gives us an element in $ B $ (unspecified so far) not in $ A $. So here is where I get stuck. Given an element not in $ a \in A $, I don't see how I can map this to an element in $ a $.

Something a little more clever must be done.

For each element $ a \in A $, I considered the union of $ A-\{ a \} $ (call this mapping $ g $). Let's call $$ C = \{ \cup (A-\{ a \}) \mid a \in A \} $$

and set $ B $ to be $ \cup A $. If the sets in $ A $ were disjoint, then $ F \circ g $ would give us the desired choice function. But for disjoint sets, I am again stuck.

$\endgroup$
3
  • 1
    $\begingroup$ $\big\{a\times\{a\}:a\in A\big\}$ is a pairwise disjoint family that corresponds in an obvious and natural way to $A$ itself. (This is a standard trick for ‘disjointing’ a family.) $\endgroup$ Commented Dec 14, 2012 at 10:46
  • $\begingroup$ @BrianM.Scott: Oh nice, I have not seen this trick before! Well I think that solved my problem. If you add that as an answer, I'd be happy to upvote. $\endgroup$
    – tskuzzy
    Commented Dec 14, 2012 at 10:49
  • $\begingroup$ I can do that; it’ll take a couple of minutes. $\endgroup$ Commented Dec 14, 2012 at 10:52

2 Answers 2

8
$\begingroup$

It is enough to show that for every non-empty set $X$ there is a choice function on $P(X)\setminus\{\varnothing\}$.

Use this formulation to show that this is actually a choice function from the complement set, i.e. set $C=P(X)\setminus X$ and $B=X$, and $F(Y)\notin Y$ is exactly a choice function from $X\setminus Y$.

$\endgroup$
5
$\begingroup$

$\big\{a\times\{a\}:a\in A\big\}$ is a pairwise disjoint family that corresponds in an obvious and natural way to $A$ itself. (This is a standard and very useful trick for ‘disjointing’ a family of sets.)

$\endgroup$
1
  • 2
    $\begingroup$ I never knew that 59 seconds is "a couple of minutes". :-) $\endgroup$
    – Asaf Karagila
    Commented Dec 14, 2012 at 11:31

You must log in to answer this question.

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