[deprosun]

Let S be the set {Maine, New Hampshire, Vermont, Massachusetts, Connecticut, Rhode Island} and let R(x, y) be the relation "state x and state y begin with the same letter". How many (non-empty) sets are in the partition of S corresponding to this equivalence relation?

I don't understand that it's asking me number of sets in a partition. Lets say A = {a,b,c,d,e,f}
a, b, c, d , e, f are the elements of A. Would this be a partition,
A = {{a,b,c},{d,e,f}} ? Would {a,b,c} be a partition of A? If so, what am I answer to how many sets are in the first partition of A? In the partition, there are 3 elements, and its asking me sets.

[mostyfriedman]

yes, {{a, b, c}, {d, e, f}} is a partition of {a, b, c, d, e, f}. What you need to do is just make a partition according to the relation defined and compute its length.

This post has been edited by mostyfriedman: 30 September 2013 - 09:27 AM

[jon.kiparsky]

A partition of a set S is a disjoint collection P of nonempty and distinct subsets of S such that each member of S is member of some (and this exactly one) member of P.

Or in more formal terms: For all s in S, there exists some p in P s.t. s in p. (feel free to replace "For all" with "upside down A" and so forth)

[deprosun]

is {a,b,c} a partition of {a,b,c,d,e,f}?
So will the original question hold this partition:
{{Maine, Massachusetts}, {New Hampshire}, {Vermont}, {Rhode Island}, {Connecticut}}, giving me the answer 5?

[jon.kiparsky]

deprosun, on 30 September 2013 - 11:36 AM, said:

is {a,b,c} a partition of {a,b,c,d,e,f}?

Consider e. Is there a set p in your partition s.t. e is in p?
(hint: a partition is a collection of sets)

Quote

So will the original question hold this partition:
{{Maine, Massachusetts}, {New Hampshire}, {Vermont}, {Rhode Island}, {Connecticut}}, giving me the answer 5?

Yes, this is a correct partition according to the specified relation.

[deprosun]

Oh!! there isn't. So the correct partition would be {{a,b,c}, {d}, {e}, {f}}...well one possible way of displaying partition.

This post has been edited by deprosun: 30 September 2013 - 09:43 AM

[jon.kiparsky]

That's a correct partition. You can come up with others - a bit of math will tell you how many to look for. This is a good exercise: how many partitions are there of a set with cardinality N?

[deprosun]

2^N.....learned that last semester. Wow,everything just falls into place

[jon.kiparsky]

Really? Please list the 8 partitions of {a, b, c}

(actually, this is a little harder than I made it sound, but it's fun to think about)

[deprosun]

ab, bc, ba, ca, abc, a, b, c. Isn't this just calculating total subsets of {a,b,c}?

This post has been edited by deprosun: 30 September 2013 - 10:25 AM

[jon.kiparsky]

You're right, the power set of S has cardinality |S|^N. That's a different question, though.

I get five partitions. (using the definition above, which is the standard one)

[deprosun]

How did you get five partitions, again? What formula did you use?

[jon.kiparsky]

Exhaustive list:

{{1,2,3}}
{{1,2},{3}}
{{1,3},{2}}
{{3,2},{1}}
{{1},{2},{3}}

There can be no others. Proof by assertion for the moment, since a real proof is more tedious than informative, but you may feel free to prove it if you like. Use the definition of a partition. (no non-empty members, represents each element of S exactly once)

The math for the general case is found under the heading of "Bell's Number".

[deprosun]

Oh i see. Gotchya. Thanks for taking time!

[jon.kiparsky]

No bother. Nice to review.