The Gateway to Computer Science Excellence
+22 votes
2.5k views

Suppose $A = \{a, b, c, d\}$ and $\Pi_1$ is the following partition of A

$\Pi_1 = \left\{\left\{a, b, c\right\}\left\{d\right\}\right\}$

  1. List the ordered pairs of the equivalence relations induced by $\Pi_1$.

  2. Draw the graph of the above equivalence relation.

  3. Let $\Pi_2 = \left\{\left\{a\right\}, \left\{b\right\}, \left\{c\right\}, \left\{d\right\}\right\}$

     $\Pi_3 = \left\{\left\{a, b, c, d\right\}\right\}$

    and $\Pi_4 = \left\{\left\{a, b\right\}, \left\{c,d\right\}\right\}$

    Draw a Poset diagram of the poset, $\left\langle\left\{\Pi_1, \Pi_2, \Pi_3, \Pi_4\right\}, \text{ refines } \right\rangle$.

in Set Theory & Algebra by
recategorized by | 2.5k views
+9

.

................................

Interchange

$\Pi_2\ <-> \Pi_4\\ \Pi_1\ <-> \Pi_3$

0

Tuhin Dutta $\prod$3 refines both $\prod$4 and $\prod$1

am i right?

+1

4 Answers

+14 votes
Best answer

a. For Calculating Ordered Pairs Just multiply the partition with itself.

$ \{a,b,c\} * \{a,b,c\} = \{ (a,a),(a,b),(a,c),(b.a),(b,b),(b,c),(c,a),(c,b),(c,c)\}$

$ \{d\}*\{d\} = \{(d,d)\}$

$\therefore$ The ordered pairs of the equivalence relations are $= \{ (a,a),(a,b), (a,c), (b,a), (b,b), (b,c), (c,a), (c,b), (c,c),(d,d) \}$


b. For each ordered pair $(a,b)$ in the equivalence relation just make a directed edge from a towards $b$.


c. Suppose we have two partitions of a set $S:P_1={A_1,A_2,A_3...}\ and\ P_2={B_1,B_2,B_3...}$

We say that $P_1$ is a refinement of $P_2$ if every $A_i$ is a subset of some $B_j$ . Or We can say that $P_1$ refines $P_2$


 

Additional Note :-

First read definition of refinement given above then relate it to this example.

Refinement means refining/filtering elements.

Suppose like we have { water, ice, sugar, rasna }

now someone told you to make sugarfree rasna so you keep sugar aside like {{water,ice,rasna},{sugar}}

now someone told you to not to put ice in rasna so you do keep ice aside like {{water,rasna,sugar},{ice}}

i.e. {{water,ice,rasna},{sugar}} and {{water,rasna,sugar},{ice}} are refined versions of  { water, ice, sugar, rasna }  in one you have refined sugar and in other you refined ice.

now someone told you to make sugarfree rasna and also not add ice then you do like {{water,rasna},{ice,sugar}}.

Now this is another refined version of  { water, ice, sugar, rasna } and not refined version of  {{water,ice,rasna},{sugar}} or {{water,rasna,sugar},{ice}} . why ?

because {ice,sugar} is not a subset of {water,ice,rasna} or {water,rasna,sugar} but it is a subset of { water, ice, sugar, rasna }

by
edited by
0
What's the relation between the graph in part B and Hasse diagram?
+5
The Graph in part B is not a partial order relation because it is not antisymmetric.

So we can't draw the Hasse Daigram for it because if we try to draw it then there will be edges present between the nodes which are at equal level which is not allowed in hasse daigram.
0

@Satbir

Can u tell me one thing, that why poset need to be antisymmetric always? I mean what is logic behind?

and Are we draw Hasse diagram with self loop always? Then how Hasse diagram maintain poset property?

0

@srestha Have you completed verbal ability portions for GATE? I mean have you solved all previous year questions in them?

+5
Hasse Daigram is made for Poset.
Poset are Reflexive, transitive and antisymmetric. Its the definition of a Poset.
If a relation is Reflexive, Symmetric and transitive then it is an equivalence relation.

