1
$\begingroup$

Some definitions that I am aware of:

  1. Equivalence relation: Is reflexive, symmetric and transitive
  2. Equivalence class of $a$ under equivalence relation $R$ $[a]_R$: set of all elements that are related to an element a
  3. Partition and Equivalence class:
    • A partition of a set S is a collection of disjoint nonempty subsets of S that have S as their union.
    • Thus, equivalence classes of an equivalence relation on a set form a partition of the set.
  4. POSET / Partial Ordering: Is antisymmetric, reflexive, transitive relation.
  5. TOSET / Totally ordered POSET: POSET with every two elements in the set are comparable

The question

Suppose $A=\{a,b,c,d\}$ and $π_1$ is the following partition of A $π_1=\{\{a,b,c\}\{d\}\}$. List the ordered pairs of the equivalence relations induced by $π_1$.

The answer given

$\{(a,a),(a,b),(a,c),(b,a),(b,b),(b,c),(c,a),(c,b),(c,c),(d,d)\}$

My doubt
Equivalence relation is reflexive, symmetric and transitive. But that does not means that all symmetric and transitive pairs should be there in the equivalence class, right? We can just have reflexive pairs also, right? Like this: $\{(a,a),(b,b),(c,c),(d,d)\}$, right? Now someone will say, for pairs $\{(a,a),(b,b),(c,c),(d,d)\}$, equivalence classes will be $\{\{a\},\{b\},\{c\},\{d\}\}$. But I feel that's not compulsory, right? Have a look at definition of partition / equivalence relation again:

A partition of a set S is a collection of disjoint nonempty subsets (which are equivalence relation) of S that have S as their union.

Thus given equivalence relation, we can combine two or more (say $A$ and $B$) of them to form bigger equivalence relation. In that equivalence relation also, symmetricity, reflexivity and transitivity will follow. But there might not be pairs such as $aRb$ and $bRa$. Thus its not equivalence class, even though equivalence relation hold on it and it still forms part of valid partition (union of them forms whole set and they are disjoint). In other words,

(1) Partition is made of sets, which may or may not be equivalence classes (as partitions have only requirement that they are disjoint and their union form an original set).
(2) Set of equivalence classes on a set form a partition.

So if all above thoughts are right and since question does not use word "equivalence class", but "equivalence relation", am I right with the fact that we can just have reflexive pairs (or even some symmetric and transitive pairs, if not all), for example $\{(a,a),(b,b),(c,c),(d,d),(a,b),(b,a)\}$. Here,

  • $(a,a),(b,b),(c,c),(d,d)$ are what I call as reflexive pairs, i.e. pairs which confirm that the relation is reflexive
  • $(a,b),(b,a)$ are what I call as symmetric pairs, i.e. pairs which confirm that the relation is symmetric
  • in this example, there is no pair (x,y) dictated by transitive relationship
$\endgroup$
  • 1
    $\begingroup$ There is always one and only one total equivalence relation in each set: for a set $A$, that's $A^2$. I don't see what you mean with combining equivalence relations. If it is the union, then in general it's not an equivalence relation, but there is an equivalence relation generated by the union. It's not very clear what is your question, after all... $\endgroup$ – amrsa Feb 9 '18 at 16:47
  • $\begingroup$ what's a transitive pair ? $\endgroup$ – mercio Feb 9 '18 at 17:01
  • $\begingroup$ @amrsa I know equivalence relations are not closed under union, because union may not be transitive. This will happen when there is common element in two relations. For example, consider equivalence relations $\{(a,b),(b,a)\}$ and $\{(b,c),(c,b)\}$. Here, $b$ is common in both. So union will not contain $(a,c)$ (as dictated by $(a,b)$ and $(b,a)$). However this will not happen in case of taking union of partition's equivalence relations as they are disjoint. Right? $\endgroup$ – anir Feb 9 '18 at 20:59
  • 1
    $\begingroup$ Yes, the union of two equivalence relations $\alpha$ and $\beta$ is an equivalence relation if each block of $\alpha$ is contained in a block of $\beta$ or is a union of blocks of $\beta$. $\endgroup$ – amrsa Feb 9 '18 at 21:16
  • 1
    $\begingroup$ One more thing: remove the 'order-theory' and 'lattice-orders' tags from this question. These are not relevant here. $\endgroup$ – amrsa Feb 10 '18 at 10:02
3
$\begingroup$

You seem to be overlooking the last three words of the question. The question doesn't want any old equivalence relation on $A$ you can come up with -- it want the particular equivalence relation "induced by $\pi_1$".

Perhaps you have missed that "the equivalence relation that such-and-such partition induces" has a particular definition? The exercise is asking you to apply that definition to find which one of the many possible equivalence relations on $A$ it is speaking about.

There are various equivalent ways to define this concept -- we can either say

We say that the equivalence relation $R$ is induced by the partition $\pi$ if the elements of $\pi$ are exactly the equivalence classes under $R$.

or

Given a partition $\pi$, the equivalence relation induced by this partition is the relation $R_\pi$ defined by $$ x\mathrel{R_\pi}y \iff \exists P\in\pi: \{x,y\}\subseteq P $$

$\endgroup$
  • $\begingroup$ One precise question which sums up all my doubts. In the book by Kenneth Rosen, there is a sentence: "a partition of a set S is a collection of disjoint nonempty subsets of S that have S as their union.". Though the author have equivalence relation and classes discussed on the same page, he wrote above sentence, which does not say partitioning sets should always be equivalence classes. So, I felt any disjoint nonempty partitions with their union = S will do, regardless of whether symmetry, reflexivity and transitivity hold on them. Reading your answer, I feel that is not correct, right? $\endgroup$ – anir Feb 11 '18 at 7:59
  • $\begingroup$ @anir: symmetry, reflexivity, transitivity are not properties of the parts in the partition. It just doesn't make any sense to ask if those properties hold there. Those are properties of relations. If the relation is one induced by (not identical to) the partition, then yes, those properties must hold. $\endgroup$ – Matthew Leingang Feb 11 '18 at 13:28
  • $\begingroup$ @anir: The point is that whenever you have a partition, no matter where you get it from, there is automatically one particular equivalence relation whose equivalence classes are exactly the sets in the partition. The exercise is to construct that equivalence relation for the partition you're given. $\endgroup$ – Henning Makholm Feb 11 '18 at 14:20
1
$\begingroup$

The answer given is correct. You are right that the relation $$ \{(a,a),(b,b),(c,c),(d,d)\} $$ is also an equivalence relation—it's a different equivalence relation. And it yields a different partition.

$\endgroup$
  • $\begingroup$ The question is if the given answer is the only answer for the given question. Because that is what is stated in the book. Is my answer too valid. $\endgroup$ – anir Feb 9 '18 at 17:19
  • $\begingroup$ @anir: no, your answer is wrong. Equivalence relations and partitions are in one-to-one correspondence. So if two equivalence relations give different partitions, they are different equivalence relations. $\endgroup$ – Matthew Leingang Feb 9 '18 at 17:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.