Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
$\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.) –  Brian M. Scott Dec 14 '12 at 10:46
    
@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. –  tskuzzy Dec 14 '12 at 10:49
    
I can do that; it’ll take a couple of minutes. –  Brian M. Scott Dec 14 '12 at 10:52

2 Answers 2

up vote 4 down vote accepted

$\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.)

share|improve this answer
1  
I never knew that 59 seconds is "a couple of minutes". :-) –  Asaf Karagila Dec 14 '12 at 11:31

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.