Multiset

Este artículo trata sobre el concepto matemático. Para la estructura de datos de informática, consulte Multiset (tipo de datos abstracto) .

Conjunto matemático con repeticiones permitidas

En matemáticas , un multiset (o bag , o mset ) es una modificación del concepto de un 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 multiset. Como consecuencia, existe un número infinito de conjuntos múltiples que contienen sólo elementos un y b , pero varían en las multiplicidades de sus elementos:

• El conjunto { a , b } contiene sólo elementos a y b , teniendo cada una multiplicidad 1 cuando { a , b } es visto como un conjunto múltiple.
• En el conjunto múltiple { a , a , b } , el elemento a tiene multiplicidad 2 y b tiene multiplicidad 1.
• En el conjunto múltiple { 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 no importa en la discriminación de conjuntos múltiples, por lo que { a , a , b } y { a , b , a } denotan el mismo conjunto múltiple. Para distinguir entre conjuntos y conjuntos múltiples, a veces se utiliza una notación que incorpora corchetes: el conjunto múltiple { a , a , b } se puede denotar como [ a ,a , b ] . ^[1]

La cardinalidad de un multiset se construye sumando las multiplicidades de todos sus elementos. Por ejemplo, en la multiset { un , una , 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 . ^{[2] : 694} Sin embargo, el uso del 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, como lista , grupo , bolsa , montón , muestra , conjunto ponderado , colección.y suite . ^{[2] : 694}

Historia

Wayne Blizard rastreó los conjuntos múltiples hasta el origen mismo de los números, argumentando que "en la antigüedad, el número n a menudo se representaba mediante una colección de n trazos, marcas de conteo o unidades". ^[3] Estas y otras colecciones de objetos similares son conjuntos múltiples, porque los trazos, las marcas de conteo o las unidades se consideran indistinguibles. Esto muestra que la gente usó implícitamente conjuntos múltiples incluso antes de que surgieran las matemáticas.

Las necesidades prácticas de esta estructura han provocado que los conjuntos múltiples se redescubran varias veces, apareciendo en la literatura con diferentes nombres. ^{[4] : 323} Por ejemplo, eran importantes en los primeros lenguajes de la IA, como QA4, donde se les conocía como bolsas, un término atribuido a Peter Deutsch. ^[5] Un conjunto múltiple también se ha denominado agregado, montón, grupo, muestra, conjunto ponderado, conjunto de ocurrencias y conjunto de fuego (conjunto de elementos repetidos finitamente). ^{[4] : 320 [6]}

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ó las permutaciones de conjuntos múltiples. ^{[2] : 694} El trabajo de Marius Nizolius (1498-1576) contiene otra referencia temprana al concepto de multisets. ^[7] Athanasius Kircher encontró el número de permutaciones de múltiples conjuntos cuando un elemento puede repetirse. ^[8] Jean Prestet publicó una regla general para permutaciones de conjuntos múltiples en 1675. ^[9] John Wallis explicó esta regla con más detalle en 1685. ^[10]

Multisets apareció explícitamente en la obra de Richard Dedekind . ^{[11] : 114 [12]}

Otros matemáticos formalizaron los 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). ^{[4] : 326 [13] : 405} Monro (1987) investigó la categoría Mul de los conjuntos múltiples y sus morfismos, definiendo un conjunto múltiple como un conjunto con una relación de equivalencia entre elementos "del mismo tipo ", y un morfismo entre conjuntos múltiples como un función que respeta géneros. También introdujo un número múltiple : una función f ( x ) de un conjunto múltiple 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. ^{[4] : 327–328 [14]}

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 de elementos subyacente 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 el multiset {2, 2, 2, 3, 5} .

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 tanto, el conjunto múltiple de soluciones de la ecuación podría ser {3, 5} o podría ser {4, 4} . En el último caso tiene una solución de multiplicidad 2. De manera 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 conjunto múltiple de cardinalidad d .

Un caso especial de lo anterior son los valores propios de una matriz , cuya multiplicidad se suele definir como su multiplicidad como raíces del polinomio característico . Sin embargo, otras dos multiplicidades se definen naturalmente 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 conjuntos múltiples de valores propios, que pueden ser todos diferentes: Sea A unMatriz 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 el tamaño del bloque de Jordan más grande y su multiplicidad geométrica es el número de bloques de Jordan.

Definición

Un multiset puede definirse formalmente como una 2- tupla ( A , m ) donde A es el conjunto subyacente del multiset, formado a partir de sus elementos distintos, y es una función de A al conjunto de los enteros positivos , dando la multiplicidad , es decir, el número de apariciones del elemento a en el multiset como el número m ( a ) .${\displaystyle m\colon A\to \mathbb {Z} ^{+}}$

Representar la función m por su gráfica (el conjunto de pares ordenados ) 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)}) . Sin embargo, esta notación no se usa comúnmente y se emplean notaciones más compactas.${\displaystyle \left\{\left(a,m\left(a\right)\right):a\in A\right\}}$

