Math 2510 Spring 2010 -- Homework Problem Sets #5 & #6

Problems 1-4 Due: Friday, March 26th
Problems 5-8 Due: Wednesday, March 31st
  1. Casting Out Nines
    In our "childhood" we are taught that a number is divisible by \( 9 \) if its digits add up to \( 9 \) -- well, not quite -- if its digits add up to a number bigger than \( 9 \) we need to repeat the process. For example, \( 63 \) is divisible by \( 9 \) because \( 6+3=9 \). Also, \( 99 \) is divisible by \( 9 \) because \( 9+9=18 \) and \( 1+8=9 \). Here's a big example: \( 19,008,675 \) is divisible by \( 9 \) because \( 1+9+0+0+8+6+7+5 = 36 \) and \( 3+6=9 \). On the other hand, \( 123,454,321 \) is not divisible by 9 because \( 1+2+3+4+5+4+3+2+1=25 \) and \( 2+5=7 \not= 9 \). Why does this work? Well, it rests on the fact that if \( n = d_\ell \times 10^\ell + \cdots d_2 \times 10^2 + d_1 \times 10 + d_0 \) where \( d_j \in \{ 0,1,\dots 9 \} \) for all \( j=0,\dots,\ell \) then \( \displaystyle{ \;9 \,\Big|\, n\; } \) if and only if \( \displaystyle{ \;9 \,\Big|\, (d_\ell + \cdots + d_1 + d_0)\; } \). [This says that a number is divisible by \( 9 \) if and only if its digits sum to a number divisible by \( 9 \). By repeatedly summing digits we will eventually end up with a number between \( 0 \) and \( 9 \). So \( n \) is divisible by \( 9 \) if and only if this process terminates with a "\( 9 \)".]
    Prove the fact. Hint: Translate this statment into congruences \(\mathrm{mod\;}9 \) and consider the value of \( 10 \mathrm{\;mod\;} 9 \), \( 10^2 \mathrm{\;mod\;} 9 \), etc.

  2. Fix two sets such that \( S_0 \subseteq S \). Recall that \( \mathcal{P}(S) \) is the power set of \( S \) --- the set of all subsets of \( S \), so in particular, \( S_0 \in \mathcal{P}(S) \).

    1. Define the relation \( \sim \) on \( \mathcal{P}(S) \) by \( A \sim B \) if and only if \( A \cap S_0 \subseteq B \cap S_0 \). Is \( \sim \) reflexive, symmetric, antisymmetric, or transitive? If a property holds, prove it. If it fails, give a counterexample. Is \( \sim \) a partial order? Why or why not?

    2. Define the relation \( \approx \) on \( \mathcal{P}(S) \) by \( A \approx B \) if and only if \( A \cap S_0 = B \cap S_0 \). Show \( \approx \) is an equivalence relation.

    3. If \( S = \{ 1,2,3 \} \) and \( S_0 = \{ 1 \} \) determine the equivalence classes of \( \approx \).

  3. Let \( A \), \( B \), and \( C \) be sets. Prove the following equalities:

    1. \( A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \)

    2. \( A \cap (B - C) = (A \cap B) - (A \cap C) \)

  4. Determine what the following union and intersection are. Your answer should be of form: \( (a,b) \), \( [a,b) \), \( (a,b] \), or \( [a,b] \) --- that is an open, half-open, or closed interval.

    1. \( \displaystyle{ \bigcup_{n=1}^{\infty} \left( -1+\frac{1}{n}, 1+\frac{1}{n} \right) } \)

    2. \( \displaystyle{ \bigcap_{n=1}^{\infty} \left( -1+\frac{1}{n}, 1+\frac{1}{n} \right) } \)

  5. Two of the following three formulas yield well-defined functions. Prove that the well-defined formula is --- well --- well-defined and give a counter-example for each of the other formulas to show that they are not well-defined. [Let \( \mathbb{Z}_n \) be the set of equivalence classes of intergers mod \( n \) and let \( [k] \) be the equivalence class of \( k \in \mathbb{Z} \).]

    1. Let \( f_1 : \mathbb{Q} \rightarrow \mathbb{Z} \) be ?defined? by \( \displaystyle{ f_1\left( \frac{a}{b} \right) = a } \).

    2. Let \( f_2 : \mathbb{Z}_6 \rightarrow \mathbb{Z}_3 \) be ?defined? by \( \displaystyle{ f_2\left( [m] \right) = [m] } \).

    3. Let \( f_3 : \mathbb{Z}_6 \rightarrow \mathbb{Z}_4 \) be ?defined? by \( \displaystyle{ f_3\left( [m] \right) = [m] } \).

  6. For each of the following functions, determine if the function is one-to-one, onto, both or neither. Prove your answers.

    1. \( g_1 : \mathbb{R} \rightarrow \mathbb{R}_{\geq 0} \) defined by \( g_1(x)=x^2 + 1 \).

    2. \( g_2 : \mathbb{Z} \rightarrow \mathbb{Z} \) defined by \( \displaystyle{ g_2(n) = \left\{ \begin{array}{cl} \frac{n}{2} & n \mbox{ is even} \\ 2n & n \mbox{ is odd} \end{array} \right. } \).

    3. \( g_3 : \mathbb{Z} \rightarrow \mathbb{Z} \) defined by \( \displaystyle{ g_3(n) = \left\{ \begin{array}{cl} n+1 & n \mbox{ is even} \\ 2n & n \mbox{ is odd} \end{array} \right. } \).

  7. Let \( f:X \rightarrow Y \) and \( g:Y \rightarrow Z \) be surjective functions. Show that \( g \circ f:X \rightarrow Z \) is surjective.

  8. Let \( f:X \rightarrow Y \) be a function, let \( T_1, T_2 \subseteq Y \), and let \( S_1, S_2 \subseteq X \). Prove the following:

    1. \( f(S_1)-f(S_2) \subseteq f(S_1-S_2) \)

    2. \( f^{-1}(T_1 \cup T_2) = f^{-1}(T_1) \cup f^{-1}(T_2) \)

    3. If \( T_1 \subseteq T_2 \), then \( f^{-1}(T_1) \subseteq f^{-1}(T_2) \).