infinite equivalence classes

820 Views Asked by At

How would you prove that this relation $$(a,b)R(c,d)$$ if and only if $$a+d=b+c$$ has infinite equivalence classes if it is defined in a set with only non negative integers? I've already proved that is an equivalence relation.

2

There are 2 best solutions below

0
On

Hint: when is $(m,0)\mathrel{R}(n,0)$?

0
On

Fix the pair $(a,b)$, and start with any $(c,d)$ it's equivalent to. It's clear that $(c+1,d+1)$ is also going to be equivalent, and distinct from $(c,d)$. So we can take the function $f$ with $f(n)=(c+n,d+n)$ and get a bijection between $\mathbb{N}$ and a subset of the equivalence class.