I am trying to show that the axiom of choice implies the well ordering principle, but I don't know anything about ordinals or transfinite recursion... I found a proof in a set theory for dummies book that avoids both of these things but is much longer than any proof I've seen. It goes a little like this

Let $X$ be a nonempty set. Let P(X) be the power set of $X$.\ Let $f$ be a choice function on P(X), that is $$f: P(X) \to X \text{ with } f(A) \in A, \text{ for every } A \subset X$$ Let $A$ and $B$ be normal subsets of $X$. Since $A$ and $B$ are normal, they are well ordered so there exists a similarity mapping $\alpha : A \to B$. Set $$A' = \{x \in A | \alpha(x) \neq x \}$$ If $A' = \emptyset$ then $A = B$ or $A$ is an initial segment of $B$. Suppose $A' \neq \emptyset$ and let $a_{0}$ be the minimal element in $A'$ (this exist since $A'$ well ordered since it is a subset of $A$ well ordered), then $s_{A}(a_{0}) = s_{B}(\alpha(a_{0}))$. But $A$ and $B$ are normal so $$a_{0} = f(X-s_{A}(a_{0})) = f(X-s_{B}(\alpha(a_{0}))) = \alpha(a_{0})$$ This contradicts $a_{0} \in A'$, therefore $A = B$ or $A$ is an initial segment of $B$ (so a subset of b). $a \leq b$ as elements of $A$ \textit{iff} $a \leq b$ as elements of $B$. (expand .. talk about $\alpha(a) = a$).\ Let $Y$ be the set of all elements in $X$ that belong to a normal subset of $X$. define $a \leq b$ in $Y$ is $a \leq b$ in $A$. Show $Y$ is well ordered i.e. take an arbitrary subset and show it has a minimal element. Let $Z$ be a nonempty subset of $Y$, then there exist $a \in Z$ such that $a$ belongs to a normal subset of $X$, $A$. Hence the intersection is nonempty and so contains a least element. this least element is the first element of $Z$ prove... Therefore $Y$ is indeed well ordered.\ Now show $Y$ is normal\ Show $Y$ = $X$ and thus $X$ is well ordered.\ Suppose not, suppose $X - Y \neq \emptyset$ and let $a = f(X - Y)$. Set $Y' = Y \cup \{a\}$. Then $$f(X - s_{Y}(a)) = f(X - Y) = a$$ and so $Y'$ is normal, thus $a \in Y$. But contradicts $f$ a choice function as $f(X - Y) = a \in X - Y$. Hence $Y = X$.

Does anyone think that this proof would lose me marks if I include this version in my essay rather than the original version?

  • $\begingroup$ Please give the source (author, title, publisher, ISBN) of the quoted matter in your post. $\endgroup$ – bof Jan 4 '17 at 18:21
  • 1
    $\begingroup$ I suppose the book you copied that proof from included a definition of "normal" set? $\endgroup$ – bof Jan 4 '17 at 18:22
  • $\begingroup$ Schaum's outlines, set theory, Seymour lipschutz.... yes it does include def of normal set $\endgroup$ – B. Drennan Jan 4 '17 at 18:30
  • 2
    $\begingroup$ please provide the definition of "normal set" and "similarly mapping" this text uses. $\endgroup$ – Henno Brandsma Jan 5 '17 at 4:58
  • $\begingroup$ BTW, have you done Zorn's lemma at this point? The usual proofs go : AC implies Zorn, Zorn implies WO (use a maximal element in the set of partial well-orders) $\endgroup$ – Henno Brandsma Jan 5 '17 at 5:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.