# How to find a representative of an equivalence relation on $\omega\times\omega$

In one of my exercises we are shown that the relation "$\sim$" is defined as the following:

$$\langle n,m \rangle \sim \langle k,l \rangle \iff |(n\setminus m)| = |(k\setminus l)|$$

in which $|X|$ symbolizes the number of elements of the set. We need to:

(a) Show that "$\sim$" is a equivalence relation on $\omega\times\omega$.

(b) Find a "representative system" ("system of representatives") of this equivalence relation.

For part (a) it is straight forward, we show that it is reflexive, symmetric and transitive. But for part (b) I am stuck. So far I think I have an understanding of the definition for a representative, in terms of this exercise.(Please correct me if I am wrong):

I understand that if "$\sim$" is an equivalence relation on $\omega\times\omega$, then for $x \in \omega\times\omega$, the set

$[x]_{\sim} = \{ y \in \omega\times\omega : y\sim x\}$ is called an equivalence class of $x$. So every $y \in [x]_{\sim}$ (i.e $y\sim x$) is then called a "representative" of the equivalence class of $x$.

However I am lost on how to apply this definition to the question. Some guidance would be very much appreciated. Thank you in advance.

• @HenningMakholm I noticed your edits, is there a difference between |n\m|=|k\l| and |(n\m)|=|(k\l)| ? because in my exercise it is written with parenthesis. – math189925 Feb 2 '15 at 13:12
• x @math: Sorry, I've reinserted the parentheses. I'm not aware of any context where $|(n\setminus m)|$ would mean something different from $|n\setminus m|$. – hmakholm left over Monica Feb 2 '15 at 13:14
• If you put $m=\emptyset$, is there exactly one $n$ such that $\langle n,\emptyset \rangle$ belongs to a given equivalence class? – Martin Sleziak Feb 2 '15 at 14:16

Each equivalence class is described by a natural number, and contains all pairs $\langle n,m\rangle$ such that $n\setminus m$ has that many elements. (Since $n$ is always finite, $n\setminus m$ will always be finite too).
So what you need to do is simply, for each natural number $k$, to decide on one particular pair $\langle n_k,m_k\rangle$ where $n_k\setminus m_k$ has $k$ elements.