Partición de un conjunto

Formas matemáticas de agrupar elementos de un conjunto.

Un conjunto de sellos divididos en paquetes: ningún sello está en dos paquetes, ningún paquete está vacío y cada sello está en un paquete.

Los 52 tabiques de un conjunto de 5 elementos. Una región coloreada indica un subconjunto de X que forma un miembro de la partición circundante. Los puntos sin color indican subconjuntos de un solo elemento. La primera partición mostrada contiene cinco subconjuntos de un solo elemento; la última partición contiene un subconjunto que tiene cinco elementos.

Los símbolos tradicionales japoneses para los 54 capítulos del Cuento de Genji se basan en las 52 formas de dividir cinco elementos (los dos símbolos rojos representan la misma partición y el símbolo verde se añade al llegar a 54). ^[1]

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

Cada relación de equivalencia en un conjunto define una partición de este conjunto, y cada partición define una relación de equivalencia. Un conjunto equipado con una relación de equivalencia o una partición a veces se denomina setoide , típicamente en teoría de tipos y teoría de prueba .

Definición y notación

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

De manera equivalente, una familia de conjuntos P es una partición de X si y sólo si se cumplen todas las condiciones siguientes: ^[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 ). Se dice que los conjuntos en P agotan o cubren X. Véase también eventos y cobertura (topología) colectivamente exhaustivos . ${\displaystyle \textstyle \bigcup _{A\in P}A=X}$
• La intersección de dos conjuntos distintos cualesquiera en P está vacía (es decir ). Se dice que los elementos de P son disjuntos por pares o mutuamente excluyentes. Véase también exclusividad mutua . ${\displaystyle (\forall A,B\in P)\;A\neq B\implies A\cap B=\emptyset }$

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

Cada partición puede identificarse con una relación de equivalencia en , es decir, la relación tal que para cualquiera tenemos si y sólo si (de manera equivalente, si y sólo si ). La notación evoca la idea de que la relación de equivalencia puede construirse a partir de la partición. Por el contrario, 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 , entonces algunos autores escriben . Esta notación sugiere la idea de que la partición es el conjunto X dividido en celdas. La notación también evoca la idea de que, a partir de la relación de equivalencia, se puede construir la partición. ${\displaystyle P}$ ${\displaystyle X}$ ${\displaystyle \sim _{\!P}}$ ${\displaystyle a,b\in X}$ ${\displaystyle a\sim _{\!P}b}$ ${\displaystyle a\in [b]}$ ${\displaystyle b\in [a]}$ ${\displaystyle \sim _{\!P}}$ ${\displaystyle \sim }$ ${\displaystyle P=X/\sim }$

El rango de es , si es finito . ${\displaystyle P}$ ${\displaystyle |X|-|P|}$ ${\displaystyle X}$

Ejemplos

