Conjunto múltiple

En matemáticas , un multiconjunto (o bag , 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 denomina 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 varían en las multiplicidades de sus elementos:

El conjunto ${a, b}$ contiene sólo los elementos $a$ y $b$ , cada uno con multiplicidad 1 cuando ${a, b}$ se considera 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}$ , $a$ y $b$ ambos tienen multiplicidad 3.

Estos objetos son todos diferentes cuando se los ve como multiconjuntos, 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 el que se enumeran los elementos no importa para discriminar 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.

Según Donald Knuth , Nicolaas Govert de Bruijn acuñó la palabra multiconjunto en la década de 1970. ^[3]^{: 694} Sin embargo, el concepto de multiconjuntos es anterior a la acuñación de la palabra multiconjunto por muchos siglos. El propio Knuth atribuye el primer estudio de los 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, incluidos lista , grupo , bolsa , montón , muestra , conjunto ponderado , colección y suite . ^[3]^{: 694}

Historia

Wayne Blizard rastreó los multiconjuntos hasta el origen mismo de 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 similares de objetos pueden considerarse multiconjuntos, porque los trazos, las marcas de conteo o las unidades se consideran indistinguibles. Esto demuestra que la gente utilizaba implícitamente multiconjuntos incluso antes de que surgiera la matemática.

Las necesidades prácticas de esta estructura han hecho que los multiconjuntos se redescubrieran 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 los conocía como bolsas, un término atribuido a Peter Deutsch . ^[6] Un multiconjunto también se ha denominado agregado, montón, racimo, muestra, conjunto ponderado, conjunto de ocurrencia y conjunto de elementos repetidos finitamente. ^[5]^{: 320}^[7]

Aunque los multiconjuntos se han utilizado de forma implícita desde la antigüedad, su exploración explícita se produjo mucho después. El primer estudio conocido de los multiconjuntos se atribuye al matemático indio Bhāskarāchārya alrededor de 1150, que describió las permutaciones de los multiconjuntos. ^[3]^{: 694} El trabajo 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 las 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 los 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]

Ejemplos

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

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. Por lo tanto, el multiconjunto 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 multiconjunto de cardinalidad $d$ .

Un caso especial de lo anterior son los valores propios de una matriz , cuya multiplicidad se define habitualmente como su multiplicidad como raíces del polinomio característico . Sin embargo, se definen naturalmente otras dos multiplicidades 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$ una matriz $n \times n$ en forma normal de Jordan que tiene un único 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 multiconjunto puede definirse formalmente como un par ordenado $(A, m)$ donde $A$ es el conjunto subyacente del multiconjunto, formado a partir de sus elementos distintos, y es una función de $A$ al conjunto de números enteros positivos, dando la multiplicidad –es decir, el número de ocurrencias– del elemento $a$ en el multiconjunto como el número $m$ $($ $a$ $)$ . $m\colon A\to \mathbb {Z} ^{+}$

(También es posible permitir la multiplicidad 0 o , especialmente cuando se consideran submulticonjuntos. ^[16] Este artículo está restringido a multiplicidades positivas finitas). ${\estilo de visualización\infty}$

Representar la función $m$ por su gráfico (el conjunto de pares ordenados ) permite escribir el multiconjunto ${$ $a$ $,$ $a$ $,$ $b$ $}$ como ${($ $a$ $, 2), ($ $b$ $, 1)$ }, y el multiconjunto ${$ $a$ $,$ $b$ $}$ como ${($ $a$ $, 1), ($ $b$ $, 1)$ }. Sin embargo, esta notación no se utiliza comúnmente; se emplean notaciones más compactas. $\{(a,m(a)):a\en A\}$

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

\left\{a_{1}^{m(a_{1})},\ldots ,a_{n}^{m(a_{n})}\right\},\quad

A veces simplificado a

\quad a_{1}^{m(a_{1})}\cdots a_{n}^{m(a_{n})},

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

