0
$\begingroup$

Suppose R is an equivalence relation on a set A, with four equivalence classes. How many different equivalence relations S on A are there for which R is a subset of S?

I understand this question has been asked before and answered by several users. However, I am not convinced the answers of 15 given the "merging" of equivalence classes is correct in general. Consider the equivalence relation congruence modulo 4 on the set of integers. This relation has four distinct equivalence classes but the set of integers can have an infinite amount of equivalence relations, S, for which R can be a subset of any if we take R to be the relation that consists of only ordered pairs of the form (x, x) for all integers.

I would truly appreciate clarification on this point. Perhaps, I am thinking about this incorrectly but after considering any equivalence relation on the set of integers can contain all elements of R as described above in addition to any number of other elements that maintain the properties of being symmetric and transitive, It seems unlikely to me that the correct answer is 15 and not infinite for an infinite set. It would make sense if the set A is finite and thus, given 4 distinct equivalence classes of R, must have four distinct elements since R is an equivalence relation. But, otherwise, these answers seem wrong.

$\endgroup$
7
  • $\begingroup$ Your example is not clear. You appear to start with the equivalence relation on $\mathbb Z$ given by congruence $\pmod 4$, but then you appear switch to the equivalence relation in which each integer is only equivalent to itself. Please clarify your example. Also, please provide the link to the prior versions of this question. $\endgroup$ Commented Sep 9, 2018 at 21:44
  • $\begingroup$ math.stackexchange.com/questions/329371/… $\endgroup$ Commented Sep 9, 2018 at 21:45
  • $\begingroup$ If $R$ and $S$ are both equivalence relations on $A$ and $R\subseteq S$ then $aRb\implies aSb$ showing that $[a]_R\subseteq[a]_S$ for every $a\in A$. Do you agree with that? Here $[a]_R$ denotes the equivalence class linked with $R$ and represented by $a\in A$. $\endgroup$ Commented Sep 9, 2018 at 21:47
  • $\begingroup$ @lulu, I apologize. I am new to stack exchange and not entirely accustomed to using it. You are correct, I was wrong in switching from one example to another. The latter would have an infinite amount of equivalence classes. What I should have said is take any other equivalence relation on the set of integers that contains all elements of R when R is the equivalence relation congruence (mod 4). For example, add the elements (0,2) and (2,0) and call this relation S. Then, S has more than 4 equivalence classes as 4xR0 for any integer x but, 2R0 as well. $\endgroup$ Commented Sep 9, 2018 at 21:56
  • $\begingroup$ @drhab. I see. Perhaps, I should trek on a little further in the chapter I am currently reading about relations. I have not yet gotten to partitions and what the term coarser would mean. But, I do agree with the claim in your first comment. $\endgroup$ Commented Sep 9, 2018 at 21:59

1 Answer 1

Reset to default
0
$\begingroup$

Equivalence relations on a set correspond one-to-one with partitions of that set.

The question can actually be rephrased as:

"If $P$ is a partition on set $A$ and has $4$ elements then how many partitions on $A$ exist that are coarser than $P$?"

A partition $Q$ is by definition coarser than partition $P$ if every element of $P$ is a subset of an element of $Q$.

The answer is $15$.

$\endgroup$
2
  • $\begingroup$ Thank you, @drhab. I appreciate the information and suggestion greatly and will get to that as soon as possible. This problem has been quite vexing for several days and I was obstinate in refraining from proceeding in the chapter prior to understanding this answer. $\endgroup$ Commented Sep 9, 2018 at 22:03
  • $\begingroup$ You are very welcome. $\endgroup$ Commented Sep 9, 2018 at 22:04

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.