We've seen the following two definitions for comparing set cardinalities using **bijections** and **one-to-one functions**:

- Two sets A and B have the same cardinality (|A|=|B|) if and only if there is a bijection from A to B
- |A| ≤ |B| if and only if there is a one-to-one function from A to B.

Do you think there is also a way to compare cardinalities of two sets using **onto functions**? Why or why not? (once you've thought about it, a handwavy justification is fine)

Hint: Given a one-to-one function f:A→B, could we construct an onto function g:B→A? How about the other way around?

Hint if you want to formally construct the one-to-one function: Recall that when you have a non-empty set S, you can choose a "representative" element from it (for example we've frequently said things like "let x be an element of S"). You will need to do that here for arbitrarily many sets at once, so you may find it useful to assume that there is a "choice function"*h* which does this for us: *h* takes as input any set and gives as output some element of that set. (The "Axiom of Choice" says that such choice functions do indeed exist.)

Hint if you want to formally construct the one-to-one function: Recall that when you have a non-empty set S, you can choose a "representative" element from it (for example we've frequently said things like "let x be an element of S"). You will need to do that here for arbitrarily many sets at once, so you may find it useful to assume that there is a "choice function"