8. The cardinality of S is less than or equal to the cardinalityof T, i.e. |S| ? |T| iff there is a one to one function from S toT. In this problem you’ll show that the ? relation is transitivei.e. |S| ? |T| and |T| ? |U| implies |S| ? |U|.
a. Show that the composition of two one-to-one functions isone-to-one. This will be a very simple direct proof using thedefinition of one-to-one (twice). Assume that f is one-to-one fromS to T and g is one-to-one from T to U. Then show that f ? g mustbe 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 sametime? That would mean T is proper subset of S but the cardinalityof S is less than or equal to the cardinality of T. If it ispossible, give an example. If it isn’t possible, prove that itisn’t possible
