Мультимножество

В математике , A мультимножеством (или мешок , или MSET ) является модификацией концепции набора , что, в отличие от множества, позволяет несколько экземпляров для каждого из его элементов . Количество экземпляров, заданных для каждого элемента, называется кратностью этого элемента в мультимножестве. Как следствие, существует бесконечное количество мультимножеств, которые содержат только элементы a и b , но различаются по кратности их элементов:

• Набор { a , b } содержит только элементы a и b , каждый из которых имеет кратность 1, когда { a , b } рассматривается как мультимножество.
• В мультимножестве { a , a , b } элемент a имеет кратность 2, а элемент b имеет кратность 1.
• В мультимножестве { a , a , a , b , b , b } , a и b оба имеют кратность 3.

Все эти объекты различны, если рассматривать их как мультимножества, хотя они являются одним и тем же набором , поскольку все они состоят из одних и тех же элементов. Как и в случае с наборами, и в отличие от кортежей , порядок не имеет значения при различении мультимножеств, поэтому { a , a , b } и { a , b , a } обозначают одно и то же мультимножество. Чтобы различать наборы и мультимножества, иногда используется нотация, включающая квадратные скобки: мультимножество { a , a , b } может быть обозначено как [ a ,а , б ] . ^[1]

Мощность из мультимножества строится путем суммирования кратностей всех его элементов. Например, в мультимножестве { a , a , b , b , b , c } кратности членов a , b и c равны соответственно 2, 3 и 1, и поэтому мощность этого мультимножества равна 6.

По словам Дональда Кнута, Николаас Говерт де Брёйн придумал слово « мультимножество» в 1970-х годах . ^{[2] : 694} Однако использование концепции мультимножества возникло на много веков раньше, чем слово « мультимножество ». Сам Кнут приписывает первое исследование мультимножеств индийскому математику Бхаскарачарье , который описал перестановки мультимножеств около 1150 года. Для этой концепции были предложены или использованы другие названия, в том числе список , группа , сумка , куча , образец , взвешенное множество , коллекция, и люкс . ^{[2] : 694}

История [ править ]

Уэйн Близард проследил мультимножества до самого происхождения чисел, утверждая, что «в древние времена число n часто представлялось набором из n штрихов, счетных отметок или единиц». ^[3] Эти и подобные коллекции объектов являются мультимножествами, потому что штрихи, метки подсчета или единицы считаются неразличимыми. Это показывает, что люди неявно использовали мультимножества еще до появления математики.

Практические потребности в этой структуре привели к тому, что мультимножества переоткрывались несколько раз, появляясь в литературе под разными именами. ^{[4] : 323} Например, они были важны в ранних языках искусственного интеллекта, таких как QA4, где их называли мешками - термин, приписываемый Питеру Дойчу. ^[5] Мультимножество также называют агрегатом, кучей, связкой, выборкой, взвешенным набором, набором вхождений и набором огней (набор элементов с конечным числом повторений). ^{[4] : 320 [6]}

Хотя мультимножества неявно использовались с древних времен, их явное исследование произошло намного позже. Первое известное исследование мультимножеств приписывается индийскому математику Бхаскарачарье около 1150 года, который описал перестановки мультимножеств. ^{[2] : 694} Работа Мариуса Низолиуса (1498–1576) содержит еще одно раннее упоминание концепции мультимножеств. ^[7] Афанасиус Кирхер обнаружил количество перестановок мультимножества, когда один элемент может повторяться. ^[8] Жан Престе опубликовал общее правило для перестановок мультимножеств в 1675 году. ^[9] Джон Уоллис более подробно объяснил это правило в 1685 году. ^[10]

Мультимножества явно появились в работе Ричарда Дедекинда . ^{[11] : 114 [12]}

Другие математики формализовали мультимножества и начали изучать их как точные математические структуры в 20 веке. Например, Уитни (1933) описал обобщенные множества («множества», характеристические функции которых могут принимать любое целочисленное значение - положительное, отрицательное или нулевое). ^{[4] : 326 [13] : 405} Монро (1987) исследовал категорию Mul мультимножеств и их морфизмы, определяя мультимножество как множество с отношением эквивалентности между элементами «одного вида » и морфизм между мультимножествами как функция, которая уважает сортировки. Он также ввел мультичисло : функцию f ( x ) из мультимножества в натуральные числа , задающую кратность элемента x в мультимножестве. Монро утверждал, что концепции мультимножества и нескольких номеров часто смешиваются без разбора, хотя оба они полезны. ^{[4] : 327–328 [14]}

