Example of equivalence relation

Clash Royale CLAN TAG#URR8PPP

up vote
0
down vote

favorite

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.

elementary-set-theory

share|cite|improve this question

asked Jul 18 at 21:48

Joren Janssens

32

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  The word 'partition' does not mean 'subset', it means 'set of inhabited, pairwise disjoint subsets, whose union is the whole set'.
  – Clive Newstead
  Jul 18 at 21:58
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  On one hand you claim to understand what equivalence relations are, but on the other hand need to be told how $(a,a), (b,b), (c,c),(b,c),(c,b)$ is an example of an equivalence relation on $a,b,c$. You may need to drop back and revisit the definition of a relation, and then understand which relations are the equivalence relations.
  – hardmath
  Jul 18 at 22:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @CliveNewstead I've never seen "inhabited" in lieu of "non-empty", that's poetic, I like it!
  – Arnaud Mortier
  Jul 18 at 22:09
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @ArnaudMortier I've mostly seen "inhabited" used in intuitionistic set (and type) theory, as a way to distinguish between $exists x, x in A$ and $A ne emptyset leftrightarrow lnot forall x, x notin A$ which are classically equivalent but not equivalent in say a general topos.
  – Daniel Schepler
  Jul 19 at 0:15
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Arnaud: 'Empty' means 'doesn't have elements', so 'non-empty' means 'doesn't not have elements', which is silly if you think about it ;) ...and like Daniel suggests, problematic if your logic doesn't admit double negation elimination.
  – Clive Newstead
  Jul 19 at 2:01
  

  
  
  
  

add a comment | 

up vote
0
down vote

favorite

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.

elementary-set-theory

share|cite|improve this question

asked Jul 18 at 21:48

Joren Janssens

32

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  The word 'partition' does not mean 'subset', it means 'set of inhabited, pairwise disjoint subsets, whose union is the whole set'.
  – Clive Newstead
  Jul 18 at 21:58
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  On one hand you claim to understand what equivalence relations are, but on the other hand need to be told how $(a,a), (b,b), (c,c),(b,c),(c,b)$ is an example of an equivalence relation on $a,b,c$. You may need to drop back and revisit the definition of a relation, and then understand which relations are the equivalence relations.
  – hardmath
  Jul 18 at 22:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @CliveNewstead I've never seen "inhabited" in lieu of "non-empty", that's poetic, I like it!
  – Arnaud Mortier
  Jul 18 at 22:09
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @ArnaudMortier I've mostly seen "inhabited" used in intuitionistic set (and type) theory, as a way to distinguish between $exists x, x in A$ and $A ne emptyset leftrightarrow lnot forall x, x notin A$ which are classically equivalent but not equivalent in say a general topos.
  – Daniel Schepler
  Jul 19 at 0:15
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Arnaud: 'Empty' means 'doesn't have elements', so 'non-empty' means 'doesn't not have elements', which is silly if you think about it ;) ...and like Daniel suggests, problematic if your logic doesn't admit double negation elimination.
  – Clive Newstead
  Jul 19 at 2:01
  

  
  
  
  

add a comment | 

up vote
0
down vote

favorite

up vote
0
down vote

favorite

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.

elementary-set-theory

share|cite|improve this question

asked Jul 18 at 21:48

Joren Janssens

32

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.

elementary-set-theory

share|cite|improve this question

asked Jul 18 at 21:48

Joren Janssens

32

share|cite|improve this question

share|cite|improve this question

asked Jul 18 at 21:48

Joren Janssens

32

asked Jul 18 at 21:48

Joren Janssens

32

asked Jul 18 at 21:48

Joren Janssens

32