Un multiconjunto corresponde a un conjunto ordinario si la multiplicidad de cada elemento es 1. Una familia indexada $(a i) i \in I$ , donde $i$ varía sobre algún conjunto de índices I , puede definir un multiconjunto, a veces escrito ${a i}$ . En esta visión, el conjunto subyacente del multiconjunto está 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 . En este artículo, las multiplicidades se consideran finitas, de modo que ningún elemento ocurre infinitas veces en la familia; incluso en un multiconjunto infinito, las multiplicidades son números finitos. $Estilo de visualización ai=x$

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

Propiedades y operaciones básicas

Los elementos de un multiconjunto se toman generalmente 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 multiconjunto dado tiene una multiplicidad 0 en este multiconjunto. Esto extiende la función de multiplicidad del multiconjunto a una función de $U$ al conjunto de números enteros no negativos. Esto define una correspondencia uno a uno entre estas funciones y los multiconjuntos que tienen sus elementos en $U$ . $\mathbb {N}$

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 ha sido fijado. 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 ${\estilo de visualización A}$ ${\estilo de visualización m}$ $\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 es finita. El multiconjunto vacío es el único multiconjunto con un soporte vacío (conjunto subyacente) y, por lo tanto, una cardinalidad 0. $|A|=\sum _{x\in \operatorname {Supp} (A)}m_{A}(x)=\sum _{x\in U}m_{A}(x)$

Las operaciones habituales de conjuntos pueden extenderse a multiconjuntos utilizando la función de multiplicidad, de forma similar a la utilización de la función indicadora para subconjuntos. En lo que sigue, $A$ y $B$ son multiconjuntos en un universo dado $U$ , con funciones de multiplicidad y $Estilo de visualización mA$ $m_{B}.$

Inclusión: $A$ está incluido en $B$ , denotado $A \subseteq B$ , si $m_{A}(x)\leq m_{B}(x)\quad \para todo x\en 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] $m_{C}(x)=\max(m_{A}(x),m_{B}(x))\quad \para todo x\en 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 $m_{C}(x)=\min(m_{A}(x),m_{B}(x))\quad \para todo x\en U.$
Suma: la suma de $A$ y $B$ es el multiconjunto $C$ con función de multiplicidad Puede considerarse como una generalización de la unión disjunta de conjuntos. Define una estructura monoide conmutativa sobre los multiconjuntos finitos en un universo dado. Este monoide es un monoide conmutativo libre , con el universo como base. $m_{C}(x)=m_{A}(x)+m_{B}(x)\quad \para todo x\en U.$
Diferencia: la diferencia de $A$ y $B$ es el multiconjunto $C$ con función de multiplicidad $m_{C}(x)=\max(m_{A}(x)-m_{B}(x),0)\quad \para todo x\en 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 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. ^{[ cita requerida ]}

Contando multiconjuntos

El número de multiconjuntos de cardinalidad $k$ , con elementos tomados de un conjunto finito de cardinalidad $n$ , a veces se denomina coeficiente de multiconjunto o número de multiconjunto . 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$ " para Al igual que la distribución binomial que implica coeficientes binomiales, existe una distribución binomial negativa en la que aparecen los coeficientes de multiconjunto. Los coeficientes de multiconjunto no deben confundirse con los coeficientes multinomiales no relacionados que aparecen en el teorema multinomial . $\textstyle \left(\!\!{n \elige k}\!\!\right)$ ${\tbinom {n}{k}}.$

El valor de los coeficientes de multiconjuntos se puede dar explícitamente como donde la segunda expresión es un coeficiente binomial; ^[a] de hecho, muchos autores evitan la notación separada y solo 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 ascendente para que coincida con la expresión de coeficientes binomiales utilizando una potencia factorial descendente: $\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) \sobre k!},$ $\left(\!\!{n \choose k}\!\!\right)={n^{\overline {k}} \sobre k!},$ ${n \choose k}={n^{\underline {k}} \sobre k!}.$

