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.

I recently read a proof that had the following in it: "since $A$ is non-empty, we can find an element $x$ in $A$." This proof did not mention the axiom of choice, but it seems to me that it would be required to make the proof formal. Would I not require a choice function to allow me to find/pick some element $x$ from $A$ after noting that A is non-empty? Thanks

share|improve this question
1  
No, you don’t need AC: you can always pick a single element from a non-empty set. –  Brian M. Scott Sep 19 '12 at 8:01
    
Could you please explain why. I understand that there obviously exists an element in A, but why do I not need the axiom of choice to choose such an element? –  Paul Sep 19 '12 at 8:09
1  
It follows from one of the rules of first-order logic. Informally, that rule says that from $\exists x~\varphi(x)$ one may infer $\varphi(c)$, where $c$ is a new name created specifically for the purpose of naming something that has the property $\varphi$. –  Brian M. Scott Sep 19 '12 at 8:16
    
Very interesting. Thank you for this! –  Paul Sep 19 '12 at 8:21
1  
@BrianM.Scott Mmmm, a bit misleading, methinks. Take an ND system. Given $\exists x\varphi(x)$, you make the (temporary) new assumption $\varphi(c)$, deduce something $\psi$ that doesn't depend on $c$, and discharge the assumption and conclude $\psi$ by $\exists$-elimination. But at no point do you infer something like $\varphi(c)$. –  Peter Smith Sep 19 '12 at 8:24
show 1 more comment

1 Answer 1

The axiom of choice is needed when you need to make infinitely many arbitrary choices at once.

Recall that a set $A$ is not empty if and only if $\exists x. x\in A$, so assuming that $A$ is not empty we can provably pick such $x$.

share|improve this answer
1  
You might want to qualify that first sentence: it’s when you make infinitely many arbitrary choices. It’s the old socks versus shoes business: given infinitely many pairs of shoes, you don’t need the axiom of choice to form the set of left shoes. –  Brian M. Scott Sep 19 '12 at 8:13
    
@Brian: Yes, although it was boots in the original version methinks. –  Asaf Karagila Sep 19 '12 at 8:16
    
You’re probably right, since as I recall the original was British. –  Brian M. Scott Sep 19 '12 at 8:17
1  
It was probably Bertrand Russell as the originator of shoes/socks analogy? –  Sniper Clown Sep 19 '12 at 8:33
    
@Mahmud: Yes, that was Russell. –  Asaf Karagila Sep 19 '12 at 8:45
add comment

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.