1

Let $X =\mathbb N$ . Say $(k, l) ∼\text{di}(m, n)$ if and only if $k + n = l + m$.

  1. Prove that $∼\text{di}$ is an equivalence relation on $X$.
  2. Prove that $\{(m, 1)|m ∈ \mathbb N\} ∪ \{(1, n)|n ∈ \mathbb N, n > 1\}$ is a complete set of representatives for $∼\text{di}$.
TheHolyJoker
  • 2,040
V Harvey
  • 15
  • Welcome to maths SE. Have a look at Mathjax to improve your mathematical expressions. It will be easier to read. – Alain Remillard Jan 12 '20 at 23:55
  • Does $\mathbf N$ comprise $0$ for you? – Bernard Jan 12 '20 at 23:59
  • @Bernard: I don't think it matters. It adds some pairs to the universe, but does not change whether it is an equivalence relation or whether the given pairs form a set of representatives. We could also replace the $1$s with some higher number without changing the result. – Ross Millikan Jan 13 '20 at 00:10
  • @RossMillikan: You're right, but I wondered whether there was a transcription error, as it is so close to the construction of $\mathbf Z$ from $\mathbf N$. – Bernard Jan 13 '20 at 10:15
  • @Bernard: I agree it is a step in the construction of $\Bbb Z$ from $\Bbb N$ but it works fine even if $\Bbb N$ does not include $0$. You just define $(m,1)$ to be $m-1$ in $\Bbb Z$ and $(1,1)$ to be $0$ in $\Bbb Z$. In the spirit of the end of my second paragraph, we could make the pairs be $(m,1000)$ and $(1000,n)$ for $m,n \ge 1000$ and it would work the same. – Ross Millikan Jan 13 '20 at 14:49

1 Answers1

1

They don't say it, but the relation is on ordered pairs of naturals, not on naturals. Once you have proven that $\sim$di is an equivalence relation on $X \times X$ it separates the pairs in $X \times X$ into equivalence classes. In part B you are expected to show that every pair in $X \times X$ is equivalent to exactly one of the given pairs. This also requires showing that no two of the given pairs are equivalent.

For a similar but simpler problem, let our set be $\Bbb Z$, the integers, and the relation being equivalence $\bmod 5$. Part A would ask us to show that this is an equivalence relation. Part B might ask to show that $\{0,1,2,3,4\}$ is a set of representatives, so every integer is equivalent to exactly one of these. It could also ask us to show that $\{-73,41,9,-15,1004\}$ is a set of representatives. This is also a set of representatives, but it is harder to keep track of.

Ross Millikan
  • 374,822
  • So the relation R is the set of ordered Pairs of ordered pairs? – V Harvey Jan 13 '20 at 03:08
  • Aren’t the set of representatives that each element of its equivalent class has other elements in the original set that have the same equivalence class? – V Harvey Jan 13 '20 at 03:17
  • Yes, the relation (but it is $\sim$di) is a (not the) set of ordered pairs of ordered pairs of naturals. I cannot understand your second question. Given an equivalence relation, the universe is split into equivalence classes. A set of representatives is a set that includes exactly one member of each equivalence class. – Ross Millikan Jan 13 '20 at 14:52