Multiset
En matemáticas, un multiconjunto (o bolsa, o mset) es una modificación del concepto de conjunto que, a diferencia de un conjunto, permite múltiples instancias para cada uno de sus elementos. El número de instancias dadas para cada elemento se denomina multiplicidad de ese elemento en el conjunto múltiple. Como consecuencia, existe una cantidad infinita de conjuntos múltiples que contienen solo elementos a y b, pero varían en la multiplicidad de sus elementos:
- El set {}a, b} sólo contiene elementos a y b, cada uno con multiplicidad 1 cuando {}a, b} se ve como un multiset.
- En el multiset {}a, a, b}, el elemento a tiene multiplicidad 2, y b tiene multiplicidad 1.
- En el multiset {}a, a, a, b, b, b}, a y b ambos tienen multiplicidad 3.
Estos objetos son todos diferentes cuando se ven como conjuntos múltiples, aunque son el mismo conjunto, ya que todos constan de los mismos elementos. Al igual que con los conjuntos, y en contraste con las tuplas, el orden en que se enumeran los elementos no importa al discriminar conjuntos múltiples, por lo que {a, a, b} y {a, b, a} denota el mismo conjunto múltiple. Para distinguir entre conjuntos y conjuntos múltiples, a veces se usa una notación que incorpora corchetes: el conjunto múltiple {a, a, b } se puede indicar mediante [a, a, b].
La cardinalidad de un conjunto múltiple es la suma de las multiplicidades de todos sus elementos. Por ejemplo, en el conjunto múltiple {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 conjunto múltiple es 6.
Nicolaas Govert de Bruijn acuñó la palabra multiset en la década de 1970, según Donald Knuth. Sin embargo, el concepto de multiset es anterior a la acuñación de la palabra multiset por muchos siglos. El propio Knuth atribuye el primer estudio de conjuntos múltiples al matemático indio Bhāskarāchārya, quien describió las permutaciones de conjuntos múltiples alrededor de 1150. Se han propuesto o utilizado otros nombres para este concepto, incluidos lista, grupo, bolsa, montón, muestra, conjunto ponderado, colección y suite.
Historia
Wayne Blizard rastreó los multiconjuntos hasta el origen mismo de los números, argumentando que "en la antigüedad, el número n a menudo se representaba por una colección de n trazos, marcas de conteo o unidades." Estas colecciones de objetos y otras similares son conjuntos múltiples, porque los trazos, las marcas de conteo o las unidades se consideran indistinguibles. Esto muestra que la gente usaba implícitamente conjuntos múltiples incluso antes de que surgieran las matemáticas.
Las necesidades prácticas de esta estructura han hecho que los conjuntos múltiples se redescubran varias veces, apareciendo en la literatura con diferentes nombres. Por ejemplo, eran importantes en los primeros lenguajes de IA, como QA4, donde se los denominaba bolsas, un término atribuido a Peter Deutsch. Un conjunto múltiple también se denomina agregado, montón, grupo, muestra, conjunto ponderado, conjunto de ocurrencia y conjunto de fuego (conjunto de elementos repetidos finitamente).
Aunque los conjuntos múltiples se usaron implícitamente desde la antigüedad, su exploración explícita ocurrió mucho más tarde. El primer estudio conocido de conjuntos múltiples se atribuye al matemático indio Bhāskarāchārya alrededor de 1150, quien describió permutaciones de conjuntos múltiples. El trabajo de Marius Nizolius (1498-1576) contiene otra referencia temprana al concepto de conjuntos múltiples. Athanasius Kircher encontró el número de permutaciones de conjuntos múltiples cuando un elemento se puede repetir. Jean Prestet publicó una regla general para permutaciones de conjuntos múltiples en 1675. John Wallis explicó esta regla con más detalle en 1685.
Multisets apareció explícitamente en el trabajo de Richard Dedekind.
Otros matemáticos formalizaron conjuntos múltiples y comenzaron a estudiarlos como estructuras matemáticas precisas en el siglo XX. Por ejemplo, Whitney (1933) describió conjuntos generalizados ("conjuntos" cuyas funciones características pueden tomar cualquier valor entero: positivo, negativo o cero). 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 sort", y un morfismo entre multiconjuntos como una función que respeta sorts. También introdujo un multinúmero : una función f (x) de un multiconjunto a los números naturales, dando la multiplicidad del elemento x en el conjunto múltiple. Monro argumentó que los conceptos de multiconjunto y multinúmero a menudo se mezclan indiscriminadamente, aunque ambos son útiles.
Ejemplos
Uno de los ejemplos más simples y naturales es el conjunto múltiple 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
Un ejemplo relacionado es el conjunto múltiple de soluciones de una ecuación algebraica. Una ecuación cuadrática, por ejemplo, tiene dos soluciones. Sin embargo, en algunos casos ambos son el mismo número. Por lo tanto, el conjunto múltiple de soluciones de la ecuación podría ser {3, 5}, o podría ser {4, 4}. En este último caso tiene una solución de multiplicidad 2. Más generalmente, el teorema fundamental del álgebra afirma que las soluciones complejas de una ecuación polinomial de grado d siempre forman un conjunto múltiple de cardinalidad d.
Un caso especial de lo anterior son los valores propios de una matriz, cuya multiplicidad suele definirse como su multiplicidad como raíces del polinomio característico. Sin embargo, otras dos multiplicidades se definen de forma natural para los valores propios, 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 valor propio de la matriz A). Estas tres multiplicidades definen tres multiconjuntos de valores propios, que pueden ser todos diferentes: Sea A un Matriz n × n en forma normal de Jordan que tiene un solo valor propio. Su multiplicidad es n, su multiplicidad como raíz del polinomio mínimo es del tamaño del bloque Jordan más grande y su multiplicidad geométrica es el número de bloques Jordan.
Definición
A multiset puede ser definido formalmente como un par ordenado ()A, m) Donde A es subyacente del multiset, formado a partir de sus distintos elementos, y m:: A→ → Z+{displaystyle mcolon Atomathbb} es una función A al conjunto de enteros positivos, dando el multiplicidad – es decir, el número de ocurrencias – del elemento a en el multiset como el número m()a).
Representación de la función m por su gráfico (el conjunto de pares ordenados {}()a,m()a)):a▪ ▪ A}{displaystyle left{left(a,mleft(aright)right:ain Aright}}) permite escribir el multiset {}a, a, b} como ({a, b} {a, 2), (b, 1)}), y el multiset {}a, b} como ({a, b} {a, 1), (b, 1)}). Esta notación no es comúnmente utilizada y se emplean notaciones más compactas.
Si A={}a1,...... ,an}{displaystyle A={a_{1},ldotsa_{n}} es un conjunto finito, el multiset ()A, m) a menudo representado como
- {}a1m()a1),...... ,anm()an)},{displaystyle left{a_{1} {m(a_{1}}}ldotsa_{n}{m(a_{n}}right}quad } a veces simplificado a1m()a1)⋯ ⋯ anm()an),{displaystyle quad a_{1} {m(a_{1}}cdots a_{n}^{m(a_{n}}}}
donde se omiten índices superiores iguales a 1 Por ejemplo, el multiset {a, a, b} puede ser escrito {}a2,b}{displaystyle {a^{2},b} o a2b.{displaystyle a^{2}b.} Si los elementos del multiset son números, es posible una confusión con operaciones aritméticas ordinarias, las que normalmente pueden ser excluidas del contexto. Por otra parte, la última notación es coherente con el hecho de que la factorización principal de un entero positivo es un multiset de una definición única, como afirma el teorema fundamental de la aritmética. Además, un monomial es un multiconjunto de indeterminados; por ejemplo, el monomial x3Sí.2 corresponde al multiset {x, x, x, Sí., Sí.}.
Un multiset corresponde a un conjunto ordinario si la multiplicidad de cada elemento es 1. Una familia indexada ()ai)i▪I, donde i varia sobre un conjunto de índices I, puede definir un multiset, a veces escrito {}ai}. En esta opinión, el conjunto subyacente del multiconjunto se da por la imagen de la familia, y la multiplicidad de cualquier elemento x es el número de valores índice i tales que ai=x{displaystyle A_{i}=x}. En este artículo se considera que las multiplicidades son finitas, por lo que ningún elemento ocurre infinitamente muchas veces en la familia; incluso en un multiset infinito, las multiplicidades son números finitos.
Es posible extender la definición de un conjunto múltiple al permitir que las multiplicidades de elementos individuales sean cardinales infinitos en lugar de números enteros positivos, pero no todas las propiedades se trasladan a esta generalización.
Propiedades y operaciones básicas
Los elementos de un multiset se toman generalmente en un conjunto fijo U, a veces se llama universo, que es a menudo el conjunto de números naturales. Un elemento U que no pertenece a un determinado multiset se dice que tiene una multiplicidad 0 en este multiset. Esto extiende la función multiplicidad del multiset a una función desde U al conjunto N{displaystyle mathbb {N} de enteros no negativos. Esto define una correspondencia única entre estas funciones y los multiconjuntos que tienen sus elementos en U.
Esta función de multiplicidad extendida comúnmente se llama simplemente la función de multiplicidad, y es suficiente para definir multiconjuntos cuando el universo que contiene los elementos ha sido 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 Apoyo de un multiset A{displaystyle A} en un universo U es el conjunto subyacente del multiset. Usando la función multiplicidad m{displaystyle m}, se caracteriza como
Un conjunto múltiple es finito si su soporte es finito o, de manera equivalente, si su cardinalidad
Las operaciones habituales de los conjuntos se pueden ampliar a los multisets utilizando la función multiplicidad, de manera similar a utilizar la función indicadora para subconjuntos. En lo siguiente, A y B son multiconjuntos en un universo dado U, con funciones multiplicidad mA{displaystyle m_{A} y mB.{displaystyle M_{B}.
- Inclusión: A es incluido dentro B, denotado A ⊆ B, si mA()x)≤ ≤ mB()x)О О x▪ ▪ U.{displaystyle m_{A}(x)leq m_{B}(x)quad forall xin U.}
- Unión: el sindicato (llamados, en algunos contextos, los máximo o más bajo común múltiples) de A y B es el multiset C con función multiplicidad mC()x)=max()mA()x),mB()x))О О x▪ ▪ U.{displaystyle m_{C}(x)=max(m_{A}(x),m_{B}(x)quad forall xin U.}
- Intersección: el intersección (llamados, en algunos contextos, los infimum o mayor divisor común) de A y B es el multiset C con función multiplicidad mC()x)=min()mA()x),mB()x))О О x▪ ▪ U.{displaystyle m_{C}(x)=min(m_{A}(x),m_{B}(x)quad forall xin U.}
- Sum: el suma de A y B es el multiset C con función multiplicidad Puede considerarse como una generalización de la unión descomunal de conjuntos. Define una estructura monoide comunicativa en los multiconjuntos finitos en un universo dado. Este monoide es un monoide libre, con el universo como base.mC()x)=mA()x)+mB()x)О О x▪ ▪ U.{displaystyle m_{C}(x)=m_{A}(x)+m_{B}(x)quad forall xin U.}
- Diferencia: el diferencia de A y B es el multiset C con función multiplicidad mC()x)=max()mA()x)− − mB()x),0)О О x▪ ▪ U.{displaystyle m_{C}(x)=max(m_{A}(x)-m_{B}(x),0)quad forall xin U.}
Dos multiconjuntos son disjuntos si sus soportes son conjuntos disjuntos. Esto es equivalente 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 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 posibles intersecciones de un número impar de los multiconjuntos dados, mientras que en la segunda suma consideramos todas las posibles intersecciones de un número par de los multiconjuntos dados.
Contar conjuntos múltiples
El número de multiconjuntos de la cardinalidad k, con elementos tomados de un conjunto finito de la cardenalidad n, se llama el coeficiente multiset o Número multiset. Este número está escrito por algunos autores como ()()nk)){displaystyle textstyle left(!!{n {fnMicrosoft Sans Serif}, una notación que está destinada a parecerse a la de los coeficientes binomiales; se utiliza por ejemplo en (Stanley, 1997), y podría ser pronunciada "n multichoose k"para parecer "n elegir kpara ()nk).{displaystyle {tbinom {n}}}} Al igual que la distribución binomial que implica coeficientes binomiales, hay una distribución binomial negativa en la que se producen los coeficientes multiconjuntos. Los coeficientes multiconjuntos no deben confundirse con los coeficientes multinomios no relacionados que ocurren en el teorema multinomio.
El valor de los coeficientes de conjuntos múltiples se puede dar explícitamente como
Hay por ejemplo 4 multiconjuntos de cardinalidad 3 con elementos tomados del conjunto {1, 2} de cardinalidad 2 ( n = 2, k = 3), es decir, {1, 1, 1}, {1, 1, 2}, {1, 2, 2}, {2, 2, 2}. También hay 4 subconjuntos de cardinalidad 3 en el conjunto {1, 2, 3, 4} de cardinalidad 4 (n + k − 1), a saber, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}.
Una forma sencilla de demostrar la igualdad de los coeficientes de conjuntos múltiples y los coeficientes binomiales dados anteriormente consiste en representar conjuntos múltiples de la siguiente manera. Primero, considere la notación para conjuntos múltiples que representaría {a, a, a, a , a, a, b, b, c, c, c, d, d, d, d, d, d, d} (6 as, 2 bs, 3 cs, 7 ds) de esta forma:
- • • • • • • • • • • • • • • • • • • • • • • • • • • •
Este es un conjunto múltiple de cardinalidad k = 18 hecho de elementos de un conjunto de cardinalidad n = 4. La cantidad de caracteres que se usan en esta notación, incluidos los puntos y las líneas verticales, es 18 + 4 − 1. El número de líneas verticales es 4 − 1. El número de conjuntos múltiples de cardinalidad 18 es entonces el número de formas de organizar las 4 − 1 líneas verticales entre los 18 + 4 − 1 caracteres y, por lo tanto, es el número de subconjuntos de cardinalidad 4 − 1 de un conjunto de cardinalidad 18 + 4 − 1. De manera equivalente, es el número de formas de organizar 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
De la relación entre coeficientes binomiales y coeficientes multiconjunto, se deduce que el número de multiconjuntos de cardinalidad k en un conjunto de cardinalidad n se puede escribir
Relación de recurrencia
Se puede dar una relación de recurrencia para coeficientes de conjuntos múltiples como
La recurrencia anterior puede interpretarse como sigue. Vamos [n]:={}1,...... ,n}{displaystyle [n]:={1,dotsn} sea el conjunto de fuentes. Siempre hay exactamente un (vacío) multiset de tamaño 0, y si n = 0 no hay multisets más grandes, que da las condiciones iniciales.
Ahora, considere el caso en el que n, k > 0. Un conjunto múltiple de cardinalidad k con elementos de [n] puede o no contener ninguna instancia del elemento final n. Si aparece, al eliminar n una vez, queda un conjunto múltiple de cardinalidad k − 1 de elementos de [n], y puede surgir cada multiconjunto, lo que da una Total de
Si n no aparece, entonces nuestro conjunto múltiple original es igual a un conjunto múltiple de cardinalidad k con elementos de [n − 1], de los cuales hay
Por lo tanto,
Generando series
La función generadora de los coeficientes multiconjunto es muy simple, siendo
As ()()nd)){displaystyle left(! {fnMicrosoft Sans Serif} es un polinomio en n, ella y la función generadora están bien definidas para cualquier valor complejo n.
Generalización y conexión a la serie binomial negativa
La fórmula multiplicativa permite ampliar la definición de coeficientes de conjuntos múltiples reemplazando n por un número arbitrario α (negativo, real o complejo):
Con esta definición uno tiene una generalización de la fórmula binomial negativa (con una de las variables fijadas a 1), que justifica llamar a la ()()α α k)){displaystyle left(!!{alpha choose k}!!right)} coeficientes binomiales negativos:
Esta fórmula de la serie de Taylor es válida para todos los números complejos α y X con |X| < 1. También se puede interpretar como una identidad de series de potencias formales en X, donde en realidad puede servir como definición de potencias arbitrarias de series con coeficiente constante igual a 1; el punto es que con esta definición todas las identidades tienen lo que uno espera para la exponenciación, en particular
Si α es un número entero no positivo n, luego todos los términos con k > −n son cero, y la serie infinita se convierte en una suma finita. Sin embargo, para otros valores de α, incluidos los números enteros positivos y los números racionales, la serie es infinita.
Aplicaciones
Los conjuntos múltiples tienen varias aplicaciones. Se están volviendo fundamentales en combinatoria. Los multiconjuntos se han convertido en una herramienta importante en la teoría de las bases de datos relacionales, que a menudo utiliza el sinónimo bolsa. Por ejemplo, los conjuntos múltiples se utilizan a menudo para implementar relaciones en los sistemas de bases de datos. En particular, una tabla (sin clave principal) funciona como un conjunto múltiple, ya que puede tener varios registros idénticos. De manera similar, SQL opera en conjuntos múltiples y devuelve registros idénticos. Por ejemplo, considere "SELECCIONAR nombre de Estudiante". En el caso de que haya varios registros con el nombre "Sara" en la tabla de estudiantes, se muestran todos. Eso significa que el resultado de una consulta SQL es un conjunto múltiple; si el resultado fuera un conjunto, los registros repetitivos en el conjunto de resultados se habrían eliminado. Otra aplicación de los multiconjuntos es el modelado de multigrafos. En los multigrafos puede haber múltiples aristas entre dos vértices dados. Como tal, la entidad que muestra los bordes es un conjunto múltiple y no un conjunto.
También hay otras aplicaciones. Por ejemplo, Richard Rado usó conjuntos múltiples como dispositivo para investigar las propiedades de las familias de conjuntos. Escribió: "La noción de un conjunto no tiene en cuenta la ocurrencia múltiple de cualquiera de sus miembros y, sin embargo, es precisamente este tipo de información la que suele tener importancia". Solo necesitamos pensar en el conjunto de raíces de un polinomio f (x) o el espectro de un operador lineal."
Generalizaciones
Se han introducido, estudiado y aplicado diferentes generalizaciones de conjuntos múltiples para resolver problemas.
- Multiconjuntos de valor real (en los que la multiplicidad de un elemento puede ser cualquier número real)
- Fuzzy multisets
- Multisets Rough
- Sets híbridos
- Multisets cuya multiplicidad es cualquier función de paso real
- Soft multisets
- Soft fuzzy multisets
- Nombre de conjuntos (unificación de todas las generalizaciones de conjuntos)
Contenido relacionado
Juego de terminación de cuatro hilos
Resistencia
Claro