• El conjunto vacío tiene exactamente una partición, a saber . (Nota: esta es la partición, no un miembro de la partición). ${\displaystyle \emptyset }$ ${\displaystyle \emptyset }$
• Para cualquier conjunto X no vacío , P = { X } es una partición de X , llamada partición trivial .
  • En particular, cada conjunto singleton { 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 , es decir, { 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 123 (en contextos donde no habrá confusión con el número).
• 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}.

Particiones y relaciones de equivalencia.

Para cualquier relación de equivalencia en un conjunto X , el conjunto de sus clases de equivalencia es una partición de X . A la inversa, 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 en P. Por tanto, las nociones de relación de equivalencia y partición son esencialmente equivalentes. ^[5]

El axioma de elección garantiza para cualquier partición de un conjunto X la existencia de un subconjunto de X que contenga 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 canónico representativo de cada clase de equivalencia.

Refinamiento de particiones.

Particiones de un conjunto de 4 elementos ordenados por refinamiento

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 ρ . Informalmente, esto significa que α es una fragmentación adicional de ρ . En ese caso, se escribe que α ≤ ρ .

Esta relación "más fina 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 una red , y más específicamente (para particiones de un conjunto finito) es una red geométrica y red supersoluble . ^{[6] [7]} La ​​red de partición de un conjunto de 4 elementos tiene 15 elementos y se muestra en el diagrama de Hasse a la izquierda.

El encuentro y la unión de las particiones α y ρ se definen de la siguiente manera. El encuentro 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 es la intersección de un bloque de α y un bloque de ρ que no están separados entre sí. Para definir la unión , forme una relación en los bloques A de α y los bloques B de ρ por A ~ B si A y B no son disjuntos. Entonces es la partición en la que cada bloque C es la unión de una familia de bloques conectados por esta relación. ${\displaystyle \alpha \wedge \rho }$ ${\displaystyle \alpha \wedge \rho }$ ${\displaystyle \alpha \vee \rho }$ ${\displaystyle \alpha \vee \rho }$

Basado en la equivalencia entre redes geométricas y matroides , esta red de particiones de un conjunto finito corresponde a una matroide en la que el conjunto base de la matroide consta de los átomos de la red, es decir, las particiones con conjuntos singleton y uno de dos elementos. colocar. Estas particiones atómicas se corresponden uno por uno con los bordes de un gráfico completo . El cierre matroide de un conjunto de particiones atómicas es el mejor engrosamiento común de todos ellos; en términos de teoría de grafos, es la partición de los vértices del gráfico completo en los componentes conectados del subgrafo formado por el conjunto dado de aristas. De esta forma, el entramado de particiones corresponde al entramado de pisos de la matroide gráfica del grafo completo. ${\displaystyle n-2}$

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

Particiones que no se cruzan

Una partición del conjunto N = {1, 2, ..., n } con la correspondiente relación de equivalencia ~ no se cruza si tiene la siguiente propiedad: Si cuatro elementos a , b , c y d de N que tienen a < b < c < d satisface a ~ c y b ~ d , luego a ~ b ~ c ~ d . El nombre proviene de la siguiente definición equivalente: Imagine los elementos 1, 2, ..., n de N dibujados como los n vértices de un n -gón regular (en orden antihorario). Luego se puede visualizar una partición dibujando cada bloque como un polígono (cuyos vértices son los elementos del bloque). La partición entonces no se cruza si y sólo si estos polígonos no se cruzan.

La red de particiones que no se cruzan 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 concuerdan.

La red de partición sin cruces ha adquirido importancia recientemente debido a su papel en la teoría de la probabilidad libre .

Contando particiones

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 OEIS ). Los números de campana satisfacen la recursividad.

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

y tener la función generadora exponencial

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

Construcción del triángulo de Bell

Los números de Bell también se pueden calcular usando 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 posteriores se calculan sumando dos números, el número de la izquierda y el número de arriba. izquierda de la posición. Los números de Bell se repiten a 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 elemento n conjunto en exactamente k partes (no vacías) es el número de Stirling de segunda especie S ( n , k ).

El número de particiones que no se cruzan de un conjunto de n elementos es el número catalán

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

Ver también

• Cobertura exacta
• Diseño de bloques
• Análisis de conglomerados
• 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 punto finita
• Esquemas de rima por partición establecida
• Ordenamiento débil (partición de conjunto ordenado)

Notas

1. Knuth, Donald E. (2013), "Dos mil años de combinatoria", en Wilson, Robin; Watkins, John J. (eds.), Combinatoria: antigua y moderna , Oxford University Press, págs. 7–37
2. Halmos, Paul (1960). Teoría ingenua de conjuntos R. Springer. pag. 28.ISBN _ 9780387900926.
3. Lucas, John F. (1990). Introducción a la Matemática Abstracta. Rowman y Littlefield. pag. 187.ISBN​ 9780912675732.
4. Brualdi 2004, págs. 44–45.
5. Schechter 1997, pág. 54.
6. Birkhoff, Garrett (1995), Teoría del entramado, Publicaciones del coloquio, vol. 25 (3ª ed.), Sociedad Matemática Estadounidense, pág. 95, ISBN 9780821810255.
7. * Stern, Manfred (1999), Celosías semimodulares. Teoría y Aplicaciones , Enciclopedia de las Matemáticas y sus Aplicaciones, vol. 73, Cambridge University Press, doi :10.1017/CBO9780511665578, ISBN 0-521-46105-7

Referencias

• 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 . Prensa académica. ISBN 0-12-622760-8.