32

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  The word 'partition' does not mean 'subset', it means 'set of inhabited, pairwise disjoint subsets, whose union is the whole set'.
  – Clive Newstead
  Jul 18 at 21:58
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  On one hand you claim to understand what equivalence relations are, but on the other hand need to be told how $(a,a), (b,b), (c,c),(b,c),(c,b)$ is an example of an equivalence relation on $a,b,c$. You may need to drop back and revisit the definition of a relation, and then understand which relations are the equivalence relations.
  – hardmath
  Jul 18 at 22:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @CliveNewstead I've never seen "inhabited" in lieu of "non-empty", that's poetic, I like it!
  – Arnaud Mortier
  Jul 18 at 22:09
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @ArnaudMortier I've mostly seen "inhabited" used in intuitionistic set (and type) theory, as a way to distinguish between $exists x, x in A$ and $A ne emptyset leftrightarrow lnot forall x, x notin A$ which are classically equivalent but not equivalent in say a general topos.
  – Daniel Schepler
  Jul 19 at 0:15
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Arnaud: 'Empty' means 'doesn't have elements', so 'non-empty' means 'doesn't not have elements', which is silly if you think about it ;) ...and like Daniel suggests, problematic if your logic doesn't admit double negation elimination.
  – Clive Newstead
  Jul 19 at 2:01
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  The word 'partition' does not mean 'subset', it means 'set of inhabited, pairwise disjoint subsets, whose union is the whole set'.
  – Clive Newstead
  Jul 18 at 21:58
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  On one hand you claim to understand what equivalence relations are, but on the other hand need to be told how $(a,a), (b,b), (c,c),(b,c),(c,b)$ is an example of an equivalence relation on $a,b,c$. You may need to drop back and revisit the definition of a relation, and then understand which relations are the equivalence relations.
  – hardmath
  Jul 18 at 22:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @CliveNewstead I've never seen "inhabited" in lieu of "non-empty", that's poetic, I like it!
  – Arnaud Mortier
  Jul 18 at 22:09
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @ArnaudMortier I've mostly seen "inhabited" used in intuitionistic set (and type) theory, as a way to distinguish between $exists x, x in A$ and $A ne emptyset leftrightarrow lnot forall x, x notin A$ which are classically equivalent but not equivalent in say a general topos.
  – Daniel Schepler
  Jul 19 at 0:15
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Arnaud: 'Empty' means 'doesn't have elements', so 'non-empty' means 'doesn't not have elements', which is silly if you think about it ;) ...and like Daniel suggests, problematic if your logic doesn't admit double negation elimination.
  – Clive Newstead
  Jul 19 at 2:01
  

  
  
  
  

2

2

The word 'partition' does not mean 'subset', it means 'set of inhabited, pairwise disjoint subsets, whose union is the whole set'.
– Clive Newstead
Jul 18 at 21:58

The word 'partition' does not mean 'subset', it means 'set of inhabited, pairwise disjoint subsets, whose union is the whole set'.
– Clive Newstead
Jul 18 at 21:58

1

1

On one hand you claim to understand what equivalence relations are, but on the other hand need to be told how $(a,a), (b,b), (c,c),(b,c),(c,b)$ is an example of an equivalence relation on $a,b,c$. You may need to drop back and revisit the definition of a relation, and then understand which relations are the equivalence relations.
– hardmath
Jul 18 at 22:04

On one hand you claim to understand what equivalence relations are, but on the other hand need to be told how $(a,a), (b,b), (c,c),(b,c),(c,b)$ is an example of an equivalence relation on $a,b,c$. You may need to drop back and revisit the definition of a relation, and then understand which relations are the equivalence relations.
– hardmath
Jul 18 at 22:04

@CliveNewstead I've never seen "inhabited" in lieu of "non-empty", that's poetic, I like it!
– Arnaud Mortier
Jul 18 at 22:09

@CliveNewstead I've never seen "inhabited" in lieu of "non-empty", that's poetic, I like it!
– Arnaud Mortier
Jul 18 at 22:09

1

1

@ArnaudMortier I've mostly seen "inhabited" used in intuitionistic set (and type) theory, as a way to distinguish between $exists x, x in A$ and $A ne emptyset leftrightarrow lnot forall x, x notin A$ which are classically equivalent but not equivalent in say a general topos.
– Daniel Schepler
Jul 19 at 0:15

@ArnaudMortier I've mostly seen "inhabited" used in intuitionistic set (and type) theory, as a way to distinguish between $exists x, x in A$ and $A ne emptyset leftrightarrow lnot forall x, x notin A$ which are classically equivalent but not equivalent in say a general topos.
– Daniel Schepler
Jul 19 at 0:15

@Arnaud: 'Empty' means 'doesn't have elements', so 'non-empty' means 'doesn't not have elements', which is silly if you think about it ;) ...and like Daniel suggests, problematic if your logic doesn't admit double negation elimination.
– Clive Newstead
Jul 19 at 2:01

@Arnaud: 'Empty' means 'doesn't have elements', so 'non-empty' means 'doesn't not have elements', which is silly if you think about it ;) ...and like Daniel suggests, problematic if your logic doesn't admit double negation elimination.
– Clive Newstead
Jul 19 at 2:01

add a comment | 

2 Answers
2

active

oldest

votes

up vote
3
down vote



accepted

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,cin 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) $acup 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.

