# Proving $(A\le B)\vee (B\le A)$ for sets $A$ and $B$

For any pair of sets $A$ and $B$, we can define $A\le B$ iff there exists injection $f\colon A\rightarrow B$. I am trying prove that $$(A\le B)\vee (B\le A).$$

I have tried assuming $\neg (A\le B)$, then proving $B\le A$ by constructing the required injection, but I haven't been able to make any progress. Any hints, etc. would be appreciated.

EDIT

Assuming $\neg (A\le B)$, can you prove there exists a surjection $f: A\rightarrow B$? Then it would be easy, by applying AC, to construct an injection $g: B\rightarrow A$

• I don't think you're likely to get anywhere pleasant by approaching the problem from that direction. It seems much easier to use the well-ordering approach directly, or else apply Zorn or (easier, I think) Tukey-Teichmüller to get an relation and show that it gives you one of the two directions, as explained in Arthur's and my answers. Jun 16, 2013 at 15:09
• Dan, the bounty ends in five hours. Is there anything you want to say on my answer? Does it help you in any way? Jul 1, 2013 at 10:56
• @AsafKaragila Sorry, I am just back from a 2 week vacation. I see that you got half the bounty by default. Intuitively, it seemed to me that a much simpler proof was possible. I work with formal proofs. Your approach, it seemed to me, would take several thousand lines of proof in my system -- a daunting task that I think I will shelve for now. (Sigh!) But thanks anyway. Jul 15, 2013 at 14:59
• Welcome back, Dan. Yes, our intuition in 2013 is very different than the one they had in 1913. We accept the axiom of choice by default, whereas back then the axiom of choice was taken with a grain of salt (in particular because infinite objects outside the setting of the natural numbers, the real numbers, and the "very new [at the time] Borel sets" were taken with a grain of salt. Jul 15, 2013 at 15:01
• Apr 5, 2016 at 15:42

There is no way to construct a surjection without an appeal to the axiom of choice. If there was then we could have proved that between every two (non-empty) sets there exists a surjection in some direction. This already implies the axiom of choice.

So in order to carry out any construction you will have to tell us what sort of appeals to the axiom of choice you are willing to use.

• If you are willing to use Zorn's lemma then it will be easy to assume $\lnot(A\leq B)$ and show that the partial order $$\Big<\{f\subseteq B\times A\mid f\text{ is an injection}\},\subseteq\Big>$$ satisfies the condition that every chain is bounded (the increasing union of injections is an injection), and a maximal element must be an injection from $B$ into $A$.

• If you are willing to use the well-ordering theorem then it is just a matter of proving that if $\alpha$ and $\beta$ are ordinals, and $\alpha\nleq\beta$ then $\beta<\alpha$. So if $|A|=\alpha$ and $|B|=\beta$ we are done.

• If you only want to use the axiom of choice itself. Let $F_A,F_B$ be choice functions from the non-empty subsets of $A$ and $B$ respectively. Proceed by transfinite recursion to define a sequence of partial injections:

1. $f_0=\varnothing$.
2. If $f_\alpha$ was defined, let $f_{\alpha+1}=f_\alpha\cup\{\langle F_B(B\setminus\operatorname{dom}(f_\alpha)),F_A(A\setminus\operatorname{rng}(f_\alpha))\}$. Then $f_{\alpha+1}$ is an injection because $f_\alpha$ was an injection, and the only element we added to the range came from outside the range of $f_\alpha$.
3. If $f_\alpha$ was defined for all $\alpha<\delta$, for a limit ordinal $\delta$ then $f_\delta=\bigcup_{\alpha<\delta} f_\alpha$. It is not hard to see that $f_\delta$ is an injection, otherwise some $\alpha<\delta$ would have witnessed otherwise, in contradiction to the induction hypothesis.

Now we argue that the recursion has to stop because $A$ and $B$ are sets, so there is no injection from the class of ordinals into any of them; but if the recursion carries all the way through the ordinals then $\alpha\mapsto F_A(A\setminus\operatorname{rng}(f_\alpha))$ is an injection into $A$ and the obvious one with $\operatorname{dom}(f_\alpha)$ defines an injection into $B$.

So the recursion halts at some point, let $f$ be the union of all the defined $f_\alpha$. If $f$ is injective from $B$ into $A$ then we are done, otherwise its domain is a proper subset of $B$ and $f$ is surjective, or else we can continue one more step (because both $B\setminus\operatorname{dom}(f)$ and $A\setminus\operatorname{rng}(f)$ are non-empty). So either $f$ is an injection from $B$ into $A$ or $f^{-1}$ is an injection from $A$ into $B$.

This list can grow with pretty much every equivalent to the axiom of choice, some will be longer and some will be shorter. But there's no "explicit" way to construct a surjection because that would amount to proving the axiom of choice holds.

• I'm trying to prove this result by using Zorn's lemma but since in the text I'm using a function is not defined as a subset of a cartesian product but as an object which given any input $x\in X$ assigns the unique output $f(x)\in Y$ such that $P(x,f(x))$ is true (where $P(x,y)$ is a property pertaining to an object $x\in X$ and $y\in Y$ such that $\forall x\in X \exists ! y\in Y$ such that $P(x,y)$ is true) I don't understand what $<\{f\subseteq B\times A|f\ injective \}, \subseteq \}>$ means. Could you explain to me in greater detail how you've defined this poset? Thank you. Nov 8, 2016 at 23:21
• I'm not sure what your text means by this definition. Nov 9, 2016 at 3:23
• No no, this is certainly not the right partial order. For starters, you cannot prove (without using the axiom of choice in the first place) that the partial order satisfies the condition that every chain has an upper bound. What you want to consider is injective functions with domain which is a subset of $B$ and range which is a subset of $A$. Then the union of a chain of injective functions is again an injective function, and we can prove the condition for Zorn's lemma holds. Again, the key point is that the elements are not just subsets of $B$, but rather partial injections from $B$ to $A$. Nov 9, 2016 at 13:19
• @Darius: The domain and the range of the function $f$. Mar 28, 2018 at 14:50
• @Kareem: This is really too much for the comments. Please ask a new question where you can explain the context properly. Sep 1, 2020 at 22:20

