В математике , 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 , a , b ] . [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 имеет разложение на простые множители
что дает мультимножество {2, 2, 2, 3, 5} .
Связанный пример - мультимножество решений алгебраического уравнения. Например, квадратное уравнение имеет два решения. Однако в некоторых случаях это одно и то же число. Таким образом, мультимножество решений уравнения может быть {3, 5} или {4, 4} . В последнем случае оно имеет решение кратности 2. В более общем плане основная теорема алгебры утверждает, что комплексные решения полиномиального уравнения степени d всегда образуют мультимножество мощности d .
Особый случай выше являются собственными значениями матрицы А матриц , кратность которого обычно определяются как их кратность как корни характеристического полинома . Однако две другие кратности естественным образом определены для собственных значений, их кратности как корней минимального полинома , и геометрической кратности , который определяется как размерность этого ядра из А - & lambda ; i (где λ является собственным значением матрицы А ). Эти три кратности определяют три мультимножества собственных значений, которые могут быть разными: Пусть A - матрица размера n × n в жордановой нормальной форме , имеющая единственное собственное значение. Его кратность равна n , его кратность как корня минимального многочлена равна размеру наибольшей жордановой клетки, а ее геометрическая кратность - это количество жордановых блоков.
Определение
Мультимножество может быть формально определенно как 2- кортеж ( А , м ) , где является основным набором из мультимножества, сформированное из его отдельных элементов, ипредставляет собой функцию от A до набора положительных целых чисел , задающую кратность , то есть количество вхождений элемента a в мультимножество как число m ( a ) .
Представляя функцию m ее графиком (множество упорядоченных пар ) позволяет записать мультимножество { a , a , b } как ({ a , b }, {( a , 2), ( b , 1)}) , а мультимножество { a , b } как ({ a , b }, {( a , 1), ( b , 1)}) . Однако это обозначение обычно не используется, и используются более компактные обозначения.
Если - конечное множество , мультимножество ( A , m ) часто представляется в виде
- иногда упрощается до
где опущены верхние индексы, равные 1. Например, мультимножество { a , a , b } может быть записано или же Если элементами мультимножества являются числа, возможна путаница с обычными арифметическими операциями , которые обычно можно исключить из контекста. С другой стороны, последнее обозначение согласуется с тем фактом, что факторизация положительного целого числа на простые множители является однозначно определенным мультимножеством, как утверждается в основной теореме арифметики . Кроме того, одночлен - это мультимножество неопределенных ; например, моном x 3 y 2 соответствует мультимножеству { x , x , x , y , y }.
Мультимножество соответствует обычному набору, если кратность каждого элемента равна единице (в отличие от некоторого большего положительного целого числа). Индексированное семейство , ( я ) я ∈ I , где я изменяется по некоторому индексу множество I , может определить мультимножество, иногда написанный { а I } . В этом представлении базовый набор мультимножества задается изображением семейства, а кратность любого элемента x - это количество значений индекса i, таких что. В этой статье кратности считаются конечными, т.е. ни один элемент не встречается в семействе бесконечно много раз: даже в бесконечном мультимножестве кратности являются конечными числами.
Можно расширить определение мультимножества, разрешив множественности отдельных элементов быть бесконечными кардиналами вместо положительных целых чисел, но не все свойства переносятся в это обобщение.
Основные свойства и операции
Элементы мультимножества обычно берутся в фиксированном наборе U , иногда называемом вселенной , который часто является набором натуральных чисел . Говорят, что элемент U , не принадлежащий данному мультимножеству, имеет кратность 0 в этом мультимножестве. Это расширяет функцию кратности мультимножества до функции от U до множестваиз неотрицательных целых чисел . Это определяет взаимно-однозначное соответствие между этими функциями и мультимножествами , которые имеют свои элементы в U .
Эта расширенная функция кратности обычно называется просто функцией кратности , и ее достаточно для определения мультимножеств, когда юниверс, содержащий элементы, был исправлен. Эта функция кратности является обобщением индикаторной функции подмножества и имеет с ней некоторые общие свойства.
Поддержка из мультимножествяво вселенной U - это базовый набор мультимножества. Использование функции кратности, он характеризуется как
- .
Мультимножество конечно, если его носитель конечен или, что то же самое, если его мощность
конечно. Пустым мультимножеством является уникальным мультимножеством с пустым носителем (основной набор), и , следовательно, мощность 0.
Обычные операции над наборами могут быть расширены до мультимножеств с помощью функции кратности, аналогично использованию функции индикатора для подмножеств. Далее A и B - мультимножества в данной вселенной U с функциями кратности а также
- Включение: A входит в B , обозначается A ⊆ B , если
- Пересечение: пересечение ( так называемое, в некоторых контекстах инфимум или наибольший общий делитель ) из A и B является мультимножеством С с функцией кратности
- Союз: союз ( так называемый, в некоторых контекстах максимальных или наименьшее общее кратное ) от А и В является мультимножеством С с функцией кратности
- [15]
- Сумма: сумму мультимножеств можно рассматривать как обобщение дизъюнктного объединения множеств, и она определяется как мультимножество C с функцией кратности
- Сумма определяет коммутативную структуру моноида на конечных мультимножествах в данной вселенной. Этот моноид является свободным коммутативным моноидом , в основе которого лежит Вселенная.
Два мультимножества не пересекаются, если их носители являются непересекающимися множествами . Это эквивалентно тому, что их пересечение является пустым мультимножеством или что их сумма равна их объединению.
Для конечных мультимножеств существует принцип включения-исключения (аналогичный принципу для множеств), гласящий, что конечное объединение конечных мультимножеств - это разность двух сумм мультимножеств: в первой сумме мы рассматриваем все возможные пересечения нечетного числа данных мультимножеств, а во второй сумме мы рассматриваем все возможные пересечения четного числа данных мультимножеств. [ необходима цитата ]
Подсчет мультимножеств
Количество мультимножеств мощности k с элементами, взятыми из конечного набора мощности n , называется коэффициентом мультимножества или числом мультимножества . Это число записывается некоторыми авторами как, обозначение, которое должно напоминать обозначение биномиальных коэффициентов ; он используется, например, в (Stanley, 1997) и может произноситься как « n multichoose k », чтобы напоминать « n choose k » для. В отличие от биномиальных коэффициентов, не существует «теоремы о мультимножестве», в которой коэффициенты мультимножества встречались бы, и их не следует путать с несвязанными полиномиальными коэффициентами, которые встречаются в теореме о полиномах .
Значение коэффициентов мультимножества может быть явно задано как
где второе выражение представляет собой биномиальный коэффициент; на самом деле многие авторы избегают отдельных обозначений и просто пишут биномиальные коэффициенты. Таким образом, количество таких мультимножеств равно количеству подмножеств мощности k в наборе мощности n + k - 1 . Аналогию с биномиальными коэффициентами можно подчеркнуть, записав числитель в приведенном выше выражении как возрастающую факторную степень
чтобы соответствовать выражению биномиальных коэффициентов, используя падающую факторную мощность:
Например, есть 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 s, 2 b s, 3 c 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. Это
таким образом, значение коэффициента мультимножества и его эквивалентов:
Можно определить обобщенный биномиальный коэффициент
в котором n не обязательно должно быть неотрицательным целым числом, но может быть отрицательным, нецелым или не действительным комплексным числом . (Если k = 0, то значение этого коэффициента равно 1, потому что это пустое произведение .) Тогда количество мультимножеств мощности k в наборе мощности n равно
Отношение повторения
Рекуррентное соотношение для коэффициентов мультимножеств может быть задано как
с участием
Вышеуказанное повторение можно интерпретировать следующим образом. Пусть [ n ] : = быть исходным набором. Всегда существует ровно одно (пустое) мультимножество размера 0, а если n = 0 , нет мультимножеств большего размера, что дает начальные условия.
Теперь рассмотрим случай, когда n , k > 0 . Мультимножество мощности k с элементами из [ n ] может содержать или не содержать ни одного экземпляра последнего элемента n . Если он действительно появляется, то при удалении n один раз остается мультимножество мощности k - 1 элементов из [ n ] , и каждое такое мультимножество может возникнуть, что в сумме дает
- возможности.
Если n не появляется, то наше исходное мультимножество равно мультимножеству мощности k с элементами из [ n - 1] , из которых есть
Таким образом,
Генерация серии
Производящая функция из мультимножеств коэффициентов очень просто, будучи
Поскольку мультимножества находятся во взаимно однозначном соответствии с одночленами, Также число одночленов степени г в п неизвестных. Таким образом, этот ряд также ряд Гильберта в кольце многочленов
В виде является многочленом от n , он определен для любого комплексного значения n .
Обобщение и связь с отрицательным биномиальным рядом
Мультипликативная формула позволяет расширить определение коэффициентов мультимножества, заменив n произвольным числом α (отрицательным, действительным, комплексным):
С помощью этого определения можно получить обобщение формулы отрицательного бинома (с одной из переменных, установленной на 1), что оправдывает вызов отрицательные биномиальные коэффициенты:
Эта формула ряда Тейлора верна для всех комплексных чисел α и X с | X | <1. Его также можно интерпретировать как тождество формального степенного ряда в X , где он фактически может служить определением произвольных степеней ряда с постоянным коэффициентом, равным 1; Дело в том, что с этим определением сохраняются все тождества, которых можно ожидать от возведения в степень , особенно
- ,
и формулы, подобные этим, можно использовать для доказательства тождеств для коэффициентов мультимножества.
Если α - неположительное целое число 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 + = [0, ∞). Однако этот подход не может быть легко расширен для обобщенных нечетких множеств, в которых вместо простой степени принадлежности используется ЧУМ или решетка . Было разработано несколько других подходов к нечетким мультимножествам, которые не имеют этого ограничения.
- Нечеткие мультимножества [25]
- Грубые мультимножества [26]
- Гибридные наборы [27]
- Мультимножества, кратность которых представляет собой любую действительную ступенчатую функцию [28]
- Мягкие мультимножества [29]
- Мягкие нечеткие мультимножества [30]
- Именованные множества (объединение всех обобщений множеств) [31] [32] [33] [34]
Смотрите также
- Частота (статистика) как аналог кратности
- Квази-множества
- Теория множеств
- Учебные материалы по разделам мультимножеств в Викиверситете
Рекомендации
- ^ Хайн, Джеймс Л. (2003). Дискретная математика . Издательство "Джонс и Бартлетт". стр. 29 -30. ISBN 0-7637-2210-3.
- ^ а б в Кнут, Дональд Э. (1998). Получисловые алгоритмы . Искусство программирования . 2 (3-е изд.). Эддисон Уэсли . ISBN 0-201-89684-2.
- ^ Близард, Уэйн Д. (1989). «Теория мультимножеств» . Журнал формальной логики Нотр-Дам . 30 (1): 36–66. DOI : 10.1305 / ndjfl / 1093634995 .
- ^ а б в г д Близард, Уэйн Д. (1991). «Развитие теории мультимножеств» . Современная логика . 1 (4): 319–352.
- ^ Rulifson, JF; Derkson, JA; Waldinger, RJ (ноябрь 1972 г.). QA4: Процедурное исчисление для интуитивного мышления (технический отчет). SRI International. 73.
- ^ а б Singh, D .; Ибрагим, AM; Йоханна, Т .; Сингх, Дж. Н. (2007). «Обзор приложений мультимножеств». Нови-Садский математический журнал . 37 (2): 73–92.
- ^ Анджелелли, И. (1965). «Непонимание Лейбницем понятия Низолия о« множественности » ». Журнал формальной логики Нотр-Дам (6): 319–322.
- ^ Кирхер, Афанасий (1650 г.). Musurgia Universalis . Рим: Корбеллетти.
- ^ Престе, Жан (1675). Elemens des Mathematiques . Париж: Андре Пралар.
- ^ Уоллис, Джон (1685). Трактат по алгебре . Лондон: Джон Плейфорд.
- ^ Дедекинд, Ричард (1888). Was sind und was sollen die Zahlen? . Брауншвейг: Vieweg.
- ^ Сиропулос, Апостолос (2001). «Математика мультимножеств». В Калуде, CS; и другие. (ред.). Обработка нескольких наборов: точки зрения математики, информатики и молекулярных вычислений . Springer-Verlag. С. 347–358.
- ^ Уитни, Х. (1933). «Характеристические функции и алгебра логики». Анналы математики . 34 : 405–414. DOI : 10.2307 / 1968168 .
- ^ Монро, ГП (1987). «Концепция мультимножества». Zeitschrift für Mathematische Logik und Grundlagen der Mathematik . 33 : 171–178. DOI : 10.1002 / malq.19870330212 .
- ^ Сиропулос, Апостолос (2000). «Математика мультимножеств» . Конспект лекций по информатике . 2235 : 347-358. DOI : 10.1007 / 3-540-45523-X_17 . Проверено 16 февраля 2021 года .
- ^ Айгнер, М. (1979). Комбинаторная теория . Нью-Йорк / Берлин: Springer Verlag.
- ^ Андерсон, И. (1987). Комбинаторика конечных множеств . Оксфорд: Clarendon Press.
- ^ Стэнли, Ричард П. (1997). Перечислительная комбинаторика . 1 . Издательство Кембриджского университета. ISBN 0-521-55309-1.
- ^ Стэнли, Ричард П. (1999). Перечислительная комбинаторика . 2 . Издательство Кембриджского университета. ISBN 0-521-56069-1.
- ^ Grumbach, S .; Майло, Т. (1996). «К сговорчивым алгебрам сумок». Журнал компьютерных и системных наук . 52 (3): 570–588. DOI : 10.1006 / jcss.1996.0042 .
- ^ Либкин, Л .; Вонг, Л. (1994). «Некоторые свойства языков запросов для сумок». Материалы семинара по языкам программирования баз данных . Springer Verlag. С. 97–114.
- ^ Либкин, Л .; Вонг, Л. (1995). «О представлении и запросе неполной информации в базах данных с мешками». Письма об обработке информации . 56 (4): 209–214. DOI : 10.1016 / 0020-0190 (95) 00154-5 .
- ^ Близард, Уэйн Д. (1989). «Реальные мультимножества и нечеткие множества». Нечеткие множества и системы . 33 : 77–97. DOI : 10.1016 / 0165-0114 (89) 90218-2 .
- ^ Близард, Уэйн Д. (1990). «Отрицательное членство». Журнал формальной логики Нотр-Дам . 31 (1): 346–368.
- ^ Ягер, Р.Р. (1986). «К теории сумок». Международный журнал общих систем . 13 : 23–37. DOI : 10.1080 / 03081078608934952 .
- ^ Grzymala-Busse, J. (1987). «Учимся на примерах на грубых мультимножествах». Материалы 2-го Международного симпозиума по методологиям интеллектуальных систем . Шарлотта, Северная Каролина. С. 325–332.
- ^ Лоеб, Д. (1992). «Наборы с отрицательным числом элементов» . Успехи в математике . 91 : 64–74. DOI : 10.1016 / 0001-8708 (92) 90011-9 .
- ^ Миямото, С. (2001). «Нечеткие мультимножества и их обобщения». Обработка мультимножества . 2235 : 225–235.
- ^ Alkhazaleh, S .; Салле, штат Арканзас; Хасан, Н. (2011). "Теория мягких мультимножеств". Прикладные математические науки . 5 (72): 3561–3573.
- ^ Alkhazaleh, S .; Салле, АР (2012). "Нечеткая теория мягких мультимножеств". Аннотация и прикладной анализ .
- ^ Бургин, Марк (1990). «Теория именованных множеств как основа математики» . Структуры в математических теориях . Сан-Себастьян. С. 417–420.
- ^ Бургин, Марк (1992). «О концепции мультимножества в кибернетике». Кибернетика и системный анализ . 3 : 165–167.
- ^ Бургин, Марк (2004). «Единые основы математики». arXiv : math / 0403186 .
- ^ Бургин, Марк (2011). Теория именованных множеств . Развитие математических исследований. Nova Science Pub Inc. ISBN 978-1-61122-788-8.