=====

I have one more question and that is about the "relation" part. How am I to view the relation in this context? Becaus it is all so abstract.

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:

$Timto Sam, Timto Mary, Samto Tim, Samto Mary, Juneto Mike$. (Notice this is an assymetric relation relationship; we have $Timto Mary$ but not $Maryto 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 $Atimes A$ as the set of all possible ordered pairs. That is $Atimes 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 $Atimes 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 Atimes A$.

ANd that's the definition in math of a "relation". A relation on a set $A$ is simply a subset $R$ of $Atimes A$.

So in $R = (a,a),(b,b), (c,c), (b,c),(c,b)subset a,b,ctimes a,b,c$ thought of as the relationship where $a to a; bto b; cto c; bto c;$ and $cto b$.

An eqvalence relation, $R$, on $A$ (so $R subset Aties A$) is one where

i) it is reflexive.

So for every $a in A$ with have $ato a$.

Or in other words $(a,a)in R$.

ii) it is symmetric.

For every pair where $ato b$ then we also have $bto a$.

Or in other words if $(a,b)in R$ then $(b,a)in R$.

iii) it is transitive.

For any $a,b,cin A$ where $ato b$ and $bto 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, Marycup 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.

share|cite|improve this answer

edited Jul 19 at 0:09

answered Jul 18 at 22:32

fleablood

60.4k22575

• 
  
  
  

  
  

  
  
  
  
  
  

  
  thanks for the very usefull explanation. I am new to set theory. I have one more question and that is about the "relation" part. How am I to view the relation in this context? Becaus it is all so abstract.
  – Joren Janssens
  Jul 18 at 22:47
  
  

  
  
  
  

add a comment | 

up vote
1
down vote

1. A binary relation on a set $A$ is a subset of $A^2$ and $(a,a), (b,b), (c,c),(b,c),(c,b)$ is indeed a subset of $a,b,c^2$, right?


2. It is not a subset of $a,b,c$. Each if its elements is (and these elements are the equivalence classes).

share|cite|improve this answer

answered Jul 18 at 21:52

José Carlos Santos

114k1698177

• 
  
  
  

  
  

  
  
  
  
  
  

  
  (+1) I would also have asked the OP why they would expect $a,b,c$ to be a subset of $a,b,c$.
  – Arnaud Mortier
  Jul 18 at 21:55
  
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2856043%2fexample-of-equivalence-relation%23new-answer', 'question_page');

);

Post as a guest

Name Email

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
3
down vote



accepted

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,cin 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) $acup 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.

=====

I have one more question and that is about the "relation" part. How am I to view the relation in this context? Becaus it is all so abstract.

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:

$Timto Sam, Timto Mary, Samto Tim, Samto Mary, Juneto Mike$. (Notice this is an assymetric relation relationship; we have $Timto Mary$ but not $Maryto 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 $Atimes A$ as the set of all possible ordered pairs. That is $Atimes 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 $Atimes 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 Atimes A$.

ANd that's the definition in math of a "relation". A relation on a set $A$ is simply a subset $R$ of $Atimes A$.

So in $R = (a,a),(b,b), (c,c), (b,c),(c,b)subset a,b,ctimes a,b,c$ thought of as the relationship where $a to a; bto b; cto c; bto c;$ and $cto b$.

An eqvalence relation, $R$, on $A$ (so $R subset Aties A$) is one where

i) it is reflexive.

So for every $a in A$ with have $ato a$.

Or in other words $(a,a)in R$.

ii) it is symmetric.

For every pair where $ato b$ then we also have $bto a$.

Or in other words if $(a,b)in R$ then $(b,a)in R$.

iii) it is transitive.

For any $a,b,cin A$ where $ato b$ and $bto 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, Marycup 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.

share|cite|improve this answer

edited Jul 19 at 0:09

answered Jul 18 at 22:32

fleablood

60.4k22575

• 
  
  
  

  
  

  
  
  
  
  
  

  
  thanks for the very usefull explanation. I am new to set theory. I have one more question and that is about the "relation" part. How am I to view the relation in this context? Becaus it is all so abstract.
  – Joren Janssens
  Jul 18 at 22:47
  
  

  
  
  
  

add a comment | 

up vote
3
down vote



accepted

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,cin 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) $acup 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.

=====

I have one more question and that is about the "relation" part. How am I to view the relation in this context? Becaus it is all so abstract.

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:

$Timto Sam, Timto Mary, Samto Tim, Samto Mary, Juneto Mike$. (Notice this is an assymetric relation relationship; we have $Timto Mary$ but not $Maryto 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 $Atimes A$ as the set of all possible ordered pairs. That is $Atimes 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 $Atimes 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 Atimes A$.

ANd that's the definition in math of a "relation". A relation on a set $A$ is simply a subset $R$ of $Atimes A$.

So in $R = (a,a),(b,b), (c,c), (b,c),(c,b)subset a,b,ctimes a,b,c$ thought of as the relationship where $a to a; bto b; cto c; bto c;$ and $cto b$.

An eqvalence relation, $R$, on $A$ (so $R subset Aties A$) is one where

i) it is reflexive.

So for every $a in A$ with have $ato a$.

Or in other words $(a,a)in R$.

ii) it is symmetric.

For every pair where $ato b$ then we also have $bto a$.

Or in other words if $(a,b)in R$ then $(b,a)in R$.

iii) it is transitive.

For any $a,b,cin A$ where $ato b$ and $bto 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, Marycup 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.

share|cite|improve this answer

edited Jul 19 at 0:09

answered Jul 18 at 22:32

fleablood

60.4k22575

• 
  
  
  

  
  

  
  
  
  
  
  

  
  thanks for the very usefull explanation. I am new to set theory. I have one more question and that is about the "relation" part. How am I to view the relation in this context? Becaus it is all so abstract.
  – Joren Janssens
  Jul 18 at 22:47
  
  

  
  
  
  

add a comment | 

up vote
3
down vote



accepted

up vote
3
down vote



accepted

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,cin 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) $acup 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.

=====

I have one more question and that is about the "relation" part. How am I to view the relation in this context? Becaus it is all so abstract.

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:

$Timto Sam, Timto Mary, Samto Tim, Samto Mary, Juneto Mike$. (Notice this is an assymetric relation relationship; we have $Timto Mary$ but not $Maryto 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 $Atimes A$ as the set of all possible ordered pairs. That is $Atimes 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 $Atimes 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 Atimes A$.

ANd that's the definition in math of a "relation". A relation on a set $A$ is simply a subset $R$ of $Atimes A$.

So in $R = (a,a),(b,b), (c,c), (b,c),(c,b)subset a,b,ctimes a,b,c$ thought of as the relationship where $a to a; bto b; cto c; bto c;$ and $cto b$.

An eqvalence relation, $R$, on $A$ (so $R subset Aties A$) is one where

i) it is reflexive.

So for every $a in A$ with have $ato a$.

Or in other words $(a,a)in R$.

ii) it is symmetric.

For every pair where $ato b$ then we also have $bto a$.

Or in other words if $(a,b)in R$ then $(b,a)in R$.

iii) it is transitive.

For any $a,b,cin A$ where $ato b$ and $bto 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, Marycup 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.

share|cite|improve this answer

edited Jul 19 at 0:09

answered Jul 18 at 22:32

fleablood

60.4k22575

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,cin 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) $acup 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.

=====

I have one more question and that is about the "relation" part. How am I to view the relation in this context? Becaus it is all so abstract.

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:

$Timto Sam, Timto Mary, Samto Tim, Samto Mary, Juneto Mike$. (Notice this is an assymetric relation relationship; we have $Timto Mary$ but not $Maryto 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 $Atimes A$ as the set of all possible ordered pairs. That is $Atimes 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 $Atimes 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 Atimes A$.

ANd that's the definition in math of a "relation". A relation on a set $A$ is simply a subset $R$ of $Atimes A$.

So in $R = (a,a),(b,b), (c,c), (b,c),(c,b)subset a,b,ctimes a,b,c$ thought of as the relationship where $a to a; bto b; cto c; bto c;$ and $cto b$.

An eqvalence relation, $R$, on $A$ (so $R subset Aties A$) is one where

i) it is reflexive.

So for every $a in A$ with have $ato a$.

Or in other words $(a,a)in R$.

ii) it is symmetric.

For every pair where $ato b$ then we also have $bto a$.

Or in other words if $(a,b)in R$ then $(b,a)in R$.

iii) it is transitive.

For any $a,b,cin A$ where $ato b$ and $bto 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, Marycup 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.

share|cite|improve this answer

edited Jul 19 at 0:09

answered Jul 18 at 22:32

fleablood

60.4k22575

share|cite|improve this answer

share|cite|improve this answer

edited Jul 19 at 0:09

edited Jul 19 at 0:09

edited Jul 19 at 0:09

answered Jul 18 at 22:32

