Conjunto múltiple

En matemáticas , un multiconjunto (o bolsa , o mset ) es una modificación del concepto de conjunto que, a diferencia de un conjunto, ^{[ 1 ]} permite múltiples instancias para cada uno de sus elementos . El número de instancias dadas para cada elemento se llama multiplicidad de ese elemento en el multiconjunto. Como consecuencia, existe un número infinito de multiconjuntos que contienen solo los elementos a y b , pero que varían en las multiplicidades de sus elementos:

• El conjunto { a , b } contiene solo los elementos a y b , cada uno con multiplicidad 1 cuando { a , b } se considera como un multiconjunto.
• En el multiconjunto { a , a , b } , el elemento a tiene multiplicidad 2 y b tiene multiplicidad 1.
• En el multiconjunto { a , a , a , b , b , b } , tanto a como b tienen multiplicidad 3.

Estos objetos son todos diferentes cuando se consideran multiconjuntos, aunque son el mismo conjunto, ya que todos constan de los mismos elementos. Al igual que con los conjuntos, y a diferencia de las tuplas , el orden en que se enumeran los elementos no importa para distinguir los multiconjuntos, por lo que { a , a , b } y { a , b , a } denotan el mismo multiconjunto. Para distinguir entre conjuntos y multiconjuntos, a veces se utiliza una notación que incorpora corchetes: el multiconjunto { a , a , b } se puede denotar por [ a , a , b ] . ^{[ 2 ]}

La cardinalidad o "tamaño" de un multiconjunto es la suma de las multiplicidades de todos sus elementos. Por ejemplo, en el multiconjunto { a , a , b , b , b , c } las multiplicidades de los miembros a , b , y c son respectivamente 2, 3 y 1, y por lo tanto la cardinalidad de este multiconjunto es 6.

Nicolaas Govert de Bruijn acuñó el término «multiconjunto» en la década de 1970, según Donald Knuth . ^{[ 3 ] : 694} Sin embargo, el concepto de multiconjuntos es anterior a la acuñación del término por muchos siglos. El propio Knuth atribuye el primer estudio de multiconjuntos al matemático indio Bhāskarāchārya , quien describió permutaciones de multiconjuntos alrededor de 1150. Se han propuesto o utilizado otros nombres para este concepto, como lista , grupo , bolsa , montón , muestra , conjunto ponderado , colección y suite . ^{[ 3 ] : 694}

Wayne Blizard rastreó el origen mismo de los multiconjuntos hasta los números, argumentando que «en la antigüedad, el número n se representaba a menudo mediante una colección de n trazos, marcas de conteo o unidades». ^{[ 4 ]} Estas y otras colecciones de objetos similares pueden considerarse multiconjuntos, ya que los trazos, las marcas de conteo y las unidades se consideran indistinguibles. Esto demuestra que la gente utilizaba implícitamente los multiconjuntos incluso antes del surgimiento de las matemáticas.

Las necesidades prácticas de esta estructura han provocado que los multiconjuntos se redescubran varias veces, apareciendo en la literatura con diferentes nombres. ^{[ 5 ] : 323} Por ejemplo, fueron importantes en los primeros lenguajes de IA , como QA4, donde se les denominaba bolsas, un término atribuido a Peter Deutsch . ^{[ 6 ]} Un multiconjunto también se ha llamado agregado, montón, grupo, muestra, conjunto ponderado, conjunto de ocurrencia y fireset (conjunto de elementos repetidos finitamente). ^{[ 5 ] : 320 [ 7 ]}

Aunque los multiconjuntos se usaban implícitamente desde la antigüedad, su exploración explícita ocurrió mucho más tarde. El primer estudio conocido de multiconjuntos se atribuye al matemático indio Bhāskarāchārya alrededor de 1150, quien describió permutaciones de multiconjuntos. ^{[ 3 ] : 694} La obra de Marius Nizolius (1498–1576) contiene otra referencia temprana al concepto de multiconjuntos. ^{[ 8 ]} Athanasius Kircher encontró el número de permutaciones de multiconjuntos cuando un elemento puede repetirse. ^{[ 9 ]} Jean Prestet publicó una regla general para permutaciones de multiconjuntos en 1675. ^{[ 10 ]} John Wallis explicó esta regla con más detalle en 1685. ^{[ 11 ]}

