# HW 2 Solutions

1. Suppose |A| = m and |B| = n. We show by induction that |A x B| = mn.

Let $A = \{ a_1, a_2, \ldots, a_m \}$ so that A has m elements.

First, suppose n = 0. Then $B = \emptyset$. For any set A, $A \times \emptyset = \emptyset$, since there are no ordered pairs (a, b) with $a \in A$ and $b \in \emptyset$. Hence, |A x B| = 0.

Now assume (inductively) that for any set B of size n, then |A x B| = mn. We show that if |B| = n + 1, then |A x B|= m(n+1).

Let $B = \{ b_1, b_2, \ldots, b_n, b_{n+1} \}$. By induction, we know that $| A \times \{ b_1, b_2, \ldots, b_n \} | = mn$. The set A x B also contains the ordered pairs $(a_1, b_{n+1}), (a_2, b_{n+1}, \ldots, (a_m, b_{n+1})$. There are m of these. Therefore, | A x B | = mn + m = m(n + 1).

2. First we show that the relation is anti-symmetric: Let a and b be integers, and suppose $a - b \leq 0$ and $b - a \leq 0$. Therefore, $a \leq b$. If $a \leq b$, then either $a < b$ or $a = b$. If $a < b$, then $b - a > 0$, which is a contradiction because we know $b - a \leq 0$. Therefore, a and b must be equal.

Next we show that the relation is transitive: suppose a, b, and c are integers, and $a - b \leq 0$ and $b - c \leq 0$. Notice that $a - c = (a - b) + (b - c)$. If we add two numbers that are at most 0, we cannot get a number that is greater than 0. Therefore, $a - c \leq 0$.

Lastly, we show that the relation is total. Suppose a and b are integers and $a - b \not \leq 0$. Therefore, $a - b > 0$. In other words, a – b is positive. Notice that $b - a = -(a - b)$, so if a – b is positive, b – a is negative. That is, $b - a < 0$ and hence $(b, a) \in R$.

Now we consider the relation R = {(x, y) : x is a factor of y }. Because 2 is not a factor of 3 and 3 is not a factor of 2, we know that $(2, 3) \not \in R$ and $(3, 2) \not \in R$. Hence R is not total.

3. We will prove a more general statement: if A and B are finite sets of size n, there are $n!$ bijections between A and B. (Here, n! is n factorial: the product 1 x 2 x 3 x … x n). We prove this by induction. Our base case is $n = 1$.

Suppose $A = \{ a \}$ and $B = \{ b \}$. There is only one function from A to B: namely the function $f : A \to B$ defined by $f(a) = b$. This function is a bijection (it is not hard to check this). Since there is only one such bijection, and $1! = 1$.

Inductively, assume that if $|A| = |B| = n$, then there are n! bijections between A and B. Let $A = \{ a_1, a_2, \ldots, a_n, a_{n+1} \}$ and $B = \{ b_1, b_2, \ldots, b_n, b_{n+1} \}$ so these sets have n + 1 elements. Any bijection between A and B has to send $a_{n+1}$ to some element $b \in B$. By induction, there are n! bijections between $A \setminus \{ a_{n+1} \}$ and $B \setminus \{ b \}$. Therefore, for each $b \in B$, there are n! bijections $f : A \to B$ such that $f(a_{n+1}) = b$. Since there are n + 1 different elements b, there are, in total, $(n+1)\cdot n! = (n+1)!$ bijections from A to B.

This, more general result, implies the result for A = B = { 0, 1, 2, …, n – 1 }. Therefore there are n! bijections from the set { 0, 1, 2, …, n – 1} to itself.

4. First we show that this relation is reflexive. Let $a \in X$ be an arbitrary element. Then a – a = 0, which is an even integer. Therefore, $(a, a) \in R$.

Next, we show that R is symmetric. Let $a, b \in X$ be such that a – b is an even integer. Then, since $b - a = -(a - b)$, and the negation of an even integer is an even integer, b – a is also an even integer. Therefore, $(b, a) \in R$.

Lastly we show that R is transitive. Suppose $(a, b) \in R$ and $(b, c) \in R$. Then $a - b$ is even and $b - c$ is even. That means, using the definition of “even integer”, there are integers m and n such that $a - b = 2m$ and $b - c = 2n$. Notice that $a - c = (a - b) + (b - c)$, so $a - c = 2m + 2n = 2(m + n)$, which is also an even integer. Therefore, $(a, c) \in R$.

It is not hard to see that $(0, 2) \in R$ and $(0, 1) \not \in R$. We can actually extend this relation to the set $\mathbb{Z}$ of all integers. Every integer is either related to 0 or 1 (and certainly not both): notice that if x is even, then x – 0 is even, but if x is odd, then x – 1 is even.