20. Reflexive Relations
21. Relations which are Not Reflexive
22. Irreflexive Relations
23. Relations which are Not Irreflexive
24. Reflexive and Irreflexive Relations
25. Symmetric Relations
26. Symmetric and Inverse Relations
27. Relations which are Not Symmetric
28. Symmetric Relations and Negation
29. Antisymmetric Relations
30. Relations which are Not Antisymmetric
31. Antisymmetric and Irreflexive Relations
32. Transitive Relations
33. Intransitive Relations
34. Properties of Inverses
35. Equivalence Relations
36. Equivalence Classes
37. Simple Order Relations
Example: Let x and y stand for telescopes, and let x R y mean x has the same power as y. Then R is reflexive because every telescope has the same power as itself.
We define a reflexive relation in symbols as follows:
R is reflexive when Ax: x R x.
R is not reflexive when Ex: x not-R x.Example: Let x and y stand for people, and let x R y mean x knows the birthday of y. Most people know their own birthdays, but there are some people who do not. Therefore, the relation R is not reflexive.
Example: Let x and y stand for men, and let x R y mean x is the father of y. Since no man is the father of himself, it follows that R is irreflexive.
We define an irreflexive relation in symbols as follows:
R is irreflexive when Ax: x not-R x.
R is not irreflexive when Ex: x R x.Example: Let x and y stand for people, and let x R y mean x teaches y to use a computer. Many people are taught by someone else to use a computer, but some people teach themselves. Therefore, the relation x R y is not irreflexive.
Example: Let x and y stand for telescopes, and let x R y mean x has the same power as y. Then x not-R y means x does not have the same power as y. Here R is reflexive, because every telescope has the same power as itself, and not-R is irreflexive, because it is never true to say that a telescope does not have the same power as itself.
The general law is summarized in symbols as follows:
A relation R is reflexive if and only if not-R is irreflexive.
Example. Let the universal set consist of mountains. Let x R y mean The tops of x and y are both covered with snow. This implies The tops of y and x are both covered with snow, which is represented by y R x. Therefore, R is symmetric.
We define a symmetric relation as follows:
R is symmetric when Ax: Ay: x R y implies y R x.
R is symmetric if and only if R = R-1.
Example. Let x and y stand for horses. Let x R y mean x runs faster than y. Then y R x means y runs faster than x. There exist horses x and y such that x R y is true. For these horses y R x is not true, and it follows that R is not symmetric.
The general law is summarized as follows:
R is not symmetric if and only if Ex: Ey: x R y and y not-R x.
Example. Let x and y stand for mountains, and let x R y mean The tops of x and y are both covered with snow. The relation R is symmetric. Then x not-R y means It is not true that the tops of x and y are both covered with snow; in other words, The top of x is not covered with snow or the top of y is not covered with snow. This has the same meaning as: The top of y is not covered with snow or the top of x is not covered with snow, which is expressed in symbols as follows: y not-R x. Therefore, x not-R y implies y not-R x. This shows that not-R is symmetric.
The general law is summarized in symbols as follows:
R is symmetric if and only if not-R is symmetric.
Give the meaning of x not-R y.
Are the relations R and not-R symmetric, or not symmetric?
Example. Let x and y stand for horses; and let x R y mean x runs faster than y. If x runs faster than y, then it is not true that y runs faster than x; in other words, y does not run faster than x. This conclusion is represented by: y not-R x. Therefore, R is antisymmetric.
An antisymmetric relation is defined in symbols as follows:
R is antisymmetric when Ax: Ay: x R y implies y not-R x.
Example. Let x and y stand for telescopes; and let x R y mean x is not less powerful than y. For telescopes that have the same power as each other, x R y (which means x is not less powerful than y) and y R x (which means y is not less powerful than x) are both true. Therefore, R is not antisymmetric.
The general law is summarized as follows:
R is not antisymmetric if and only if Ex: Ey: x R y and y R x.
Example. Let x and y stand for horses. Let x R y mean x runs faster than y; and suppose that y = x. Then we have x R x, which means The horse x runs faster than itself. Since this cannot be true, the statement x not-R x must be true; therefore R is irreflexive.
The general law is summarized as follows:
If R is antisymmetric, then R is irreflexive.The converse of this law is not true: if R is irreflexive we cannot conclude that R is antisymmetric.
Example. Let x and y stand for people, and let x R y mean x and y are cousins. Since nobody is his or her own cousin, the relation R is irreflexive. However, R is not antisymmetric, because the statement x is a cousin of y does not imply y is not a cousin of x.
Example. Let the universal set consist of motor vehicles. Let x R y mean x has the same number of wheels as y. Then y R z means y has the same number of wheels as z, and it follows that x has the same number of wheels as z. Therefore, R is transitive.
We define a transitive relation in symbols as follows:
R is transitive when Ax: Ay: Az: (x R y and y R z) implies x R z.
Example. Let the universal set consist of men. Let x R y mean x is the son of y. Then y R z means y is the son of z. It follows that x is the grandson (not the son) of z, which implies x not-R z. Therefore, R is intransitive.
We define an intransitive relation in symbols as follows:
R is intransitive when Ax: Ay: Az: (x R y and y R z) implies x not-R z.
A list of important properties is as follows:
R-1 is reflexive if and only if R is reflexive.
R-1 is irreflexive if and only if R is irreflexive.
R-1 is symmetric if and only if R is symmetric.
R-1 is antisymmetric if and only if R is antisymmetric.
R-1 is transitive if and only if R is transitive.
R-1 is intransitive if and only if R is intransitive.
The logical definition of an equivalence relation is as follows:
A relation is called an equivalence relation when it is:Example. Let the universal set consist of motor vehicles; and let x R y mean x has the same number of wheels as y. Then motorcycles are equivalent because they all have two wheels; private motor-cars are equivalent because they all have four wheels; etc.
(1) reflexive,
(2) symmetric,
(3) transitive.
In this example the relation R has all the properties of an equivalence relation: (1) Since every vehicle has the same number of wheels as itself, R is reflexive. (2) Since the statement x has the same number of wheels as y always implies y has the same number of wheels as x, R is symmetric. (3) If x and y have the same number of wheels, and if y and z have the same number of wheels, then x and z have the same number of wheels; therefore, R is transitive.
Equivalence classes are subsets of the universal set with the following properties:
(1) The intersection of two different equivalence classes is empty.
(2) The union of all the equivalence classes is the universal set.
The reason for property (1) is as follows: Suppose A and B are different equivalence classes made from an equivalence relation R. Let x be any element in A, and let y be any element in B; then we have x not-R y. Now it is impossible for any element z to be in the intersection A . B, because then we would have x R z and z R y; this would imply x R y, which contradicts the relation x not-R y.
The reason for property (2) is that every element in the universal set is used to form the collection of equivalence classes; no element is left out.
Example. The universal set of motor vehicles may be divided into equivalence classes consisting of vehicles with the same number of wheels. All motorcycles belong to the equivalence class of vehicles with two wheels; motor-tricycles belong to the equivalence class of vehicles with three wheels; private cars and small vans belong to the class of vehicles with four wheels; trucks belong to the class with six wheels, or to the class with ten wheels, etc.
Give the equivalence classes into which this set is divided by the following equivalence relation: x and y are on the same side (east or west) of the Greenwich meridian and are also on the same side (north or south) of the equator. Note: the Greenwich meridian passes through London.
The logical definition of a simple order relation is as follows:
A relation R is called a simple order relation when:Example. Let the universal set consist of words; and let x R y mean x is before y in alphabetical order. (1) In every pair of different words one of the words is before the other in alphabetical order. (2) R is antisymmetric: for example, the word light is before the word like, and this implies that like is not before light. (3) R is transitive: for example, the word easy is before eat, and eat is before edge; this implies that easy is before edge.
(1) Ax: Ay: x not= y implies x R y or y R x;
(2) R is antisymmetric;
(3) R is transitive.
Backward links: Statements I Statements II Quantifiers I Quantifiers II Sets I Sets II Relations I
By R. H. B. Exell, 1998. King Mongkut's University of Technology Thonburi.
Back to Home Page