Discrete Math: Solve Problem & Describe Equivalence Classes

[barbara]

Can someone help me solve this problem I need to

Define the following relation on the set of real numbers

xRy if |x - y| is an even integer and

Show that R is an equivalence relation and describe the equivalence classes.

 

[I like Serena]

Can someone help me solve this problem I need to

Define the following relation on the set of real numbers

xRy if |x - y| is an even integer and

Show that R is an equivalence relation and describe the equivalence classes.

Hi barbara! Welcome to MHB! (Smile)

From wikipedia:
A given binary relation ~ on a set X is said to be an equivalence relation if and only if it is reflexive, symmetric and transitive. That is, for all a, b and c in X:
1. a ~ a. (Reflexivity)
2. if a ~ b then b ~ a. (Symmetry)
3. if a ~ b and b ~ c then a ~ c. (Transitivity)

In our case X is the set of the real numbers.
Let's start with the first.
We need to verify if for any real number $a$ we have $aRa$.
Since $|a-a|=0$ is an even integer, it follows that indeed $aRa$.

Care to give it a try? (Wondering)

 

[barbara]

Hi barbara! Welcome to MHB! (Smile)

From wikipedia:
A given binary relation ~ on a set X is said to be an equivalence relation if and only if it is reflexive, symmetric and transitive. That is, for all a, b and c in X:
1. a ~ a. (Reflexivity)
2. if a ~ b then b ~ a. (Symmetry)
3. if a ~ b and b ~ c then a ~ c. (Transitivity)

In our case X is the set of the real numbers.
Let's start with the first.
We need to verify if for any real number $a$ we have $aRa$.
Since $|a-a|=0$ is an even integer, it follows that indeed $aRa$.

Care to give it a try? (Wondering)

I have truly don't know how to answer this question even with your example in which I truly appreciate

 

[I like Serena]

I have truly don't know how to answer this question even with your example in which I truly appreciate

Well, if $aRb$, then we have that $|a-b|$ is an even integer.
And we want to verify if that implies $bRa$ (symmetry), which is the case if $|b-a|$ is an even integer.
Does that sound likely to be true? (Wondering)

 

[Deveno]

It's not clear to me, barbara, if your problem is with verifying *this particular relation* is an equivalence relation, or if equivalence relations in general confuse you.

Let me give a very "simple" example. Suppose we define, for some set $S$:

$aRb \iff a = b$. Note we are assuming that both $a,b$ are elements of (or "belong to") the set $S$.

In other words, a relation on set $S$ is a subset of $S\times S$ ("pairs in $S$"), namely the pairs in $S$ that are related.

We could write this as $R \subseteq S \times S$.

Is this $R$ (sometimes $aRb$ is also written as $a\sim b$ ("$a$ is *similar" to $b$)) an equivalence relation?

We have 3 conditions to check:

1. Is every $a$ similar to itself? That is, is every $a$ related to $a$? This property is called reflexiveness. We can also write this as:

is the set $\Delta S = \{(a,a): a \in S\} \subseteq R$? The set $\Delta S$ is called the *diagonal* of $S$, for if we were to display $S \times S$ as a rectangular square grid, with one element of a pair $(a,b)$ (usually the "$a$" being in the horizontal direction) and the other in the vertical direction, the diagonal of $S$ would lie on the diagonal of our square.

Well, for the $R$ I gave above, we must verify that:

$a = a$.

(Don't worry, you don't have to "prove" this-you can take it as given, it's ALWAYS true).

2. If $a$ is similar to (related to) $b$, is $b$ likewise also related to $a$? This property is called symmetry, because it says our relation (considered as a subset of $S \times S$) is "symmetric about the diagonal".

In our case, we must show that if $a = b$ then $b = a$. Again, this is obvious, no proof is needed, but here goes:

If $a = b$, then we may substitute $a$ for any $b$, and vice versa (they are literally the same element), so:

$b = b$ (substituting $b$ for $a$ in the "first place")

$b = a$ (substituting $a$ for $b$ in the "second place").

Not all relations are symmetric, for example, if our set $S$ is "all the women in the world" and $aRb$ means "$a$ is a daughter of $b$", then this relation is not symmetric.

3. The third condition is called "transitivty" and is the hardest to explain-I think of it as "pass-it-along-ness":

If $a \sim b$ AND $b \sim c$ (both of these have to be true), THEN we must have $a \sim c$ true, as well. One often sees this kind of property with things like $\leq$ or $<$:

If $a < b$ and $b < c$, then $a < c$.

On the set of "all people in the world", the relation "is a descendent of" is transitive.

Anyway, so now let's look at our relation:

If $a = b$ and $b = c$, then $a = c$-yes, this is always true. So our relation, called EQUALITY, is an equivalence relation. In fact, our relation consists of *just* the diagonal of $S$, so we can say this:

Equality is a MINIMAL equivalence relation.

Let's turn this around:

Equivalence is an *extension* of (a GENERALIZATION of) equality. So an equivalence is something that "acts" like equality, but isn't quite as restrictive. For example, if $S$ is the set of all nails, we might define an equivalence by saying:

$n_1 \sim n_2$ if $n_1,n_2$ are both the same size nail. In other words, one nail of a given size is "the same" (equivalent) as any other (that is, any two nails of a given size can be used interchangeably, we don't have to use and re-use "the exact same nail" every time).

***************

Now, in your given relation is this problem, things are complicated a bit, by the use of the absolute value, which adds a layer of difficulty to just what would otherwise be some simple algebraic manipulation. Here is a small hint, which I hope will help:

$|b - a| = b - a$ if $a \leq b$

$|b - a| = a - b$ if $b < a$.

Convince yourself that $|k|$ is an integer if and only if $k$ is an integer. Furthermore, that $|k|$ is an even integer if and only if $k$ is an even integer. This will help with the transitivity part.