Proof:≤ is transitive

If and then . In other words, the relation on cardinalities is transitive.

Proof: (using definitions)

I claim is also an injection. To see this, suppose that . We want to show that [math]x_1 = x_2 [/math].

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)

I claim is also an injection. To see this, note that [math]f [/math] and [math]g [/math] 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.