2.1. Countable Infinity
Example: Countable Chairs
Suppose you are standing in an empty classroom, with a lot of students waiting to get in. How can you know whether there are enough chairs for everyone? Use the mathematical definition of cardinality to determine the answer.We can not count the students, since they are moving around too much. Therefore, we set up a function f that associates each chair with a student by simply asking each student to find a chair and sit down. If all chairs are taken, and no students are left standing, then what does this mean for our function f ?
- the domain of f is the space of all students
- the range of f is the space of all chairs
- the function f is one-to-one, because: if f(a) = f(b), then student a and student b are occupying the same chair. This can not happen unless student a and student b is the same. Hence, f is injective.
- the function f is onto, because: the range is the space of all chairs. Since all chairs are occupied, there is a student associated with each chair. Hence, f is surjective.
On the other hand, if the two sets did not contain the same number of elements, the following could happen:
- if f was one-to-one, but not onto, then there would be empty chairs. Hence, cardinality of the students is less than the cardinality of the chairs.
- if f was onto, but not one-to-one, then all chairs are taken, but some chairs hold more than one student. Hence, cardinality of the students is greater than the cardinality of the chairs.