Namespaces
Variants
Actions

Difference between revisions of "Partition"

From Encyclopedia of Mathematics
Jump to: navigation, search
(→‎Comments: LaTeX part)
 
(7 intermediate revisions by one other user not shown)
Line 1: Line 1:
 
{{MSC|54B}}
 
{{MSC|54B}}
{{TEX|part}}
+
{{TEX|done}}
 
==Of a topological space==
 
==Of a topological space==
A closed set $E$ in a topological space $X$ that partitions $X$ between two given sets $P$ and $Q$ (or, in other words, separates $P$ and $Q$ in $X$), i.e. such that $X \setminus E = H_1 \cup H_2$, where $H_1$ and $H_2$ are disjoint and open in $X \setminus E$, $P \subseteq H_1$, $Q \subseteq H_2$ ($P$ and $Q$ are open in all of $X$). A partition is called fine if its interior is empty. Any binary [[Decomposition|decomposition]] (i.e. a partition consisting of two elements) $\alpha = (A_1,A_2)$ of a space $X$ defines a fine partition in $X$: $B$ is the boundary of $A_1$, which is the boundary of $A_2$, where $X\setminus B = O_1 \cup O_2$, in which $O_i$ is the open kernel (cf. [[Kernel of a set|Kernel of a set]]) of $A_i$, $i=1,2$. The converse is also true. In essence, the concept of a partition between sets leads to the concept of connectedness. The converse also applies: A space $X$ is disconnected if $\emptyset$ is a partition between non-empty sets.
+
A closed set $E$ in a topological space $X$ that partitions $X$ between two given sets $P$ and $Q$ (or, in other words, separates $P$ and $Q$ in $X$), i.e. such that $X \setminus E = H_1 \cup H_2$, where $H_1$ and $H_2$ are disjoint and open in $X \setminus E$, $P \subseteq H_1$, $Q \subseteq H_2$ ($P$ and $Q$ are open in all of $X$). A partition is called fine if its interior is empty. Any binary [[Decomposition|decomposition]] (i.e. a partition consisting of two elements) $\alpha = (A_1,A_2)$ of a space $X$ defines a fine partition in $X$: $B$ is the boundary of $A_1$, which is the boundary of $A_2$, where $X\setminus B = O_1 \cup O_2$, in which $O_i$ is the [[Interior of a set|interior]] of $A_i$, $i=1,2$. The converse is also true. In essence, the concept of a partition between sets leads to the concept of connectedness. The converse also applies: A space $X$ is disconnected if $\emptyset$ is a partition between non-empty sets.
  
  
Line 9: Line 9:
 
Related notions in this context are those of a separator and of a cut.
 
Related notions in this context are those of a separator and of a cut.
  
If $A$ and $B$ are disjoint subsets of a space $X$, then a ''separator'' between$A$ and $B$ is a set $S$ such that $X \setminus S = V \cup W$ with $V$ and $WW$ disjoint and open in $X \setminus S$, and $A \subseteq V$ and $B \subseteq W$. So a partition is a closed separator.
+
If $A$ and $B$ are disjoint subsets of a space $X$, then a ''separator'' between$A$ and $B$ is a set $S$ such that $X \setminus S = V \cup W$ with $V$ and $W$ disjoint and open in $X \setminus S$, and $A \subseteq V$ and $B \subseteq W$. So a partition is a closed separator.
  
 
A set $C$ is a cut between $A$ and $B$ if $C$ intersects every [[continuum]] that intersects both $A$ and $B$.
 
A set $C$ is a cut between $A$ and $B$ if $C$ intersects every [[continuum]] that intersects both $A$ and $B$.
  
 
One readily sees that every partition is a separator and that every separator is a cut, and the following examples show that the notions are in general distinct: the open interval $(0,1)$ is a separator between $\{0\}$ and $\{1\}$ in the interval $[0,1]$, but not a partition; in the well-known subspace $\{0\} \times [-1,1] \cup \{ (x,\sin(1/x)) : 0 < x \le 1 \}$ of the Euclidean space, the point $(0,0)$ is a cut but not a separator between the points $(0,1)$ and $(1,\sin 1)$.
 
One readily sees that every partition is a separator and that every separator is a cut, and the following examples show that the notions are in general distinct: the open interval $(0,1)$ is a separator between $\{0\}$ and $\{1\}$ in the interval $[0,1]$, but not a partition; in the well-known subspace $\{0\} \times [-1,1] \cup \{ (x,\sin(1/x)) : 0 < x \le 1 \}$ of the Euclidean space, the point $(0,0)$ is a cut but not a separator between the points $(0,1)$ and $(1,\sin 1)$.
 +
 +