Примеры [ править ]

Один из простейших и наиболее естественных примеров - это мультимножество простых множителей натурального числа n . Здесь основной набор элементов - это набор простых делителей n . Например, число 120 имеет разложение на простые множители

${\ displaystyle 120 = 2 ^ {3} 3 ^ {1} 5 ^ {1}}$

что дает мультимножество {2, 2, 2, 3, 5} .

Связанный пример - мультимножество решений алгебраического уравнения. Например, квадратное уравнение имеет два решения. Однако в некоторых случаях это одно и то же число. Таким образом, мультимножество решений уравнения может быть {3, 5} или {4, 4} . В последнем случае оно имеет решение кратности 2. В более общем плане основная теорема алгебры утверждает, что комплексные решения полиномиального уравнения степени d всегда образуют мультимножество мощности d .

Особый случай выше являются собственными значениями матрицы А матриц , кратность которого обычно определяются как их кратность как корни характеристического полинома . Однако две другие кратности естественным образом определены для собственных значений, их кратности как корней минимального полинома , и геометрической кратности , который определяется как размерность этого ядра из А - & lambda ; i (где λ является собственным значением матрицы А ). Эти три кратности определяют три мультимножества собственных значений, которые могут быть разными: пусть A будетМатрица размера n  ×  n в жордановой нормальной форме , имеющая одно собственное значение. Его кратность равна n , его кратность как корня минимального многочлена равна размеру наибольшей жордановой клетки, а ее геометрическая кратность - это количество жордановых блоков.

Определение [ править ]

Мультимножество может быть формально определенно как 2- кортеж ( , м ) , где является основным набором из мультимножества, сформированное из его отдельных элементов, и является функцией от А к набору из положительных целых чисел , давая кратность , то есть количество вхождений элемента a в мультимножество как число m ( a ) .${\ displaystyle m \ двоеточие A \ to \ mathbb {Z} ^ {+}}$

Представление функции m ее графиком (набором упорядоченных пар ) позволяет записать мультимножество { a , a , b } как ({ a , b }, {( a , 2), ( b , 1)}) и мультимножество { a , b } как ({ a , b }, {( a , 1), ( b , 1)}) . Однако это обозначение обычно не используется, и используются более компактные обозначения.${\ Displaystyle \ влево \ {\ влево (а, м \ влево (а \ вправо) \ вправо): а \ в А \ вправо \}}$

Если - конечное множество , мультимножество ( A , m ) часто представляется как ${\ Displaystyle А = \ {а_ {1}, \ ldots, а_ {п} \}}$

${\ displaystyle \ left \ {a_ {1} ^ {m (a_ {1})}, \ ldots, a_ {n} ^ {m (a_ {n})} \ right \}, \ quad}$ иногда упрощается до ${\ displaystyle \ quad a_ {1} ^ {m (a_ {1})} \ cdots a_ {n} ^ {m (a_ {n})},}$

где опущены верхние индексы, равные 1. Например, мультимножество { a , a , b } может быть записано или Если элементы мультимножества являются числами, возможна путаница с обычными арифметическими операциями , которые обычно могут быть исключены из контекста. С другой стороны, последнее обозначение согласуется с тем фактом, что факторизация положительного целого числа на простые множители является однозначно определенным мультимножеством, как утверждается в основной теореме арифметики . Кроме того, одночлен - это мультимножество неопределенных ; например, моном x ³ y ²${\displaystyle \{a^{2},b\}}$${\displaystyle a^{2}b.}$соответствует мультимножеству { x , x , x , y , y }.

