# How do I work with a relation that is a set of 4-tuples?

Define the relation $\sim$ on $\mathbb{Z}\times\mathbb{Z}$ by $(a,b)\sim(c,d)$ if $a-c=b-d$. Show that $\sim$ is an equivalence relation. What is the equivalence class of $(1,2)$?

I'm not sure how to approach this since I've never had to deal with 4-tuples before.

-
The relation is not a set of 4-tuples. The relation is between ordered pairs of integers. The relation is a set of pairs of ordered pairs of integers. –  Ross Millikan Apr 9 '13 at 0:02

For every $(a,b)\in\mathbb Z\times\mathbb Z$, $a-a=0=b-b$. Hence the relation is reflexive.

For every $(a,b),(c,d)\in\mathbb Z\times\mathbb Z$, if $a-c=b-d$, then $c-a=d-b$. Hence the relation is symmetric.

For every $(a,b),(c,d),(e,f)\in\mathbb Z\times\mathbb Z$, if $a-c=b-d$ and $c-e=d-f$, then $a-e=(a-c)+(c-e)=(b-d)+(d-f)=b-f$. Hence the relation is transitive.

The class of $(1,2)$ is simply the set of all ordered pairs of integers $(a,b)$ such that $a-1=b-2$. This means $\{(x,x+1):x\in\mathbb Z\}$.

-

Maybe it would help to rewrite $a-c=b-d$ as $a-b=c-d$. Note that if $a=1$ and $b=2$, then $a-b=-1$. So the $(c,d)$ that are equivalent to $(1,2)$ are all $(c,d)$ such that $c-d=-1$.

Let's think of some: $(10,11)$; $(47,48)$: and so on. Also $(-17,-16)$, and so on.

Remark: It is not really $4$-tuples that you are dealing with here. It is ordered pairs (as usual), but this time it is ordered pairs of ordered pairs.

-

After proving that $\sim$ is an equivalence relation, try to study $$(a,b)\sim (1,2) \Leftrightarrow a-1=b-2,$$ that is $$a-b=-2+1=-1.$$ So you are looking for pairs $(a,b)$ with $b=a+1$.

-

It’s no different from what you’ve done before; the notation is just a bit more complicated. For instance, to show that $\sim$ is symmetric, you have to show that if $\langle a,b\rangle,\langle c,d\rangle\in\Bbb Z\times\Bbb Z$, and $\langle a,b\rangle\sim\langle c,d\rangle$, then $\langle c,d\rangle\sim\langle a,b\rangle$. Go back to the definition of $\sim$ to see what this really means.

• $\langle a,b\rangle\sim\langle c,d\rangle$ means that $a-c=b-d$; this is your hypothesis.

• $\langle c,d\rangle\sim\langle a,b\rangle$ means that $c-a=d-b$; this is what you need to prove in order to show that $\sim$ is symmetric. And this is easy to do: $c-a=-(a-c)\overset{*}=-(b-d)=d-b$, where the starred step uses the hypothesis that $\langle a,b\rangle\sim\langle c,d\rangle$.

Now see if you can prove reflexivity and transitivity on your own.

The equivalence class of $\langle 1,2\rangle$ is the set of all $\langle a,b\rangle$ such that $\langle 1,2\rangle\sim\langle a,b\rangle$, i.e., such that $1-a=2-b$; solve this to find what $b$ must be in terms of $a$ in order for $\langle a,b\rangle$ to be in the equivalence class.

-
I'm a bit confused - this looks to me like the relation will contain 4-tuples like $\sim=\{(a_{1},b_{1},c_{1},d_{1}),\dots ,(a_{n},b_{n},c_{n},d_{n})\}$ is that not the case? Or is that not even relevant? –  agent154 Feb 8 '13 at 0:38
@agent154, the relation is just a way to identify some pairs of integers. You have infinite number of pairs identified and also infinite number of equivalence classes. –  Sigur Feb 8 '13 at 0:43
@agent154: It’s not quite right: the relation contains ordered pairs of ordered pairs. For instance, $\langle 1,2\rangle\sim\langle 2,3\rangle$, so the relation contains the ordered pair $$\Big\langle\langle 1,2\rangle,\langle 2,3\rangle\Big\rangle\;.$$ However, you don’t need to worry about any of this in order to do the problem. Just use the same approach to reflexivity and transitivity that I used to prove symmetry. –  Brian M. Scott Feb 8 '13 at 0:43

Hint $\rm\ \ (a,b)\sim (c,d)\smash[t]{\overset{\ def}{\iff}} a\!-\!b = c\!-\!d \iff f(a,b) = f(c,d)\$ for $\rm\ f(x,y) = x\!-\!y$

More generally, suppose $\rm\: u\sim v\ \smash[t]{\overset{\ def}{\iff}}\, f(u) \approx f(v)\:$ for a function $\rm\,f\,$ and equivalence relation $\,\approx.\$ Then the equivalence relation properties of $\,\approx\,$ transport to $\,\sim\,$ by using the definition:

• reflexive $\rm\quad\ f(v) \approx f(v)\:\Rightarrow\:v\sim v$

• symmetric $\rm\,\ u\sim v\:\Rightarrow\ f(u) \approx f(v)\:\Rightarrow\:f(v)\approx f(u)\:\Rightarrow\:v\sim u$

• transitive $\rm\ \ \ u\sim v,\, v\sim w\:\Rightarrow\: f(u)\approx f(v),\,f(v)\approx f(w)\:\Rightarrow\:f(u)\approx f(w)\:\Rightarrow u\sim w$

Such relations are called (equivalence) kernels. One calls $\, \sim\,$ the $\,(\approx)\,$ kernel of $\rm\,f.$

-