Math 120A HW 1 Solutions

1. Consider the sets $X = \{1,2,3\}$ and $Y = \{a,b,c\}$ where $a$, $b$, and $c$ are distinct elements.
   1. $X \times Y = \{(1,a),(1,b),(1,c),(2,a),(2,b),(2,c),(3,a),(3,b),(3,c)\}$.
   2. Yes, it is a function from $X$ to $Y$ because for every element $x \in \{1,2,3\}$ there is one and only one element $y \in \{a,b,c\}$ such that $(x,y) \in R$.
   3. No, it is not injective because $(2,a)$ and $(3,a)$ are both elements of $R$, or equivalently $R(2) = R(3)$, but $2 \ne 3$. (Alternatively, you can show that it is not surjective.)
   4. No, it is not a function at all because it contains both $(a,2)$ and $(a,3)$, so it doesn't specify a unique element for $a$ to map to.
2. If we define $f$ by $f(1) = 2$, $f(2) = 1$, and $f(3) = 3$ and we define $g$ by $g(1) = 1$, $g(2) = 3$, and $g(3) = 2$, then $(f \circ g)(1) = f(g(1)) = f(1) = 2$, but $(g \circ f)(1) = g(f(1)) = g(2) = 3$, so $f \circ g \ne g \circ f$.
3. To see that $f$ is injective, let $m, n \in \mathbb{Z}$ and assume that $f(m) = f(n)$. If this common value of $f(m)$ and $f(n)$ is even, then $m,n \ge 0$, so $2m = 2n$, and therefore $m = n$. If the common value of $f(m)$ and $f(n)$ is odd, then $m,n \lt 0$, so $-2m - 1 = -2n - 1$, so $-2m = -2n$, and again we have $m = n$.

   To see that $f$ is surjective, let $r \in \mathbb{N}$. If $r$ is even, say $r = 2n$ where $n \ge 0$, then $f(n) = r$. If $r$ is odd, say $r = 2n-1$ where $n \gt 0$, then $-n \lt 0$ and we can compute $f(-n) = r$. In both cases we showed that $r$ is in the range of $f$.

4. We can define a bijection $f : \mathbb{Z} \to \mathbb{Z}^*$ by $$ f(n) = \begin{cases} n+1 & \text{if } n \ge 0\\ n & \text{if } n \lt 0. \end{cases} $$ You can prove that $f$ is injective and surjective by splitting into cases as in the previous problem, except that the cases are positive and negative rather than even and odd. Or I think a picture would be sufficient for this problem, showing $\mathbb{Z}$ and $\mathbb{Z}^*$ and arrows between their elements.
5. Let $r_1,r_2 \in T$, say $r_1 = 2^{m_1} a_1$ and $r_2 = 2^{m_2}a_2$ where $m_1,a_1,m_2,a_2 \in \mathbb{Z}$. Without loss of generality we may assume that $m_1 \le m_2$. Then $r_1 + r_2 = 2^{m_1} a_1 + 2^{m_2}a_2 = 2^{m_1} (a_1 + 2^{m_2-m_1}a_2)$, which is in $T$ because $m_1$ and $a_1 + 2^{m_2-m_1}a_2$ are in $\mathbb{Z}$, so $T$ is closed under addition. Also, $r_1r_2 = 2^{m_1} a_12^{m_2}a_2 = 2^{m_1+m_2}(a_1a_2)$, which is in $T$ because $m_1+m_2$ and $a_1a_2$ are in $\mathbb{Z}$, so $T$ is closed under multiplication.
6. For each of the following operations, prove that it is associative or else find a counterexample.
   1. For all $a,b,c\in \mathbb{R}$ we have $a \ast (b \ast c) = a \ast (bc/2) = a(bc/2)/2 = abc/4$ and also $(a \ast b) \ast c = (ab/2) \ast c = (ab/2)c/2 = abc/4$, so this operation $\ast$ is associative.
   2. This operation $\ast$ is not associative: $(0 \ast 1) \ast 0 = 1 \ast 0 = 0$, but $0 \ast (1 \ast 0) = 0 \ast 0 = 1$.