Por ejemplo, hay 4 multiconjuntos 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 multiconjuntos y los coeficientes binomiales dados anteriormente implica representar los multiconjuntos de la siguiente manera. Primero, considere 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) en 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 que incluyen tanto puntos como 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 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 tanto el número de subconjuntos de cardinalidad 4 − 1 de un conjunto de cardinalidad $18 + 4 - 1$ . Equivalentemente, 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$ . Este es entonces el valor del coeficiente multiconjunto y sus equivalencias: ${4+18-1 \elige 4-1}={4+18-1 \elige 18}=1330,$ ${\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 multiconjunto, se deduce que el número de multiconjuntos de cardinalidad $k$ en un conjunto de cardinalidad $n$ se puede escribir Además, $\left(\!\!{n \choose k}\!\!\right)=(-1)^{k}{-n \choose k}.$ $\left(\!\!{n \choose k}\!\!\right)=\left(\!\!{k+1 \choose n-1}\!\!\right).$

Relación de recurrencia

Se puede dar una relación de recurrencia para coeficientes multiconjunto como con $\left(\!\!{n \choose k}\!\!\right)=\left(\!\!{n \choose k-1}\!\!\right)+\left(\!\!{n-1 \choose k}\!\!\right)\quad {\mbox{for }}n,k>0$ $\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 puede interpretarse de la siguiente manera. Sea el conjunto fuente. Siempre hay exactamente un multiconjunto (vacío) de tamaño 0, y si $n$ $= 0$ no hay multiconjuntos mayores, lo que da las condiciones iniciales. $[n]:=\{1,\dots ,n\}$

Ahora, consideremos el caso en el que $n, k > 0$ . Un multiconjunto de cardinalidad $k$ con elementos de $[n]$ podría o no contener alguna instancia del elemento final $n$ . Si aparece, entonces al eliminar $n$ una vez, uno queda con un multiconjunto de cardinalidad $k - 1$ de elementos de $[n]$ , y cada uno de esos multiconjuntos puede surgir, lo que da un total de posibilidades. $\left(\!\!{n \choose k-1}\!\!\right)$

Si $n$ no aparece, entonces nuestro multiconjunto original es igual a un multiconjunto de cardinalidad $k$ con elementos de $[n - 1]$ , de los cuales hay $\left(\!\!{n-1 \choose k}\!\!\right).$

De este modo, $\left(\!\!{n \choose k}\!\!\right)=\left(\!\!{n \choose k-1}\!\!\right)+\left(\!\!{n-1 \choose k}\!\!\right).$

Generando series

La función generadora de los coeficientes de los multiconjuntos es muy sencilla, siendo Como los multiconjuntos están en correspondencia biunívoca con los monomios , es también el número de monomios de grado $d$ en $n$ indeterminados. Por tanto, la serie anterior es también la serie de Hilbert del anillo de polinomios $\sum _{d=0}^{\infty }\left(\!\!{n \choose d}\!\!\right)t^{d}={\frac {1}{(1-t)^{n}}}.$ $\left(\!\!{n \choose d}\!\!\right)$ $k[x_{1},\ldots ,x_{n}].$

Como es un polinomio en $n$ , éste y la función generadora están bien definidos para cualquier valor complejo de $n$ . $\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 multiconjunto reemplazando $n$ por un número arbitrario $α$ (negativo, real o complejo): $\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 establecida en 1), lo que justifica llamar a los coeficientes binomiales negativos: $\left(\!\!{\alpha \choose k}\!\!\right)$ $(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 se cumplen todas las identidades que uno espera para la exponenciación , en particular

$(1-X)^{-\alpha }(1-X)^{-\beta }=(1-X)^{-(\alpha +\beta )}\quad {\text{and}}\quad ((1-X)^{-\alpha })^{-\beta }=(1-X)^{-(-\alpha \beta )},$ y fórmulas como éstas se pueden utilizar para demostrar identidades para los coeficientes del multiconjunto.

Si $α$ es un 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 multiconjuntos tienen varias aplicaciones. ^[7] Se están volviendo fundamentales en la combinatoria . ^[17]^[18]^[19]^[20] 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 bag . ^[21]^[22]^[23] Por ejemplo, los multiconjuntos se utilizan a menudo para implementar relaciones en sistemas de bases de datos. En particular, una tabla (sin una clave principal) funciona como un multiconjunto, porque puede tener múltiples registros idénticos. De manera similar, SQL opera en 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, se muestran todos. 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 dados . Como tal, la entidad que especifica los bordes es un multiconjunto y no un conjunto.

Existen también otras aplicaciones. Por ejemplo, Richard Rado utilizó los multiconjuntos como un dispositivo para investigar las propiedades de las 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 frecuentemente es importante. Sólo necesitamos pensar en el conjunto de raíces de un polinomio f ( x ) o en el espectro de un operador lineal ". ^[5]^{: 328–329}

Generalizaciones

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

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

Véase también

Frecuencia (estadística) como análogo de multiplicidad
Cuasi-conjuntos
Teoría de conjuntos
Modelo de bolsa de palabras
Materiales de aprendizaje relacionados con Particiones de multiconjuntos en Wikiversidad

Notas

^ La fórmula $(.mw-parser-output .RMbox{box-shadow:0 2px 2px 0 rgba(0,0,0,.14),0 1px 5px 0 rgba(0,0,0,.12),0 3px 1px -2px rgba(0,0,0,.2)}.mw-parser-output .RMinline{float:none;width:100%;margin:0;border:none}.mw-parser-output table.routemap{padding:0;border:0;border-collapse:collapse;background:transparent;white-space:nowrap;line-height:1.2;margin:auto}.mw-parser-output table.routemap .RMcollapse{margin:0;border-collapse:collapse;vertical-align:middle}.mw-parser-output table.routemap .RMreplace{margin:0;border-collapse:collapse;vertical-align:middle;position:absolute;bottom:0}.mw-parser-output table.routemap .RMsi{display:inline;font-size:90%}.mw-parser-output table.routemap .RMir{padding:0!important}.mw-parser-output table.routemap .RMl1{padding:0 3px!important;text-align:left}.mw-parser-output table.routemap .RMr1{padding:0 3px!important;text-align:right}.mw-parser-output table.routemap .RMl{padding:0!important;text-align:right}.mw-parser-output table.routemap .RMr{padding:0!important;text-align:left}.mw-parser-output table.routemap .RMl4{padding:0 3px 0 0!important;text-align:left}.mw-parser-output table.routemap .RMr4{padding:0 0 0 3px!important;text-align:right}.mw-parser-output table.routemap>tbody>tr{line-height:1}.mw-parser-output table.routemap>tbody>tr>td,.mw-parser-output table.RMcollapse>tbody>tr>td,.mw-parser-output table.RMreplace>tbody>tr>td{padding:0;width:auto;vertical-align:middle;text-align:center}.mw-parser-output .RMir>div{display:inline-block;vertical-align:middle;padding:0;height:20px;min-height:20px}.mw-parser-output .RMir img{height:initial!important;max-width:initial!important}.mw-parser-output .RMir .RMov{position:relative}.mw-parser-output .RMir .RMov .RMic,.mw-parser-output .RMir .RMov .RMtx{position:absolute;left:0;top:0;padding:0}.mw-parser-output .RMir .RMtx{line-height:20px;height:20px;min-height:20px;vertical-align:middle;text-align:center}.mw-parser-output .RMir .RMsp{height:20px;min-height:20px}.mw-parser-output .RMir .RMtx>abbr,.mw-parser-output .RMir .RMtx>div{line-height:.975;display:inline-block;vertical-align:middle}.mw-parser-output .RMir .RMts{font-size:90%;transform:scaleX(.89)}.mw-parser-output .RMir .RMf_{height:5px;min-height:5px;width:20px;min-width:20px}.mw-parser-output .RMir .RMfm{height:100%;min-height:100%;width:4px;min-width:4px;margin:0 auto}.mw-parser-output .RMir .RMo{width:2.5px;min-width:2.5px}.mw-parser-output .RMir .RMc{width:5px;min-width:5px}.mw-parser-output .RMir .RMoc{width:7.5px;min-width:7.5px}.mw-parser-output .RMir .RMd{width:10px;min-width:10px}.mw-parser-output .RMir .RMod{width:12.5px;min-width:12.5px}.mw-parser-output .RMir .RMcd{width:15px;min-width:15px}.mw-parser-output .RMir .RMocd{width:17.5px;min-width:17.5px}.mw-parser-output .RMir .RM_{width:20px;min-width:20px}.mw-parser-output .RMir .RM_o{width:22.5px;min-width:22.5px}.mw-parser-output .RMir .RM_c{width:25px;min-width:25px}.mw-parser-output .RMir .RM_oc{width:27.5px;min-width:27.5px}.mw-parser-output .RMir .RM_d{width:30px;min-width:30px}.mw-parser-output .RMir .RM_od{width:32.5px;min-width:32.5px}.mw-parser-output .RMir .RM_cd{width:35px;min-width:35px}.mw-parser-output .RMir .RM_ocd{width:37.5px;min-width:37.5px}.mw-parser-output .RMir .RMb{width:40px;min-width:40px}.mw-parser-output .RMir .RMcb{width:45px;min-width:45px}.mw-parser-output .RMir .RMdb{width:50px;min-width:50px}.mw-parser-output .RMir .RMcdb{width:55px;min-width:55px}.mw-parser-output .RMir .RM_b{width:60px;min-width:60px}.mw-parser-output .RMir .RM_cb{width:65px;min-width:65px}.mw-parser-output .RMir .RM_db{width:70px;min-width:70px}.mw-parser-output .RMir .RM_cdb{width:75px;min-width:75px}.mw-parser-output .RMir .RMs{width:80px;min-width:80px}.mw-parser-output .RMir .RMds{width:90px;min-width:90px}.mw-parser-output .RMir .RM_s{width:100px;min-width:100px}.mw-parser-output .RMir .RM_ds{width:110px;min-width:110px}.mw-parser-output .RMir .RMbs{width:120px;min-width:120px}.mw-parser-output .RMir .RMdbs{width:130px;min-width:130px}.mw-parser-output .RMir .RM_bs{width:140px;min-width:140px}.mw-parser-output .RMir .RM_dbs{width:150px;min-width:150px}.mw-parser-output .RMir .RMw{width:160px;min-width:160px}.mw-parser-output .RMir .RM_w{width:180px;min-width:180px}.mw-parser-output .RMir .RMbw{width:200px;min-width:200px}.mw-parser-output .RMir .RM_bw{width:220px;min-width:220px}.mw-parser-output .RMir .RMsw{width:240px;min-width:240px}.mw-parser-output .RMir .RM_sw{width:260px;min-width:260px}.mw-parser-output .RMir .RMbsw{width:280px;min-width:280px}.mw-parser-output .RMir .RM_bsw{width:300px;min-width:300px}.mw-parser-output .RMsplit{font-weight:inherit;color:black;background:transparent;margin-top:-3px;margin-bottom:-3px;width:initial!important;box-sizing:initial;display:inline-table;vertical-align:middle}.mw-parser-output table.routemap .RMl>.RMsplit,.mw-parser-output table.routemap .RMr>.RMsplit{font-size:90%}@media screen{html.skin-theme-clientpref-night .mw-parser-output .RMbox{background:inherit!important;color:white}html.skin-theme-clientpref-night .mw-parser-output .RMbox img{filter:contrast(0.4)}html.skin-theme-clientpref-night .mw-parser-output .navbar-brackets a abbr{color:white!important}html.skin-theme-clientpref-night .mw-parser-output .RMbox th{background:inherit!important;color:inherit!important;border-bottom:solid 1px #be2d2c}html.skin-theme-clientpref-night .mw-parser-output .RMbox small{color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .RMbox img{filter:contrast(0.4)}html.skin-theme-clientpref-os .mw-parser-output .navbar-brackets a abbr{color:white!important}html.skin-theme-clientpref-os .mw-parser-output .RMbox{background:inherit!important;color:white}html.skin-theme-clientpref-os .mw-parser-output .RMbox th{background:inherit!important;color:inherit!important;border-bottom:solid 1px #be2d2c}html.skin-theme-clientpref-os .mw-parser-output .RMbox small{color:white}} )$ no funciona para $n = 0$ (donde necesariamente también $k = 0$ ) si se ve como un coeficiente binomial ordinario ya que evalúa como $( )$ , sin embargo la fórmula $n (n +1)(n +2)...(n + k -1)/ k!$ funciona en este caso porque el numerador es un producto vacío que da $1/0! = 1$ . Sin embargo $( )$ tiene sentido para $n = k = 0$ si se interpreta como un coeficiente binomial generalizado ; de hecho $( )$ visto como un coeficiente binomial generalizado es igual al extremo derecho de la ecuación anterior.

Referencias

^ Cantor, Georg ; Jourdain, Philip EB (Traductor) (1895). "beiträge zur begründung der transfiniten Mengenlehre" [contribuciones a la fundación de la teoría de los números transfinitos]. Mathematische Annalen (en alemán). xlvi, xlix. Publicaciones de Dover de Nueva York (traducción al inglés de 1954): 481–512, 207–246. Archivado desde el original el 10 de junio de 2011. Por conjunto (Menge) debemos entender cualquier colección en un todo (Zusammenfassung zu einem Gansen) M de objetos definidos y separados m (p.85)
^ Hein, James L. (2003). Matemáticas discretas . Jones & Bartlett Publishers. Págs. 29-30. ISBN. 0-7637-2210-3.
^ abc Knuth, Donald E. (1998). Algoritmos seminuméricos . El arte de la programación informática . Vol. 2 (3.ª ed.). Addison Wesley . ISBN 0-201-89684-2.
^ Blizard, Wayne D (1989). "Teoría de conjuntos múltiples". Notre Dame Journal of Formal Logic . 30 (1): 36–66. doi : 10.1305/ndjfl/1093634995 .
^ abcde Blizard, Wayne D. (1991). "El desarrollo de la teoría de conjuntos múltiples". Lógica moderna . 1 (4): 319–352.
^ Rulifson, JF; Derkson, JA; Waldinger, RJ (noviembre de 1972). QA4: Un cálculo procedimental para el razonamiento intuitivo (informe técnico). SRI International. 73.
^ ab Singh, D.; Ibrahim, AM; Yohanna, T.; Singh, JN (2007). "Una visión general de las aplicaciones de los multiconjuntos". Novi Sad Journal of Mathematics . 37 (2): 73–92.
^ Angelelli, I. (1965). "La incomprensión de Leibniz de la noción de 'multitudo' de Nizolius"". Revista de lógica formal de Notre Dame (6): 319–322.
^ Kircher, Atanasio (1650). Musurgia Universalis. Roma: Corbelletti.
^ Prestet, Jean (1675). Elementos de Matemáticas . París: André Pralard.
^ Wallis, John (1685). Un tratado de álgebra . Londres: John Playford.
^ Dedekind, Richard (1888). Was sind und was sollen die Zahlen? . Braunschweig: Vieweg. pag. 114.
^ ab Syropoulos, Apostolos (2000). "Matemáticas de multiconjuntos". En Calude, Cristian; Paun, Gheorghe; Rozenberg, Grzegorz; Salomaa, Arto (eds.). Procesamiento de multiconjuntos, puntos de vista matemáticos, informáticos y de computación molecular [Taller sobre procesamiento de multiconjuntos, WMP 2000, Curtea de Arges, Rumania, 21-25 de agosto de 2000] . Apuntes de clase en informática. Vol. 2235. Springer. págs. 347-358. doi :10.1007/3-540-45523-X_17.
^ Whitney, Hassler (1933). "Funciones características y el álgebra de la lógica". Anales de matemáticas . 34 (3): 405–414. doi :10.2307/1968168. JSTOR 1968168.
^ Monroe, médico de cabecera (1987). "El concepto de multiconjunto". Zeitschrift für Mathematische Logik und Grundlagen der Mathematik . 33 (2): 171-178. doi :10.1002/malq.19870330212.
^ Cf., por ejemplo, Richard Brualdi, Introductory Combinatorics , Pearson.
^ Aigner, M. (1979). Teoría combinatoria . Nueva York/Berlín: Springer Verlag.
^ Anderson, I. (1987). Combinatoria de conjuntos finitos . Oxford: Clarendon Press. ISBN 978-0-19-853367-2.
^ Stanley, Richard P. (1997). Combinatoria enumerativa. Vol. 1. Cambridge University Press. ISBN 0-521-55309-1.
^ Stanley, Richard P. (1999). Combinatoria enumerativa . Vol. 2. Cambridge University Press. ISBN 0-521-56069-1.
^ Grumbach, S.; Milo, T (1996). "Hacia álgebras manejables para bolsas". Revista de Ciencias de la Computación y de Sistemas . 52 (3): 570–588. doi : 10.1006/jcss.1996.0042 .
^ Libkin, L. ; Wong, L. (1994). "Algunas propiedades de los lenguajes de consulta para bolsas". Actas del taller sobre lenguajes de programación de bases de datos . Springer Verlag. págs. 97–114.
^ Libkin, L.; Wong, L. (1995). "Sobre la representación y consulta de información incompleta en bases de datos con bolsas". Information Processing Letters . 56 (4): 209–214. doi :10.1016/0020-0190(95)00154-5.
^ Blizard, Wayne D. (1989). "Multiconjuntos con valores reales y conjuntos difusos". Conjuntos y sistemas difusos . 33 : 77–97. doi :10.1016/0165-0114(89)90218-2.
^ Blizard, Wayne D. (1990). "Membresía negativa". Notre Dame Journal of Formal Logic . 31 (1): 346–368. doi : 10.1305/ndjfl/1093635499 . S2CID 42766971.
^ Yager, RR (1986). "Sobre la teoría de las bolsas". Revista internacional de sistemas generales . 13 : 23–37. doi :10.1080/03081078608934952.
^ Grzymala-Busse, J. (1987). "Aprendizaje a partir de ejemplos basados en multiconjuntos aproximados". Actas del 2º Simposio Internacional sobre Metodologías para Sistemas Inteligentes . Charlotte, Carolina del Norte. págs. 325–332.{{cite book}}: CS1 maint: location missing publisher (link)
^ Loeb, D. (1992). "Conjuntos con un número negativo de elementos". Advances in Mathematics . 91 : 64–74. doi : 10.1016/0001-8708(92)90011-9 .
^ Miyamoto, S. (2001). "Multiconjuntos difusos y sus generalizaciones". Procesamiento de conjuntos múltiples . Apuntes de clase en informática. Vol. 2235. págs. 225-235. doi :10.1007/3-540-45523-X_11. ISBN 978-3-540-43063-6.
^ Alkhazaleh, S.; Salleh, AR; Hassan, N. (2011). "Teoría de multiconjuntos blandos". Applied Mathematical Sciences . 5 (72): 3561–3573.
^ Alkhazaleh, S.; Salleh, AR (2012). "Teoría de multiconjuntos difusos y suaves". Análisis abstracto y aplicado . 2012 : 1–20. doi : 10.1155/2012/350603 .
^ Burgin, Mark (1990). "Teoría de conjuntos nombrados como base fundamental para las matemáticas". Estructuras en teorías matemáticas . San Sebastián. pp. 417–420.
^ Burgin, Mark (1992). "Sobre el concepto de multiconjunto en cibernética". Cibernética y análisis de sistemas . 3 : 165–167.
^ Burgin, Mark (2004). "Fundamentos unificados de las matemáticas". arXiv : math/0403186 .
^ Burgin, Mark (2011). Teoría de conjuntos nombrados . Desarrollos de investigación matemática. Nova Science Pub Inc. ISBN 978-1-61122-788-8.