Si es un conjunto finito , el conjunto múltiple ( A , m ) a menudo se representa como ${\displaystyle A=\{a_{1},\ldots ,a_{n}\}}$

${\displaystyle \left\{a_{1}^{m(a_{1})},\ldots ,a_{n}^{m(a_{n})}\right\},\quad }$ a veces simplificado a ${\displaystyle \quad a_{1}^{m(a_{1})}\cdots a_{n}^{m(a_{n})},}$

donde se omiten los índices superiores iguales a 1. Por ejemplo, el multiset { a , a , b } puede escribirse o Si los elementos del multiset son números, es posible una confusión con las operaciones aritméticas ordinarias , que normalmente se pueden excluir del contexto. Por otro lado, la última notación es coherente con el hecho de que la factorización prima de un entero positivo es un conjunto múltiple definido de forma única, como lo afirma el teorema fundamental de la aritmética . Además, un monomio es un conjunto múltiple de indeterminados ; por ejemplo, el monomio x ³ y ²${\displaystyle \{a^{2},b\}}$${\displaystyle a^{2}b.}$corresponde al multiset { x , x , x , y , y }.

Un multiset corresponde a un conjunto ordinario si la multiplicidad de cada elemento es uno (a diferencia de algún entero positivo mayor). Una familia indexada , ( a _i ) _{i ∈ I} , donde i varía sobre algún conjunto de índices I , puede definir un multiset, a veces escrito { a _i } . En esta vista, el conjunto subyacente del conjunto múltiple viene dado por la imagen de la familia, y la multiplicidad de cualquier elemento x es el número de valores de índice i tales que${\displaystyle a_{i}=x}$. En este artículo, las multiplicidades se consideran finitas, es decir, ningún elemento aparece infinitamente muchas veces en la familia: incluso en un multiset infinito, las multiplicidades son números finitos.

Es posible ampliar la definición de un conjunto múltiple permitiendo que las multiplicidades de elementos individuales sean cardinales infinitos en lugar de enteros positivos, pero no todas las propiedades se trasladan a esta generalización.

Propiedades y operaciones básicas

Los elementos de un conjunto múltiple generalmente se toman en un conjunto fijo U , a veces llamado universo , que a menudo es el conjunto de números naturales . Se dice que un elemento de U que no pertenece a un multiset dado tiene una multiplicidad 0 en este multiset. Esto extiende la función de multiplicidad del multiset a una función de U al conjunto de enteros no negativos . Esto define una correspondencia uno-a-uno entre estas funciones y los conjuntos múltiples que tienen sus elementos en U .${\displaystyle \mathbb {N} }$

Esta función de multiplicidad extendida se denomina comúnmente simplemente función de multiplicidad , y es suficiente para definir conjuntos múltiples 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 soporte de un multiconjunto en un universo U es el conjunto subyacente del multiconjunto. Utilizando la función de multiplicidad , se caracteriza como ${\displaystyle A}$${\displaystyle m}$

${\displaystyle \operatorname {Supp} (A):=\left\{x\in U\mid m_{A}(x)>0\right\}}$.

Un multiset es finito si su soporte es finito o, de manera equivalente, si su cardinalidad

${\displaystyle |A|=\sum _{x\in \operatorname {Supp} (A)}m_{A}(x)=\sum _{x\in U}m_{A}(x)}$

es finito. El conjunto múltiple vacío es el conjunto múltiple único con un soporte vacío (conjunto subyacente) y, por lo tanto, una cardinalidad 0.

Las operaciones habituales de conjuntos pueden extenderse a conjuntos múltiples mediante el uso de la función de multiplicidad, de manera similar al uso de la función de indicador para subconjuntos. A continuación, A y B son conjuntos múltiples en un universo U dado , con funciones de multiplicidad y${\displaystyle m_{A}}$${\displaystyle m_{B}.}$

