Unit 18 Answers
1.
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 n2. Thus the power set of the Cartesian product has 2n2 elements. Hence there are 2n2 binary relations on a set of cardinality n.