Partición de un conjunto

En matemáticas , una partición de un conjunto es una agrupación de sus elementos en subconjuntos no vacíos , de tal manera que cada elemento esté incluido en exactamente un subconjunto.

Toda relación de equivalencia en un conjunto define una partición de dicho conjunto, y toda partición define una relación de equivalencia. Un conjunto dotado de una relación de equivalencia o una partición se denomina a veces setoide , generalmente en teoría de tipos y teoría de la demostración .

Una partición de un conjunto X es un conjunto de subconjuntos no vacíos de X tales que cada elemento x en X está en exactamente uno de estos subconjuntos ^{[ 2 ]} (es decir, los subconjuntos son conjuntos mutuamente disjuntos no vacíos ).

De forma equivalente, una familia de conjuntos P es una partición de X si y solo si se cumplen todas las siguientes condiciones: ^{[ 3 ]}

• La familia P no contiene el conjunto vacío (es decir,${\displaystyle \emptyset \notin P}$).
• La unión de los conjuntos en P es igual a X (es decir,${\displaystyle \textstyle \bigcup _ {A\in P}A=X}$). Se dice que los conjuntos en P agotan o cubren X. Véase también eventos colectivamente exhaustivos y cobertura (topología) .
• La intersección de cualesquiera dos conjuntos distintos en P es vacía (es decir,${\displaystyle (\forall A,B\in P)\;A\neq B\implies A\cap B=\emptyset }$). Se dice que los elementos de P son disjuntos por pares o mutuamente excluyentes. Véase también exclusividad mutua .

Los conjuntos en${\displaystyle P}$se denominan bloques , partes o celdas de la partición. ^{[ 4 ]} Si${\displaystyle a\in X}$luego representamos la célula que contiene${\displaystyle a}$por${\displaystyle [a]}$. Es decir,${\displaystyle [a]}$es notación para la celda en${\displaystyle P}$que contiene${\displaystyle a}$.

Cada partición${\displaystyle P}$puede identificarse con una relación de equivalencia en${\displaystyle X}$, es decir la relación${\displaystyle \sim _{\!P}}$de tal manera que para cualquier${\displaystyle a,b\in X}$tenemos${\displaystyle a\sim _{\!P}b}$si y solo si${\displaystyle a\in [b]}$(equivalentemente, si y solo si${\displaystyle b\in [a]}$). La notación${\displaystyle \sim _{\!P}}$evoca la idea de que la relación de equivalencia puede construirse a partir de la partición. A la inversa, toda relación de equivalencia puede identificarse con una partición. Por eso, a veces se dice informalmente que "una relación de equivalencia es lo mismo que una partición". Si P es la partición identificada con una relación de equivalencia dada${\displaystyle \sim }$, entonces algunos autores escriben${\displaystyle P=X/{\sim }}$Esta notación sugiere que la partición es el conjunto X dividido en celdas. Además, evoca la idea de que, a partir de la relación de equivalencia, se puede construir la partición.

• El conjunto vacío${\displaystyle \emptyset }$tiene exactamente una partición, a saber:${\displaystyle \emptyset }$(Nota: esta es la partición, no un miembro de la partición).
• Para cualquier conjunto no vacío X , P = { X } es una partición de X , llamada partición trivial .
  • En particular, cada conjunto unitario { x } tiene exactamente una partición, a saber, { { x } } .
• Para cualquier subconjunto propio no vacío A de un conjunto U , el conjunto A junto con su complemento forman una partición de U , a saber, { A , U ∖ A } .
• El conjunto {1, 2, 3} tiene estas cinco particiones (una partición por elemento):
  • { {1}, {2}, {3} } , a veces escrito 1 | 2 | 3.
  • { {1, 2}, {3} } , o 1 2 | 3.
  • { {1, 3}, {2} } , o 1 3 | 2.
  • { {1}, {2, 3} } , o 1 | 2 3.
  • { {1, 2, 3} } , o 1 2 3.
• Las siguientes no son particiones de {1, 2, 3} :
  • { {}, {1, 3}, {2} } no es una partición (de ningún conjunto) porque uno de sus elementos es el conjunto vacío .
  • { {1, 2}, {2, 3} } no es una partición (de ningún conjunto) porque el elemento 2 está contenido en más de un bloque.
  • { {1}, {2} } no es una partición de {1, 2, 3} porque ninguno de sus bloques contiene 3; sin embargo, es una partición de {1, 2} .

Para cualquier relación de equivalencia en un conjunto X , el conjunto de sus clases de equivalencia es una partición de X. Recíprocamente, a partir de cualquier partición P de X , podemos definir una relación de equivalencia en X estableciendo x ~ y precisamente cuando x e y están en la misma parte de P. Por lo tanto, las nociones de relación de equivalencia y partición son esencialmente equivalentes. ^{[ 5 ]}

El axioma de elección garantiza que, para cualquier partición de un conjunto X, existe un subconjunto de X que contiene exactamente un elemento de cada parte de la partición. Esto implica que, dada una relación de equivalencia en un conjunto, se puede seleccionar un elemento representativo canónico de cada clase de equivalencia.

Una partición α de un conjunto X es un refinamiento de una partición ρ de X —y decimos que α es más fina que ρ y que ρ es más gruesa que α— si cada elemento de α es un subconjunto de algún elemento de ρ . De manera informal, esto significa que α es una fragmentación adicional de ρ . En ese caso, se escribe que α ≤ ρ .