• Inclusión: A está incluido en B , denotado A ⊆ B , si

${\displaystyle \forall x\in U,m_{A}(x)\leq m_{B}(x).}$

• Intersección: la intersección (llamada, en algunos contextos, el mínimo 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.}$

• Unión: la unión (llamada, en algunos contextos, el máximo o mínimo común múltiplo ) de A y B es el multiconjunto C con función de multiplicidad

${\displaystyle m_{C}(x)=\max(m_{A}(x),m_{B}(x))\quad \forall x\in U.}$^[15]

• Suma: la suma de conjuntos múltiples puede verse como una generalización de la unión disjunta de conjuntos, y se define como la C de conjuntos múltiples con función de multiplicidad

${\displaystyle m_{C}(x)=m_{A}(x)+m_{B}(x)\quad \forall x\in U.}$

La suma define una estructura monoide conmutativa en los conjuntos múltiples finitos en un universo dado. Este monoide es un monoide conmutativo libre , con el universo como base.

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

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

Contando conjuntos múltiples

Biyección entre 3 subconjuntos de un conjunto de 7 (izquierda)
y 3 conjuntos de múltiples con elementos de un conjunto de 5 (derecha)
Así que esto ilustra eso .${\displaystyle \textstyle {7 \choose 3}=\left(\!\!{5 \choose 3}\!\!\right)}$

Ver también: Estrellas y barras (combinatoria)

El número de conjuntos múltiples de cardinalidad k , con elementos tomados de un conjunto finito de cardinalidad n , se denomina coeficiente de conjuntos múltiples o número de conjuntos múltiples . Algunos autores escriben este número como , una notación que pretende parecerse a la de los coeficientes binomiales ; se utiliza, por ejemplo, en (Stanley, 1997), y podría pronunciarse " n multichoose k " para parecerse a " n choose k " . A diferencia de los coeficientes binomiales, no existe un "teorema de conjuntos múltiples" en el que se producirían coeficientes de conjuntos múltiples, y no deben confundirse con los coeficientes multinomiales no relacionados.${\displaystyle \textstyle \left(\!\!{n \choose k}\!\!\right)}$${\displaystyle {\tbinom {n}{k}}}$que ocurren en el teorema multinomial .

El valor de los coeficientes de conjuntos múltiples 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 un coeficiente binomial; de hecho, muchos autores evitan la notación separada y simplemente escriben coeficientes binomiales. Entonces, el número de tales conjuntos múltiples es el mismo que el número de subconjuntos de cardinalidad k en 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 ascendente

${\displaystyle \left(\!\!{n \choose k}\!\!\right)={n^{\overline {k}} \over k!},}$

para igualar la expresión de coeficientes binomiales usando una potencia factorial decreciente:

${\displaystyle {n \choose k}={n^{\underline {k}} \over k!}.}$

Hay, por ejemplo, 4 conjuntos múltiples de cardinalidad 3 con elementos tomados del conjunto {1, 2} de cardinalidad 2 ( n = 2 , k = 3 ), a saber {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, implica 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 a s, 2 b s, 3c s, 7 d s) en esta forma:

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

Se trata de un conjunto múltiple de cardinalidad k = 18 formado por elementos de un conjunto de cardinalidad n = 4. El número de caracteres, incluidos puntos y líneas verticales, utilizados en esta notación 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 líneas verticales 4 - 1 entre los caracteres 18 + 4 - 1 y, por lo tanto, es el número de subconjuntos de cardinalidad 4 - 1 en 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. Este es

${\displaystyle {4+18-1 \choose 4-1}={4+18-1 \choose 18}=1330,}$

así es el valor del coeficiente multiset y sus equivalencias:

${\displaystyle \left(\!\!{4 \choose 18}\!\!\right)={21 \choose 18}={\frac {21!}{18!\,3!}}={21 \choose 3}=\left(\!\!{19 \choose 3}\!\!\right),}$

${\displaystyle ={\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}}}}},}$

${\displaystyle ={\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\,\times \,\mathbf {1\cdot 2\cdot 3\quad } }},}$

${\displaystyle ={\frac {19\cdot 20\cdot 21}{1\cdot 2\cdot 3}}.}$

Se puede definir un coeficiente binomial generalizado

${\displaystyle {n \choose k}={n(n-1)(n-2)\cdots (n-k+1) \over k!}}$

