MHB Glad I could help! Good luck with your studies.

[the rambler]

Hi guys! First time poster, long time lurker! I can't make any sense out of equivalence relations These kinda questions crop up every year on the exam and I was wondering if someone could help me understand the concept behind them.

(i)Show that relation R defined on the of the
set S = {0, 1, . . . , 99} as R = {(a, b) € S × S : a − b is a multiple of 25} is an
equivalence relation.
I understand that to show something is an equivalence relation you need to show that they are reflexive, symmetric and transistive but I've no idea how to apply that to a question like this?

(ii) How many elements does the R-equivalence class of
a = 73 have?

Would this be 4? As in 73 itself, 73-25= 48, 73-50=23 and 73+25= 98

(i) Show that relation ~ defined on the set X = N x N = {(a, b) : a € N; b € N} as
(a,b)  (c,d) if and only if a + d = c + b
is an equivalence relation. (ii) Write down three elements of the equivalence class of
(12, 7). What do they all have in common?

[€ = an element of]

No clue at all hereExcuse my very humble attempts at answering the questions (Blush) Any help at all would be very much appreciated :)

 

[Fermat1]

Hi guys! First time poster, long time lurker! I can't make any sense out of equivalence relations These kinda questions crop up every year on the exam and I was wondering if someone could help me understand the concept behind them.

(i)Show that relation R defined on the of the
set S = {0, 1, . . . , 99} as R = {(a, b) € S × S : a − b is a multiple of 25} is an
equivalence relation.
I understand that to show something is an equivalence relation you need to show that they are reflexive, symmetric and transistive but I've no idea how to apply that to a question like this?

(ii) How many elements does the R-equivalence class of
a = 73 have?

Would this be 4? As in 73 itself, 73-25= 48, 73-50=23 and 73+25= 98

(i) Show that relation ~ defined on the set X = N x N = {(a, b) : a € N; b € N} as
(a,b)  (c,d) if and only if a + d = c + b
is an equivalence relation. (ii) Write down three elements of the equivalence class of
(12, 7). What do they all have in common?

[€ = an element of]

No clue at all hereExcuse my very humble attempts at answering the questions (Blush) Any help at all would be very much appreciated :)

$a$ is related to $b$ if $a-b$ is a multiple of 25. $a$ is related to $a$ since 0 is a multiple of 25. The relation is symmetric since $a-b$ is a multiple of 25 implies $b-a$ is a multiple of 25. You do transitivity.

For ii) You need to find the set of $b$ in S such that $73-b$ is a multiple of 25.Clearly the set of suitable $b$ is {23, 48,73,98}

You should now have a better idea how to answer the remaining questions

 

[the rambler]

$a$ is related to $b$ if $a-b$ is a multiple of 25.

It seems so simple but this is the bit I couldn't grasp! The notation completely threw me off.. Thanks so much :D

 

[Deveno]

There are a couple of different ways to express an equivalence relation on a set $S$, both are used, although one often sees this form:

$a \sim b$ as meaning: "$a$ is related to $b$" (also called "infix symbol notation").

In accordance with this, the equivalence class of $a$, written $[a]$ (usually), is the set:

$\{x \in S: a \sim x\}$.

However, a relation $R$ on $S$, (of which equivalence relations are "special kinds") is just a subset of $S \times S$. So one also sees the notation:

$(a,b) \in R$

instead of $a \sim b$. They mean the same thing.

**********

Here is another way to look at your problem:

For any function $f:A \to B$, we can define $a \sim a'$ (these are two elements of $A$) if $f(a) = f(a')$. It would be well worth your while to prove this indeed does define an equivalence relation on $A$. This is called the equivalence relation induced by the function $f$.

So...what would our function be, in this case?

Well, given any natural number $n$, we can write:

$n = 25q_n + r_n$ for a pair of UNIQUE natural numbers $q_n,r_n$ ($q_n$ is called the QUOTIENT, and $r_n$ the REMAINDER).

Convince yourself that this means we have a function:

$f:\Bbb N \to \{0,1,2,\dots,24\}$ given by:

$f(n) = r_n$.

This is still a function if we restrict our domain to $S = \{0,1,2,\dots,99\} \subseteq \Bbb N$

Finally, can you see that we have: $a \sim b$ (that is: $a - b = 25k$ for some integer $k$) if and only if $r_a = r_b$?

 

[the rambler]

There are a couple of different ways to express an equivalence relation on a set $S$, both are used, although one often sees this form:

$a \sim b$ as meaning: "$a$ is related to $b$" (also called "infix symbol notation").

In accordance with this, the equivalence class of $a$, written $[a]$ (usually), is the set:

$\{x \in S: a \sim x\}$.

However, a relation $R$ on $S$, (of which equivalence relations are "special kinds") is just a subset of $S \times S$. So one also sees the notation:

$(a,b) \in R$

instead of $a \sim b$. They mean the same thing.

**********

Here is another way to look at your problem:

For any function $f:A \to B$, we can define $a \sim a'$ (these are two elements of $A$) if $f(a) = f(a')$. It would be well worth your while to prove this indeed does define an equivalence relation on $A$. This is called the equivalence relation induced by the function $f$.

So...what would our function be, in this case?

Well, given any natural number $n$, we can write:

$n = 25q_n + r_n$ for a pair of UNIQUE natural numbers $q_n,r_n$ ($q_n$ is called the QUOTIENT, and $r_n$ the REMAINDER).

Convince yourself that this means we have a function:

$f:\Bbb N \to \{0,1,2,\dots,24\}$ given by:

$f(n) = r_n$.

This is still a function if we restrict our domain to $S = \{0,1,2,\dots,99\} \subseteq \Bbb N$

Finally, can you see that we have: $a \sim b$ (that is: $a - b = 25k$ for some integer $k$) if and only if $r_a = r_b$?

This makes a lot more sense now! Thank you :)