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

I'm doing the following exercise from Just/Weese:

Show in ZF that (WO) implies (IC) and that (IC) implies (SC).


(WO) Every set can be well-ordered.

(IC) For any two sets $X,Y$ either there is an injection $X \hookrightarrow Y$ or $Y \hookrightarrow X$.

(SC) For any two sets $X,Y$ either there is an surjection $X \twoheadrightarrow Y$ or $Y \twoheadrightarrow X$.

(WO) $\rightarrow$ (IC): Let $X,Y$ be two sets. Then by (WO) they can be well-ordered. Therefore each is in bijection with an ordinal $\alpha$ (and $\beta$, respectively):

Claim: Every well-ordered set is isomorphic to an ordinal.

Proof: Let $\langle, X,W \rangle$ be a well-ordered set. Let $\alpha$ be an ordinal with $|\alpha| \ge |X|$. Define an injective map $f: X \hookrightarrow \alpha$ as follows:

(i) Let $x_0$ be the $W$-minimal element. Then $x_0 \mapsto \varnothing$.

(ii) Assume $f$ has been defined for $x \in I_W (x')$. Define $x' \mapsto \sup^+ f(I_W (x'))$.

Let $\tilde{f} = f: X \to \mathrm{im}f$. Then $\tilde{f}$ is a bijection and $\mathrm{im}f$ is an initial segment of an ordinal hence also an ordinal.$\Box$

Either $\alpha \in \beta$ or $\beta \in \alpha$. Hence either $X \hookrightarrow Y$ or $Y \hookrightarrow X$.

(IC) $\rightarrow$ (SC): Let $X,Y$ be sets. Then either $X \hookrightarrow Y$ or $Y \hookrightarrow X$. Given $X \hookrightarrow Y$ it is easy to construct a surjection $Y \twoheadrightarrow X$, similarly for $Y \hookrightarrow X$.

Can you tell me if these proofs are correct? Thanks.

I also wanted to prove (IC) $\rightarrow$ (WO), but I'm stuck. I thought of something like if $X$ is a set and $\alpha$ is an ordinal then either $X \hookrightarrow \alpha$ or $\alpha \hookrightarrow X$ but the latter case seems to be a dead end.

share|cite|improve this question

HINT for (IC) $\to$ (WO): You’re on the right track. Let $X$ be any set, and let $\kappa$ be the Hartogs number of $X$.

share|cite|improve this answer

Hint: Let $A$ be a set, and let $\aleph(A)$ the least ordinal $\alpha$ such that there is no injection from $\alpha$ into $A$. (You need to show that such ordinal indeed exists!)

Since there is an injection between every two sets, there is an injection between $A$ and $\aleph(A)$. It cannot be from $\aleph(A)$ so it is from $A$. Now you can show that $A$ can be well-ordered.

The idea for surjection is the same, replace $\aleph(A)$ by $\aleph^\ast(A)$ which is the least ordinal $\alpha$ such that $A$ cannot be mapped onto $\alpha$.

The proofs you gave are correct.

share|cite|improve this answer
@Matt: You're welcome. I thought that you asked about the last part originally because it would be enough to close the three equivalences directly instead of using a fourth implication... :-) – Asaf Karagila Dec 1 '12 at 15:21
up vote 0 down vote accepted

The two answers are a draw so I'm merging the two into one, to avoid having to choose one of them:

From Asaf's answer: My two proofs are correct.

From Brian's answer: Assume (IC) and let $X$ be any set. Let $\alpha$ be the Hartogs number of $X$ that is, the smallest ordinal such that there is no injection $\alpha \hookrightarrow X$. By (IC) there is an injection $X \hookrightarrow \alpha$, hence $X$ is well-ordered.

share|cite|improve this answer

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.