Unit 18 Answers

1.

1. {(1, 0), (2, 0), (2, 1), (3, 0), (3, 1), (3, 2)}
2. {(0, 3), (1, 2), (2, 1), (3, 0)}
3. {(1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (2, 0), (2, 2), (2, 4), (3, 0), (3, 3)}
4. {(0, 0), (1, 1), (2, 2), (3, 3)}
5. {(0, 1), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (3, 1), (3, 2), (3, 4)}
6. {(2, 3), (3, 2)}

2. Let R denote the relation.

Basis clause: (0, 0)   R.
Inductive clause: For any natural numbers x and y,   if (x,  y)   R,   then   (x + 2,  y + 1)   R.
Extremal clause: Nothing is in R unless it is obtained by the Basis and Inductive clauses.

3. A unary relation is a set of 1-tuples. Hence there are eight unary relations on {1, 2, 3}.
They are ,   {(1)},   {(2)},   {(3)},   {(1), (2)},   {(1), (3)},   {(2), (3)},   {(1), (2), (3)}.

4. A binary relation on a set is a subset of the Cartesian product of the set with itself. If the cardinality of the set is n, then the cardinality of the Cartesian product of the set with itself is n². Thus the power set of the Cartesian product has 2ⁿ² elements. Hence there are 2ⁿ² binary relations on a set of cardinality n.