When we convert a graph to a Hasse Daigram then we remove Self loops(i.e. reflexive property) and also transitive edges(i.e. transitive property) So the only property that configures the structure of hasse Daigam is the Antisymmetric property.
i.e. Hasse Daigram is mainly used to represent the antisymmetric property.

So if you the don't obey the Antisymmetric property then there is no meaning in making the Hasse Daigram.
0

@Arjun Sir

I have no book for it. Yes chked prev year ques once. but why?

@Satbir

When we convert a graph to a Hasse Daigram then we remove Self loops(i.e. reflexive property) and also transitive edges(i.e. transitive property) So the only property that configures the structure of hasse Daigam is the Antisymmetric property.
i.e. Hasse Daigram is mainly used to represent the antisymmetric property.

So if you the don't obey the Antisymmetric property then there is no meaning in making the Hasse Daigram.

from where u got this? yes, logic may be correct.

0
Logic is my own and the above i derived from the steps to convert a graph into hasse daigram.
0
ok yes correct.
0

@Satbir

what is the actual difference between refinement & subset ???

+6

First read definition of refinement given in answer then relate it to this example.

refinement means refining/filtering elements.

Suppose like we have { water, ice, sugar, rasna }

now someone told you to make sugarfree rasna so you keep sugar aside like {{water,ice,rasna},{sugar}}

now someone told you to not to put ice in rasna so you do keep ice aside like {{water,rasna,sugar},{ice}}

i.e. {{water,ice,rasna},{sugar}} and {{water,rasna,sugar},{ice}} are refined versions of  { water, ice, sugar, rasna }  in one you have refined sugar and in other you refined ice.

now someone told you to make sugarfree rasna and also not add ice then you do like {{water,rasna},{ice,sugar}}.

Now this is another refined version of  { water, ice, sugar, rasna } and not refined version of  {{water,ice,rasna},{sugar}} or {{water,rasna,sugar},{ice}} . why ?

because {ice,sugar} is not a subset of {water,ice,rasna} or {water,rasna,sugar} but it is a subset of { water, ice, sugar, rasna }


subset means like from a set like {2,3,4,5} you remove some elements then it becomes a subset

eg:- {2,3} is a subset of {2,3,4,5}

0

@Satbir I don't know what induced means here. Can you suggest me some resource from where I can read? 

0
"induced "  means derived
+1

@Satbir Not the literal meaning. What is the concept behind listing the ordered pairs as you did? 

My main doubt here is why are we not multiplying {a,b,c} with {d}.

+7
0
Got it. In a partition, all the elements are related to each other and in two different partitions, no two elements are related to each other.
+2

@Satbir In the last statement where you have written If P1 is a refinement of P2 then it means P1 refines P2.

Is this correct or do you mean P2 refines P1?

0
first statement
0

partition of the given interval, Q, is defined as a refinement of the partition, P, when it contains all the points of P and possibly some other points as well; the partition Q is said to be “finer” than P. Given two partitions, P and Q, one can always form their common refinement, denoted P ∨ Q, which consists of all the points of P and Q, re-numbered in order.

So in last statement it should be p2 refines p1

0

We say P1 refines P2 or P1 is finer than P2 if every partition of P1 is subset of some partition of P2.

ref: https://www.cs.sfu.ca/~ggbaker/zju/math/equiv-rel.html

0
suppose P = {A,B} and Q = {{A},{B}}

then Q refines P or we can write Q is a refinement of P.
0

@Satbir Yes, You can write so...because every partition of Q is subset of partitions of P. And now you have corrected the statement in your answer.

0
YES ...i got little confused with harshpeswani's comment.
0
Thanks, now got the concept clearly.
+9 votes
(a) The ordered pairs of the equivalence relations induced $= \{ (a,a),(a,b), (a,c), (b,a), (b,b), (b,c), (c,a), (c,b), (c,c),(d,d) \}$

PS: equivalence relations = each partition in power set - $\phi$
by
+22
we can find the same by { {a,b,c} ${\times }$ {a,b,c} , {d} ${\times }$  {d} }

