PDA

View Full Version : Equivalence Classes: (x,y) rho (z,w) iff x+y = z+w

may
05-29-2007, 12:19 PM
I don't really know how this work, but I have a question. In class, we've just gone over equivalence classes. The book doesn't really go over it too well. Anyways, the problem I'm stuck with is as follows:

Allow S = N x N, where N is the set of all natural numbers, and allow rho to equal a binary relation on S defined by (x,y) rho (z,w) <-> x +y = z +w. Show that rho is an equivalence relation on S and describe the resulting equivalence classes.

This is how I started. I showed reflexivity, (x,y) rho (x,y), because y = y here. I then showed symmetricity. If (x,y) rho (z,w), then y = w so w = y and (z, w) rho (x,w).

Next, I did transitivity. I said if (x,y) rho (z,w) and (z,w) rho (s,t), then y = w and w = t, so y = t and (x,y) rho (s,t).

I have no idea on how to incorporate the x + y = z +w, nor figure out what the equivalence classes are.

pka
05-29-2007, 02:11 PM
Allow S = N x N, where N is the set of all natural numbers, and allow rho to equal a binary relation on S defined by (x,y) rho (z,w) <-> x +y = z +w. Show that rho is an equivalence relation on S and describe the resulting equivalence classes. It appears as if you are confusing several different ideas.
Given the relation, \L (a,b)\rho (x,y)\quad \Leftrightarrow \quad a + b = x + y

\L \begin{array}{l}
a + b = x + y\quad \Leftrightarrow \quad x + y = a + b\quad \text{symmetric.} \\
\end{array}

Now you try transitivity.

may
05-29-2007, 06:03 PM
Okay, so I was on the right track. It was just instead of saying y = y, it was x+y = x+y and so forth. I had the idea right for transitivity, just change the terms? Thanks.

pka
05-29-2007, 06:43 PM
I have no idea on how to figure out what the equivalence classes are. This a interesting question. Let’s suppose that N = \left\{ {0,1,2,3, \cdots } \right\}, that is N contains 0. Now the equivalence classes of (a,b)\rho (x,y)\quad \Leftrightarrow \quad a + b = x + y are determined by each element in N.
The equivalence class determined by 0, \rho /0 = \left\{ {(0,0)} \right\}.
Here are some more examples:
\begin{array}{l}
\rho /2 = \left\{ {(0,2),(2,0),(1,1)} \right\} \\
\rho /4 = \left\{ {(0,4),(4,0),(1,3),(3,1),(2,2)} \right\} \\
\end{array}.

The number of pairs in \rho /n is n+1.