In: Advanced Math
8. The cardinality of S is less than or equal to the cardinality of T, i.e. |S| ≤ |T| iff there is a one to one function from S to T. In this problem you’ll show that the ≤ relation is transitive i.e. |S| ≤ |T| and |T| ≤ |U| implies |S| ≤ |U|.
a. Show that the composition of two one-to-one functions is one-to-one. This will be a very simple direct proof using the definition of one-to-one (twice). Assume that f is one-to-one from S to T and g is one-to-one from T to U. Then show that f ○ g must be one-to-one from S to U.
b. For sets S, T, U prove that |S| ≤ |T| and |T| ≤ |U| implies |S| ≤ |U|. Hint: Apply the definitions of |S| ≤ |T| and |T| ≤ |U| then use part a to construct a one-to-one function from S to U.
c. Is it possible for ? ⊊ ? and |S| ≤ |T| to be true at the same time? That would mean T is proper subset of S but the cardinality of S is less than or equal to the cardinality of T. If it is possible, give an example. If it isn’t possible, prove that it isn’t possible