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.