Relation Problem

Let Z denote the set of integers. Which of the following relations E are equivalence relations? Explain.

(a) xEy (if and only if) x – y is an even integer
(b) xEy (if and only if) x – y is an odd integer

*I seem to have a lot of trouble on these relation type problems. Thank you to everybody who has helped me with these problems.

The thing that stands out at is that the only difference above is one is even and one is odd. Also, I know I will have to use Reflexivity, Symmetry, Transitivity to solve the problem.

Quote:

---

Originally Posted by MathStudent1

Let Z denote the set of integers. Which of the following relations E are equivalence relations? Explain.

(a) xEy (if and only if) x – y is an even integer
(b) xEy (if and only if) x – y is an odd integer

*I seem to have a lot of trouble on these relation type problems. Thank you to everybody who has helped me with these problems.

The thing that stands out at is that the only difference above is one is even and one is odd. Also, I know I will have to use Reflexivity, Symmetry, Transitivity to solve the problem.

---

For this type of questions you need to be familiar with definitions.

Here are the definitions you need:

Reflexive - A relation R on a set A is called reflexive if we have xRx for all x in A. That is, every element in A maps to (is related to) itself

Symmetric - A relation R on a set A is called symmetric if whenever xRy, then yRx for all x,y in A. That is, xRy => yRx. Note => means "implies" which is a logical operator.

Transitive - A relation R on a set A is called transitive if whenever xRy and yRz, then xRz for all x,y,z in A. That is, (xRy ^ yRz) => xRz. Note ^ here represents the logic symbol "and."

Equivalence Relation - A relation R on a set A is called an Equivalence Relation if R is reflexive, symmetric and transitive.

other things to note: iff and <=> mean "if and only if"

Now to answer your question.


(a) xEy (if and only if) x – y is an even integer

We show that E here is an equivalence relation.

Note that we have x - y being even <=> x,y are of the same parity, that is, they are both even or both odd at the same time. Thus E is reflexive, since every even number and every odd number is related to itself, that is, we have xEx for all x in Z.

Moreover, we have E symmetric. Since if x - y is even, then y - x is even, that is xEy => yEx.

Finally, we show that E is transitive. If x - y is even, and y - z is even, then x, y and z are of the same parity, and so x - z is even. That is, xEy and yEz => xEz.

Since E is reflexive, symmetric and transitive, E is an equivalence relation.


(b) xEy (if and only if) x – y is an odd integer

We show E is not an equivalence relation. Note that we have x - y odd <=> x and y are of opposite parities, that is, if x is even, y must be odd, and if x is odd, y must be even. Thus we do not have have any even number or any odd number related to itself, that is, we do not have xEx for any x in Z. This means E is not reflexive and hence cannot be an equivalence relation.

Thank you Jhevon. One thing I need a little clarifiction on is below. The part in bold is what I am thinking about.

Note that we have x - y being even <=> x,y are of the same parity, that is, they are both even or both odd at the same time. Thus E is reflexive, since every even number and every odd number is related to itself, that is, we have xEx for all x in Z.

I think I am confused since it said x - y is an even integer.

Thanks!

Quote:

---

Originally Posted by MathStudent1

Thank you Jhevon. One thing I need a little clarifiction on is below. The part in bold is what I am thinking about.

Note that we have x - y being even <=> x,y are of the same parity, that is, they are both even or both odd at the same time. Thus E is reflexive, since every even number and every odd number is related to itself, that is, we have xEx for all x in Z.

I think I am confused since it said x - y is an even integer.

Thanks!

---

well, think about it. if you subtract one evn number from another, you get an even number, same thing if you subtract one odd number from another.

consider these four cases:

case 1: x and y are both even.
since x and y are even, x = 2n and y = 2m for some n,m in Z. so x - y = 2n - 2m = 2(n - m). Since (n - m) is in Z, we have 2(n - m) being an even integer.


case 2: x and y are both odd.
Since x and y are odd, x = 2n + 1 and y = 2m + 1 for some n,m in Z. So x - y = 2n + 1 - (2m + 1) = 2(n - m) which is an even integer

case 3: x is even, y is odd.
since x is even and y is odd, x = 2n and y = 2m + 1 for some n,m in Z. so x - y = 2n - (2m + 1) = 2n - 2m - 1 = 2n - 2m -2 + 1 = 2(n - m - 1) + 1 which is odd

case 4: x is odd, y is even.
since x is odd and y is even, x = 2n + 1 and y = 2m for some n,m in Z. so x - y = 2n + 1 - 2m = 2(n - m) + 1 which is odd.

so you see, we only have x - y yielding an even integer when they are of the same parity.

Got it! Thank you!