2
$\begingroup$

$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?

$\endgroup$
12
  • 4
    $\begingroup$ 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. $\endgroup$
    – lulu
    Jan 18, 2022 at 17:09
  • 2
    $\begingroup$ 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. $\endgroup$
    – hardmath
    Jan 18, 2022 at 17:10
  • 2
    $\begingroup$ Looks fine although I would simply write 5. as $A^2$ rather than listing all of the elements. $\endgroup$ Jan 18, 2022 at 17:11
  • 1
    $\begingroup$ 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. $\endgroup$
    – fleablood
    Jan 18, 2022 at 17:16
  • 1
    $\begingroup$ Looks correct, all three. $\endgroup$
    – Wuestenfux
    Jan 18, 2022 at 17:18

1 Answer 1

1
$\begingroup$

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

You added:

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).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .