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

contain?

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