Let $R_1$ and $R_2$ be equivalence relations on a set $S$. Prove that $R_1$ refines $R_2$ if and only if the partition with respect to $R_1$ is a refinement of the partition with respect to $R_2$.

Question

usukidoll · Answer

We have a biconditional statement. 

1. If $R_1$ refines $R_2$, then the partition with respect to $R_1$ is a refinement of the partition with respect to $R_2$

Definition 6.2.12 states that we let $R_1$ and $R_2$ be relations on a set $S$. Then $R_1$ refines $R_2$ if $R_1 \subseteq R_2$. 

That's about all I have for this... I'm kind of lost .. so $R_1$ is a subset of $R_2$ and then what occurs afterwards? Are they related? I think they are and maybe I should use Definition 6.1.7...they must have elements inside so they're not empty sets. So $R_1$ and $R_2$ must have cells that belong to $R_1$ and $R_2$

---

The second one...


2. If the partition with respect to $R_1$ is a refinement of the partition with respect to $R_2$, then $R_1$ refines $R_2$

Definition 6.1.7 states that we let $S$ be a nonempty set, and suppose that $\mathcal{A}$ and $\mathcal{B}$ are partitions of $S$. If for every cell $B \in \mathcal{B}$ there exists a cell $A \in \mathcal{A}$ such that $B \subseteq A$, then $\mathcal{B}$ is a refinement of $\mathcal{A}$ and $\mathcal{B}$ refines $\mathcal{A}$.

Suppose that $R_1$ and $R_2$ are partitions of S. If for every cell $R_1 \in \mathcal{R}_1$, there exists a cell $R_2 \in \mathcal{R}_2$ such that $R_1 \subseteq R_2$ then $\mathcal{R}_1$ is a refinement of $\mathcal{R}_2$ and $\mathcal{R}_1$ refines $\mathcal{R}_2$.

usukidoll · Answer

-_- grrr why is it that one biconditional statement is easier to prove than the other..

anonymous · Answer

The definition of refines?

usukidoll · Answer

yeah ... the definition is exactly what I put from the textbook.

usukidoll · Answer

and then? ? ? ? ? stuff came

anonymous · Answer

Well, functions are relations.

anonymous · Answer

A relation is just a set of tuples

anonymous · Answer

Consider if $S=\{0,1\}$.  Let $R_1=\{(0,0), (1,1), (0,1)\}$.  Suppose $R_2=\{(0,1)\}$.  Then since $R_2\subseteq R_1$ we say $R_2$ refines $R_1$.

usukidoll · Answer

yes.... they both have the same elements.. wait a sec.. you're using singleton on here.

usukidoll · Answer

and we have a biconditional statement...so would the first statement work similarly to the second?

anonymous · Answer

okay, first of all, we need to define partitions.

usukidoll · Answer

wouldn't that be in definition 6.1.7?

usukidoll · Answer

instead for A being the partition it's $$R_1$$ and B being $$R_2$$?

usukidoll · Answer

or is there a pure definition for partitions?

anonymous · Answer

I don't see how 6.1.7 defines partitions, and I'm tired.

usukidoll · Answer

so there is a pure definition for partitions only? ... lol go sleep. this stuff isn't due to Wednesday... I'm just making attempts and asking asap to see if I'm on the right track XD

usukidoll · Answer

@experimentX

experimentx · Answer

how do you define refinement?

experimentx · Answer

i mean in terms of equivalence relation?

usukidoll · Answer

refinement in terms of equivalence relation... errr 

that means that it's symmetric, reflexive, and transitive if we need equivalence relation to hold

experimentx · Answer

http://en.wikipedia.org/wiki/Partition_of_a_set#Partitions_and_equivalence_relations "For any equivalence relation on a set X, the set of its equivalence classes is a partition of X. Conversely, from any partition P of X, we can define an equivalence relation on X by setting x ~ y precisely when x and y are in the same part in P. Thus the notions of equivalence relation and partition are essentially equivalent."

usukidoll · Answer

well I did include a defintiion that was similar to that.. it was def. 6.1.7

usukidoll · Answer

the question mentioned partitions so that was the definition that I needed.

experimentx · Answer

http://en.wikipedia.org/wiki/Equivalence_relation#Comparing_equivalence_relations

usukidoll · Answer

The following are all equivalence relations:

    "Is equal to" on the set of real numbers
    "Has the same birthday as" on the set of all people.
    "Is similar to" on the set of all triangles.
    "Is congruent to" on the set of all triangles.
    "Is parallel to" on the set of lines in a plane from Euclidean geometry.
    "Is congruent to, modulo n" on the integers.
    "Has the same image under a function" on the elements of the domain of the function.
    "Has the same absolute value" on the set of real numbers
    "Has the same cosine" on the set of all angles.

