recategorized by
11,405 views
29 votes
29 votes

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

recategorized by

4 Answers

Best answer
36 votes
36 votes

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 }

edited by
9 votes
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$
3 votes
3 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

Related questions

13 votes
13 votes
4 answers
2
Arjun asked Aug 12, 2018
4,122 views
Let $R$ be a binary relation on $A = \{a, b, c, d, e, f, g, h\}$ represented by the following two component digraph. Find the smallest integers $m$ and $n$ such that $m <...
32 votes
32 votes
3 answers
3
Kathleen asked Sep 26, 2014
7,096 views
Let $(A, *)$ be a semigroup, Furthermore, for every $a$ and $b$ in $A$, if $a \neq b$, then $a*b \neq b*a$.Show that for every $a$ in $A$, $a*a=a$Show that for every $a$,...
20 votes
20 votes
6 answers
4
Kathleen asked Sep 26, 2014
3,704 views
Prove by induction that the expression for the number of diagonals in a polygon of $n$ sides is $\frac{n(n-3)}{2}$