I was reading up on tensor products on wikipedia and after some further clicking I came at a topic about equivalence relations. I understand what these relations are but there was a example which I could'nt grasp. Perhaps anyone here can explain it to me.
Let the set {a,b,c} have the equivalence relation {(a,a), (b,b), (c,c),(b,c),(c,b)}.
The following sets are equivalence classes of this relation [a]={a}, [b]=[c]={b,c}.
The set of all equivalence classes for this relation is {{a},{b,c}}. This set is a partition of the set {a,b,c}.
My questions regarding this are:
1. How is this "{(a,a), (b,b), (c,c),(b,c),(c,b)}" an equivalence relation?
2. How is {{a},{b,c}} a subset of {a,b,c}? Isn't {{a},{b,c}} = {a,b,c}?
Thanks for the help.
1) How is this "{(a,a), (b,b), (c,c),(b,c),(c,b)}" an equivalence relation?
Because it satisfies the definition of "equivalence relation". It is i) reflexive ii) symmetric iii) transitive.
2) How is {{a},{b,c}} a subset of {a,b,c}? Isn't {{a},{b,c}} = {a,b,c}?
Boy, three wrongs don't make a right.
{{a},{b,c}} is not a subset of {a,b,c}. It is a partition of {a,b,c}. A partition is not a subset.
{{a},{b,c}} $\ne$ {a,b,c}
And if $A = X$ then $A$ IS a subset of $X$. All sets are subsets of themselves.
====
1 ) In an equivalence relationship you must have an element $a$ is equivalent to itself.
So part of the definition of equivalence relationship is that every $x$ ~ $x$. In other words, every $(x,x)$ is in the set that defines the relationship. And indeed, for each $a,b,c\in \{a,b,c\}$ we have $(a,a),(b,b),(c,c)$ are in $\{(a,a), (b,b), (c,c),(b,c),(c,b)\}$
So i) The set is reflexive.
Also if two things are equivalent that means you can replace one with the other. And it doesn't matter what order you do it in. So if $x$ ~ $y$ then it most also be that $y$ ~ $x$. Or in other words, if $(x,y) $ is in the relation ship then $(y,x)$ is true. And indeed we have $(b,c)$ in the relationship and we also have $(c,b)$. And those are the only non $(x,x)$ elements. And, obviously, if $(x,x)$ is in then reversing the order is $(x,x)$ which is the exact same thing.
So ii) the set is symmetric
The final requirment to be equivalent is that you can replace things with equivalent things and those can be replaced by equivalent things to them. So if $x$~$y$ and $y$~$z$ it must be that $x$~$z$. Or in other words, if $(x,y)$ and $(y,z)$ are in the set, then $(x,z)$ must be in the set.
And indeed. For ever $(x,y), (y,z)$ we have $\to (x,z)$ in the set. Let's list them all:
$(a,a),(a,a)\to (a,a)$
$(b,b),(b,b)\to (b,b)$
$(b,b),(b,c)\to (b,c)$
$(c,c),(c,c)\to (c,c)$
$(c,c),(c,b)\to (c,b)$
$(b,c),(c,c) \to (b,c)$
$(b,c),(c,b)\to (b,b)$
$(c,b),(b,b)\to (c,b)$
$(c,b),(b,c)\to (c,c)$
So because $\{(a,a), (b,b), (c,c),(b,c),(c,b)\}$ is i)reflexive ii) symmetric and iii) transitive, it is, by definition, an equivalence relationship.
Where $a$ is only equivalent to itself. Anb $b$ and $c$ as well as being equivalent to themselves are equivalent to each other.
2) A partition means as set of subsets that are i) disjoint and ii) the union of them covers all of the set.
So $\{\{a\},\{b,c\}\}$ is a partition of $\{a,b,c\}$ because i) $\{a\} \cup \{b,c\} = \emptyset$ and ii) $\{a\}\cup \{b,c\} = \{a,b,c\}$.
Any way $\{\{a\},\{\{b,c\}\} \ne \{a,b,c\}$ because the left hand side is a set with two elements: $\{a\}$ and $\{b,c\}$ and all the elements on the LHS are sets; and the right hand side has three elements: $a,b,c$ and none of those are sets.
=====
That is a very legitimate question. Let say relationship is "is the brother of" and you have Tim, Mary, and Sam are three siblings (Sam's and Tim are boys, and Mary is a girl) and Mike, and June who are two other siblings.
If we denote $\to$ as the relationship we have:
$Tim\to Sam, Tim\to Mary, Sam\to Tim, Sam\to Mary, June\to Mike$. (Notice this is an assymetric relation relationship; we have $Tim\to Mary$ but not $Mary\to Tim$.)
That is our relationship, the set of all the related pairs.
Well, in set and list and math terms we like to represent the pairs not as $a \to b$ but as the ordered pair $(a,b)$ where the first term of the pair is the left side of the relation and the second term is the right side of the relation.
So now our relationship is:
$(Tim, Sam), (Tim, Mary), (Sam\, Tim), (Sam, Mary), (June, Mike)$
In terms of sets:
We can say: Let $A = \{Tim,Mary, Sam, Mike, June\}$. That's just a set of all our people.
We define $A\times A$ as the set of all possible ordered pairs. That is $A\times A = \{(Tim,Tim),(Tim,Mary), (Time, Sam),....., (June,Mike), (June, June)\}$. As there are $5$ elements of $A$ there are $5*5=25$ possible ordered pairs. And $A\times A$.
So we can say our relationship is $Brothers = \{(Tim, Sam), (Tim, Mary), (Sam\, Tim), (Sam, Mary), (June, Mike)\}$ which is which is just a set of all the ordered pairs $(a,b)$ where $a$ is the brother of $b$.
And we note $Brothers \subset A\times A$.
ANd that's the definition in math of a "relation". A relation on a set $A$ is simply a subset $R$ of $A\times A$.
So in $R = \{(a,a),(b,b), (c,c), (b,c),(c,b)\}\subset \{a,b,c\}\times \{a,b,c\}$ thought of as the relationship where $a \to a; b\to b; c\to c; b\to c;$ and $c\to b$.
An eqvalence relation, $R$, on $A$ (so $R \subset A\ties A$) is one where
i) it is reflexive.
So for every $a \in A$ with have $a\to a$.
Or in other words $(a,a)\in R$.
ii) it is symmetric.
For every pair where $a\to b$ then we also have $b\to a$.
Or in other words if $(a,b)\in R$ then $(b,a)\in R$.
iii) it is transitive.
For any $a,b,c\in A$ where $a\to b$ and $b\to c$ then it will also be true that $a \to c$.
Or in other words: if $(a,b)\in R$ and $(b,c)\in R$ then it follows that $(a,c) \in R$.
So for example let's let $A =\{Tim,Sam,Mary,Mike,June, Betty\}$ and let $R$ be the relation: "has the same friends" where it is assumed that i) everybody likes themselves, ii) if any likes someone then the feeling is mutual, and iii) a friend of a friend is a friend; everyone likes there friends' friends.
And lets say Tim only like himself, Sam and Mary like each other but no-one else. And Mike, June and Betty all like each other.
Then the relation is $L = \{(Tim,Tim), (Sam,Sam), (Sam,Mary), (Mary, Sam), (Mary, Mary), (Mike, Mike), (Mike, June),(June,Mike),(June,June), (Mike,Betty), (Betty, Mike),(Betty,Betty),(June,Betty),(Betty,June)\}$ and the relation is an equivalence relation.
All this is a bit of an abuse of language. If people like each other they are equivalent. For all practical purposes you can replae anybody with someone they like. Sort of.
Now, let's consider the sets where the sets consist of people who like each other; i.e. the sets where everybody in them are equivalent, and everyone who is equivalent to them is in the set.
So $\{Tim\}$ consists of everybody who is equivalent to Tim.
$\{Sam, Mary\}$ consists of everybody who is equivalent to Sam, which also happens to be everybody who is equivalent to Mary.
And $\{Mike, June,Betty\}$ is everybody who is equivalent to Mike, (which means they are also equivalent to June, and Betty).
These are called the equivalence classes of $L$.
A neat thing about equivalence classes is they partition $A$.
That is i) $\{Tim\} \cup \{Sam, Mary\}\cup \{Mike, June,Betty\} = A$.
ii) The sets are all pairwise disjoint.
If any set of sets have those two properties we call it a "partition". And it is a property of equivalence relations, the set of equivalence classes form a partition of the main set.