Esta relación de "mayor que" en el conjunto de particiones de X es un orden parcial (por lo que la notación "≤" es apropiada). Cada conjunto de elementos tiene un límite superior mínimo (su "unión") y un límite inferior máximo (su "encuentro"), de modo que forma un retículo , y más específicamente (para particiones de un conjunto finito) es un retículo geométrico y supersoluble . ^{[ 6 ] [ 7 ]} El retículo de partición de un conjunto de 4 elementos tiene 15 elementos y se representa en el diagrama de Hasse de la izquierda.

La intersección y unión de las particiones α y ρ se definen de la siguiente manera. La intersección${\displaystyle \alpha \wedge \rho }$es la partición cuyos bloques son las intersecciones de un bloque de α y un bloque de ρ , excepto el conjunto vacío. En otras palabras, un bloque de${\displaystyle \alpha \wedge \rho }$es la intersección de un bloque de α y un bloque de ρ que no son disjuntos entre sí. Para definir la unión${\displaystyle \alpha \vee \rho }$, se forma una relación en los bloques A de α y los bloques B de ρ mediante A ~ B si A y B no son disjuntos. Entonces${\displaystyle \alpha \vee \rho }$es la partición en la que cada bloque C es la unión de una familia de bloques conectados por esta relación.

Basándose en la equivalencia entre retículos geométricos y matroides , este retículo de particiones de un conjunto finito corresponde a un matroide en el que el conjunto base del matroide consiste en los átomos del retículo, es decir, las particiones con${\displaystyle n-2}$Conjuntos unitarios y un conjunto de dos elementos. Estas particiones atómicas se corresponden biunívocamente con las aristas de un grafo completo . El cierre matroide de un conjunto de particiones atómicas es el engrosamiento común más fino de todos ellos; en términos de teoría de grafos, es la partición de los vértices del grafo completo en las componentes conexas del subgrafo formado por el conjunto de aristas dado. De esta manera, la red de particiones se corresponde con la red de planos del matroide gráfico del grafo completo.

Otro ejemplo ilustra el refinamiento de particiones desde la perspectiva de las relaciones de equivalencia. Si D es el conjunto de cartas de una baraja estándar de 52 cartas, la relación de igual color en D (que se puede denotar como ~ _C ) tiene dos clases de equivalencia: los conjuntos {cartas rojas} y {cartas negras}. La partición de dos partes correspondiente a ~ _C tiene un refinamiento que produce la relación de igual palo ~ _S , que tiene las cuatro clases de equivalencia {picas}, {diamantes}, {corazones} y {tréboles}.

Una partición del conjunto N = {1, 2, ..., n } con la correspondiente relación de equivalencia ~ es no cruzada si tiene la siguiente propiedad: Si cuatro elementos a , b , c y d de N con a < b < c < d satisfacen a ~ c y b ~ d , entonces a ~ b ~ c ~ d . El nombre proviene de la siguiente definición equivalente: Imaginemos los elementos 1, 2, ..., n de N dibujados como los n vértices de un n -gono regular (en sentido antihorario). Una partición puede visualizarse dibujando cada bloque como un polígono (cuyos vértices son los elementos del bloque). La partición es no cruzada si y solo si estos polígonos no se intersecan.

La red de particiones no cruzadas de un conjunto finito forma un subconjunto de la red de todas las particiones, pero no una subred, ya que las operaciones de unión de las dos redes no coinciden.

La red de particiones sin cruces ha adquirido importancia debido a su papel en la teoría de la probabilidad libre .

El número total de particiones de un conjunto de n elementos es el número de Bell B _n . Los primeros números de Bell son B ₀ = 1, B ₁ = 1, B ₂ = 2, B ₃ = 5, B ₄ = 15, B ₅ = 52 y B ₆ = 203 (secuencia A000110 en el OEIS ) . Los números de Bell satisfacen la recursión .

${\displaystyle B_{n+1}=\sum _{k=0}^{n}{n \choose k}B_{k}}$

y tienen la función generadora exponencial

${\displaystyle \sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}z^{n}=e^{e^{z}-1}.}$

Los números de Bell también se pueden calcular utilizando el triángulo de Bell, en el que el primer valor de cada fila se copia del final de la fila anterior, y los valores subsiguientes se calculan sumando dos números: el número a la izquierda y el número arriba a la izquierda de la posición. Los números de Bell se repiten a lo largo de ambos lados de este triángulo. Los números dentro del triángulo cuentan las particiones en las que un elemento dado es el singleton más grande .

El número de particiones de un conjunto de n elementos en exactamente k partes (no vacías) es el número de Stirling de segundo tipo S ( n , k ).

El número de particiones no cruzadas de un conjunto de n elementos es el número de Catalan.

${\displaystyle C_{n}={1 \over n+1}{2n \choose n}.}$

• Cobertura exacta
• Diseño de bloques
• Análisis de clúster
• Lista de temas de partición
• Laminación (topología)
• Principio MECE
• Relación de equivalencia parcial
• álgebra de partición
• Refinamiento de partición
• Colección puntual finita
• Esquemas de rima por partición de conjuntos
• Ordenación débil (partición de conjuntos ordenados)

• Brualdi, Richard A. (2004). Combinatoria introductoria (4.ª  ed.). Pearson Prentice Hall. ISBN 0-13-100119-1.
• Schechter, Eric (1997). Manual de análisis y sus fundamentos . Academic Press. ISBN 0-12-622760-8.