A partition of U into 6 blocks:
a Venn diagram representation.

In mathematics, a partition of a set X is a division of X into non-overlapping "parts" or "blocks" or "cells" that cover all of X. Venn diagrams, Euler diagrams (pronounced oiler) and Johnston diagrams are similar-looking illustrations of set, mathematical or logical relationships. ... Mathematics, often abbreviated maths in Commonwealth English and math in American English, is the study of abstraction. ... This article is about sets in mathematics. ...

Definition

A partition of a set X is a set of nonempty subsets of X such that every element x in X is in exactly one of these subsets. In set theory, a set is called non-empty (or nonempty) if it contains at least one element, and is therefore not the empty set. ... A is a subset of B If X and Y are sets and every element of X is also an element of Y, then we say or write: X is a subset of (or is included in) Y; X ⊆ Y; Y is a superset of (or includes) X; Y ⊇ X...

Equivalently, a set P of subsets of X, is a partition of X if

1. No element of P is empty.
2. The union of the elements of P is equal to X. (We say the elements of P cover X.)
3. The intersection of any two elements of P is empty. (We say the elements of P are pairwise disjoint.)

The elements of P are sometimes called the blocks of the partition. In mathematics, the empty set is the set with no elements. ... In set theory and other branches of mathematics, the union of a collection of sets is the set that contains everything that belongs to any of the sets, but nothing else. ... In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B (or equivalently, all elements of B that also belong to A), but no other elements. ... In mathematics, two sets are said to be disjoint if they have no element in common. ...

Examples

• Every singleton set {x} has exactly one partition, namely { {x} }.
• The empty set has exactly one partition, namely itself. (Axioms 1 and 3 are vacuously satisfied.)
• Forgetting momentarily about certain exotic cases, the set of all humans can be partitioned into two blocks: the males and the females.
• For any non-empty subset A of a set U, then A together with its complement is a partition of U.
• The set { 1, 2, 3 } has these five partitions.
  • { {1}, {2}, {3} }, sometimes denoted by 1/2/3.
  • { {1, 2}, {3} }, sometimes denoted by 12/3.
  • { {1, 3}, {2} }, sometimes denoted by 13/2.
  • { {1}, {2, 3} }, sometimes denoted by 1/23.
  • { {1, 2, 3} }, sometimes denoted by 123.
• Note that
  • { {}, {1,3}, {2} } is not a partition (of any set) because it contains the empty set.
  • { {1,2}, {2, 3} } is not a partition (of any set) because the element 2 is contained in more than one distinct subset.
  • { {1}, {2} } is not a partition of {1, 2, 3} because none of its blocks contains 3; however, it is a partition of {1, 2}.

Informally, a logical statement is vacuously true if it is true but doesnt say anything; examples are statements of the form everything with property A also has property B, where there is nothing with property A. It is tempting to dismiss this concept as vacuous or silly. ... Binomial name Homo sapiens Linnaeus, 1758 Subspecies Homo sapiens idaltu (extinct) Homo sapiens sapiens Human beings define themselves in biological, social, and spiritual terms. ... In set theory and other branches of mathematics, two kinds of complements are defined, the relative complement and the absolute complement. ...

Partitions and equivalence relations

If an equivalence relation is given on the set X, then the set of all equivalence classes forms a partition of X. Conversely, if a partition P is given on X, we can define an equivalence relation on X by writing x ~ y iff there exists a member of P which contains both x and y. The notions of "equivalence relation" and "partition" are thus essentially equivalent. In mathematics, an equivalence relation on a set X is a binary relation on X that is reflexive, symmetric and transitive, i. ... In mathematics, given a set X and an equivalence relation ~ on X, the equivalence class of an element a in X is the subset of all elements in X which are equivalent to a: [a] = { x in X | x ~ a } The notion of equivalence classes is useful for constructing sets... In mathematics, philosophy, logic and technical fields that depend on them, iff is used as an abbreviation for if and only if. It is often, not always, written italicized: iff. ...

Partial ordering of the lattice of partitions

Given two partitions π and ρ of a given set X, we say that π is finer than ρ, or, equivalently, that ρ is coarser than π, if π splits the set X into smaller blocks than ρ does, i.e. if every element of π is a subset of some element of ρ. In that case, one writes π ≤ ρ.

The relation of "being-finer-than" is a partial order on the set of all partitions of the set X, and indeed even a complete lattice. In case n = 4, the partial order of the set of all 15 partitions is depicted in this Hasse diagram: In mathematics, a partially ordered set (or poset for short) is a set equipped with a special binary relation which formalizes the intuitive concept of an ordering. ... See lattice for other mathematical as well as non-mathematical meanings of the term. ... In the mathematical area of order theory, a Hasse diagram (pronounced HAHS uh, named after Helmut Hasse (1898–1979)) is a simple picture of a finite partially ordered set. ...

Noncrossing partitions

The lattice of noncrossing partitions of a finite set has recently taken on importance because of its role in free probability theory. These form a subset of the lattice of all partitions, but not a sublattice, since the join operations of the two lattices do not agree. In combinatorial mathematics, the topic of noncrossing partitions has assumed some importance because of (among other things) its application to the theory free probability. ... Free probability is a mathematical theory which studies non-commutative random variables. ...

The number of partitions

The Bell number B_n, named in honor of Eric Temple Bell, is the number of different partitions of a set with n elements. The first several Bell numbers are B₀ = 1, B₁ = 1, B₂ = 2, B₃ = 5, B₄ = 15, B₅ = 52, B₆ = 203. The Bell numbers, named in honor of Eric Temple Bell, are a sequence of integers arising in combinatorics that begins thus (sequence A000110 in OEIS): In general, Bn is the number of partitions of a set of size n. ... Eric Temple Bell (1883 - 1960) was a mathematician born in Scotland who lived in the USA from 1903 until his death. ...

The Stirling number S(n, k) of the second kind is the number of partitions of a set of size n into k blocks. Stirling numbers of the first kind In combinatorics, unsigned Stirling numbers of the first kind s(n,k) (with a lower-case s) count the number of permutations of n elements with k disjoint cycles. ...

The number of partitions of a set of size n corresponding to the integer partition In mathematics, a partition of a positive integer n is a way of writing n as a sum of positive integers. ...

of n, is the Faà di Bruno coefficient

The number of noncrossing partitions of a set of size n is the nth Catalan number, given by In combinatorial mathematics, the topic of noncrossing partitions has assumed some importance because of (among other things) its application to the theory free probability. ... The Catalan numbers, named after the Belgian mathematician Eugène Charles Catalan (1814—1894), form a sequence of natural numbers that occur in various counting problems in combinatorics. ...

See also

• exponential formula
• integer partition
• list of partition topics
• data clustering