# Thread: Equivalence classes on an 8x8 chessboard

1. ## Equivalence classes on an 8x8 chessboard

Hi there, I'm struggling a bit with a uni question I've been given. I think I understand the basics but possibly not!! Any help greatly appreciated!

Take a standard 8×8 chessboard, and label the squares
(i, j) 1 ≤ i ≤ 8, 1 ≤ j ≤ 8, with (1, 1) being the bottom lefthand square,
and (8, 8) the top righthand square. Define a relation on these squares by
(i, j) ∼ (i′, j′) iff i + j = i′ + j′.

(a) Show that ∼ defines an equivalence relation on the chessboard.
(b) How many equivalence classes are there, and what are their sizes?
(c) Choose equivalence class representatives for the classes.

Here are my thoughts...
a) would I assume ~ if i+j not equal to i'+j' and show this is not the case?
b) I'm not entirely sure but I would assume that as the canonical projection map is surjective and that there are 64 ways to write i+j that there are 64 equivalence classes of size 2, then again I'm well prepared to believe I've missed the point!
c) As a set of class representatives is a subset of X which contains exactly one element from each equivalence class could the class representative just be either the i's or the j's

Luckily this is over the computer so if people tell me I'm completly wrong you won't see me blushing!!

Thanks for the help, Laura

2. Very often, when approaching a new problem, is it useful to consider several examples. What are all the squares for which the sum of coordinates is 4? 5? This will help you find out almost everything about equivalence classes.

To show that ∼ is an equivalence relation (as well as to show anything in mathematics) one should start with definitions. Once you know the definitions of an equivalence relation and related notions, you need to know what it means to prove the statements involved. Those statements have the form "For all x, ...", so you need to know what it means to prove them.

3. Hello, leshields!

With terms like "canonical projection map" and "surjective",
. . you're overthinking the problem.

Take a standard 8×8 chessboard, and label the squares: . $(i, j)\quad 1 \leq i \leq 8,\;\;1 \leq j \leq 8$

with (1, 1) being the bottom lefthand square, and (8, 8) the top righthand square.

Define a relation on these squares by: . $(i,j) \sim (i',j') \;\;\Longleftrightarrow\;\;i+j \,=\,i' + j'$
Did you make a "sketch"?

. . $\begin{array}{cccccc}
81 & 82 & 83 & 84 & \hdots & 88 \\
\vdots & \vdots & \vdots & \vdots & & \vdots \\
31 & 32 & 33 & 34 & \hdots & 38 \\
21 & 22 & 23 & 24 & \hdots & 28 \\
11 & 12 & 13 & 15& \hdots & 18\end{array}$

Two squares are related by $\sim$ if the sums of their coordinates are equal.

For example: . $(1,4) \sim (2,3) \sim (3,2) \sim (4,1)$

(a) Show that $\sim$ defines an equivalence relation on the chessboard.

Reflexive

Is $(a,b) \sim (a,b)$ ?

$a+b \:=\:a+b\quad\hdots$ Yes, "they" have the same sum.

Symmetric

If $(a,b) \sim (c,d)$, is $(c,d) \sim (a,b)$ ?

Since $(a,b) \sim(c,d)$, we have: . $a+b \,=\,c+d$

Then we have: $c+d \,=\,a+b$, which gives us: . $(c,d) \sim (a,b)$

Yes, the relation is symmetric.

Transitive

If $(a,b) \sim (c,d)$ and $(c,d) \sim (e,f)$, is $(a,b) \sim (e,f)$ ?

Since $(a,b) \sim (c,d)$, we have: . $a+b \,=\,c+d$

Since $(c,d)\sim(e,f)$, we have: . $c+d\,=\,e+f$

Then we have: . $a+b\,=\,e+f$ which gives us: . $(a,b)\sim(e,f)$

Yes, the relation is transitive.

Therefore, $\sim$ is an equivalence relation.

(b) How many equivalence classes are there, and what are their sizes?
There are 15 equivalance classes . . .

. . $\begin{array}{cc}
\text{Sum} & \text{Size} \\ \hline
2 & 1 \\ 3 & 2 \\ 4 & 3 \\ 5 & 4 \\ 6 & 5 \\ 7 & 6 \\ 8 & 7 \\ 9 & 8 \end{array}$

. . . $\begin{array}{cc}

(c) Choose equivalence class representatives for the classes.
I don't know what this means . . .

4. Originally Posted by Soroban
I don't know what this means . . .

You said there were 15 classes. you need to explicitly state one member of each class to represent that class. for example, partitioning the integers according to parity is an equivalence relation. i can choose 0 to be the class representative of the even integers while 1 can be that of the odd integers.