en el que no se requiere que n sea ​​un número entero no negativo, pero puede ser negativo o no entero, o un número complejo no real . (Si k  = 0, entonces el valor de este coeficiente es 1 porque es el producto vacío ). Entonces, el número de conjuntos múltiples de cardinalidad k en un conjunto de cardinalidad n es

${\displaystyle \left(\!\!{n \choose k}\!\!\right)=(-1)^{k}{-n \choose k}.}$

Relación de recurrencia

Una relación de recurrencia para coeficientes de conjuntos múltiples se puede dar como

${\displaystyle \left(\!\!{n \choose k}\!\!\right)=\left(\!\!{n \choose k-1}\!\!\right)+\left(\!\!{n-1 \choose k}\!\!\right)\quad {\mbox{for }}n,k>0}$

con

${\displaystyle \left(\!\!{n \choose 0}\!\!\right)=1,\quad n\in \mathbb {N} ,\quad {\mbox{and}}\quad \left(\!\!{0 \choose k}\!\!\right)=0,\quad k>0.}$

La recurrencia anterior se puede interpretar de la siguiente manera. Sea [ n ]  : =  el conjunto fuente. Siempre hay exactamente un conjunto múltiple (vacío) de tamaño 0, y si n  = 0 no hay conjuntos múltiples más grandes, lo que da las condiciones iniciales.${\displaystyle \{1,\dots ,n\}}$

Ahora, considere el caso en el que n , k  > 0 . Un conjunto múltiple de cardinalidad k con elementos de [ n ] podría contener o no cualquier instancia del elemento final n . Si aparece, entonces al eliminar n una vez, uno se queda con un conjunto múltiple de cardinalidad k  - 1 de elementos de [ n ] , y cada uno de esos conjuntos múltiples puede surgir, lo que da un total de

${\displaystyle \left(\!\!{n \choose k-1}\!\!\right)}$ posibilidades.

Si n no aparece, entonces nuestro multiset original es igual a un multiset de cardinalidad k con elementos de [ n  - 1] , de los cuales hay

${\displaystyle \left(\!\!{n-1 \choose k}\!\!\right).}$

Por lo tanto,

${\displaystyle \left(\!\!{n \choose k}\!\!\right)=\left(\!\!{n \choose k-1}\!\!\right)+\left(\!\!{n-1 \choose k}\!\!\right).}$

Generando series

La función de generación de los coeficientes multiset es muy simple, siendo

${\displaystyle \sum _{d=0}^{\infty }\left(\!\!{n \choose d}\!\!\right)t^{d}={\frac {1}{(1-t)^{n}}}.}$

Como los conjuntos múltiples están en correspondencia uno a uno con los monomios, también es el número de monomios de grado d en n indeterminados. Por lo tanto, la serie anterior es también la serie de Hilbert del anillo polinomial${\displaystyle \left(\!\!{n \choose d}\!\!\right)}$ ${\displaystyle k[x_{1},\ldots ,x_{n}].}$

Como es un polinomio en n , se define para cualquier valor complejo de n .${\displaystyle \left(\!\!{n \choose d}\!\!\right)}$

Generalización y conexión con 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, complejo):

${\displaystyle \left(\!\!{\alpha \choose k}\!\!\right)={\frac {\alpha ^{\overline {k}}}{k!}}={\frac {\alpha (\alpha +1)(\alpha +2)\cdots (\alpha +k-1)}{k(k-1)(k-2)\cdots 1}}\quad {\text{for }}k\in \mathbb {N} {\text{ and arbitrary }}\alpha .}$

Con esta definición se tiene una generalización de la fórmula binomial negativa (con una de las variables puesta a 1), lo que justifica llamar a los coeficientes binomiales negativos:${\displaystyle \left(\!\!{\alpha \choose k}\!\!\right)}$

${\displaystyle (1-X)^{-\alpha }=\sum _{k=0}^{\infty }\left(\!\!{\alpha \choose k}\!\!\right)X^{k}.}$

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 sostienen que uno espera exponenciación , notablemente

${\displaystyle (1-X)^{-\alpha }(1-X)^{-\beta }=(1-X)^{-(\alpha +\beta )}\quad {\text{and}}\quad ((1-X)^{-\alpha })^{-\beta }=(1-X)^{-(-\alpha \beta )}}$,

y se pueden utilizar fórmulas como estas para probar las identidades de los coeficientes de conjuntos múltiples.

Si α es un número entero no positivo n , entonces 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 enteros positivos y los números racionales , la serie es infinita.

Aplicaciones