Los multiconjuntos aparecieron explícitamente en el trabajo de Richard Dedekind . ^{[ 12 ] [ 13 ]}

Otros matemáticos formalizaron los multiconjuntos y comenzaron a estudiarlos como estructuras matemáticas precisas en el siglo XX. Por ejemplo, Hassler Whitney (1933) describió conjuntos generalizados ("conjuntos" cuyas funciones características pueden tomar cualquier valor entero : positivo, negativo o cero). ^{[ 5 ] : 326 [ 14 ] : 405} Monro (1987) investigó la categoría Mul de multiconjuntos y sus morfismos , definiendo un multiconjunto como un conjunto con una relación de equivalencia entre elementos "del mismo tipo " y un morfismo entre multiconjuntos como una función que respeta los tipos . También introdujo un multinúmero : una función f ( x ) de un multiconjunto a los números naturales , que da la multiplicidad del elemento x en el multiconjunto. Monro argumentó que los conceptos de multiconjunto y multinúmero a menudo se mezclan indiscriminadamente, aunque ambos son útiles. ^{[ 5 ] : 327–328 [ 15 ]}

Uno de los ejemplos más simples y naturales es el multiconjunto de factores primos de un número natural n . Aquí, el conjunto subyacente de elementos es el conjunto de factores primos de n . Por ejemplo, el número 120 tiene la factorización prima.$${\displaystyle 120=2^{3}3^{1}5^{1},}$$ lo que da como resultado el multiconjunto {2, 2, 2, 3, 5} .

Un ejemplo relacionado es el multiconjunto de soluciones de una ecuación algebraica . Una ecuación cuadrática , por ejemplo, tiene dos soluciones. Sin embargo, en algunos casos ambas son el mismo número. Así, el multiconjunto de soluciones de la ecuación podría ser {3, 5} o {4, 4} . En este último caso, tiene una solución de multiplicidad 2. De forma más general, el teorema fundamental del álgebra afirma que las soluciones complejas de una ecuación polinómica de grado d siempre forman un multiconjunto de cardinalidad d .

Un caso especial de lo anterior son los autovalores de una matriz , cuya multiplicidad se define generalmente como su multiplicidad como raíces del polinomio característico . Sin embargo, se definen naturalmente otras dos multiplicidades para los autovalores, sus multiplicidades como raíces del polinomio mínimo , y la multiplicidad geométrica , que se define como la dimensión del núcleo de A − λI (donde λ es un autovalor de la matriz A ). Estas tres multiplicidades definen tres multiconjuntos de autovalores, que pueden ser todos diferentes: Sea A una matriz n × n en forma normal de Jordan que tiene un único autovalor. Su multiplicidad es n , su multiplicidad como raíz del polinomio mínimo es el tamaño del bloque de Jordan más grande, y su multiplicidad geométrica es el número de bloques de Jordan.

Un multiconjunto puede definirse formalmente como un par ordenado ( U , m ) donde U es un conjunto llamado universo o conjunto subyacente , y${\displaystyle m\colon U\to \mathbb {N} }$es una función de U a los enteros no negativos . ^{[ 7 ]} El valor ⁠${\displaystyle m(a)}$para un elemento${\displaystyle a\in U}$Se denomina multiplicidad de​${\displaystyle a}$⁠ en el multiconjunto e interpretado como el número de ocurrencias de ⁠${\displaystyle a}$en el multiconjunto.

