Talk:Partition of a set

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated C-class, High-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
C Class
High Importance
 Field: Foundations, logic, and set theory

Displayed TeX whithin a link[edit]

I just included some displayed TeX within in a link, thus:

The [[integer partition | partition

:<math>etc. etc.</math>

of the integer]] n ...

It seems to work: you can click on the word partition, or on the displayed TeX, or on the following phrase, and get the integer partition page. Michael Hardy 20:07, 5 Feb 2004 (UTC)

Definition correct?[edit]

Is the definition of partition entirely correct / undisputed?

specifically I wonder about the requirement that the elements of the partition needing to be non-empty.

The definition given in Potter, M. "Set theory and its philosophy", ( 2004, Oxford University Press ), on p. 130 is:

"Definition. A collection B of subsets of A is a partition of A if each element of A belongs to exactly one element of B.

According to this definition, A is a partition of itself, since it certainly is a subset of itself, and furthermore { A, {null} } is also a partition of A - since there is no restriction on the elements being null.

This does not seem to quite capture the essence of partition to me, but it does seem a commonly used definition - ie see the MathWorld definition: http://mathworld.wolfram.com/SetPartition.html

so I'm wondering whether the article should be updated to clarify this ambiguity - that there are at least two alternate definitions being used.

--Corvi42 04:15, 10 Jun 2005 (UTC)

Ok, I went ahead and added a small addendum to axiom 1 saying that it is not included in all definitions.

Also, how is it that Axiom 1 can be vacuously true for the empty set - it contradicts Axiom 1!

--Corvi42 04:27, 10 Jun 2005 (UTC)

Again, I went ahead and corrected the erroneous example of the empty set, and added a few more examples. --Corvi42 15:02, 10 Jun 2005 (UTC)

You are wrong about the empty set. The partition with 0 blocks satisfies all the axioms including Axiom 1. --Zero 16:55, 10 Jun 2005 (UTC)

The partition P is a set of sets. In a set of sets there may be at most an occurrence of \emptyset . Allowing for no occurrences makes sense; otherwise for any partition with no empty set you would have one companion partition with one empty set, and this would not provide much more interest and breadth of application to the mathematical theory.

Mennucc (talk) 10:44, 25 March 2009 (UTC)

Something which currently is incorrect in this section, is the statement "This is equivalent to ...". The second "definition" is not equivalent to the first one. The first says "A partition is a set of nonempty subsets such that...". The second says, "A set of nonempty subsets is a partition if ...". Obviously, the two statements are not equivalent. For example, the second does not say anything about the set {{}}, which may not or may be a partition, according to this "definition". And also, if one of the following properties are not satisfied, the statement does not say whether we have a partition or not. — MFH:Talk 13:17, 20 September 2011 (UTC)

PS: I just made the necessary change to correct this. — MFH:Talk 13:23, 20 September 2011 (UTC)

Where does axiom 1 come from?[edit]

Just out of curiosity - where does axiom 1 come from? So far I haven't found any definition which has this axiom other than this page and other online definitions which are obviously copies of this page. The definition in Britannica doesn't include this restriction either: set partition

The first four books I pulled from my library shelves, all define a partition as a collection of non-empty sets:
  • Naive Set Theory, Paul Halmos
  • Set Theory and Logic, Robert R. Stoll
  • Axiomatic Set Theory, Patrick Suppes
  • Set Theory, Seymour Lipschutz
See also: PlanetMath
The definition you mention above from Mathworld is inconsistent with Mathworld's own definition of Bell number. It is a common oversight by authors to forget to take into account the empty set. Where else have you found the definition not to include axiom 1?
Paul August 22:57, Jun 10, 2005 (UTC)



Thanks for the references Paul. I suspected that there ought to be many, but couldn't find any myself, which got me curious. Given the "intuitive" interpretation of what a partition is, axiom 1 certainly makes sense - but it does add some theoretical complications for general theorems like "any subset and its complement is a partition" - so I can also see why some might choose not to include it.

As I mentioned above, my sources which did not use axiom 1 were the Mathworld reference, which seems to be problematic from what you say, also the Britannica reference and the Potter, M book "Set theory and its philosophy".

Anyway - thanks for the clarification. --Corvi42 22:38, 12 Jun 2005 (UTC)

You're very welcome, glad to help. Paul August 00:36, Jun 13, 2005 (UTC)

Counting Partitions[edit]

I was looking for a formula for the number of partitions of an n-element set into exactly k subsets each of size n/k, where k evenly divides n. For example, say you have 12 donuts, each a different kind; how many ways are there to divide them into four sets of three donuts to give to four cops? I couldn't find the answer, but derived the following, which I think is correct. I'm suggesting a notation here, too, along the lines of the "n choose k = nCk" notation. It might be nice to include this formula in the Counting section:

n\ partition\ k = \ _n\!T_k = \begin{bmatrix}
n \\
k 
\end{bmatrix} = {n! \over k! (({n \over k})!)^k}

The numerator is the number of ways to permute the order of the n-element set members, the first denominator term is the number of ways to permute the order of the resulting k subsets, and the second denominator term is the number of ways to permute the order of the members of the k subsets. Tedtoal (talk) 00:45, 1 July 2010 (UTC)

See Multinomial theorem#Ways to put objects into sized boxes. The connection between partitions and multinomial coefficients needs presentation in this article, though it needs care. For multinomial coefficients the order of the parts is significant but for partitions it is (usually) not significant. One can't in general just adjust the count by the factorial of the number of parts, though it is valid if empty parts are forbidden as they are here. Zerotalk 05:18, 3 July 2010 (UTC)

ME & CE[edit]

I added the line about ME and CE in the introduction. I see that there has been some discussion about the basic concept of partitioning here, so if this edit violates any of the more formal aspects of the definition please feel free to revert. capitalist 09:15, 19 October 2005 (UTC)

Improving readability[edit]

I've just completed various changes that I think make this article clearer. The only one I think the slightest bit controversial was deleting the material about the Faà di Bruno formula. I reduced it to an entry in See Also for two reasons. First, it was a verbatim repeat from the other article, and second, I couldn't figure out for the life of me what it was even trying to mean (OK, maybe I'm dense...) I'd suggest somebody who does get it ought to clarify the passage in the other article.—PaulTanenbaum (talk) 06:02, 20 March 2009 (UTC)

So "exhaustive" is redundant in "exhaustive partition"?[edit]

A partition covers the entire set, so it is exhaustive. If that is the case, we should not waste words and possibly create confusion by using the term "exhaustive partition".192.139.122.42 (talk) 20:54, 23 October 2012 (UTC)

Within the framework of set theory, I have never encountered the phrase ‘exhaustive partition’, and the article does not contain that phrase, as far as I can see. It only mentions the word ‘exhaustive’ in the lead section, where it is part of the definition: “More formally, these "cells" are both collectively exhaustive and mutually exclusive with respect to the set being partitioned.” — Tobias Bergemann (talk) 11:35, 24 October 2012 (UTC)

I think by "exhaustive partition" they may be referring to a power set, which is a set containing all possible subsets of the universal set.71.84.57.140 (talk) 02:23, 16 August 2013 (UTC)