Partición dun conxunto

Unha partición dun conxunto de selos en paquetes: ningún selo está en dous paquetes, ningún paquete está baleiro e cada selo está nun paquete.

As 52 particións dun conxunto con 5 elementos. Unha rexión coloreada indica un subconxunto de X que é o conxunto que engloba a partición. Os puntos sen cor indican subconxuntos dun só elemento. A primeira partición mostrada contén cinco subconxuntos dun só elemento; a última partición contén un único subconxunto con cinco elementos (que coincide co conxunto do que se está a facer a partición).

En matemáticas, unha partición dun conxunto é unha agrupación dos seus elementos en subconxuntos non baleiros, de tal xeito que cada elemento está incluído exactamente nun subconxunto.

Toda relación de equivalencia nun conxunto define unha partición deste conxunto, e igualmente, cada partición define unha relación de equivalencia.

Definición e notación

Unha partición dun conxunto X é un conxunto de subconxuntos non baleiros de X tal que cada elemento x en X está exactamente nun destes subconxuntos (é dicir, os subconxuntos son conxuntos non baleiros e disxuntos entre si).

De forma equivalente, unha familia de conxuntos P é unha partición de X se e só se se cumpren todas as seguintes condicións:

• A familia P non contén o conxunto baleiro (é dicir $\mathrm{\varnothing }\notin P$ ).
• A unión dos conxuntos en P é igual a X (é dicir $\bigcup _{A\in P}A=X$). Os conxuntos en P dise que esgotan ou cobren X.
• A intersección de dous conxuntos distintos en P está baleira (é dicir $(\mathrm{\forall }A,B\in P)A\ne B⟹A\cap B=\mathrm{\varnothing }$). Dise que os elementos de P son disxuntos ou mutuamente excluíntes.

Os conxuntos $P$ chámanse bloques, partes ou celas, da partición.Modelo:Sfn Se $a\in X$ entón representamos a cela que contén $a$ por $[a]$. É dicir, $[a]$ é a notación para a cela en $P$ que contén $a$ .

Cada partición $P$ pode identificarse cunha relación de equivalencia sobre $X$, é dicir, a relación ${\sim }_P$ tal que para calquera $a,b\in X$ temos $a{\sim }_{P}b$ se e só se $a\in [b]$ (equivalentemente, se e só se $b\in [a]$).

O rango de $P$ é $|X|-|P|$, se $X$ é finito.

Exemplos

• O conxunto baleiro $\mathrm{\varnothing }$ ten exactamente unha partición, a saber $\mathrm{\varnothing }$.
• Para calquera conxunto non baleiro X, P = Modelo:Mset é unha partición de X, chamada partición trivial.
  • En particular, cada conxunto unitario {x} ten exactamente unha partición, é dicir, Modelo:Mset.
• Para calquera subconxunto propio non baleiro A dun conxunto U, o conxunto A xunto co seu complemento forman unha partición de U, é dicir, Modelo:Mset .
• O conxunto Modelo:Mset ten estas cinco particións (unha partición por elemento):
  • Modelo:Mset, ás veces escríbese 1 | 2 | 3.
  • Modelo:Mset } ou 1 2 | 3.
  • Modelo:Mset } ou 1 3 | 2.
  • Modelo:Mset } ou 1 | 2 3.
  • Modelo:Mset } ou 123 (en contextos onde non haberá confusión co número).
• As seguintes non son particións de Modelo:Mset :
  • Modelo:Mset } non é unha partición (de ningún conxunto) porque un dos seus elementos é o conxunto baleiro.
  • Modelo:Mset non é unha partición (de ningún conxunto) porque o elemento 2 está contido en máis dun bloque.
  • Modelo:Mset non é unha partición de Modelo:Mset porque ningún dos seus bloques contén 3; porén, é unha partición de Modelo:Mset .

O axioma de elección garante para calquera partición dun conxunto X a existencia dun subconxunto de X que contén exactamente un elemento de cada parte da partición. Isto implica que dada unha relación de equivalencia nun conxunto pódese seleccionar un elemento representativo canónico de cada clase de equivalencia.

Refinamento de particións

Particións dun conxunto de 4 elementos ordenadas por refinamento

Unha partición α dun conxunto X é un refinamento dunha partición ρ de X (e dicimos que α é máis fina que ρ e que ρ é máis grosa que α) se cada elemento de α é un subconxunto dalgún elemento de ρ. Informalmente, isto significa que α está máis fragmentada que ρ. Nese caso, escríbese que α ≤ ρ.

Esta relación "máis fina que" no conxunto de particións de X é unha orde parcial (polo que a notación "≤" é apropiada). Cada conxunto de elementos ten un límite superior mínimo (un supremo) (o seu "join") e un límite inferior máximo (un ínfimo) (o seu "meet"), de xeito que forma unha retícula, e máis concretamente (para particións dun conxunto finito) é unha retícula xeométrica e supersolucionábel.

O meet e o join das particións α e ρ defínense do seguinte xeito. O meet $\alpha \wedge \rho$ é a partición cuxos bloques son as interseccións dun bloque de α e un bloque de ρ, agás o conxunto baleiro. Noutras palabras, un bloque de $\alpha \wedge \rho$ é a intersección dun bloque de α e un bloque de ρ que non son disxuntos entre si. O join $\alpha \vee \rho$, fórmase a partir dunha relación sobre os bloques A de α e os bloques B de ρ por A ~ B se A e B non son disxuntos, daquela $\alpha \vee \rho$ é a partición na que cada bloque C é a unión dunha familia de bloques ligados por esta relación.

Contando particións

Construción do Triángulo de Bell

O número total de particións dun conxunto de n elementos é o número de Bell B_n. Os primeiros números de Bell son B₀ = 1, B₁ = 1, B₂ = 2, B₃ = 5, B₄ = 15, B₅ = 52 e B₆ = 203 Modelo:OEIS. Os números de Bell satisfán a recursividade

$B_{n+1}=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})B_k$

e teñen a función xeradora exponencial

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

Os números de Bell tamén se poden calcular usando o triángulo de Bell no que se copia o primeiro valor de cada fila desde o final da fila anterior, e os valores posteriores son calculados engadindo dous números, o número da esquerda e o número na fila anterior da esquerda.

O número de particións dun conxunto de n elementos en exactamente k partes (non baleiras) é o número de Stirling do segundo tipo S(n,k).

Véxase tamén

Bibliografía

• Modelo:Cita libro
• Modelo:Cita libro

Outros artigos

• Orde parcial.
• Cobertura exacta.
• Join e meet.

Modelo:Control de autoridades