Los conjuntos múltiples tienen varias aplicaciones. ^[6] Se están volviendo fundamentales en la combinatoria . ^{[16] [17] [18] [19] Los conjuntos} múltiples se han convertido en una herramienta importante en la teoría de las bases de datos relacionales , que a menudo utiliza el sinónimo bag . ^{[20] [21] [22]} Por ejemplo, los conjuntos múltiples se utilizan a menudo para implementar relaciones en sistemas de bases de datos. En particular, una tabla (sin una clave principal) funciona como un conjunto múltiple, porque puede tener varios registros idénticos. Del mismo modo, SQLopera en conjuntos múltiples y devuelve registros idénticos. Por ejemplo, considere "SELECCIONAR el nombre del 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 conjunto de resultados de SQL es un conjunto múltiple. Si era un conjunto, se eliminaron los registros repetitivos en el conjunto de resultados. Otra aplicación de multiset es en el modelado de multigrafos . En los gráficos múltiples, 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 existen otras aplicaciones. Por ejemplo, Richard Rado utilizó conjuntos múltiples como un dispositivo para investigar las propiedades de familias de conjuntos. Escribió: "La noción de 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. Sólo tenemos que pensar en el conjunto de raíces de un polinomio f ( x ) o el espectro de un operador lineal ". ^{[4] : 328–329}

Generalizaciones

Esta sección necesita expansión . Puede ayudar agregando más . ( Junio ​​de 2013 )

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

• Conjuntos múltiples de valor real (en los que la multiplicidad de un elemento puede ser cualquier número real) ^{[23] [24]}

Esto parece sencillo, ya que muchas definiciones de conjuntos difusos y conjuntos múltiples son muy similares y se pueden asumir para conjuntos múltiples de valor real simplemente reemplazando el rango de valores de la función característica ([0, 1] o ℕ = {0, 1, 2 , 3, ...} respectivamente) por ℝ ₀ ⁺ = [0, ∞). Sin embargo, este enfoque no puede extenderse fácilmente para conjuntos difusos generalizados que utilizan un poset o lattice en lugar de un simple grado de pertenencia. Se han desarrollado varios otros enfoques para conjuntos múltiples difusos que no tienen esta restricción.

• Conjuntos múltiples difusos ^[25]
• Conjuntos múltiples en bruto ^[26]
• Conjuntos híbridos ^[27]
• Multiconjuntos cuya multiplicidad es cualquier función escalonada de valor real ^[28]
• Multiconjuntos suaves ^[29]
• Conjuntos múltiples difusos suaves ^[30]
• Conjuntos con nombre (unificación de todas las generalizaciones de conjuntos) ^{[31] [32] [33] [34]}

Ver también

• Frecuencia (estadísticas) como multiplicidad analógica
• Cuasi-conjuntos
• Teoría de conjuntos
• Materiales de aprendizaje relacionados con las particiones de multisets en Wikiversity

Referencias

