Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $A_i$ be a family of sets such that each $A_i$ is well-ordered. Let $\varphi(x,S,W)$ be the formula $$ \forall z ( (z,x) \in W \rightarrow z \notin S)$$ where $W$ is the well-order on $S$. Then $\varphi(x,S,W)$ is true if and only if $x$ is the $W$-minimal element of $S$.

Let's use Separation to obtain the family $A_i' = \{ x : \varphi(x,A_i,W_i) \} = \{a_i\}$ consisting of one element sets. Next let's make ordered pairs $(i,a_i)$ from these using Pairing. Finally, let's apply Union to pack these pairs into one set $F = \{(i,a_i)\}_{i\in I}$. So far we have not invoked the axiom of choice anywhere. But $F$ seems to be a function $F: I \to \{A_i\}_i$, choosing one element from each $A_i$.

Where is the flaw in my construction? As I understand it's only possible to construct a choice function for $A_i$ if not only each $A_i$ is well-ordered but $\bigcup_i A_i$ is well-ordered, too.

Thanks for your help.

share|cite|improve this question
up vote 3 down vote accepted

Your flaw is by the fact that you choose $W_i$ for each $A_i$.

It is possible that you cannot make such choice. For example if $\{A_i \mid i\in\omega\}$ is a set of pairs without a choice function, then you cannot choose $W_i$ for all $i$.

However if you have a well-order of $\bigcup A_i$ and you just take $W_i$ as the restriction of this well-order to $A_i$, then you did not use the axiom of choice anywhere. Alternatively if $(A_i,W_i)$ are given to us then you have essentially a uniform way of choosing a well-ordering $W_i$ (simply choose the one given to you).

share|cite|improve this answer
Or you assume that the $W_i$ are part of the given data. Then there is no AC needed to specify a choice function. That's ok, this is a very special case after all. – Hagen von Eitzen Nov 27 '12 at 23:00
@Hagen: Yes, thanks. I'll add that. – Asaf Karagila Nov 27 '12 at 23:16
Nice, thank you for this clear answer! – Rudy the Reindeer Nov 28 '12 at 9:19

Your Answer


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.