El soporte , raíz o portador de un multiconjunto es el subconjunto de${\displaystyle U}$formado por los elementos${\displaystyle a\in U}$de tal manera que${\displaystyle m(a)>0}$[ ^{7 ]} Un multiconjunto finito es un multiconjunto con soporte finito . La mayoría de los autores definenlos multiconjuntos como multiconjuntos finitos. Este es el caso en este artículo, donde, a menos que se indique lo contrario, todos los multiconjuntos son multiconjuntos finitos ^.

Algunos autores ^{[ 16 ]} definen multiconjuntos con la restricción adicional de que ⁠${\displaystyle m(a)>0}$por cada​${\displaystyle a}$⁠ , o, equivalentemente, el soporte es igual al conjunto subyacente. También se han estudiado multiconjuntos con multiplicidades infinitas; ^{[ 17 ]} no se consideran en este artículo. Algunos autoresdefinen un multiconjunto en términos de un conjunto de índices finito ⁠${\displaystyle I}$y una función${\displaystyle f\colon I\rightarrow U}$donde la multiplicidad de un elemento${\displaystyle a\in U}$es​​${\displaystyle |f^{-1}(a)|}$⁠ , el número de elementos de ⁠${\displaystyle I}$que se asignan a${\displaystyle a}$por​​${\displaystyle f}$⁠ .

Los multiconjuntos pueden representarse como conjuntos, con algunos elementos repetidos. Por ejemplo, el multiconjunto con soporte ⁠${\displaystyle \{a,b\}}$y función de multiplicidad tal que${\displaystyle m(a)=2,\;m(b)=1}$⁠ se puede representar como { a , a , b } . Una notación más compacta, en caso de multiplicidades altas, es ⁠${\displaystyle \{(a,2),(b,1)\}}$para el mismo multiconjunto.

Si${\displaystyle A=\{a_{1},\ldots ,a_{n}\},}$un multiconjunto con soporte incluido en${\displaystyle A}$⁠ se representa a menudo como $${\displaystyle a_{1}^{m(a_{1})}\cdots a_{n}^{m(a_{n})},}$$ a los que se pueden aplicar las reglas de cálculo de indeterminadas ; es decir, se pueden eliminar los exponentes 1 y los factores con exponente 0, y el multiconjunto no depende del orden de los factores. Esto permite extender la notación a conjuntos subyacentes infinitos como $${\displaystyle \prod _{a\in U}a^{m(a)}.}$$ Una ventaja de la notación es que permite usarla sin conocer el soporte exacto. Por ejemplo, los factores primos de un número natural .${\displaystyle n}$⁠ forman un multiconjunto tal que $${\displaystyle n=\prod _{p\;{\text{prime}}}p^{m(p)}=2^{m(2)}3^{m(3)}5^{m(5)}\cdots .}$$

Los elementos de un multiconjunto generalmente se toman en un conjunto fijo U , a veces llamado universo , que suele ser el conjunto de los números naturales . Se dice que un elemento de U que no pertenece a un multiconjunto dado tiene multiplicidad 0 en ese multiconjunto. Esto extiende la función de multiplicidad del multiconjunto a una función de U al conjunto.${\displaystyle \mathbb {N} }$de enteros no negativos. Esto define una correspondencia biunívoca entre estas funciones y los multiconjuntos que tienen sus elementos en U.

Esta función de multiplicidad extendida se denomina comúnmente función de multiplicidad y es suficiente para definir multiconjuntos cuando el universo que contiene los elementos está fijo. Esta función de multiplicidad es una generalización de la función indicadora de un subconjunto y comparte algunas propiedades con ella.

El soporte de un multiconjunto${\displaystyle A}$En un universo U es el conjunto subyacente del multiconjunto, ^{[ 7 ]} que puede representarse por${\displaystyle A^{*}}$^{[ 7 ]} o${\displaystyle \operatorname {Supp} (A)}$. Utilizando la función de multiplicidad${\displaystyle m}$, se caracteriza por $${\displaystyle \operatorname {Supp} (A):=\{x\in U\mid m_{A}(x)>0\}.}$$