This statement is equivalent to the Axiom of Choice, so you'll need to use some variant of Choice:

• Using the Well-Ordering Theorem, this just reduces to either
• showing that the statement holds for all ordinal numbers, which is pretty easy (at least using the von Neumann definition of ordinals); or
• noting that given two well-ordered sets, one is always order-isomorphic to an initial segment of the other.
• Using Zorn's Lemma, consider the partial order of all partial injections $A \to B$ ordered by extension. Show that this satisfies the hypothesis of Zorn's Lemma, and then show that any maximal element of this ordering either has domain $A$ or range $B$. (Not the easiest proof of this result, but none too difficult.)

For this to be true for general sets, you need the trichotomy principle, which is a consequence of the axiom of choice.

If $A,B$ are well-ordered, or countable, or finite, then you don't need AC and can prove directly. Specifically, you map the smallest element of $A$ to the smallest element of $B$, and so on.

One way is to use the Tukey-Teichmüller lemma:

Let $\mathscr F$ be the set of all partial injections (i.e., one-to-one relations) from $A$ to $B$.

$\mathscr F$ is of finite character:

Obviously, any finite subset of an element of $\mathscr F$ is an element of $\mathscr F$.

Let $f \subseteq A \times B$. If every finite subset of $f$ is one-to-one, then in particular each two-element subset of $f$ is one-to-one, so $f$ is one-to-one, and thus $f \in \mathscr F$.

So by the Tukey-Teichmüller lemma, $\mathcal F$ has a maximal element $g$. It should be easy to see why $g$ must be either left-total or right-total, and so either $g$ or $g^{-1}$ is an injection.

Until now I've only come up with a Zorn's Lemma way, which was inspired by the first bullet point of Asaf Karagila's answer:

Proof.

Write $$X:= \{f \subseteq {B \times A}:\text{f is an injection} \}$$, then we have a partially ordered set $$(X,\subseteq)$$. For every totally ordered subset $$Y$$ of $$X$$, $$\cup Y \subseteq {B \times A}$$ is well-defined as every element in $$Y$$ is a subset of $$B \times A$$.

Obviously, $$\cup Y$$ is an upper bound for $$Y$$. In order to use Zorn's Lemma, we need to prove that $$\cup Y \in X$$. For any $$(b_1, a_1), (b_2, a_2) \in \cup Y$$, there exist $$f_1, f_2 \in Y$$ such that $$(b_1, a_1) \in f_1, (b_2, a_2) \in f_2$$.

