First week in-class assignments

Make sure that you have looked at the preliminaries and review section.

We will work on solutions to the following problems from the text.

Chapter 1.

  1. (Problem 11) Prove that $(A\cup B)\times C = (A\times C)\cup(B\times C)$
  2. (Problem 19) Let $f:A\to B$ and $g:B\to C$ be invertible mappings, that is, functions such that $f^{-1}$ and $g^{-1}$ exist. Prove that $(g\circ f)^{-1} = f^{-1}\circ g^{-1}$.

  3. (Problem 24) Let $f:X\to Y$ be a map with $A_1,A_2\subset X$ and $B_1, B_2\subset Y$.

    • Prove that $f(A_1\cup A_2) = f(A_1)\cup f(A_2)$.
    • Prove that $f(A_2\cap A_2)\subset f(A_1)\cap f(A_2)$. Given an example in which equality fails.
    • Prove that $f^{-1}(B_1\cup B_2)=f^{-1}(B_1)\cup f^{-1}(B_2)$ where \(f^{-1}(B) = \{x\in X : f(x)\in B\}\)
    • Prove that $f^{-1}(B_1\cap B_2)=f^{-1}(B_1)\cap f^{-1}(B_2)$.
    • Prove that $f^{-1}(Y-B_1) = X-f^{-1}(B_1)$.

  4. (Problem 25) Which of the following relations are equivalence relations? For those which are, describe the associated partition. For those which aren’t, explain why not.

    • $x\sim y$ in $\mathbb{R}$ if $x\ge y$.
    • $m\sim n$ in $\mathbb{Z}$ if $mn>0$.
    • $x\sim y$ in $\mathbb{R}$ if $\vert x-y\vert\le 4$.
    • $m\sim n$ in $\mathbb{Z}$ if $m\equiv n\pmod{6}$

Chapter 2.

  1. (Problem 4) Prove that \(x+4x+7x+\cdots+(3n-2)x=\frac{n(3n-1)x}{2}\) for all $n\in \mathbb{N}$.

  2. (Problem 15) For each of the following pairs of numbers $a$, $b$, find integers $r$ and $s$ so that $ar+bs=gcd(a,b)$.
    • $14$,$39$
    • $234$, $165$
    • $1739$, $9923$
    • $471$, $562$
    • $23771$, $19945$
    • $-4357$, $3754$
  3. (Problem 17) Define the Fibonacci numbers by the recurrence relation $f_n=f_{n-1}+f_{n-2}$ with $f_1=1$ and $f_2=1$. Prove the following:
    • $f_{n}<2^{n}$.
    • $f_{n+1}f_{n-1}=f_{n}^2+(-1)^{n}$
    • $f_{n} = [\phi^{n}-\overline{\phi}^{n}]/(2^{n}\sqrt{5})$ where $\phi=(1+\sqrt{5})/2$ and $\overline{\phi}=(1-\sqrt{5})/2$.
    • Prove that $\lim_{n\to\infty} f_{n}/f_{n+1} = -\overline{\phi}$.
    • Prove that successive fibonacci numbers are relatively prime.

  4. (Problem 22) Let $n\in \mathbb{N}$. Use the division algorithm to prove that every integer is congruent mod $n$ to exactly one of the integers $0,1,\ldots, n-1$. Conclude that if $r$ is an integer, then there is exactly one $s$ in $\mathbb{Z}$ such that $0\le s<n$ and $[r]=[s]$. Conclude that the integers are partitioned into $n$ disjoint congruence classes mod $n$.

  5. (Problem 25) Show that the least common multiple of two integers $a$ and $b$ is their product if and only if their greatest common divisor is one.