Un multiconjunto es finito si su soporte es finito, o, equivalentemente, si su cardinalidad $${\displaystyle |A|=\sum _{x\in \operatorname {Supp} (A)}m_{A}(x)=\sum _{x\in U}m_{A}(x)}$$ es finito. El multiconjunto vacío es el único multiconjunto con soporte vacío (conjunto subyacente) y, por lo tanto, con cardinalidad 0.

Las operaciones habituales de conjuntos pueden extenderse a multiconjuntos mediante el uso de la función de multiplicidad, de forma similar a como se utiliza la función indicadora para subconjuntos. A continuación, A y B son multiconjuntos en un universo U dado , con funciones de multiplicidad.${\displaystyle m_{A}}$y${\displaystyle m_{B}.}$

• Inclusión: A está incluido en B , denotado A ⊆ B , si$${\displaystyle m_{A}(x)\leq m_{B}(x)\quad \forall x\in U.}$$
• Unión: la unión (llamada, en algunos contextos, máximo o mínimo común múltiplo ) de A y B es el multiconjunto C con función de multiplicidad ^{[ 13 ].}$${\displaystyle m_{C}(x)=\max(m_{A}(x),m_{B}(x))\quad \forall x\in U.}$$
• Intersección: la intersección (llamada, en algunos contextos, ínfimo o máximo común divisor ) de A y B es el multiconjunto C con función de multiplicidad$${\displaystyle m_{C}(x)=\min(m_{A}(x),m_{B}(x))\quad \forall x\in U.}$$
• Suma: la suma de A y B es el multiconjunto C con función de multiplicidad$${\displaystyle m_{C}(x)=m_{A}(x)+m_{B}(x)\quad \forall x\in U.}$$Puede considerarse una generalización de la unión disjunta de conjuntos. Define una estructura de monoide conmutativo sobre los multiconjuntos finitos de un universo dado. Este monoide es un monoide conmutativo libre , con el universo como base.
• Diferencia: la diferencia de A y B es el multiconjunto C con función de multiplicidad$${\displaystyle m_{C}(x)=\max(m_{A}(x)-m_{B}(x),0)\quad \forall x\in U.}$$

Dos multiconjuntos son disjuntos si sus soportes son conjuntos disjuntos . Esto equivale a decir que su intersección es el multiconjunto vacío o que su suma es igual a su unión.

Existe un principio de inclusión-exclusión para multiconjuntos finitos (similar al de los conjuntos ), que establece que una unión finita de multiconjuntos finitos es la diferencia de dos sumas de multiconjuntos: en la primera suma consideramos todas las intersecciones posibles de un número impar de los multiconjuntos dados, mientras que en la segunda suma consideramos todas las intersecciones posibles de un número par de los multiconjuntos dados.

Los subconjuntos finitos de un conjunto${\displaystyle U}$⁠ son exactamente los multiconjuntos con conjunto subyacente ⁠${\displaystyle U}$, de tal manera que${\displaystyle m(a)\leq 1}$por cada​${\displaystyle a\in U}$⁠ .

El número de multiconjuntos de cardinalidad k , con elementos tomados de un conjunto finito de cardinalidad n , se denomina a veces coeficiente de multiconjunto o número de multiconjunto . Algunos autores escriben este número como${\displaystyle \textstyle \left(\!\!{n \choose k}\!\!\right)}$, una notación que pretende asemejarse a la de los coeficientes binomiales ; se utiliza, por ejemplo, en (Stanley, 1997), y podría pronunciarse " n multichoose k " para asemejarse a " n choose k " para${\displaystyle {\tbinom {n}{k}}.}$Al igual que la distribución binomial , que incluye coeficientes binomiales, existe una distribución binomial negativa en la que aparecen coeficientes multiconjunto. Los coeficientes multiconjunto no deben confundirse con los coeficientes multinomiales que aparecen en el teorema multinomial .