Since $$Y$$ is totally ordered by set inclusion, we have $$f_1 \subseteq f_2 \text{ or } f_2 \subseteq f_1$$. We assume $$f_1 \subseteq f_2$$ without loss of generality. Hence we have $$(b_1, a_1) \in f_2$$. Since $$f_2 \subseteq X$$, we have $$b_1 = b_2 \Rightarrow a_1 = a_2$$ from well-definedness, and $$b_1 \neq b_2 \Rightarrow a_1 \neq a_2$$ from injectivity of $$f_2$$. This implies that $$\cup Y$$ is an injection.

Therefore, we have $$\cup Y \in X$$. By Zorn's Lemma, $$X$$ has at least one maximal element, call it $$g$$. Let $$B' = dom(g)$$.

We know that $$g: B'\to A$$ where $$B'\subseteq B$$ is an injection. Now we prove that $$B' = B$$. Suppose for sake of contradiction that $$B' \neq B$$, thus $$B \backslash B'$$ is non-empty. So there exists $$b \in B \backslash B'$$. There must also exist $$a \in A \backslash g(B')$$ (otherwise $$A = g(B')$$, so $$f$$ is also surjective. Its inverse $$f^{-1} : A \to B'$$ is hence an injection $$A \to B$$, a contradiction). Thus, $$g \cap \{(b,a)\}$$ is an injection in $$X$$, but $$g$$ is a proper subset of $$g \cap \{(b,a)\}$$, which contradicts that $$g$$ is the maximal element in $$(X, \subseteq)$$. Thus, $$B^\prime=B$$, there exists an injection from $$B$$ to $$A$$. Hence, $$B$$ has lesser or equal cardinality to $$A$$, as desired.

• Note that your proof is the first bullet point in my answer. Aug 17, 2017 at 18:26
• @AsafKaragila Done Aug 18, 2017 at 4:32

