If I have a subset, how do I define an equivalence relation.
I understand it has to satisfy three properties:transitive, symmetric and reflexive, but I'm not sure how to give an explicit definition of the equivalence relation, for example on I where
If I have a subset, how do I define an equivalence relation.
I understand it has to satisfy three properties:transitive, symmetric and reflexive, but I'm not sure how to give an explicit definition of the equivalence relation, for example on I where
As promised. First we need a little background, namely 'what is a partition?'
Definition: Let be a collection of sets, with being some indexing set. Then is a partition of a set if
1)
2)
In simpler terms, a collection of sets (specifically subsets) of is a partition if no two of them overlap and their union is the entire set. Think about it as taking the whole set and cutting it into pieces. We call the indvidual 's 'blocks' of the partition.
Definition: Equivalence class- Let be a set, and and equivalence relation on . Then the set is called the equivalence class of .
Theorem: A parition of induces an equivalence relation on .
Proof: This relation, which we'll call , is defined by for the same . We prove that is satisfies the three conditions of an equivalence relation.
1. Relfexive- Since belongs to precisely one set it is clear that
2. Symmetric- Keeping in mind that each element belongs to exactly one element of it is clear that if that
3. Transitive- Suppose that and . And note that since [tex]b[\math] belongs to precisely one that must belong the same or in other words
This proves that a partition defines a relation on .
We next move onto our next concept.
Theorem: An equivalence relation on a set induces a partition on
Proof: Define a parition on by . Let us show that this is a parition.
1) Suppose that . WLOG Let then so that which of course means that . This means that . Thus no element of is in . The exact same method shows that no element of is in . Thus .
2) Clearly . So clearly every element of is in some equivalence class (namely it's own equivalence class). So .
This shows that is a partition of
This is all that is really needed. But just in case here is one last theorem.
Theorem: If then
Proof: If hen there exists some but by definition that means that and . But because is an equivalence relation we can see that bu symmetry . So and which by transitivity means that . Now clearly then for any we can see that and therefore , so . The same methodology shows that . Thus we conclude that
This just about does it. It's late and I easily could have made a typo but I hope you get the point.