MHB Discrete Math: Solve Problem & Describe Equivalence Classes

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.
 
Namaste & G'day Postulate: A strongly-knit team wins on average over a less knit one Fundamentals: - Two teams face off with 4 players each - A polo team consists of players that each have assigned to them a measure of their ability (called a "Handicap" - 10 is highest, -2 lowest) I attempted to measure close-knitness of a team in terms of standard deviation (SD) of handicaps of the players. Failure: It turns out that, more often than, a team with a higher SD wins. In my language, that...
Hi all, I've been a roulette player for more than 10 years (although I took time off here and there) and it's only now that I'm trying to understand the physics of the game. Basically my strategy in roulette is to divide the wheel roughly into two halves (let's call them A and B). My theory is that in roulette there will invariably be variance. In other words, if A comes up 5 times in a row, B will be due to come up soon. However I have been proven wrong many times, and I have seen some...
Back
Top