1
$\begingroup$

The title isn't completely clear, but let me try to explain. The notation $|A| \leq |B|$, even for infinite sets, implies that there exists an injection $A \hookrightarrow B$. If I write $|A| < |B|$ thereafter, it means there is no surjection $A \to B$, so we can say, informally, that $B$ is "larger" in some sense than $A$.

Suppose I've established, via a chain of maps, $$ |A| = |B| < |C| = |D| \leq |E| = |F|. $$ I want to then say that $|A| < |F|$, which I would be able to do using the usual rules of arithmetic. Surely I can inject $A$ into $F$: just compose injections. But how do I know there is no surjection from $A$ to $F$? There must a way to find a contradiction, in particular, one of these equalities I know about would disappear if I assumed the existence of a surjection, in which case $|A| = |F|$, but I can't find it after multiple attempts.

One possibility is contradiction. Assume instead $|A| \geq |F|$, i.e., there exists an injection $F \hookrightarrow A$. Then $$ |F| \leq |A| = |B| < |C| = |D| \leq |E| = |F|, $$ but this doesn't really tell me anything, because I can't read off $|F| < |F|$ without using the same "transitive" property I'm trying to prove above.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

Because there is an injection $C\to F,$ and $C$ isn’t empty, there is a surjection $F\to C.$

So if there is a surjection $A\to F,$ there is a surjection $A\to C.$

This requires:

Lemma: If $f:X\to Y$ is an injection, and $X$ is non-empty, there is a surjection $g:Y\to X.$
Proof: Let $x_0\in X$ be any element. Define: $$g(y)=\begin{cases}f^{-1}(y) &\text{when }y\in f(X)\\ x_0&\text{otherwise} \end{cases}$$

$\endgroup$
2
  • $\begingroup$ The lemma makes sense to me, but I don't think I'm connecting the dots. Is this what yields a contradiction? $\endgroup$ May 26, 2021 at 14:33
  • $\begingroup$ Yes. $|A|=|B|$ means that, since there is no surjection $B\to C,$ there is no surjection $A\to C.$ $\endgroup$ May 26, 2021 at 15:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .