Countability additional tutorial problem
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? Given an onto g, could we construct a one-to-one f?
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.)