This statement (usually known as Hartogs' Trichotomy Theorem) is equivalent to the axiom of choice in ZF.

If you want to prove it from Zorn's lemma, check for my answer to this question, in which I demonstrate that Zorn's lemma implies Zermelo's well-ordering theorem.

If you want to prove it directly, using the original statement of the axiom of choice, we first need to prove the following

Theorem: The axiom of choice implies Zermelo's well-ordering theorem

Demonstration: Let $$A$$ be a set, and let $$f$$ be a choice function for $$\mathcal{P}(A)$$, that is, $$f$$ is a function whose domain includes the set $$\mathcal{P}(A)\setminus\{\varnothing\}$$ , and is such that for each $$B\subseteq A$$, if $$B\not=\varnothing$$, then $$f(B)\in B$$.

Let $$z$$ be a set that does not belong to $$A$$ (that exists as a consequence, for example, of Cantor's theorem).

By transfinite induction over the ordinals we define the following On-sequence $$(a_\alpha)_{\alpha\in\text{On}}$$: for each ordinal $$\alpha$$:

$$a_\alpha=\begin{cases} \displaystyle f(A\setminus\{a_\beta|\;\beta<\alpha\})\qquad\text{if }A\setminus\{a_\beta|\beta<\alpha\}\text{ is not empty} \\ \displaystyle z\qquad\qquad\qquad\qquad\quad\,\,\,\text{if }A\setminus\{a_\beta|\;\beta<\alpha\}=\varnothing \end{cases}$$

Let $$\alpha$$ be an ordinal such that $$A\setminus\{a_\beta|\;\beta<\alpha\}$$ is not empty, and let $$\beta_1,\beta_2<\alpha$$ such that $$\beta_1<\beta_2$$. Then $$a_{\beta_1}$$ and $$a_{\beta_2}$$ are elements of $$A$$, and are different from each other, because $$a_{\beta_2}=f(A\setminus\{a_\beta|\;\beta<\beta_2\})$$, which is a element of $$A\setminus\{a_\beta|\;\beta<\beta_2\}$$, and $$a_{\beta_1}$$ does not belong to this set. Therefore, for each ordinal $$\alpha$$ such that $$A\setminus\{a_\beta|\;\beta<\alpha\}\not=\varnothing$$, the $$\alpha$$-sequence $$\langle a_\beta|\;\beta<\alpha\rangle$$ is an injective application from $$\alpha$$ to $$A$$.

But this cannot occur for every ordinal $$\alpha$$: suppose on the contrary that this is true for every ordinal $$\alpha$$. Then the On-sequence $$(a_\alpha)_{\alpha\in\text{On}}$$ is an injective class-function from the proper class On in the set $$A$$. By the axiom-schema of subsets, the image $$\{a_\alpha|\;\alpha\in\text{On}\}$$ is a set $$-$$ which we shall denote by $$B$$ $$-$$ because it is included in the set $$A$$. And, since $$(a_\alpha)_{\alpha\in\text{On}}$$ is injective (since $$\beta<\alpha$$ implies $$a_\beta\not=a_\alpha$$), the inverse class-relation $$((a_\alpha)_{\alpha\in\text{On}})^{-1}:B\twoheadrightarrow\text{On}$$ is a class-function from the set $$B$$ onto the propper class On. This contradicts the axiom-schema of replacement, which ensures that the image of a set via a class-function is always a set, and it cannot be a proper class like On.

Therefore, there are ordinals $$\alpha$$ for which $$A\setminus\{a_\beta|\;\beta<\alpha\}=\varnothing$$. Let $$\alpha_0$$ be the least ordinal such that $$A\setminus\{a_\beta|\;\beta<\alpha_0\}=\varnothing$$. Then we have

$$A=\{a_\beta|\;\beta<\alpha_0\}$$

And $$\langle a_\beta|\beta<\alpha_0\rangle$$ is an injective function from $$\alpha_0$$ onto $$A$$, that is, it is a bijective function from $$\alpha_0$$ onto $$A$$. But $$\alpha_0$$ has a natural well-order, $$\in_{\alpha_0}$$, and this well-order of $$\alpha_0$$ is transferred by the bijective function $$\langle a_\beta|\;\beta<\alpha_0\rangle$$ to a well- order of $$A$$, that is, the relation $$<_R$$ defined by:

$$\text{For all }\,\beta,\,\gamma<\alpha_0,\qquad a_\beta

And therefore, $$A$$ has a well-order; namely, $$<_R$$.

After proving that Zorn's lemma $$-$$ or the axiom of choice $$-$$ implies Zermelo's well-ordering theorem, then we finally can prove

Hartogs' trichotomy theorem: For any sets $$A$$ and $$B$$, $$A\preccurlyeq B$$ or $$B\preccurlyeq A$$

Demonstration: from Zermelo's well-ordering theorem, if $$A$$ and $$B$$ are sets, let $$<_R$$ and $$\prec_S$$ be well-orderings of $$A$$ and $$B$$ respectively. Then there exist unique ordinals $$\alpha$$ and $$\beta$$ such that $$\langle A,<_R\rangle\cong\langle\alpha,\in_\alpha\rangle$$ and $$\langle B,\prec_S\rangle\cong\langle\beta,\in_\beta\rangle$$. And then, since $$A\approx\alpha$$ and $$B\approx\beta$$, we then have that if $$\alpha\leq\beta$$, $$A\preccurlyeq B$$, and if $$\beta\leq\alpha$$, then $$B\preccurlyeq A$$

On the other hand, if you ever want to prove the other implication, that Hartogs' trichotomy theorem implies the axiom of choice, you may want to follow this argument:

Theorem: Hartogs' trichotomy theorem implies Zermelo's well-ordering theorem

Demonstration Let $$A$$ be a set. By Hartogs' theorem (c.f. page 50, theorem 4.33), there exists an ordinal $$\alpha$$ that is not shrinkable in $$A$$. By Hartogs' trichotomy principle, if $$\alpha\not\preccurlyeq A$$, then $$A\preccurlyeq\alpha$$, and $$A$$ is shrinkable in $$\alpha$$, therefore $$A$$ has a well-ordering, the one that is transferred from the well-order $$\in_\alpha$$ os $$\alpha$$ via an injective function from $$A$$ to $$\alpha$$.

Theorem: Zermelo's well-ordering principle implies the axiom of choice

Demonstration: Let $$A$$ be a set. By Zermelo's well-ordering theorem, there exists a relation $$<_R\subseteq\,\big(\bigcup A\big)\times\big(\bigcup A\big)$$ that well orders $$\bigcup A$$. Then the function $$f$$ of domain $$A\setminus\{\varnothing\}$$ defined by: for each $$a\in A\setminus\{\varnothing\}$$

$$f(a)=\text{the minimal element of }a\text{ in the sense of }<_R$$

Is a choice function for $$A$$, if $$\varnothing\not\in A$$. If $$\varnothing\in A$$, simply take $$f\cup\{\langle \varnothing ,\varnothing\rangle\}$$

Combining the last two results, we can easily conclude that the Hartogs' trichotomy theorem implies the axiom of choice