usukidoll · Answer

hmmm let $$R_1$$ and $$R_2$$ have the same values in their set or something?

experimentx · Answer

no ... not necessarily.

usukidoll · Answer

then... hmmmmmm $$R_1 \subseteq R_2 $$
so $$R_1 $$ is the subset of $$R_2$$
so we need to prove that they are partitions. so they must be related to each other.

experimentx · Answer

an equivalence relation on set S forms a partition with it's equivalence classes. do you know what are equivalence classes?

experimentx · Answer

ok ok ... both are equivalence relations

experimentx · Answer

okay okay, let $R_1$ and $R_2$ be two equivalence relations and $R_1$ is finer than $R_2$.
that is if, $ (a,b ) \in R_2 \implies (a,b ) \in R_1 $.

usukidoll · Answer

then it's reflexive, symmetric, and transitive.. if both of them are equivalence relations

experimentx · Answer

both of them are equivalence classes ... reflexive, symmetric and transitive is not your problem. you don't need to focus it here.

experimentx · Answer

as I told you, equivalence relation forms a partition on a set ... with equivalence classes.
you need to show that R1 makes finer partiton than R2.

BRB gotta eat lunch

usukidoll · Answer

oh right....the question isn't about proving equilvalence relations.. that was the other one... it's like a combination of a refinement defintiion and a partition definition.

experimentx · Answer

do you know about equivalence classes ?

experimentx · Answer

*class lol

usukidoll · Answer

I don't remember reading that in my book

usukidoll · Answer

found the definition... 6.2.9 Let R be an equivalence relation on a set S. For each element $$x \in S$$ the set $$[x]=[y \in S:(x,y) \in R]$$ is the equivlaence class of x with respect to R

usukidoll · Answer

so for each element $$x \in S$$ the equivalence class of x with respect to $$R_1 $$ and $$R_2 $$ are 
$$[x]=[y \in S:(x,y) \in R_1]$$ and $$[x]=[y \in S:(x,y) \in R_2] $$

experimentx · Answer

yes ... equivalence relation forms a partition on a set

experimentx · Answer

consider modulo residue classes $ n \equiv m \mod 2$ and $ n \equiv m \mod 4$
the equivalence classes of mod 4 is subset of mod 2 ... hence mod 4 is finder than mod 2.

experimentx · Answer

let
$$ S=\{y \in S:(x,y) \in R_1\} $$
and 
$$ T=\{y \in S:(x,y) \in R_2\} $$
given that $ (x,y) \in R_2 \implies (x,y) \in R_1 $  show that $ T \subset S $

experimentx · Answer

$$ * S \subset T $$

usukidoll · Answer

oh hey @Loser66

usukidoll · Answer

so we need to show that S is a subset of T.

usukidoll · Answer

using equivalence class. ..what if they have the same elements? then they have got  to be related to each other

experimentx · Answer

did I read it wrong? http://en.wikipedia.org/wiki/Equivalence_relation#Comparing_equivalence_relations

usukidoll · Answer

oh hi...  umm I don't think so.. just trying to show that S is a subset of T with those two definitions of equivalence class $$[x]=[y \in S:(x,y) \in R_1] $$ and $$[x]=[y \in S:(x,y) \in R_2] $$

usukidoll · Answer

ph crap I meant $$R_1 \subseteq R_2 $$ or in backwards lan d $$R_2 \subseteq R_1 $$

usukidoll · Answer

that's for the first one.... which is if $$R_1$$ refines $$R_2$$ then it's a partition .. but how do I go further now that we have the defintiion of equilvalence classes

usukidoll · Answer

?????? let it be sets?!

usukidoll · Answer

oh crud no.. R_1 and R_2 are contained somehow..

experimentx · Answer

$$a\in S=\{y \in S:(x,y) \in R_1\} \implies a \in\{y \in S:(x,y) \in R_2\}  = T$$
or $ S \subset T $

usukidoll · Answer

$$S \subseteq T $$ because of that refinement definition... so how do we prove that part? with an example?

experimentx · Answer

^^
$$ \forall a \in A,  a \in B \implies A \subseteq B$$

usukidoll · Answer

THAT SUBSET DEFINITION!@ from chapter three! D:SER

experimentx · Answer

given that  $ S \subseteq T $ (definition of refined partition), S and T are equivalence classes, let $ a \in S$, for some element $ (x, a) \in R_1   \implies (x, a) \in R_2 $ since the equivalence class of former is subset of latter.

experimentx · Answer

*conversely

experimentx · Answer

which proves that R1 is refinement of R2. and R1 forms a refined partition of R2 on set S.
gotta go. see ya later. also see the definition of wikipedia.

usukidoll · Answer

thank you :D