2
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Part of growing up, mathematically, is being able to verify your own proofs. $\endgroup$ – Asaf Karagila Sep 19 '18 at 7:24
  • 2
    $\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 '18 at 7:25
  • $\begingroup$ @AsafKaragila. If that is so, what is the point of the proof verification tag or even peer review? $\endgroup$ – William Elliot Sep 19 '18 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 '18 at 7:49
  • 1
    $\begingroup$ Looks ok to me. $\endgroup$ – DanielWainfleet Sep 19 '18 at 8:04

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.