7
$\begingroup$

I would like find the system of representatives & equivalence class for $[(1,-1)]_{\equiv 1}$ and $[(1,-1)]_{\equiv 2}$ given:

$R_1=_{def.} (x_1,y_1)\equiv(x_2,y_2) \Leftrightarrow x_1+y_1=x_2+y_2$

$R_2=_{def.} (x_1,y_1)\equiv(x_2,y_2) \Leftrightarrow \min(x_1,y_1)=\min (x_2,y_2)$

I always have trouble to understand and define equivalence class & relations and co. Here I thought:

For $R_1$:

Given $[(1,-1)]_{\equiv 1}$ the equivalence class must be set of tuples such that the sum of the two equals zero that is $\{(x,y)|x+y=0\}$ because $\{(x,y)|1+(-1)=0\}$ which meet the criteria in the definition. And for the system of representatives I thought of $\{(x,1)|x \in \mathbb{N} \}$ (more or less a guess)

For the $R_2$ I thought: Given $[(1,-1)]_{\equiv 2}$ the equivalence class must be set of tuples such that the minimum equals the smalles component in the relation that is $\{(x,y)|\min(x,y)=-1\}$. For the system of representatives I just dont have any clue.

Thanks in advance!

$\endgroup$
2
$\begingroup$

You have defined two relations on ${\mathbb R}^2$. Both are defined by a certain function on ${\mathbb R}^2$ taking equal values on equivalent points and different values on unequal points. For $R_1$ this function is $f_1(x,y):=x+y$, and for $R_2$ this function is $f(x,y):=\min\{x,y\}$.

A "canonical representation" of the quotient set for $R_1$ would be the set of values of $f_1$, which of course is ${\mathbb R}$. But you want a set of representatives in ${\mathbb R}^2$. I propose the line $$\ell:=\{(t,t)\>|\>t\in{\mathbb R}\}\ .$$ This line contains exactly one point for every value of $f_1$. The set of all points in the equivalence class represented by $(t,t)$ is the line with slope $-1$ passing through the point $(t,t)$: $$[(t,t)]_{R_1}=\{(x,y)\in{\mathbb R}^2\>|\>x+y=2t\}\ .$$

A "canonical representation" of the quotient set for $R_2$ would be the set of values of $f_2$, which again is ${\mathbb R}$, and a set of representatives is again given by the line $\ell$: This line contains exactly one point for every value of $f_2$. This time the set of all points in the equivalence class represented by $(t,t)$ is the L-shaped union of a horizontal and a vertical ray: $$[(t,t)]_{R_2}=\{(x,t)\>|\>x\geq t\}\cup\{(t,y)\>|\>y\geq t\}\ .$$

$\endgroup$
1
$\begingroup$

For the first one, you are on the right track. As you noted, if you have any $(x, y) \equiv_1 (1, -1)$ then $x + y = 1 + (-1) = 0$, and so you are looking for the collection of all $(x, y)$ such that $x + y = 0$. That is, you are looking for pairs $(x, y)$ such that $y = -x$, or: $$ [(1, -1)]_1 = \{(x, y) \in S \times S \mid x + y = 0\} = \{(x, -x) \mid x \in S\} $$ where $S$ is either $\mathbb{Z}$ or $\mathbb{R}$ or whatever else may be appropriate.

$\endgroup$
  • $\begingroup$ Though I like your answer, it only adresses one quarter of the questions being asked. (+1) For introducing $S$ since the base set was left unspecified! $\endgroup$ – String Mar 30 '15 at 13:46
1
$\begingroup$

For the first one you have the specific equivalence class $$ [(1,-1)]_1=\{(x,y)\mid y=-x\} $$ The general representatives for all classes are $\{(x,y)\mid y=-x+k\}=[(0,k)]_1$ where each choice of $k$ defines a class. I elaborate on those representatives further down.


For the second one you have the specific equivalence class $$ [(1,-1)]_2=(\{-1\}\times[-1,\infty))\cup([-1,\infty)\times\{-1\}) $$ The representatives for all classes are $[(k,k)]_2$ where each choice of $k$ defines a class.


A little further elaboration:

For $R_1$, an equivalence class is determined by the value of $x+y$. Let this value be denoted $k$. Then $x+y=k\iff y=-x+k$ is a specific line with slope $-1$ and intercept $k$.

For $R_2$, and equivalence class is determined by either $k=x\leq y$ or $k=y\leq x$. Thus either $x=k$ and $y\in[k,\infty)$ or $y=k$ and $x\in[k,\infty)$. One natural representative is to choose $x=y=k$ which then gives rise to representatives $[(k,k)]_2$

$\endgroup$
1
$\begingroup$

Everything you solved is correct as far as I can see. It's interesting to consider what the equivalence classes actually end up being in terms of geometry though. Notice that the first relation has equivalence classes which are just lines with slope -1. (This nicely gives you that your choice for representatives makes sense).

Let's think about what the equivalence classes for the second relation are. Since the minimum is fixed what do we get? Well you can essentially split it in two pieces either $x=\min(x,y)=m$ then you get all points $(m,y)$ (but don't forget that $y$ is in some way restricted (how?)). Or you have $y=\min(x,y)=m$ in which case you get all points $(x,m)$, but again $x$ is restricted (how?). If you figure out how these restrictions and thus the equivalence classes look you should have no problem finding a set of representatives.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.