# Proof:≤ is transitive

If and then . In other words, the relation on cardinalities is transitive.
Proof: (using definitions)
Suppose and . Then by definition, there exists injections and .

I claim is also an injection. To see this, suppose that . We want to show that .

Since is injective, we have . Since is also injective, we have , as desired.

We can use inverses to give an alternate proof:

Proof: (using inverses)
Suppose and . Then by definition, there exists injections and .

I claim is also an injection. To see this, note that and have left inverses and .

Now, is a left inverse of , because for any ,

as required.

Since has a left inverse, it is injective, so by definition, we have as required.