Prove that $\sum_{i=1}^n\lvert[a_i]\rvert$ is even iff $n$ is even

Question

This is problem 8.43 from Mathematical Proofs: A Transition to Advanced Mathematics by Chartrand, Polimeni, Zhang:

Let $A=\{a_1,a_2,\dotsc,a_n\}$ be an $n$-element set and $R$ be an equivalence relation on $A$. Prove that $\sum_{i=1}^n\lvert[a_i]\rvert$ is even iff $n$ is even. Brackets denotes equivalence classes, and vertical bars denote cardinality.

The contrapositive of "If $\sum_{i=1}^n\lvert[a_i]\rvert$ is even, then $n$ is even." is "If $n$ is odd, then $\sum_{i=1}^n\lvert[a_i]\rvert$ is odd.", and the other direction is "If $n$ is even, then $\sum_{i=1}^n\lvert[a_i]\rvert$ is even.". At first I thought of just using induction on the positive odd and even integers but now instead, I want to show

For any $n$-element set $A=\{a_1,a_2,\dotsc,a_n\}$ with $n\in\mathbb{N}$ and any equivalence relation $R$ on $A$, $\sum_{i=1}^n\lvert[a_i]\rvert=n+2k$ for some non-negative integer $k$.

and then both statements follow when we substitute $n$ for positive odd or even integers.

What I have so far:

Let $A=\{a_1,a_2,\dotsc,a_n\}$ be an $n$-element set with $n\in\mathbb{N}$ and let $R$ be an equivalence (eq.) relation on $A$. By definition, eq. relations are reflexive so for any set $S$ to be an eq. relation on $A$, $\{(a_i,a_i):1\leq i\leq n\}\subseteq S$. We have that $\{(a_i,a_i):1\leq i\leq n\}$ is also symmetric and transitive so taking $S=\{(a_i,a_i):1\leq i\leq n\}$, $S$ is an eq. relation. It is clear that $S$ is also the smallest eq. relation on $A$. Additionally, we have that for every $1\leq i\leq n$, $\lvert[a_i]\rvert=1$ so that $\sum_{i=1}^n\lvert[a_i]\rvert=n=n+2k$, where $k=0$.

Now my approach is to have a set of rules which generate every eq. relation on $A$ AND which guarantee the identity $\sum_{i=1}^n\lvert[a_i]\rvert=n+2k$ for some non-negative integer $k$.

More generally, the set of all eq. relations $R$, $\mathrm{Rel}(A)$, where $\lvert A\rvert=n$ for some $n\in\mathbb{N}$, can be described as:
(i) $S=\{(a_i,a_i):1\leq i\leq n\}$ is an eq. relation, and $\sum_{i=1}^n\lvert[a_i]\rvert=n=n+2k$, where $k=0$.
(ii) If $R$ is an eq. relation, then for any $(x,y)\in A\times A$ with $(x,y)\notin S$, $R\cup\{(x,y),(y,x)\}$ is an eq. relation if $R\cup\{(x,y),(y,x)\}$ is transitive, i.e.: $$\forall a,b,c\in A\Bigl(\bigl((a,b)\in R\land(b,c)\in R\bigr)\implies(a,c)\in R\Bigr).$$ We have that $\sum_{i=1}^n\lvert[a_i]\rvert=n+2=n+2k$, where $k=1$.
Else: For any $(z_1,z_2)\in A\times A$ with $(z_1,z_2)\notin S$ and $(z_1,z_2)\neq(x,y)$, $R\cup\{(x,y),(y,x),(z_1,z_2),(z_2,z_1)\}$ is an eq. relation if $R\cup\{(x,y),(y,x),(z_1,z_2),(z_2,z_1)\}$ is transitive. We have that $\sum_{i=1}^n\lvert[a_i]\rvert=n+4=n+2k$, where $k=2$.
Else: $\dotso$ and so on.
(iii) Nothing else is an eq. relation.

The way I guarantee the sum $\sum_{i=1}^n\lvert[a_i]\rvert=n+2k$ for some non-negative integer $k$ is through rule (ii), which which only adds elements in multiples of two to $S$. Each element is not already in $S$ and each element increments some equivalence class $[a_i]$ by 1.

I'm a beginner at proofs so my main questions are:

1. Suppose my set of rules DOES generate every possible eq. relation on $A$ and that (ii) DOES guarantee the desired sum. Is this a valid proof for the original problem 8.43?
2. Does this set of rules actually generate every possible eq. relation on $A$?
3. Does (ii) actually guarantee the desired sum?

EDIT: Mostafa Ayaz's response suggested that I find another formula for the sum.

Suppose we have $m$ distinct eq. classes denoted by $C_i$, and $k_{C_i}$ denote the number of distinct copies of each $C_i$, where $[b]$ is a copy of $[a]$ if $[a]=[b]$. Then $$T=\sum_{i=1}^n\lvert[a_i]\rvert=\sum_{i=1}^mk_{C_i}\lvert C_i\rvert$$ denotes the sum of the cardinality of each $[a_i]$.

To show that $k_{C_i}=\lvert C_i\rvert$, we use the following Theorem:

Let $R$ be an eq. relation on a non-empty set $A$ and let $a$ and $b$ be elements of $A$. Then $[a]=[b]$ iff $(a,b)\in R$.

If $[b]$ is a copy of $[a]$, then $[a]=[b]$, then by the theorem, $(a,b)\in R$ so finally $b\in [a]$. Now $T$ can be written as

$$T=\sum_{i=1}^mk_{C_i}\lvert C_i\rvert=\sum_{i=1}^mk_{C_i}^2$$

I'm stuck at this part and can't see how $k_{C_i}$ relates to $n$ at all.

Answer 1

I have decided to check the solution provided by the textbook. My answer was very similar to it and I kept worrying about transitivity (thus my whole set of rules) when I didn't need to.

Solution:

For $a_i\in A$, $[a_i]=\{x\in A:xRa_i\}=\{x\in A:(x,a_i)\in R\}$. So we have that $\lvert[a_i]\rvert$ counts the ordered pairs in $R$ that have $a_i$ as the second element and so $\sum_{i=1}^n\lvert[a_i]\rvert$ counts all ordered pairs in $R$, that is, $\sum_{i=1}^n\lvert[a_i]\rvert=\lvert R\rvert$. Since $R$ is reflexive, $(a_i,a_i)\in R$ for $i=1,2,\dotsc,n$, and for each pair $i,j$ of distinct integers, either $(a_i,a_j),(a_j,a_i)\in R$ or neither are in $R$. Suppose there are $k$ ordered pairs $(a_i,a_j)\in R$ with $1\leq i<j\leq n$. Then $\lvert R\rvert=n+2k$ and so $\sum_{i=1}^n\lvert[a_i]\rvert$ is even iff $n$ is even.

Answer 2

Assume we have k different equivalence classes denoting by $C_i$ and each of $r_i$ members. Obviously $r_1+...+r_k=n$. Defining $S=\sum_{i=1}^{n}|[a_i]|$ we have:$$S=\sum_{i=1}^{k}\sum_{a_i's \ \ belonging\ \ to \\ ith \ \ class}|[a_i]|=\sum_{i=1}^{k}r_i|[a_i]_{typical}|=\sum_{i=1}^{k}r_i^2$$reminding $\sum_{i=1}^{k}r_i=n$ we can write $S$ as following:$$S=(r_1+...+r_k)^2-2\sum_{i<j}r_ir_j=n^2-2\sum_{i<j}r_ir_j$$this leads us to what we wanted (evenity of $S$ is equivalent to that of $n$).