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.
Previous Page Next Page