Partición dun conxunto

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^[1] (é 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:^[2]

A familia P non contén o conxunto baleiro (é dicir $\emptyset \notin P$ ).
A unión dos conxuntos en P é igual a X (é dicir $\textstyle \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 $(\forall A,B\in P)\;A\neq B\implies A\cap B=\emptyset$ ). Dise que os elementos de P son disxuntos ou mutuamente excluíntes.

Os conxuntos $P$ chámanse bloques, partes ou celas, da partición.^[3] 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 $\emptyset$ ten exactamente unha partición, a saber $\emptyset$ .
Para calquera conxunto non baleiro X, P = {X} é unha partición de X, chamada partición trivial.
- En particular, cada conxunto unitario {x} ten exactamente unha partición, é dicir, { {x} }.
Para calquera subconxunto propio non baleiro A dun conxunto U, o conxunto A xunto co seu complemento forman unha partición de U, é dicir, {A, U ∖ A} .
O conxunto {1, 2, 3} ten estas cinco particións (unha partición por elemento):
- { {1}, {2}, {3} }, ás veces escríbese 1 | 2 | 3.
- { {1, 2}, {3} } ou 1 2 | 3.
- { {1, 3}, {2} } ou 1 3 | 2.
- { {1}, {2, 3} } ou 1 | 2 3.
- { {1, 2, 3} } ou 123 (en contextos onde non haberá confusión co número).
As seguintes non son particións de {1, 2, 3} :
- { {}, {1, 3}, {2} } non é unha partición (de ningún conxunto) porque un dos seus elementos é o conxunto baleiro.
- { {1, 2}, {2, 3} } non é unha partición (de ningún conxunto) porque o elemento 2 está contido en máis dun bloque.
- { {1}, {2} } non é unha partición de {1, 2, 3} porque ningún dos seus bloques contén 3; porén, é unha partición de {1, 2} .

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

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

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 (secuencia A000110 na OEIS). Os números de Bell satisfán a recursividade

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

e teñen a función xeradora exponencial

\sum _{n=0}^{\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).

Notas

↑ Halmos, Paul (1960). Naive Set Theory R. Springer. p. 28. ISBN 9780387900926.
↑ Lucas, John F. (1990). Introduction to Abstract Mathematics. Rowman & Littlefield. p. 187. ISBN 9780912675732.
↑ Brualdi 2004.

Véxase tamén

Bibliografía

Brualdi, Richard A. (2004). Introductory Combinatorics (4th ed.). Pearson Prentice Hall. ISBN 0-13-100119-1.
Schechter, Eric (1997). Handbook of Analysis and Its Foundations. Academic Press. ISBN 0-12-622760-8.

Outros artigos

[1] Halmos, Paul (1960). Naive Set Theory R. Springer. p. 28. ISBN 9780387900926.

[2] Lucas, John F. (1990). Introduction to Abstract Mathematics. Rowman & Littlefield. p. 187. ISBN 9780912675732.

[FOOTNOTEBrualdi2004-3] Brualdi 2004.

[1]

[2]

[3]