$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), (2,2), (3,3)$
- $(1,1), (1,2), (2,1), (2,2), (3,3)$
- $(1,1), (1,3), (2,2), (3,1), (3,3)$
- $(1,1), (2,2), (2,3), (3,2), (3,3)$
- $(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?
Recall that $A = \{1,\ldots,n\}$ is by construction not empty.
You added:
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).