1. Hein, James L. (2003). Matemáticas discretas . Editores Jones & Bartlett. págs.  29 –30. ISBN 0-7637-2210-3.
2. Knuth, Donald E. (1998). Algoritmos seminuméricos . El arte de la programación informática . 2 (3ª ed.). Addison Wesley . ISBN 0-201-89684-2.
3. Blizard, Wayne D (1989). "Teoría de multiset" . Notre Dame Journal of Formal Logic . 30 (1): 36–66. doi : 10.1305 / ndjfl / 1093634995 .
4. Blizard, Wayne D. (1991). "El desarrollo de la teoría de multiset" . Lógica moderna . 1 (4): 319–352.
5. Rulifson, JF; Derkson, JA; Waldinger, RJ (noviembre de 1972). QA4: Un cálculo procedimental para el razonamiento intuitivo (informe técnico). SRI Internacional. 73.
6. Singh, D .; Ibrahim, AM; Yohanna, T .; Singh, JN (2007). "Una visión general de las aplicaciones de multisets". Revista Novi Sad de Matemáticas . 37 (2): 73–92.
7. Angelelli, I. (1965). "El malentendido de Leibniz de la noción de 'multitudo ' de Nizolius ". Notre Dame Journal of Formal Logic (6): 319–322.
8. Kircher, Atanasio (1650). Musurgia Universalis . Roma: Corbelletti.
9. Prestet, Jean (1675). Elemens des Mathematiques . París: André Pralard.
10. Wallis, John (1685). Un tratado de álgebra . Londres: John Playford.
11. Dedekind, Richard (1888). Was sind und was sollen die Zahlen? . Braunschweig: Vieweg.
12. Syropoulos, Apostolos (2001). "Matemáticas de Multisets". En Calude, CS; et al. (eds.). Procesamiento de múltiples conjuntos: puntos de vista matemáticos, informáticos y de computación molecular . Springer-Verlag. págs. 347–358.
13. Whitney, H. (1933). "Funciones características y el álgebra de la lógica". Annals of Mathematics . 34 : 405–414. doi : 10.2307 / 1968168 .
14. Monro, GP (1987). "El concepto de Multiset". Zeitschrift für Mathematische Logik und Grundlagen der Mathematik . 33 : 171-178. doi : 10.1002 / malq.19870330212 .
15. Syropoulos, Apostolos (2000). "Matemáticas de Multisets" . Apuntes de conferencias en Ciencias de la Computación . 2235 : 347--358. doi : 10.1007 / 3-540-45523-X_17 . Consultado el 16 de febrero de 2021 .
16. Aigner, M. (1979). Teoría combinatoria . Nueva York / Berlín: Springer Verlag.
17. Anderson, I. (1987). Combinatoria de conjuntos finitos . Oxford: Clarendon Press.
18. Stanley, Richard P. (1997). Combinatoria enumerativa . 1 . Prensa de la Universidad de Cambridge. ISBN 0-521-55309-1.
19. Stanley, Richard P. (1999). Combinatoria enumerativa . 2 . Prensa de la Universidad de Cambridge. ISBN 0-521-56069-1.
20. Grumbach, S .; Milo, T (1996). "Hacia álgebras manejables para bolsas". Revista de Ciencias de la Computación y Sistemas . 52 (3): 570–588. doi : 10.1006 / jcss.1996.0042 .
21. Libkin, L .; Wong, L. (1994). "Algunas propiedades de los lenguajes de consulta para bolsos". Actas del Taller sobre lenguajes de programación de bases de datos . Springer Verlag. págs. 97-114.
22. Libkin, L .; Wong, L. (1995). "Sobre la representación y consulta de información incompleta en bases de datos con bolsas". Cartas de procesamiento de información . 56 (4): 209–214. doi : 10.1016 / 0020-0190 (95) 00154-5 .
23. Blizard, Wayne D. (1989). "Multisets de valor real y Fuzzy Sets". Conjuntos y sistemas difusos . 33 : 77–97. doi : 10.1016 / 0165-0114 (89) 90218-2 .
24. Blizard, Wayne D. (1990). "Membresía negativa". Notre Dame Journal of Formal Logic . 31 (1): 346–368.
25. Yager, RR (1986). "Sobre la teoría de las bolsas". Revista Internacional de Sistemas Generales . 13 : 23–37. doi : 10.1080 / 03081078608934952 .
26. Grzymala-Busse, J. (1987). "Aprendiendo de ejemplos basados ​​en multisets aproximados". Actas del II Simposio Internacional de Metodologías para Sistemas Inteligentes . Charlotte, Carolina del Norte. págs. 325–332.
27. Loeb, D. (1992). "Conjuntos con un número negativo de elementos" . Avances en Matemáticas . 91 : 64–74. doi : 10.1016 / 0001-8708 (92) 90011-9 .
28. Miyamoto, S. (2001). "Multisets difusos y sus generalizaciones". Procesamiento de múltiples conjuntos . 2235 : 225–235.
29. Alkhazaleh, S .; Salleh, AR; Hassan, N. (2011). "Teoría Soft Multisets". Ciencias Matemáticas Aplicadas . 5 (72): 3561–3573.
30. Alkhazaleh, S .; Salleh, AR (2012). "Teoría Multiset suave difusa". Análisis abstracto y aplicado .
31. Burgin, Mark (1990). "Teoría de conjuntos nombrados como base fundamental para las matemáticas" . Estructuras en teorías matemáticas . San Sebastian. págs. 417–420.
32. Burgin, Mark (1992). "Sobre el concepto de multiset en cibernética". Cibernética y análisis de sistemas . 3 : 165-167.
33. Burgin, Mark (2004). "Fundamentos unificados de las matemáticas". arXiv : matemáticas / 0403186 .
34. Burgin, Mark (2011). Teoría de conjuntos nombrados . Desarrollos de la investigación matemática. Nova Science Pub Inc. ISBN 978-1-61122-788-8.