Proving proper inequality of cardinality of sets is transitive

Question

I need to prove the following:

If $A,B,C$ are sets (finite or infinite), such that $|A|< |B|$, and $|B| < |C|$ then $|A| < |C|$.

My proof:

Let $f:A \to B$ be in injective, since $|A| \le |B|$, and $|A| \ne |B|$.

Let $g: B \to C$ also an injective, for the same reasoning.

Additionally we know there is no surjective from $A$ to $B$, and from $B$ to $C$.

We define $h:A \to C, h=g \circ f$ an injective as a composition of two injectives. Thus $|A| \le |C|$. Now we need to show that $|A| \ne |C| $. Suppose there exists a function $k: A \to C$ such that $k$ is surjective. That means, for every $c \in C$ there is an element $a \in A$ such that $k(a) = c$. We can conclude that since $\mathrm{Dom} (k) \subseteq A$, $|\mathrm{Dom}(k)| \le |A|$, and $|\mathrm{Dom}(k)| \ge |C|$.

Where Dom(k) is the domain of $k$.

$\star$ Now we get $|A| \ge |C| >|B| > |A|$ and that is a contradiction of $|A| = |A|$. $\square$

My concern is with the last part which I put a $\star$ next to. I'm not sure I can write out this chain of inequalities. Am I allowed to use this reasoning? I have tried another way of trying to go between the sets, knowing there is no surjective function between any consecutive sets, but I was not sure how to proceed.

Any feedback, help, and ideas, would be greatly appreciated.

Answer 1

If $k:A\to C$ then by all standard accounts, "$\mathrm{Dom}(k)$" is just $A$.

You're right to be concerned about $\star$ since the chain of inequalities is valid but the conclusion "... so $|A|>|A|$ which is a contradiction" is already assuming transitivity; from $|C|>|B|>|A|$ you are assuming $|C|>|A|$ which, though true, is the very thing you're trying to prove.

Instead, consider that $B$ cannot be empty so the existence of an injection $B\to C$ entails the existence of a surjection $C\to B$. Then, the existence of a surjection $A\to C$ implies there is a composite surjection $A\to C\to B$ contradicting the assumption $|A|<|B|$. All assuming axiom of choice.

Answer 2

It's incorrect to say that you know there is no surjective $A\twoheadrightarrow B$ or $B\twoheadrightarrow C$. This is something you need the axiom of choice for. The theorem you're trying to prove holds in $\mathbf{ZF}$. What you're given is

• There's an injective $f:A\to B$
• There's an injective $g:B\to C$
• There's no bijection $A\to B$
• There's no bijection $B\to C$

The composition $g\circ f$ gives an injective $A\to C$ proving that $|A|\le |C|$. You need to show there is no bijection $A\to C$. Assume by contradiction $h:A\to C$ is a bijection. Then $f\circ h^{-1}:C\to B$ is injective. So we have injective maps $g:B\to C$ and $f\circ h^{-1}:C\to B$. By the Schröder-Bernstein theorem $|B|=|C|$ - a contradiction. The Schröder-Bernstein theorem is provable in $\mathbf{ZF}$ without the axiom of choice.