El valor de los coeficientes del multiconjunto se puede dar explícitamente como $${\displaystyle \left(\!\!{n \choose k}\!\!\right)={n+k-1 \choose k}={\frac {(n+k-1)!}{k!\,(n-1)!}}={n(n+1)(n+2)\cdots (n+k-1) \over k!},}$$ donde la segunda expresión es como un coeficiente binomial; ^{[ a ]} ​​muchos autores, de hecho, evitan la notación separada y simplemente escriben coeficientes binomiales. Por lo tanto, el número de tales multiconjuntos es el mismo que el número de subconjuntos de cardinalidad k de un conjunto de cardinalidad n + k − 1. La analogía con los coeficientes binomiales se puede enfatizar escribiendo el numerador en la expresión anterior como una potencia factorial creciente.$${\displaystyle \left(\!\!{n \choose k}\!\!\right)={n^{\overline {k}} \over k!},}$$ para igualar la expresión de los coeficientes binomiales utilizando una potencia factorial decreciente: $${\displaystyle {n \choose k}={n^{\underline {k}} \over k!}.}$$

Por ejemplo , hay${\displaystyle \textstyle 4=\left(\!{\binom {2}{3}}\!\right)}$⁠ multiconjuntos de cardinalidad 3 con elementos tomados del conjunto de dos elementos {1, 2} , a saber, {1, 1, 1} , {1, 1, 2} , {1, 2, 2} y {2, 2, 2} . También hay ⁠${\displaystyle \textstyle 4={\binom {4}{3}}}$subconjuntos de cardinalidad 3 en el conjunto de cuatro elementos {1, 2, 3, 4} , a saber, {1, 2, 3} , {1, 2, 4} , {1, 3, 4} y { 2, 3, 4} .

Una forma sencilla de demostrar la igualdad de los coeficientes de multiconjuntos y los coeficientes binomiales dados anteriormente implica representar los multiconjuntos de la siguiente manera. Primero, consideremos la notación para multiconjuntos que representaría { a , a , a , a , a , a , b , b , c , c , c , d , d , d , d , d , d } (6 a s, 2 b s, 3 c s, 7 d s ) de esta forma :

 • • • • • • | • • | • • • | • • • • • • •                    

Este es un multiconjunto de cardinalidad k = 18 formado por elementos de un conjunto de cardinalidad n = 4. El número de caracteres, incluyendo puntos y líneas verticales, utilizado en esta notación es 18 + 4 − 1. El número de líneas verticales es 4 − 1. El número de multiconjuntos de cardinalidad 18 es entonces el número de maneras de ordenar las 4 − 1 líneas verticales entre los 18 + 4 − 1 caracteres, y es, por lo tanto, el número de subconjuntos de cardinalidad 4 − 1 de un conjunto de cardinalidad 18 + 4 − 1. De forma equivalente, es el número de maneras de ordenar los 18 puntos entre los 18 + 4 − 1 caracteres, que es el número de subconjuntos de cardinalidad 18 de un conjunto de cardinalidad 18 + 4 − 1. Esto es $${\displaystyle {4+18-1 \choose 4-1}={4+18-1 \choose 18}=1330,}$$ Así pues, el valor del coeficiente del multiconjunto y sus equivalencias son: $${\displaystyle {\begin{aligned}\left(\!\!{4 \choose 18}\!\!\right)&={21 \choose 18}={\frac {21!}{18!\,3!}}={21 \choose 3},\\[1ex]&={\frac {{\color {red}{\mathfrak {4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10\cdot 11\cdot 12\cdot 13\cdot 14\cdot 15\cdot 16\cdot 17\cdot 18}}}\cdot \mathbf {19\cdot 20\cdot 21} }{\mathbf {1\cdot 2\cdot 3} \cdot {\color {red}{\mathfrak {4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10\cdot 11\cdot 12\cdot 13\cdot 14\cdot 15\cdot 16\cdot 17\cdot 18}}}}},\\[1ex]&={\frac {1\cdot 2\cdot 3\cdot 4\cdot 5\cdots 16\cdot 17\cdot 18\;\mathbf {\cdot \;19\cdot 20\cdot 21} }{\,1\cdot 2\cdot 3\cdot 4\cdot 5\cdots 16\cdot 17\cdot 18\;\mathbf {\cdot \;1\cdot 2\cdot 3\quad } }},\\[1ex]&={\frac {19\cdot 20\cdot 21}{1\cdot 2\cdot 3}}.\end{aligned}}}$$

