4
$\begingroup$

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

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

where

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

3 Answers 3

0

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.

3

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.

  • 0
    @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... :-)2012-12-01
3

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