Мультимножество соответствует обычному набору, если кратность каждого элемента равна единице (в отличие от некоторого большего положительного целого числа). Индексированное семейство , ( _я ) _{я ∈ I} , где я изменяется по некоторому индексу множество I , может определить мультимножество, иногда написанный { а _I } . В этом представлении базовый набор мультимножества задается изображением семейства, а кратность любого элемента x - это количество значений индекса i, таких что${\displaystyle a_{i}=x}$. В этой статье кратности считаются конечными, т.е. ни один элемент не встречается в семействе бесконечно много раз: даже в бесконечном мультимножестве кратности являются конечными числами.

Можно расширить определение мультимножества, разрешив множественности отдельных элементов быть бесконечными кардиналами вместо положительных целых чисел, но не все свойства переносятся в это обобщение.

Основные свойства и операции [ править ]

Элементы мультимножества обычно берутся в фиксированном наборе U , иногда называемом вселенной , который часто является набором натуральных чисел . Говорят, что элемент U , не принадлежащий данному мультимножеству, имеет кратность 0 в этом мультимножестве. Это расширяет функцию кратности мультимножестве в зависимости от U до множества из неотрицательных целых чисел . Это определяет взаимно-однозначное соответствие между этими функциями и мультимножествами , которые имеют свои элементы в U .${\displaystyle \mathbb {N} }$

Эта расширенная функция кратности обычно называется просто функцией кратности , и ее достаточно для определения мультимножеств, когда юниверс, содержащий элементы, был исправлен. Эта функция кратности является обобщением индикаторной функции подмножества и имеет с ней некоторые общие свойства.

Поддержка из мультимножестве во вселенной U является основным набором мультимножества. Используя функцию кратности , он характеризуется как ${\displaystyle A}$${\displaystyle m}$

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

Мультимножество конечно, если его носитель конечен или, что то же самое, если его мощность

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

конечно. Пустым мультимножеством является уникальным мультимножеством с пустым носителем (основной набор), и , следовательно, мощность 0.

Обычные операции над наборами могут быть расширены до мультимножеств с помощью функции кратности, аналогично использованию функции индикатора для подмножеств. Далее A и B - мультимножества в данной вселенной U с функциями кратности и${\displaystyle m_{A}}$${\displaystyle m_{B}.}$

• Включение: A входит в B , обозначается A ⊆ B , если

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

• Пересечение: пересечение ( так называемое, в некоторых контекстах инфимум или наибольший общий делитель ) из A и B является мультимножеством С с функцией кратности

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

• Союз: союз ( так называемый, в некоторых контекстах максимальных или наименьшее общее кратное ) из A и B является мультимножеством С с функцией кратности

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

• Сумма: сумму мультимножеств можно рассматривать как обобщение дизъюнктного объединения множеств, и она определяется как мультимножество C с функцией кратности

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

Сумма определяет коммутативную структуру моноида на конечных мультимножествах в данной вселенной. Этот моноид является свободным коммутативным моноидом , в основе которого лежит Вселенная.

Два мультимножества не пересекаются, если их носители являются непересекающимися множествами . Это эквивалентно тому, что их пересечение является пустым мультимножеством или что их сумма равна их объединению.

Для конечных мультимножеств существует принцип включения-исключения (аналогичный принципу для множеств), гласящий, что конечное объединение конечных мультимножеств - это разность двух сумм мультимножеств: в первой сумме мы рассматриваем все возможные пересечения нечетного числа данных мультимножеств, а во второй сумме мы рассматриваем все возможные пересечения четного числа данных мультимножеств. ^{[ необходима цитата ]}

Подсчет мультимножеств [ править ]

Взаимодействие между 3-подмножествами 7-множества (слева)
и 3-мультимножествами с элементами из 5-набора (справа)
Это иллюстрирует это .${\displaystyle \textstyle {7 \choose 3}=\left(\!\!{5 \choose 3}\!\!\right)}$

Количество мультимножеств мощности k с элементами, взятыми из конечного набора мощности n , называется коэффициентом мультимножества или числом мультимножества . Это число пишется некоторыми авторами как обозначение, которое должно напоминать обозначение биномиальных коэффициентов ; он используется, например, в (Stanley, 1997) и может произноситься как « n multichoose k », чтобы напоминать « n choose k » для . В отличие от биномиальных коэффициентов, не существует «теоремы о мультимножестве», в которой коэффициенты мультимножества встречались бы, и их не следует путать с несвязанными полиномиальными коэффициентами.${\displaystyle \textstyle \left(\!\!{n \choose k}\!\!\right)}$${\displaystyle {\tbinom {n}{k}}}$которые входят в полиномиальную теорему .

