
Abstract Algebra Abstract Algebra Math Forum 
 LinkBack  Thread Tools  Display Modes 
March 7th, 2013, 10:53 PM  #1 
Member Joined: Aug 2012 Posts: 30 Thanks: 0  equivalence relations
Suppose R is an equivalence relation on a set A, with four equivalence classes. How many different equivalence relations S on A are there for which R?S? Thanking you in anticipation 
March 9th, 2013, 06:13 PM  #2 
Senior Member Joined: Aug 2012 Posts: 2,413 Thanks: 755  Re: equivalence relations
(deleted)

March 11th, 2013, 08:32 PM  #3 
Member Joined: Aug 2012 Posts: 30 Thanks: 0  Re: equivalence relations
The answer that appears in my book is 15. How is that possible? 
March 13th, 2013, 03:29 PM  #4  
Senior Member Joined: Aug 2012 Posts: 2,413 Thanks: 755  Re: equivalence relations Quote:
See http://en.wikipedia.org/wiki/Partition_ ... partitions I counted by hand the number of equivalence relations on a 4element set by enumerating all the possible partitions. * 1element partitions: {1,2,3,4} One of those. * 2element partitions:  {{1,2}, {3,4}}  {{1,3}, {2,4}}  {{1,4}, {2,3}}  {1}, {2,3,4}  {2}, {1,3,4}  {3}, {1,2,4}  {4}, {1,2,3} Seven of those. * 3element partitions:  {{1,2}, {3}, {4}}  {{1,3}, {2}, {4}}  {{1,4}, {2}, {3}}  {{2,3}, {1}, {4}}  {{2,4}, {1}, {1}}  {{3,4}, {1}, {2}} Six of those. * 4element partitions:  {{1}, {2}, {3}, {4}} One of those. Total number of partitions, hence total number of equivalence relations: 1 + 7 + 6 + 1 = 15. The only 4equivclass relation is {{1}, {2}, {3}, {4}}. Which ones is it a subset of? Well, since an equivalence relation must be reflexive, the ordered pairs (1,1), (2,2), (3,3), and (4,4) must be in every possible equivalence relation. So the 4equivclass relation is a subset of every other equivalence relation. So in this case the answer to your original problem is 15. Clearly this number depends on A. I was way too lazy to work this out for any other sets, since the combinatorics rapidly become tedious. Hmmm ... if A has more than 4 elements, perhaps there's some reason that only 15 of the equivalence relations can contain the 4equivclass one. I'll have to think about this some more.  

Tags 
equivalence, relations 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Equivalence Relations!  Jet1045  Abstract Algebra  5  May 19th, 2013 01:03 PM 
equivalence relations  shine123  Applied Math  1  March 5th, 2013 01:52 AM 
Equivalence Relations  astro  Abstract Algebra  4  August 25th, 2010 05:15 AM 
Equivalence relations  remeday86  Applied Math  1  June 13th, 2010 12:10 AM 
equivalence relations  shine123  Number Theory  1  December 31st, 1969 04:00 PM 