## 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**is the space of all students*f* - the
**range of**is the space of all chairs*f* - the function
, because: if*f*is one-to-one*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
, 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 onto*f*is surjective.

*f*is a bijection between the domain and the range, and by definition of cardinality the number of students matches the number of chairs, i.e. both sets have the same cardinality.

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.