EQUIVALENCE RELATIONS
Of particular interest are relations that are transitive, reflexive, and symmetric. In fact, these are important enough to be given their own name:
An EQUIVALENCE RELA TION is a relation that is transitive, reflexive, and symmetric.
The class of all individuals standing in an equivalence relation to one another is called an EQUIVALENCE CLASS.
These relations are particularly efficacious in clearing up controversies about what is meant by certain terms. A very early example occurs in Euclid’s elements. To explicate what he meant by the term ratio of magnitudes he set out certain conditions that must be satisfied for one pair of magnitudes to have the same ratio as another (Elements, V, 5). Taking his cue from this, Leibniz, in his famous correspondence with Clarke, attempted to throw light on the concept of place by explicating what is meant by one body being at the same place as another. A body A has certain relations of situation to all bodies co-existing with it. Supposing some subset of these (C, E, F, G, etc.) maintain the same relation among themselves for a given time, a second body B can be said to be in the same place as A iff it has the same relations of situation with C, E, F, G, etc. that A formerly had. [85]PlaceF says Leibniz, “is that which is said to be the same for A and for B, when the relation of co-existence between B and C, E, F, G, etc. entirely agrees with the relation of co-existence that A previously had with those bodies, supposing there to have been no cause of change in C, F, F, G, etc.” Given this, it clearly follows that if any body A is in the same place as a body B, and B is in the same place as C, then A is in the same place as C (transitivity); if A is in the same place as a B, then B is in the same place as A (symmetry), and every body is in the same place as itself (reflexivity).
Thus being in the same place as is an equivalence relation. Since the class of all individuals standing in an equivalence relation to one another is an equivalence class, Leibniz has in effect defined place as an equivalence class of all bodies standing in this relation of sameness of place to one another.
of all those bom in October of the same year, just because all members of the September subset will be OLDER2 than all those of the October one. We will return to the notion of orderings in the next chapter.
EXERCISES 20.2
7. On the domain (UD) of natural numbers, only one of the following relations is intransitive. Which?
(a) ‘is GREATEr2 than’; (b) ‘is EQUAL2 to’; (c) ‘is greater than OR2 equal to’; (d) ‘is the immediate SUCCESSOR2 of’; (e) ‘is LESS2 than.’
8. State whether each of the following relations is (i) symmetric, (H) asymmetric, or (Hi) nonsymmetric on the domain (UD) in question:
(a) ‘is GREATEr2 than’ (UD: natural numbers); (b) ‘is SISTER2 of’ (UD: siblings); (c) ‘is SISTER2 of’ (UD: the Andrews sisters); (d) ‘is EQUAL2 to’ (UD: natural numbers); (e) ‘is GREATER2 than or equal to’ (UD: the four rational numbers 1/2, 1,2/2,2/1).
9. State whether each of the following relations is (i) reflexive, (H) irreflexive, or (Hi) nonreflexive on the domain (UD) in question:
(a) ‘is GREATEr2 than’ (UD: natural numbers); (b) ‘is BROTHER2 of’ (UD: the Marx brothers); (c) ‘is genetically RELATED2 to’ (UD: people); (d) iLOOKS2 after’ (UD: people).
Prove the formal validity of each of arguments 10-13. Some depend for their validity on a property or properties of the relation involved.
In those cases you will need to treat those properties as implicit premises that must be included in the symbolization of the argument:10. Mars must be SMALLER2 than Earth, since Mars is smaller than Venus, and Venus is smaller than Earth. [UD: planets]
11. Three is EQUAL2 to the square root of nine, and pi does not equal three. So the square root of nine does not equal pi. [UD: numbers]
12. Shaquille O’Neal is not TALLER2 than everyone on his team, since he is not taller than himself. [UD: players on Shaquille’s team]
13. Vancouver is NORTH2 of Seattle, which is north of Chicago. So Chicago is not north ofVancouver. [UD: cities]
14. Prove that any binary relation R that is neither reflexive nor irreflexive must be nonreflexive.
15. Prove that any binary relation R that is asymmetric is also irreflexive.
16. The relation ‘is the FATHER2 of is intransitive. Prove that from this property alone itfollows that it is irreflexive.
17. Prove that if a relation R does not hold on any pair Ofindividuals in a domain, then the relation is symmetric: i.e., prove
18. Prove that any binary relation R that is irreflexive and transitive is asymmetric.
19. Prove that no binary relation R can be transitive, nonsymmetric, and irreflexive, i.e., show that these properties are inconsistent.
20. Prove that any symmetric and transitive relation R is also Euclidean.
21. Prove that any reflexive and Euclidean relation R is also symmetric.
22. (CHALLENGE) Prove that any reflexive and Euclidean relation R is also transitive.
23. (CHALLENGE) What do the results of 20-22 tell you about a relation R that is Euclidean and also reflexive ?
24. (CHALLENGE) Prove that any symmetric, Euclidean, and serial relation R is also reflexive.
25. (CHALLENGE) Prove that any symmetric, transitive, and serial relation R is also reflexive.
26. (CHALLENGE) Prove that any transitive and symmetric relation R is partially reflexive.