====References====
 +
<table>
 +
<TR><TD valign="top">[a4]</TD> <TD valign="top">  R. Engelking,  "Dimension theory" , North-Holland &amp; PWN  (1978)  pp. 19; 50</TD></TR>
 +
</table>
  
 
{{MSC|11P}}
 
{{MSC|11P}}
  
 
==Of a positive integer==
 
==Of a positive integer==
A partition of a positive integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071740/p07174056.png" /> is a decomposition of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071740/p07174057.png" /> as a sum of positive integers. For example, the partitions of 4 read: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071740/p07174058.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071740/p07174059.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071740/p07174060.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071740/p07174061.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071740/p07174062.png" />. The number of different partitions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071740/p07174063.png" /> is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071740/p07174064.png" />. So, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071740/p07174065.png" />. L. Euler gave a non-trivial recurrence relation for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071740/p07174066.png" /> (see [[#References|[a1]]]) and Ramanujan discovered the surprising congruences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071740/p07174067.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071740/p07174068.png" />), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071740/p07174069.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071740/p07174070.png" />), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071740/p07174071.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071740/p07174072.png" />), and others. He also found the asymptotic relation
+
A partition of a positive integer $n$ is a decomposition of $n$ as a sum of positive integers. For example, the partitions of $4$ read: $4$, $3+1$, $2+2$, $2+1+1$, $1+1+1+1$. The ''[[Partition function (number theory)|partition function]]'' $p(n)$ gives the number of different partitions of $n$. So, $p(4) = 5$. L. Euler gave a non-trivial recurrence relation for $p(n)$ (see [[#References|[a1]]]) and Ramanujan discovered the surprising congruences $p(5n+4) \equiv 0 \pmod 5$, $p(7m+5) \equiv 0 \pmod 7$, $p(11m+6) \equiv 0 \pmod{11}$, and others. He also found the asymptotic relation
 +
$$
 +
p(n) \sim \frac{e^{K\sqrt n}}{4n\sqrt3}\ \ \ \text{as}\ n\rightarrow \infty
 +
$$
 +
where $K=\pi\sqrt{2/3}$. Later this was completed to an exact series expansion by H. Rademacher (see [[#References|[a2]]]).
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071740/p07174073.png" /></td> </tr></table>
+
One can also distinguish other partitions, having particular properties, such as the numbers in the decomposition being distinct (see [[#References|[a3]]]). See also [[Additive number theory]]; [[Additive problems]].
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p071/p071740/p07174074.png" />. Later this was completed to an exact series expansion by H. Rademacher (see [[#References|[a2]]]).
+
====References====
 +
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  G.H. Hardy,  E.M. Wright,  "An introduction to the theory of numbers" , Oxford Univ. Press  (1979)  pp. Chapt. XVI</TD></TR>
 +
<TR><TD valign="top">[a2]</TD> <TD valign="top">  T.M. Apostol,  "Modular functions and Dirichlet series in number theory" , Springer  (1976)</TD></TR>
 +
<TR><TD valign="top">[a3]</TD> <TD valign="top"> G.E. Andrews,  "The theory of partitions" , Addison-Wesley  (1976)</TD></TR>
 +
</table>
  
One can also distinguish other partitions, having particular properties, such as the numbers in the decomposition being distinct (see [[#References|[a3]]]). See also [[Additive number theory|Additive number theory]]; [[Additive problems|Additive problems]].
+
==Of a set==
 +
Expression of a set $Y$ as a [[disjoint union]] of subsets: a family of subsets $X_\lambda \subseteq Y$ for $\lambda \in \Lambda$, for some index set $\Lambda$, which are pairwise disjoint, $\lambda \neq \mu \Rightarrow X_\lambda \cap X_\mu = \emptyset$ and such that the union $\bigcup_{\lambda \in \Lambda} X_\lambda = Y$.  The classes of an [[equivalence relation]] on $Y$ form a partition of $Y$, as does the [[kernel of a function]]; conversely a partition defines an equivalence relation and a function giving rise to that partition.    See also [[Decomposition]].
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  G.H. Hardy,   E.M. Wright,   "An introduction to the theory of numbers" , Oxford Univ. Press  (1979)  pp. Chapt. XVI</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  T.M. Apostol,  "Modular functions and Dirichlet series in number theory" , Springer (1976)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  G.E. Andrews,  "The theory of partitions" , Addison-Wesley  (1976)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  R. Engelking,  "Dimension theory" , North-Holland &amp; PWN  (1978)  pp. 19; 50</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[b1]</TD> <TD valign="top">  P. R. Halmos, ''Naive Set Theory'', Undergraduate Texts in Mathematics, Springer (1960) {{ISBN|0-387-90092-6}}</TD></TR>
 +
</table>

Latest revision as of 15:32, 11 November 2023

2020 Mathematics Subject Classification: Primary: 54B [MSN][ZBL]

Of a topological space

A closed set $E$ in a topological space $X$ that partitions $X$ between two given sets $P$ and $Q$ (or, in other words, separates $P$ and $Q$ in $X$), i.e. such that $X \setminus E = H_1 \cup H_2$, where $H_1$ and $H_2$ are disjoint and open in $X \setminus E$, $P \subseteq H_1$, $Q \subseteq H_2$ ($P$ and $Q$ are open in all of $X$). A partition is called fine if its interior is empty. Any binary decomposition (i.e. a partition consisting of two elements) $\alpha = (A_1,A_2)$ of a space $X$ defines a fine partition in $X$: $B$ is the boundary of $A_1$, which is the boundary of $A_2$, where $X\setminus B = O_1 \cup O_2$, in which $O_i$ is the interior of $A_i$, $i=1,2$. The converse is also true. In essence, the concept of a partition between sets leads to the concept of connectedness. The converse also applies: A space $X$ is disconnected if $\emptyset$ is a partition between non-empty sets.


Comments

Related notions in this context are those of a separator and of a cut.

If $A$ and $B$ are disjoint subsets of a space $X$, then a separator between$A$ and $B$ is a set $S$ such that $X \setminus S = V \cup W$ with $V$ and $W$ disjoint and open in $X \setminus S$, and $A \subseteq V$ and $B \subseteq W$. So a partition is a closed separator.

A set $C$ is a cut between $A$ and $B$ if $C$ intersects every continuum that intersects both $A$ and $B$.

One readily sees that every partition is a separator and that every separator is a cut, and the following examples show that the notions are in general distinct: the open interval $(0,1)$ is a separator between $\{0\}$ and $\{1\}$ in the interval $[0,1]$, but not a partition; in the well-known subspace $\{0\} \times [-1,1] \cup \{ (x,\sin(1/x)) : 0 < x \le 1 \}$ of the Euclidean space, the point $(0,0)$ is a cut but not a separator between the points $(0,1)$ and $(1,\sin 1)$.

References

[a4] R. Engelking, "Dimension theory" , North-Holland & PWN (1978) pp. 19; 50

2020 Mathematics Subject Classification: Primary: 11P [MSN][ZBL]

Of a positive integer

A partition of a positive integer $n$ is a decomposition of $n$ as a sum of positive integers. For example, the partitions of $4$ read: $4$, $3+1$, $2+2$, $2+1+1$, $1+1+1+1$. The partition function $p(n)$ gives the number of different partitions of $n$. So, $p(4) = 5$. L. Euler gave a non-trivial recurrence relation for $p(n)$ (see [a1]) and Ramanujan discovered the surprising congruences $p(5n+4) \equiv 0 \pmod 5$, $p(7m+5) \equiv 0 \pmod 7$, $p(11m+6) \equiv 0 \pmod{11}$, and others. He also found the asymptotic relation $$ p(n) \sim \frac{e^{K\sqrt n}}{4n\sqrt3}\ \ \ \text{as}\ n\rightarrow \infty $$ where $K=\pi\sqrt{2/3}$. Later this was completed to an exact series expansion by H. Rademacher (see [a2]).

One can also distinguish other partitions, having particular properties, such as the numbers in the decomposition being distinct (see [a3]). See also Additive number theory; Additive problems.

References

[a1] G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers" , Oxford Univ. Press (1979) pp. Chapt. XVI
[a2] T.M. Apostol, "Modular functions and Dirichlet series in number theory" , Springer (1976)
[a3] G.E. Andrews, "The theory of partitions" , Addison-Wesley (1976)

Of a set

Expression of a set $Y$ as a disjoint union of subsets: a family of subsets $X_\lambda \subseteq Y$ for $\lambda \in \Lambda$, for some index set $\Lambda$, which are pairwise disjoint, $\lambda \neq \mu \Rightarrow X_\lambda \cap X_\mu = \emptyset$ and such that the union $\bigcup_{\lambda \in \Lambda} X_\lambda = Y$. The classes of an equivalence relation on $Y$ form a partition of $Y$, as does the kernel of a function; conversely a partition defines an equivalence relation and a function giving rise to that partition. See also Decomposition.

References

[b1] P. R. Halmos, Naive Set Theory, Undergraduate Texts in Mathematics, Springer (1960) ISBN 0-387-90092-6
How to Cite This Entry:
Partition. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Partition&oldid=35401
This article was adapted from an original article by M.I. Voitsekhovskii (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article