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

Let so that A has m elements.

First, suppose n = 0. Then . For any set A, , since there are no ordered pairs (a, b) with and . 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 . By induction, we know that . The set A x B also contains the ordered pairs . 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 and . Therefore, . If , then either or . If , then , which is a contradiction because we know . Therefore, a and b must be equal.

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

Lastly, we show that the relation is total. Suppose a and b are integers and . Therefore, . In other words, a – b is positive. Notice that , so if a – b is positive, b – a is negative. That is, and hence .

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 and . 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 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 .

Suppose and . There is only one function from A to B: namely the function defined by . This function is a bijection (it is not hard to check this). Since there is only one such bijection, and .

Inductively, assume that if , then there are n! bijections between A and B. Let and so these sets have n + 1 elements. Any bijection between A and B has to send to some element . By induction, there are n! bijections between and . Therefore, for each , there are n! bijections such that . Since there are n + 1 different elements b, there are, in total, 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 be an arbitrary element. Then a – a = 0, which is an even integer. Therefore, .

Next, we show that R is symmetric. Let be such that a – b is an even integer. Then, since , and the negation of an even integer is an even integer, b – a is also an even integer. Therefore, .

Lastly we show that R is transitive. Suppose and . Then is even and is even. That means, using the definition of “even integer”, there are integers m and n such that and . Notice that , so , which is also an even integer. Therefore, .

It is not hard to see that and . We can actually extend this relation to the set 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.