Math 120A HW 1

1. Consider the sets $X = \{1,2,3\}$ and $Y = \{a,b,c\}$ where $a$, $b$, and $c$ are distinct elements.
   1. Compute $X \times Y$ by listing its elements.
   2. Consider the relation $R = \{(1,c), (2,a), (3,a)\}$ from $X$ to $Y$. Is it a function from $X$ to $Y$? Justify your answer.
   3. Is $R$ a bijection from $X$ to $Y$? Justify your answer.
   4. Consider the inverse relation $R^{-1} = \{(c,1),(a,2), (a,3)\}$ from $Y$ to $X$. Is it a function from $Y$ to $X$? Justify your answer.
2. Consider the set $A = \{1,2,3\}$. Give an example of functions $f:A \to A$ and $g:A \to A$ such that $f \circ g \ne g \circ f$. Justify your answer.
3. Consider the function $f : \mathbb{Z} \to \mathbb{N}$ defined by $$ f(n) = \begin{cases} 2n & \text{if } n \ge 0\\ -2n-1 & \text{if } n \lt 0. \end{cases} $$ Prove that $f$ is a bijection. (Recall that we consider $0$ to be an element of $\mathbb{N}$.)
4. Denote the set of all nonzero integers by $\mathbb{Z}^*$. Prove that $\mathbb{Z}$ and $\mathbb{Z}^*$ are equinumerous (have the same cardinality) by proving that there is a bijection from $\mathbb{Z}$ to $\mathbb{Z}^*$.
5. Define the set $T = \{r \in \mathbb{Q} : r = 2^ma \text{ for some } a,m \in \mathbb{Z}\}$. Prove that $T$ is closed under the operations of addition and multiplication.
6. For each of the following operations, prove that it is associative or else find a counterexample.
   1. The operation $\ast$ on $\mathbb{R}$ defined by $a \ast b = ab/2$.
   2. The operation $\ast$ on $\{0,1\}$ defined by $$a \ast b = \begin{cases} 1 & \text{if } a \le b\\ 0 &\text{if } a > b.\end{cases}$$