Значение коэффициентов мультимножества может быть явно задано как

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

где второе выражение представляет собой биномиальный коэффициент; на самом деле многие авторы избегают отдельных обозначений и просто пишут биномиальные коэффициенты. Таким образом, количество таких мультимножеств равно количеству подмножеств мощности k в наборе мощности n + k - 1 . Аналогию с биномиальными коэффициентами можно подчеркнуть, записав числитель в приведенном выше выражении как возрастающую факторную степень

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

чтобы соответствовать выражению биномиальных коэффициентов, используя падающую факторную мощность:

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

Например, есть 4 мультимножества мощности 3 с элементами, взятыми из множества {1, 2} мощности 2 ( n = 2 , k = 3 ), а именно {1, 1, 1} , {1, 1, 2} , {1, 2, 2} , {2, 2, 2} . Также есть 4 подмножества мощности 3 в наборе {1, 2, 3, 4} мощности 4 ( n + k - 1 ), а именно {1, 2, 3} , {1, 2, 4} , {1 , 3, 4} , {2, 3, 4} .

Один простой способ доказать равенство коэффициентов мультимножества и биномиальных коэффициентов, приведенных выше, включает представление мультимножеств следующим образом. Сначала рассмотрим обозначения мультимножеств, которые будут представлять { a , a , a , a , a , a , b , b , c , c , c , d , d , d , d , d , d , d } (6 a с, 2 б с, 3c s, 7 d s) в таком виде:

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

Это мультимножество мощности k = 18, состоящее из элементов набора мощности n = 4. Количество символов, включая точки и вертикальные линии, используемых в этой нотации, составляет 18 + 4 - 1. Количество вертикальных линий равно 4 - 1. Количество мультимножеств мощности 18 - это количество способов расположить 4-1 вертикальные линии среди 18 + 4-1 символов, и, таким образом, количество подмножеств мощности 4-1 в наборе мощности 18. + 4 - 1. Точно так же это количество способов расположить 18 точек среди 18 + 4 - 1 символов, которое является количеством подмножеств мощности 18 в наборе мощности 18 + 4 - 1. Это

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

таким образом, значение коэффициента мультимножества и его эквивалентов:

${\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}}.}$

Можно определить обобщенный биномиальный коэффициент

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

в котором n не обязательно должно быть неотрицательным целым числом, но может быть отрицательным, нецелым или не действительным комплексным числом . (Если k  = 0, то значение этого коэффициента равно 1, потому что это пустое произведение .) Тогда количество мультимножеств мощности k в наборе мощности n равно

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

Отношение повторения [ править ]

Рекуррентное соотношение для коэффициентов мультимножеств может быть задано как

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

с участием

${\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.}$

Вышеуказанное повторение можно интерпретировать следующим образом. Пусть [ n ]  : =  будет исходным набором. Всегда существует ровно одно (пустое) мультимножество размера 0, а если n  = 0 , нет мультимножеств большего размера, что дает начальные условия.${\displaystyle \{1,\dots ,n\}}$

Теперь рассмотрим случай, когда n , k  > 0 . Мультимножество мощности k с элементами из [ n ] может содержать или не содержать ни одного экземпляра последнего элемента n . Если он действительно появляется, то при удалении n один раз остается мультимножество мощности k  - 1 элементов из [ n ] , и каждое такое мультимножество может возникнуть, что в сумме дает

${\displaystyle \left(\!\!{n \choose k-1}\!\!\right)}$ возможности.

Если n не появляется, то наше исходное мультимножество равно мультимножеству мощности k с элементами из [ n  - 1] , из которых есть

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

Таким образом,

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

Создание серии [ править ]

Производящая функция из мультимножеств коэффициентов очень просто, будучи

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

Как мультимножества находятся во взаимно-однозначном соответствии с мономами, также число одночленов степени г в п неизвестный. Таким образом, этот ряд также ряд Гильберта в кольце многочленов${\displaystyle \left(\!\!{n \choose d}\!\!\right)}$ ${\displaystyle k[x_{1},\ldots ,x_{n}].}$

