Definition: $|A|\le |B| \iff$ there exists an injection from $A$ to $B$.

Theorem: For any two sets $A$ and $B$, $|A|\le |B|$ or $|B|\le |A|$.

My attempt:

Assume $|B| \not\le |A|$, I will prove $|A|\le |B|$.

Let $X=\{f:A'\to B \mid A'\subseteq A \text{ and } f\text{ is injective}\}$. We define a partial order $<$ on $X$ by $$f_1<f_2 \iff f_1\subseteq f_2$$

Since $f:\emptyset\to B$ is injective, $f\in X$. Thus $X\neq\emptyset$. For any chain $Y$ from $X$, let $f^\ast=\bigcup Y$.

  1. $f^\ast$ is a mapping

For $(a,b_1),(a,b_2)\in f^\ast$, there are $f_1,f_2 \in Y$ such that $(a,b_1)\in f_1$ and $(a,b_2)\in f_2$. Since $Y$ is a chain, we can safely assume $f_1 < f_2$. It follows that $f_1 \subseteq f_2$. Thus $(a,b_1),(a,b_2)\in f_2$ and consequently $b_1=b_2$ by the fact that $f_2$ is a mapping.

  1. $f^\ast$ is injective

Assume $(a_1,b),(a_2,b)\in f^\ast$. Then there exists $f_1,f_2 \in Y$ such that $(a_1,b) \in f_1$ and $(a_2,b) \in f_2$. Since $Y$ is a chain, we can safely assume $f_1 < f_2$. It follows that $f_1 \subseteq f_2$. Thus $f_1(a_1)=f_2(a_1)$ and consequently $f_2(a_2)=b=f_1(a_1)=f_2(a_1)$. Hence $f_2(a_2)=f_2(a_1)$ and consequently $a_2=a_1$ by the fact that $f_2$ is injective. It follows that $f^\ast$ is injective.

To sum up, $f^\ast$ is injective and thus $f^\ast \in X$. Furthermore, $f^\ast$ is an upper bound of chain $Y$. Thus $X$ satisfies the requirement of Zorn's Lemma and hence has a maximal element $\bar{f}:\bar{A} \to B$. Let $\bar{B}=\operatorname{ran}\bar{f}$. Then $\bar{f}:\bar{A} \to \bar{B}$ is bijective.

I claim that $\bar{B}\subsetneq B$. If not, $\bar{B} = B$. Then $\bar{f}:\bar{A} \to B$ is bijective and thus $\bar{f}^{-1}:B \to \bar{A} \subseteq A$ is bijective. This contradicts our very first assumption that $|B| \not\le |A|$. Hence $\bar{B}\subsetneq B$ and thus $\exists b'\in B\setminus \bar{B}$. It follows that $b'\notin \bar{B}=\operatorname{ran}\bar{f}$.

I claim that $\bar{A}=A$. If not, $A\setminus \bar{A} \neq \emptyset$. Thus there exits $a'\in A\setminus \bar{A}$. It follows that $a'\notin \bar{A} = \operatorname{dom}\bar{f}$. We define $F:\bar{A}\cup\{a'\} \to \bar{B}\cup\{b'\}$ by $F(a)=\bar{f}(a)$ for all $a\in\bar{A}$ and $F(a')=b'$. It's clear that $F$ is a bijection from $\bar{A}\cup\{a'\}$ to $\bar{B}\cup\{b'\}$ and that $\bar{f}\subsetneq F$. Then $F$ is an injection from $\bar{A}\cup\{a'\}$ to $B$ and $\bar{f}\subsetneq F$. This contradicts the maximality of $\bar{f}$. Hence $\bar{A}=A$.

To sum up, $\bar{f}:A \to B$ is injective and thus $|A|\le |B|$.

Does this proof look fine or contain gaps? Do you have suggestions? Many thanks for your dedicated help!

  • 1
    $\begingroup$ Part of growing up, mathematically, is being able to verify your own proofs. $\endgroup$
    – Asaf Karagila
    Sep 19, 2018 at 7:24
  • 3
    $\begingroup$ @AsafKaragila And part of learning to verify your own proofs is to have your proofs dissected by others in order to know what to even look for. $\endgroup$
    – Arthur
    Sep 19, 2018 at 7:25
  • $\begingroup$ @AsafKaragila. If that is so, what is the point of the proof verification tag or even peer review? $\endgroup$ Sep 19, 2018 at 7:47
  • 1
    $\begingroup$ @William: This is not a website for peer review. I don't post my papers from arXiv here to get them checked. The point of the tag, well, that's a different story. What was the point of the [homework] tag back when it existed? Your logic is circular, just because something exists in the system, doesn't mean it's an actual good fit. Proof verification poses "the next" problem to the site, after homework milling. But these are all discussions for Mathematics Meta. $\endgroup$
    – Asaf Karagila
    Sep 19, 2018 at 7:49
  • 1
    $\begingroup$ Looks ok to me. $\endgroup$ Sep 19, 2018 at 8:04


You must log in to answer this question.

Browse other questions tagged .