My Math Forum equivalence relations

 Abstract Algebra Abstract Algebra Math Forum

 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,333 Thanks: 724 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,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.

 Tags equivalence, relations

 Thread Tools Display Modes Linear Mode

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

 Contact - Home - Forums - Cryptocurrency Forum - Top