Solutions to Problem Set 27

Math 310-01/02

11-27-2017

1. Suppose that X and Y are sets, $|X| = 6$ and $|Y| = 8$ .

(a) What is $|X \times Y|$ ?

(b) What is $|\powerset(X)|$ ?

(c) What is the largest that $|X
   \cup Y|$ can be? What is the smallest that $|X \cup Y|$ can be?

(a)

$$|X \times Y| = |X| \cdot |Y| = 6 \cdot 8 = 48.\quad\halmos$$

(b)

$$|\powerset(X)| = 2^{|X|} = 2^6 = 64.\quad\halmos$$

(c) If X and Y are disjoint, then $|X \cup Y| = 6 + 8 = 14$ , and this is the largest that $|X
   \cup Y|$ can be.

If $X \subset Y$ , then $X \cup Y = Y$ , and $|X \cup Y| = 8$ . This is the smallest that $|X \cup Y|$ can be.


2. Prove that the following sets of integers have the same cardinality by constructing a bijection $f: X \to Y$ .

$$X = \{0, 2, 4, \ldots 2 m, \ldots\} \quad\hbox{and}\quad Y = \{1, 3, 5, 7, \ldots 2 n + 1, \ldots\}.$$ Define $f: X \to Y$ by

$$f(x) = x + 1.$$

Note that if $x = 2 n$ is even, then $f(x) = 2 n + 1$ is odd. Further, if $x \ge 0$ , then $f(x) = x + 1 \ge 1$ . This shows f maps X into Y.

Define $f^{-1}: Y \to X$ by

$$f^{-1}(x) = x - 1.$$

Note that if $x = 2 n + 1$ is odd, then $f^{-1}(x) = 2 n + 1 - 1 = 2 n$ is even. Further, if $x \ge 1$ , then $f^{-1}(x) = x - 1 \ge 0$ . This shows $f^{-1}$ maps Y into X.

Finally,

$$f[f^{-1}(x)] = f(x - 1) = (x - 1) + 1 = x.$$

$$f^{-1}[f(x)] = f^{-1}(x + 1) = (x + 1) - 1 = x.$$

This shows that f and $f^{-1}$ are inverses, so f is bijective and X and Y have the same cardinality.


3. Prove that $[5, 9]$ and $[-4, 4]$ have the same cardinality by constructing a bijection $f: [5, 9] \to [-4, 4]$ .

Show that f is bijective by constructing the inverse function $f^{-1}$ . (You must prove that f and $f^{-1}$ are inverses.)

Define $f: [5, 9] \to [-4, 4]$ by

$$f(x) = 2 x - 14.$$

If $x \in [5, 9]$ , then

$$\eqalign{ 5 \le & x \le 9 \cr 10 \le & 2 x \le 18 \cr -4 \le & 2 x - 14 \le 4 \cr -4 \le & f(x) \le 4 \cr}$$

Hence, f maps $[5, 9]$ into $[-4, 4]$ .

Define $f^{-1}: [-4, 4] \to [5,
   9]$ by

$$f^{-1}(x) = \dfrac{1}{2} x + 7.$$

If $x \in [-4, 4]$ , then

$$\eqalign{ -4 \le & x \le 4 \cr \noalign{\vskip2pt} -2 \le & \dfrac{1}{2} x \le 2 \cr \noalign{\vskip2pt} 5 \le & \dfrac{1}{2} x + 7 \le 9 \cr \noalign{\vskip2pt} 5 \le & f^{-1}(x) \le 9 \cr}$$

Hence, $f^{-1}$ maps $[-4, 4]$ into $[5, 9]$ .

Finally,

$$f[f^{-1}(x)] = f\left(\dfrac{1}{2} x + 7\right) = 2 \cdot \left(\dfrac{1}{2} x + 7\right) - 14 = x + 14 - 14 = x.$$

$$f^{-1}[f(x)] = f^{-1}(2 x - 14) = \dfrac{1}{2} (2 x - 14) + 7 = x - 7 + 7 = x.$$

Hence, f and $f^{-1}$ are inverses. Therefore, f is bijective, and $[5, 9]$ and $[-4, 4]$ have the same cardinality.


Without work, all life goes rotten. But when work is soulless, life stifles and dies. - Albert Camus


Contact information

Bruce Ikenaga's Home Page

Copyright 2017 by Bruce Ikenaga