Partición de un conjunto

Formas matemáticas de agrupar elementos de un conjunto

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

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 este 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 , por lo general en teoría de tipos y teoría de pruebas .

Definición y notació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á 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 solo si se cumplen todas las siguientes condiciones: ^[3]

La familia P no contiene el conjunto vacío (es decir ). $\conjunto vacío \no en 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 colectivamente exhaustivos y cobertura (topología) . $\textstyle \bigcup _ {A\in P}A=X$
La intersección de dos conjuntos distintos cualesquiera en P es vacía (es decir, ). Se dice que los elementos de P son disjuntos por pares o mutuamente excluyentes. Véase también exclusividad mutua . $(\para todo A,B\en P)\;A\neq B\implies A\cap B=\conjunto vacío$

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

Toda partición puede identificarse con una relación de equivalencia en , es decir, la relación tal que para cualquier tenemos si y solo si (equivalentemente, si y solo si ). La notación 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 , 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. ${\estilo de visualización P}$ ${\estilo de visualización X}$ $\sim _{\!P}$ $a,b\en X$ $a\sim _{\!P}b$ $a\in [b]$ $b\en [a]$ $\sim _{\!P}$ ${\estilo de visualización \sim}$ $P=X/{\sim }$

El rango de es , si es finito . ${\estilo de visualización P}$ $|X|-|P|$ ${\estilo de visualización X}$

Ejemplos

El conjunto vacío tiene exactamente una partición, es decir . (Nota: esta es la partición, no un miembro de la partición). $\conjunto vacío$ $\conjunto vacío$
Para cualquier conjunto no vacío X , P = { X } es una partición de X , llamada partición trivial .
- En particular, cada conjunto singleton { x } tiene exactamente una partición, es decir { { 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 fijando x ~ y precisamente cuando x e y están en la misma parte en 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, exista 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

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 "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 supersoluble . ^[6]^[7] La red de particiones de un conjunto de 4 elementos tiene 15 elementos y se representa en el diagrama de Hasse de 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 disjuntos entre sí. Para definir la unión , forme una relación sobre los bloques A de α y los bloques B de ρ por A ~ B si A y B no están 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. $\alpha \cuña \rho$ $\alpha \cuña \rho$ $\alpha \vee \rho$ $\alpha \vee \rho$

Basándose 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 consiste en los átomos de la red, es decir, las particiones con conjuntos unitarios y un conjunto de dos elementos. Estas particiones atómicas corresponden uno a uno 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 los componentes conexos del subgrafo formado por el conjunto dado de aristas. De esta manera, la red de particiones corresponde a la red de planos del matroide gráfico del grafo completo. ${\estilo de visualización n-2}$

Otro ejemplo ilustra el refinamiento de las 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 mismo color en D –que puede denotarse ~ _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 mismo palo ~ _S , que tiene las cuatro clases de equivalencia {picas}, {diamantes}, {corazones} y {tréboles}.

Particiones sin cruce

Una partición del conjunto N = {1, 2, ..., n } con la relación de equivalencia correspondiente ~ no es cruzada si tiene la siguiente propiedad: Si cuatro elementos a , b , c y d de N que tienen 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 orden antihorario). Una partición puede entonces visualizarse dibujando cada bloque como un polígono (cuyos vértices son los elementos del bloque). La partición es entonces 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 concuerdan.

La red de particiones sin cruce ha adquirido importancia debido a su papel en la teoría de 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 la OEIS ). Los números de Bell satisfacen la recursión

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

y tienen la función generadora exponencial

\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 posteriores 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 Catalan

C_{n}={1 \sobre n+1}{2n \elija n}.

Véase también

Cobertura exacta
Diseño de bloques
Análisis de conglomerados
Lista de temas de particiones
Laminación (topología)
Principio MECE
Relación de equivalencia parcial
Álgebra de particiones
Refinamiento de particiones
Colección de puntos finitos
Esquemas de rima por partición de conjuntos
Ordenamiento débil (partición de conjuntos ordenados)

Notas

^ 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
^ Halmos, Paul (1960). Teoría ingenua de conjuntos R. Springer. pag. 28.ISBN 9780387900926.
^ Lucas, John F. (1990). Introducción a las matemáticas abstractas. Rowman & Littlefield. pág. 187. ISBN 9780912675732.
^ Brualdi 2004, págs. 44-45.
^ Schechter 1997, pág. 54.
^ Birkhoff, Garrett (1995), Lattice Theory, Colloquium Publications, vol. 25 (3.ª ed.), American Mathematical Society, pág. 95, ISBN 9780821810255.
^ * Stern, Manfred (1999), Redes semimodulares. Teoría y aplicaciones , Enciclopedia de 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 . Academic Press. ISBN 0-12-622760-8.

[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 las matemáticas abstractas. Rowman & Littlefield. pág. 187. ISBN 9780912675732.

[FOOTNOTEBrualdi200444–45-4] Brualdi 2004, págs. 44-45.

[FOOTNOTESchechter199754-5] Schechter 1997, pág. 54.

[6] Birkhoff, Garrett (1995), Lattice Theory, Colloquium Publications, vol. 25 (3.ª ed.), American Mathematical Society, pág. 95, ISBN 9780821810255.

[7] * Stern, Manfred (1999), Redes semimodulares. Teoría y aplicaciones , Enciclopedia de matemáticas y sus aplicaciones, vol. 73, Cambridge University Press, doi :10.1017/CBO9780511665578, ISBN 0-521-46105-7