= { (a,a), (a,b), (a,c), (b,a), (b,b), (b,c), (c,a), (c,b) ,(c,c), (d,d) }
0
what about (b) and (c) ?
0
c.) Make the graph according to the given connected vertices below.  
PI1----->PI3
PI4----->PI3
PI2----->PI4
PI2----->PI1
+1

Equivalence relation is reflexive, symmetric and transitive.

But that does not means that all symmetric and transitive pairs should be there, right? We can just have
reflexive pairs also, right? Like this: $\{(a,a),(b,b),(c,c),(d,d)\}$

Will it make difference if we notice that the question does not at all make use of word "equivalence class", but use word "equivalence relation", what you say? I guess it makes difference if we think of the following three points:

1. "equivalence relation" has no such restriction that each elements in the set should be related to each other, which is the restriction put by "equivalence class".

2. Set of all "equivalence classes" form partition, but the converse is not true, that is 

3. Partition is made of sets which may or may not be "equivalence classes". The only criteria is that they should be disjoint and their union should be original set.

I guess after considering these facts, we are allowed to have only reflexive pairs, or even some symmetric and transitive pairs, if not all, right?

+7

Hasse diagram

You can interchange $\prod_1$ and $\prod_4$ as they are unrelated

0
@Ayush I am not understanding the a) part of the question please explain it
+3
@Prince -You must be knowing the two way theorem

Every Equivalence relation induces a partition on a set if and only if Every partition of the set induces an equivalence relation on the set.

Now to find the ordered pairs from the partition, simply take cross product of the partitions among themselves.
+2

A partition α of a set X is a refinement of a partition ρ of X—and we say that α is finerthan ρ and that ρ is coarser than α—if every element of α is a subset of some element of ρ. Informally, this means that α is a further fragmentation of ρ. In that case, it is written that α ≤ ρ.

https://en.wikipedia.org/wiki/Partition_of_a_set#Refinement_of_partitions

0

 @Ayush Upadhyaya you mean to say cross product of equivalence classes? coz equivalence relation divide set into disjoint classes.

0
Yes, and those classes form the biggest equivalence relation possible on the set.
0

,how we will draw part (b)

0

@codingo1234-Do you know what refines relation means?

+1

@,earlier I was not knowing what "refines relation" means ,but I saw 's comment and came to know about when a partition is refinement of other

"A partition α of a set X is a refinement of a partition ρ of X—and we say that α is finer than ρ and that ρ is coarser than α—if every element of α is a subset of some element of ρ. Informally, this means that α is a further fragmentation of ρ. In that case, it is written that α ≤ ρ." ,

but I was confused regarding drawing graph of equivalence relation of part(a) and I was thinking about hasse digaram(god knows  why everything mixes up in mind),I think it will be directed graph,am i correct?

 

0

@Ayush Upadhyaya Can you please provide a resource to read two-way theorem

+3 votes
by
0 votes

List the ordered pairs of the equivalence relations induced by Π1.

 

Partitions of an equivalence relation are also called equivalence classes.

They go by the property that all the elements in a partition are related to each other, and none of them is related to any element of any other partition.

Example, if A and B are two partitions of some set S, then every element in A relates to all other elements in A.

Also, $A\cup B \cup C\cup D...\cup N = Original$ $Set$

$A\cap B \cap C\cap D...\cap N = \phi$

where A,B,C..,N are partitions of S.

 

Since every element in a partition is related to each other; cross-product a partition with itself to obtain the equivalence relation.

So, $\left \{ (a,a),(a,b),(a,c),(b.a),(b,b),(b,c),(c,a),(c,b),(c,c), (d,d) \right \}$


Draw the graph of the above equivalence relation.

In any relation, we all know that (a,b) means a relates to b. NOT b relates to a, too. So for (a,b) and (b,a) we need two directed edges.


 

Draw a Poset diagram of the poset...

A "refines" B means that A is finer than B. Or B is coarser than A. In plain English a finer particle would be smaller than a coarser particle. So, A refines B could loosely mean that A has smaller elements than B.

So,

   Π3

  /      \

Π4    Π1

  \     /

   Π2

by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,484 answers
201,812 comments
95,289 users