De la relación entre los coeficientes binomiales y los coeficientes de multiconjuntos, se deduce que el número de multiconjuntos de cardinalidad k en un conjunto de cardinalidad n se puede escribir $${\displaystyle \left(\!\!{n \choose k}\!\!\right)=(-1)^{k}{-n \choose k}.}$$ Además, $${\displaystyle \left(\!\!{n \choose k}\!\!\right)=\left(\!\!{k+1 \choose n-1}\!\!\right).}$$

Los multiconjuntos tienen diversas aplicaciones. ^{[ 7 ]} Se están volviendo fundamentales en combinatoria . ^{[ 18 ] [ 19 ] [ 20 ] [ 21 ]} Los multiconjuntos se han convertido en una herramienta importante en la teoría de bases de datos relacionales , que a menudo utiliza el sinónimo bolsa . ^{[ 22 ] [ 23 ] [ 24 ]} Por ejemplo, los multiconjuntos se utilizan a menudo para implementar relaciones en sistemas de bases de datos. En particular, una tabla (sin una clave primaria) funciona como un multiconjunto, porque puede tener múltiples registros idénticos. De manera similar, SQL opera sobre multiconjuntos y devuelve registros idénticos. Por ejemplo, considere "SELECT name FROM Student". En el caso de que haya múltiples registros con el nombre "Sara" en la tabla student, todos ellos se muestran. Eso significa que el resultado de una consulta SQL es un multiconjunto; si el resultado fuera en cambio un conjunto, los registros repetitivos en el conjunto de resultados se habrían eliminado. Otra aplicación de los multiconjuntos es en el modelado de multigrafos . En los multigrafos puede haber múltiples aristas entre dos vértices cualesquiera . Por lo tanto, la entidad que especifica las aristas es un multiconjunto, y no un conjunto.

También existen otras aplicaciones. Por ejemplo, Richard Rado utilizó multiconjuntos como herramienta para investigar las propiedades de las familias de conjuntos. Escribió: «La noción de conjunto no tiene en cuenta la aparición múltiple de ninguno de sus miembros, y sin embargo, es precisamente este tipo de información la que suele ser importante. Basta con pensar en el conjunto de raíces de un polinomio f ( x ) o en el espectro de un operador lineal ». ^{[ 5 ] : 328-329}

Se han introducido, estudiado y aplicado diferentes generalizaciones de multiconjuntos para la resolución de problemas.

• Multiconjuntos con signo (en los que la multiplicidad de un elemento puede ser cualquier entero ) ^{[ 25 ]}
• Multiconjuntos de valores reales (en los que la multiplicidad de un elemento puede ser cualquier número real ) ^{[ 26 ]}
• Multiconjuntos difusos ^{[ 27 ]}
• Multiconjuntos aproximados ^{[ 28 ]}
• Conjuntos híbridos ^{[ 29 ]}
• Multiconjuntos cuya multiplicidad es cualquier función escalonada de valor real ^{[ 30 ]}
• Multiconjuntos suaves ^{[ 31 ]}
• Multiconjuntos difusos suaves ^{[ 32 ]}
• Conjuntos con nombre (unificación de todas las generalizaciones de conjuntos) ^{[ 33 ] [ 34 ] [ 35 ] [ 36 ]}

• Frecuencia (estadística) como análogo de multiplicidad
• Cuasiconjuntos
• teoría de conjuntos
• modelo de bolsa de palabras
• Materiales de aprendizaje relacionados con particiones de multiconjuntos en Wikiversidad