MHB Discrete Math: Solve Problem & Describe Equivalence Classes

AI Thread Summary
The discussion focuses on defining a relation R on the set of real numbers, where xRy if |x - y| is an even integer. Participants confirm that R is an equivalence relation by verifying its reflexivity, symmetry, and transitivity. Reflexivity is established since |a - a| equals zero, an even integer. Symmetry and transitivity are also explored, emphasizing the properties of absolute values and integer parity. The conversation aims to clarify these concepts and assist in understanding equivalence classes related to the defined relation.
barbara
Messages
10
Reaction score
0
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.
 
Last edited:
Physics news on Phys.org
barbara said:
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)
 
I like Serena said:
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
 
barbara said:
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)
 
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.
 
Back
Top