Question

Question 8

Let R be relation on a set A. 1. When is R said to be an equivalence relation? Give a precise definition, using appropriate quantifiers etc. 2. When is R said to be an partial order? Give a precise definition, using appropriate quantifiers etc (You don't need to redefine things that you defined in the previous part... you may simply mention them to save time.) 3. On Z, define a relation: a D biff a - b is divisible by 5. Show that is an equivalence relation. 4. Under the equivalence relation D, find [7] (that is, the equivalence class of 7). Provide your answer in the "set builder notation", that is, in the form: [7] = {x EZ .........}

Answer 1

(1)

An equivalence relation is a relation that is reflexive, symmetric, and transitive. Reflexive: A relation R on a set A is said to be reflexive if (a, a) ER Va E A. Symmetric: A relation R on a set A is said to be symmetric if Va, b E A, (a,b) ER= (b, a) ER. Transitive: A relation R on a set A is said to be transitive if Va,b,ce A, (a,b) E R and (b, c) ERG (a,c) ER.

(2)

An partial order is a relation that is reflexive, antisymmetric, and transitive. Antisymmetric: A relation R on a set A is said to be antisymmetric if Va, b E A, (a, b) ER and (b, a) ER= a=b.

(3)

Reflexive: Let a e Z. Then, a - a = 0, which is divisible by 5. BaDa = D is reflexive. Symmetric: Let a, b e Z such that a Db. Then, a – b is divisible by 5. = -(a - b) is divisible by 5. = b - a is divisible by 5. =bDa D is symmetric. Transitive: Let a,b,c EZ such that aDb and bDc. Then, a – b is divisible by 5 and b - c is divisible by 5, = (a - b) + (b – c) is divisible by 5. S a - cis divisible by 5. = aDc 3 D is transitive. Hence, D is an equivalence relation.

(4)

[7] = {x € Z17Dx} = {x € Z17 – x is divisible by 5} = {2 E Z|– 7 is divisible by 5} = {2 E Z|– 7 = 5k, k E N} x = 5k + 7, k EN}