My Math Forum  

Go Back   My Math Forum > College Math Forum > Abstract Algebra

Abstract Algebra Abstract Algebra Math Forum


Reply
 
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
shine123 is offline  
 
March 9th, 2013, 06:13 PM   #2
Senior Member
 
Joined: Aug 2012

Posts: 2,333
Thanks: 724

Re: equivalence relations

(deleted)
Maschke is offline  
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?
shine123 is offline  
March 13th, 2013, 03:29 PM   #4
Senior Member
 
Joined: Aug 2012

Posts: 2,333
Thanks: 724

Re: equivalence relations

Quote:
Originally Posted by shine123
The answer that appears in my book is 15.
How is that possible?
Is it possible that A is restricted to have 4 elements?

See

http://en.wikipedia.org/wiki/Partition_ ... partitions

I counted by hand the number of equivalence relations on a 4-element set by enumerating all the possible partitions.

* 1-element partitions:

{1,2,3,4}

One of those.

* 2-element 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.

* 3-element 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.

* 4-element 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 4-equiv-class 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 4-equiv-class 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 4-equiv-class one. I'll have to think about this some more.
Maschke is offline  
Reply

  My Math Forum > College Math Forum > Abstract Algebra

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





Copyright © 2019 My Math Forum. All rights reserved.