As usual, let’s start with relevant definitions.
Definition: “A relation R on a set A is called reflexive if (a,a) ∈ R for every element a ∈ A.”
Definition: “A relation R on a set A is called symmetric if (b,a) ∈ R whenever (a,b) ∈ R, for all a,b ∈ A. A relation R on a set A such that for all a, b ∈ A, if (a, b) ∈ R and (b, a) ∈ R, then a = b is called antisymmetric.”
Definition: “A relation R on a set A is called transitive if whenever (a,b)∈R and (b,c)∈R, then (a,c) ∈ R, for all a,b,c ∈ A.”
The definitions above are from the textbook “Discrete Mathematics and its Applications” by Rosen.
Now we can start solving the exercises.
Table of Contents
- a) x≠y
- b) xy≥1
- c) x=y+1 or x=y−1
- d) x≡y(mod7)
- e) x is a multiple of y
- f) x and y are both negative or both nonnegative
- g) x=y2
- h) x≥y2
a) x≠y
Not reflexive by definition.
Symmetric: if x≠y then (x,y)∈R. This means that for all (x,y)∈R, with x≠y, (y,x)∈R as y≠x. Therefore, the relation is symmetric.
Antisymmetric: (1,2)∈R and (2,1)∈R, but 1≠2. Therefore, the relation is not antisymmetric.
Transitive: (1,2)∈R and (2,1)∈R, but (1,1)∉R. Therefore, the relation is not transitive.
b) xy≥1
Reflexive: 0∈Z, but (0,0)∉R. Therefore, the relation is not reflexive.
Symmetric: xy=yx. So, if xy≥1 then yx≥1. Therefore, the relation is symmetric.
Antisymmetric: (2,3)∈R, (3,2)∈R, but 2≠3. Therefore, the relation is not antisymmetric.
Transitive: if xy≥1 and yz≥1, then it follows that xz≥1. Therefore, the relation is transitive.
c) x=y+1 or x=y−1
Reflexive: (1,1)∉R. Therefore, the relation is not reflexive.
Symmetric: (x,y)∈R when x=y+1 or x=y-1. The pairs will have the form (y+1,y) or (y-1,y), so (5,4)∈R and also (4,5)∈R. Therefore, the relation is symmetric.
Antisymmetric: (5,4)∈R and also (4,5)∈R. Therefore, the relation is not antisymmetric.
Transitive: (2,3)∈R, (3,2)∈R, but (2,2)∉R. Therefore, the relation is not transitive.
d) x≡y(mod7)
“We say integers a and b are “congruent modulo n” if their difference is a multiple of n. For example, 17 and 5 are congruent modulo 3 because 17 – 5 = 12 = 4⋅3, and 184 and 51 are congruent modulo 19 since 184 – 51 = 133 = 7⋅19. We often write this as 17 ≡ 5 mod 3 or 184 ≡ 51 mod 19.” Source.
Reflexive: x-x is a multiple of 7. Therefore, the relation is reflexive.
Symmetric: if x-y is a multiple of 7, then y-x is also a multiple of 7. Therefore, the relation is symmetric.
Antisymmetric: 14-7= 7 is a multiple of 7 and 7-14=-7 is also a multiple of 7. (14,7)∈R and (7,14)∈R. Therefore, the relation is not antisymmetric.
Transitive: if x-y is a multiple of 7 and y-z is a multiple of 7, then x-z is also a multiple of 7. Therefore, the relation is transitive.
e) x is a multiple of y
Reflexive: An integer is always multiple of itself. Therefore, the relation is reflexive.
Symmetric: 4 is a multiple of 2, but 2 is not a multiple of 4. Therefore, the relation is not symmetric.
Antisymmetric: -5 is a multiple of 5 and 5 is a multiple of -5, but 5≠-5. Therefore, the relation is not antisymmetric.
Transitive: If a is a multiple of b, and b is a multiple of c, then a is also a multiple of c. Therefore, the relation is transitive.
f) x and y are both negative or both nonnegative
Reflexive: x is negative or nonnegative, which includes all elements in Z. Therefore, the relation is reflexive.
Symmetric: if x and y are both negative or nonnegative, then y and x are both negative or nonnegative. Therefore, the relation is symmetric.
Antisymmetric: (2,3)∈R and (3,2)∈R. Therefore, the relation is not antisymmetric.
Transitive: if x and y are both negative or nonnegative, and y and z are both negative or nonnegative, then x and z are both negative or nonnegative. Therefore, the relation is transitive.
g) x=y2
Reflexive: (3,3)∉R. Therefore, the relation is not reflexive.
Symmetric: (4,2)∈R and (2,4)∉R. Therefore, the relation is not symmetric.
Antisymmetric: if x=y2 and y=x2, then x=y. Therefore, the relation is antisymmetric.
Transitive: 16=42,4=22, (16,4)∈R and (4,2)∈R, but (16,2)∉R. Therefore, the relation is not transitive.
h) x≥y2
Reflexive: (2,2)∉R. Therefore, the relation is not reflexive.
Symmetric: (10,3)∈R and (3,10)∉R. Therefore, the relation is not symmetric.
Antisymmetric: if x≥y2 and y2≥x, then x=y. Therefore, the relation is antisymmetric.
Transitive: if x≥y2 and y2≥z2, then x≥z2. Therefore, the relation is transitive.
Related exercises:
- Determine whether the relation R on the set of all people is reflexive, symmetric, antisymmetric, and/or transitive, where (a,b)∈R if and only if
- For each of these relations on the set {1, 2, 3, 4}, decide whether it is reflexive, whether it is symmetric, whether it is antisymmetric, and whether it is transitive.
- List the ordered pairs in the relation R from A = {0,1,2,3,4} to B = {0,1,2,3}, where (a,b) ∈ R if and only if