Determine whether the relation R on the set of all integers is reflexive, symmetric, antisymmetric, and/or transitive, where (x,y) ∈ R if and only if 

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

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: