Is it possible to have an equivalence relation with exactly $n + 1$ elements on $A$?

$$A = \{1,2,\dots,n\}$$, and $$R$$ be a relation on $$A$$ (so that $$R \subset A \times A$$).

i) Is it possible to have an equivalence relation with exactly $$n+1$$ elements on $$A$$? If yes, give an example, if no, explain why?

For this I considered what adding an extra element from the possible relations would do. For example from $$R = \{(1,1),(2,2),(3,3)\}$$ adding an extra element $$(1,2)$$ would stop the relation from being symmetric, meaning adding in just one element would prevent this from being an equivalence relation. So you cannot have an equivalence relation with exactly $$n+1$$ elements in.

ii) Is it possible to have an equivalence relation with exactly $$n+2$$ elements on $$A$$? If yes, give an example, if no, explain why?

My reasoning for this question follows a similar patter to I, two elements could be added that allow it maintain being an equivalence relation. Adding in $$(1,2)$$ and $$(2,1)$$ would ensure it was still symmetric, and so still an equivalence relation.

iii) When $$n = 3$$, give all possible equivalence relations on $$A$$.

For this question I considered what adding in specific extra elements would require to be included in the final set.

1. $$(1,1), (2,2), (3,3)$$
2. $$(1,1), (1,2), (2,1), (2,2), (3,3)$$
3. $$(1,1), (1,3), (2,2), (3,1), (3,3)$$
4. $$(1,1), (2,2), (2,3), (3,2), (3,3)$$
5. $$(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)$$

Are my answers and reasoning correct?

Also, should $$\emptyset$$ be included as an equivalency relation for III?

• Well, to generalize your approach, since we must have the $n$ elements $(k,k)$ for each $k$, a new element would have to be of the form $(i,j)$ for $i\neq j$. But then we need $(j,i)$ as well, hence at least $n+2$ elements.
– lulu
Jan 18, 2022 at 17:09
• Your reasoning on the first two parts look good to me. When trying to list all the possible equivalence relationships on (say) $\{1,2,3\}$, it might be helpful to see that an equivalence relation amounts to a partition of the set. Jan 18, 2022 at 17:10
• Looks fine although I would simply write 5. as $A^2$ rather than listing all of the elements. Jan 18, 2022 at 17:11
• i) Your reasoning on the first part is fine but you need to make it more general. What if $n > 3$ and what if the element you are adding isn't $(1,2)$. ii) ditto but how do you know it is transitive. Jan 18, 2022 at 17:16
• Looks correct, all three. Jan 18, 2022 at 17:18

Recall that $$A = \{1,\ldots,n\}$$ is by construction not empty.

Also, should ∅ be included as an equivalency relation for III?

No. While the empty set is a relation (a subset of $$A\times A$$), it is not an equivalence relation. It is not reflexive.

The observation in my earlier Comment, that an equivalence relation on $$A$$ corresponds to a partition of the set $$A$$, has been discussed here before. We can use this idea to give a more formal justification of your ideas for parts 1,2,3.

By definition each of the $$n$$ elements of $$A$$ belong to one and only one equivalence class that appears in the corresponding partition of $$A$$.

If we are interested in counting the number of ordered pairs in such equivalence relations, it can be determined from the corresponding sizes of the equivalence classes that partition $$A$$, namely the integer partitions of $$n = |A|$$.

The smallest case is $$n = 1 + 1 + \ldots + 1$$ corresponding to the equality relation on $$A$$, i.e. using singleton subsets to partition $$A$$. The size of the equivalence relation is the sum of squares of the integer parts:

$$1^2 + 1^2 + \ldots + 1^2 = n$$

Since any other equivalence relation will have more relations, we can solve part (1) by observing that putting any two elements of $$A$$ into the same equivalence class would create four ordered pairs in place of the two that merely relate those two elements to themselves:

$$2^2 + 1^2 + \ldots + 1^2 = 4 + (n-2) = n + 2$$

This not only answers (1) being impossible, it shows (2) is always possible (as long as $$A$$ contains more than one element).