22 2. Background
Exercise 2.3.3. Let A = {a, b, c, d, e}.
(i) What is the ternary relation R on A defined by (x, y, z) R
(xyz is an English word)?
(ii) What is the unary relation on A which is true of elements of A
that are vowels?
(iii) What is the complement of the relation in (ii)? We may describe
it in two ways: as “the negation of the relation in (ii),” and how?
(iv) Define the 5-ary relation R by (v, w, x, y, z) R (v, w, x, y, z
are all distinct elements of A). How many elements does R
(v) How many unary relations are possible on A? What other collec-
tion associated with A does the collection of all unary relations
correspond to?
Exercise 2.3.4. How many n-ary relations are possible on an m-
element set?
We tend to focus on binary relations, since most of our common,
useful examples are binary: , ≤, =, =, ⊂, ⊆. Binary relations may
have certain properties:
Reflexivity: (∀x)R(x, x)
Symmetry: (∀x, y)[R(x, y) R(y, x)]
i.e., (∀x, y)[(R(x, y) & R(y, x)) (¬R(x, y) & ¬R(y, x))]
Antisymmetry: (∀x, y)[(R(x, y) & R(y, x)) x = y]
Transitivity: (∀x, y, z)[(R(x, y) & R(y, z)) R(x, z)]
I want to point out that reflexivity is a property of possession:
R must have the reflexive pairs (the pairs (x, x)). Antisymmetry is,
loosely, a property of nonpossession. Symmetry and transitivity, on
the other hand, are closure properties: if R has certain pairs, then
it must also have other pairs. Those conditions may be met either
by adding in the pairs that are consequences of the pairs already
present, or omitting the pairs that are requiring such additions. In
particular, the empty relation is symmetric and transitive, though it
is not reflexive.
Previous Page Next Page