Как и многочлен от n , он определен для любого комплексного значения n .${\displaystyle \left(\!\!{n \choose d}\!\!\right)}$

Обобщение и связь с отрицательным биномиальным рядом [ править ]

Мультипликативная формула позволяет расширить определение коэффициентов мультимножества, заменив n произвольным числом α (отрицательным, действительным, комплексным):

${\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 .}$

С помощью этого определения можно получить обобщение формулы отрицательного бинома (с одной из переменных, установленной на 1), что оправдывает вызов отрицательных биномиальных коэффициентов:${\displaystyle \left(\!\!{\alpha \choose k}\!\!\right)}$

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

Эта формула ряда Тейлора верна для всех комплексных чисел α и X с | X | <1. Его также можно интерпретировать как тождество формального степенного ряда в X , где он фактически может служить определением произвольных степеней ряда с постоянным коэффициентом, равным 1; Дело в том, что с этим определением сохраняются все тождества, которых можно ожидать от возведения в степень , особенно

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

и формулы, подобные этим, можно использовать для доказательства тождеств для коэффициентов мультимножества.

Если α - неположительное целое число n , то все члены с k  > - n равны нулю, и бесконечный ряд становится конечной суммой. Однако для других значений α , включая положительные целые и рациональные числа , ряд бесконечен.

Приложения [ править ]

Мультимножества имеют различные применения. ^[6] Они становятся фундаментальными в комбинаторике . ^{[16] [17] [18] [19]} Мультимножества стали важным инструментом в теории реляционных баз данных , которая часто использует мешок синонимов . ^{[20] [21] [22]} Например, мультимножества часто используются для реализации отношений в системах баз данных. В частности, таблица (без первичного ключа) работает как мультимножество, поскольку может иметь несколько идентичных записей. Точно так же SQLработает с мультимножествами и возвращает идентичные записи. Например, рассмотрим «ВЫБРАТЬ имя от студента». В случае, если в таблице учеников есть несколько записей с именем «sara», отображаются все они. Это означает, что результирующий набор SQL является мультимножеством. Если это был набор, повторяющиеся записи в наборе результатов удалялись. Еще одно применение мультимножества - моделирование мультиграфов . В мультиграфах между любыми двумя заданными вершинами может быть несколько ребер. Таким образом, объект, который показывает ребра, является мультимножеством, а не набором.

Есть и другие приложения. Например, Ричард Радо использовал мультимножества как устройство для исследования свойств семейств наборов. Он писал: «Понятие множества не принимает во внимание многократное вхождение любого из его членов, и все же именно такого рода информация часто имеет значение. Нам нужно только подумать о множестве корней многочлена f. ( x ) или спектр линейного оператора ». ^{[4] : 328–329}

Обобщения [ править ]

Были введены, изучены и применены к решению задач различные обобщения мультимножеств.

• Действительные мультимножества (в которых кратность элемента может быть любым действительным числом) ^{[23] [24]}

Это кажется простым, поскольку многие определения для нечетких множеств и мультимножеств очень похожи и могут использоваться для мультимножеств с действительными значениями, просто заменив диапазон значений характеристической функции ([0, 1] или ℕ = {0, 1, 2 , 3, ...} соответственно) на ℝ ₀ ⁺ = [0, ∞). Однако этот подход не может быть легко расширен для обобщенных нечетких множеств, в которых вместо простой степени принадлежности используется ЧУМ или решетка . Было разработано несколько других подходов к нечетким мультимножествам, которые не имеют этого ограничения.

• Нечеткие мультимножества ^[25]
• Грубые мультимножества ^[26]
• Гибридные наборы ^[27]
• Мультимножества, кратность которых представляет собой любую действительную ступенчатую функцию ^[28]
• Мягкие мультимножества ^[29]
• Мягкие нечеткие мультимножества ^[30]
• Именованные множества (объединение всех обобщений множеств) ^{[31] [32] [33] [34]}

См. Также [ править ]

• Частота (статистика) как аналог кратности
• Квази-множества
• Теория множеств
• Учебные материалы по разделам мультимножеств в Викиверситете

Ссылки [ править ]