fleablood

60.4k22575

answered Jul 18 at 22:32

fleablood

60.4k22575

answered Jul 18 at 22:32

fleablood

60.4k22575

60.4k22575

• 
  
  
  

  
  

  
  
  
  
  
  

  
  thanks for the very usefull explanation. I am new to set theory. I have one more question and that is about the "relation" part. How am I to view the relation in this context? Becaus it is all so abstract.
  – Joren Janssens
  Jul 18 at 22:47
  
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  thanks for the very usefull explanation. I am new to set theory. I have one more question and that is about the "relation" part. How am I to view the relation in this context? Becaus it is all so abstract.
  – Joren Janssens
  Jul 18 at 22:47
  
  

  
  
  
  

thanks for the very usefull explanation. I am new to set theory. I have one more question and that is about the "relation" part. How am I to view the relation in this context? Becaus it is all so abstract.
– Joren Janssens
Jul 18 at 22:47

thanks for the very usefull explanation. I am new to set theory. I have one more question and that is about the "relation" part. How am I to view the relation in this context? Becaus it is all so abstract.
– Joren Janssens
Jul 18 at 22:47

add a comment | 

up vote
1
down vote

1. A binary relation on a set $A$ is a subset of $A^2$ and $(a,a), (b,b), (c,c),(b,c),(c,b)$ is indeed a subset of $a,b,c^2$, right?


2. It is not a subset of $a,b,c$. Each if its elements is (and these elements are the equivalence classes).

share|cite|improve this answer

answered Jul 18 at 21:52

José Carlos Santos

114k1698177

• 
  
  
  

  
  

  
  
  
  
  
  

  
  (+1) I would also have asked the OP why they would expect $a,b,c$ to be a subset of $a,b,c$.
  – Arnaud Mortier
  Jul 18 at 21:55
  
  

  
  
  
  

add a comment | 

up vote
1
down vote

1. A binary relation on a set $A$ is a subset of $A^2$ and $(a,a), (b,b), (c,c),(b,c),(c,b)$ is indeed a subset of $a,b,c^2$, right?


2. It is not a subset of $a,b,c$. Each if its elements is (and these elements are the equivalence classes).

share|cite|improve this answer

answered Jul 18 at 21:52

José Carlos Santos

114k1698177

• 
  
  
  

  
  

  
  
  
  
  
  

  
  (+1) I would also have asked the OP why they would expect $a,b,c$ to be a subset of $a,b,c$.
  – Arnaud Mortier
  Jul 18 at 21:55
  
  

  
  
  
  

add a comment | 

up vote
1
down vote

up vote
1
down vote

1. A binary relation on a set $A$ is a subset of $A^2$ and $(a,a), (b,b), (c,c),(b,c),(c,b)$ is indeed a subset of $a,b,c^2$, right?


2. It is not a subset of $a,b,c$. Each if its elements is (and these elements are the equivalence classes).

share|cite|improve this answer

answered Jul 18 at 21:52

José Carlos Santos

114k1698177

1. A binary relation on a set $A$ is a subset of $A^2$ and $(a,a), (b,b), (c,c),(b,c),(c,b)$ is indeed a subset of $a,b,c^2$, right?


2. It is not a subset of $a,b,c$. Each if its elements is (and these elements are the equivalence classes).

share|cite|improve this answer

answered Jul 18 at 21:52

José Carlos Santos

114k1698177

share|cite|improve this answer

share|cite|improve this answer

answered Jul 18 at 21:52

José Carlos Santos

114k1698177

answered Jul 18 at 21:52

José Carlos Santos

114k1698177

answered Jul 18 at 21:52

José Carlos Santos

114k1698177

114k1698177

• 
  
  
  

  
  

  
  
  
  
  
  

  
  (+1) I would also have asked the OP why they would expect $a,b,c$ to be a subset of $a,b,c$.
  – Arnaud Mortier
  Jul 18 at 21:55
  
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  (+1) I would also have asked the OP why they would expect $a,b,c$ to be a subset of $a,b,c$.
  – Arnaud Mortier
  Jul 18 at 21:55
  
  

  
  
  
  

(+1) I would also have asked the OP why they would expect $a,b,c$ to be a subset of $a,b,c$.
– Arnaud Mortier
Jul 18 at 21:55

(+1) I would also have asked the OP why they would expect $a,b,c$ to be a subset of $a,b,c$.
– Arnaud Mortier
Jul 18 at 21:55

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2856043%2fexample-of-equivalence-relation%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email