Введение
Математическое понятие
Математическое множество с допустимыми повторениями
В математике, мультимножество (или мешок, или mset) является модификацией понятия множества, которое, в отличие от множества, допускает множественные экземпляры для каждого из его элементов. Количество экземпляров, заданное для каждого элемента, называется кратностью этого элемента в мультимножестве. Как следствие, существует бесконечное число мультимножеств, которые содержат только элементы a и b, но различаются кратностью их элементов: множество содержит только элементы a и b, каждый из которых имеет кратность 1, если рассматривать его как мультимножество. В мультимножестве элемент a имеет кратность 2, а элемент b — кратность 1. В мультимножестве a и b оба имеют кратность 3. Эти объекты все различны, если рассматривать их как мультимножества, хотя они являются одним и тем же множеством, поскольку все они состоят из одних и тех же элементов. Как и в случае множеств, и в отличие от кортежей, порядок, в котором перечислены элементы, не имеет значения для различения мультимножеств, поэтому [a, a, b] и [a, b, a] обозначают одно и то же мультимножество. Для различения множеств и мультимножеств иногда используется обозначение с квадратными скобками: мультимножество [a, a, b] может быть обозначено как [a, a, b]. Кардинальность мультимножества — это сумма кратностей всех его элементов. Например, в мультимножестве [a, a, b, b, b, c] кратности элементов a, b и c равны соответственно 2, 3 и 1, и, следовательно, кардинальность этого мультимножества равна 6. Николас Говерт де Брюин ввёл термин «мультимножество» в 1970-х годах, согласно Дональду Кнуту. Однако концепция мультимножеств предшествует введению термина «мультимножество» на многие века. Сам Кнут приписывает первое исследование мультимножеств индийскому математику Бхаскарачарье, который описал перестановки мультимножеств около 1150 года. Для этой концепции были предложены или использованы другие названия, включая список, группу, мешок, кучу, выборку, взвешенное множество, коллекцию и набор. Эти и подобные коллекции объектов можно рассматривать как мультимножества, поскольку штрихи, зарубки или единицы считаются неразличимыми. Это показывает, что люди неявно использовали мультимножества ещё до появления математики. Практическая необходимость в этой структуре привела к тому, что мультимножества были повторно открыты несколько раз, появляясь в литературе под разными названиями. Например, они были важны в ранних языках искусственного интеллекта, таких как QA4, где их называли мешками, термин, приписываемый Питеру Дойчу. Мультимножество также называют агрегатом, кучей, группой, выборкой, взвешенным множеством, множеством появлений и множеством огней (конечно повторяющимся множеством элементов). Хотя мультимножества использовались неявно с древних времен, их явное исследование произошло гораздо позже. Первое известное исследование мультимножеств приписывается индийскому математику Бхаскарачарье около 1150 года, который описал перестановки мультимножеств. Афанасий Кирхер нашёл число перестановок мультимножества, когда один элемент может повторяться. Жан Престе опубликовал общее правило для перестановок мультимножеств в 1675 году. Джон Уоллис объяснил это правило более подробно в 1685 году. Мультимножества явно появились в работах Ричарда Дедекинда. Другие математики формализовали мультимножества и начали изучать их как точные математические структуры в XX веке. Например, Уитни (1933) описал обобщённые множества («множества», чьи характеристические функции могут принимать любое целое число — положительное, отрицательное или нулевое). Монро (1987) исследовал категорию Mul мультимножеств и их морфизмов, определяя мультимножество как множество с отношением эквивалентности между элементами «одного и того же типа», а морфизм между мультимножествами — как функцию, которая уважает типы. Он также ввёл мультичисло: функцию f(x) от мультимножества к натуральным числам, дающую кратность элемента x в мультимножестве. Монро утверждал, что понятия мультимножества и мультичисла часто смешиваются без разбора, хотя оба они полезны.
Mathematical set with repetitions allowed
In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that element in the multiset. As a consequence, an infinite number of multisets exist which contain only elements a and b, but vary in the multiplicities of their elements:
The set contains only elements a and b, each having multiplicity 1 when is seen as a multiset. In the multiset , the element a has multiplicity 2, and b has multiplicity 1. In the multiset , a and b both have multiplicity 3. These objects are all different when viewed as multisets, although they are the same set, since they all consist of the same elements. As with sets, and in contrast to tuples, the order in which elements are listed does not matter in discriminating multisets, so and denote the same multiset. To distinguish between sets and multisets, a notation that incorporates square brackets is sometimes used: the multiset can be denoted by [a, a, b]. The cardinality of a multiset is the sum of the multiplicities of all its elements. For example, in the multiset the multiplicities of the members a, b, and c are respectively 2, 3, and 1, and therefore the cardinality of this multiset is 6. Nicolaas Govert de Bruijn coined the word multiset in the 1970s, according to Donald Knuth. However, the concept of multisets predates the coinage of the word multiset by many centuries. Knuth himself attributes the first study of multisets to the Indian mathematician Bhāskarāchārya, who described permutations of multisets around 1150. Other names have been proposed or used for this concept, including list, bunch, bag, heap, sample, weighted set, collection, and suite. These and similar collections of objects can be regarded as multisets, because strokes, tally marks, or units are considered indistinguishable. This shows that people implicitly used multisets even before mathematics emerged. Practical needs for this structure have caused multisets to be rediscovered several times, appearing in literature under different names. For instance, they were important in early AI languages, such as QA4, where they were referred to as bags, a term attributed to Peter Deutsch. A multiset has been also called an aggregate, heap, bunch, sample, weighted set, occurrence set, and fireset (finitely repeated element set). Although multisets were used implicitly from ancient times, their explicit exploration happened much later. The first known study of multisets is attributed to the Indian mathematician Bhāskarāchārya circa 1150, who described permutations of multisets. Athanasius Kircher found the number of multiset permutations when one element can be repeated. Jean Prestet published a general rule for multiset permutations in 1675. John Wallis explained this rule in more detail in 1685. Multisets appeared explicitly in the work of Richard Dedekind. Other mathematicians formalized multisets and began to study them as precise mathematical structures in the 20th century. For example, Whitney (1933) described generalized sets ("sets" whose characteristic functions may take any integer value positive, negative or zero). Monro (1987) investigated the category Mul of multisets and their morphisms, defining a multiset as a set with an equivalence relation between elements "of the same sort", and a morphism between multisets as a function which respects sorts. He also introduced a multinumber : a function f (x) from a multiset to the natural numbers, giving the multiplicity of element x in the multiset. Monro argued that the concepts of multiset and multinumber are often mixed indiscriminately, though both are useful.
Примеры
Один из простейших и наиболее естественных примеров — мультимножество простых множителей натурального числа n. Здесь базовым множеством элементов является множество простых множителей n. Например, число 120 имеет простое разложение на множители
что дает мультимножество. Связанный пример — мультимножество решений алгебраического уравнения. Квадратное уравнение, например, имеет два решения. Однако в некоторых случаях они оба совпадают. Таким образом, мультимножество решений уравнения может быть , или может быть. В последнем случае оно имеет решение кратности 2. В более общем смысле, основная теорема алгебры утверждает, что комплексные решения полиномиального уравнения степени d всегда образуют мультимножество кардинальности d.
A related example is the multiset of solutions of an algebraic equation. A quadratic equation, for example, has two solutions. However, in some cases they are both the same number. Thus the multiset of solutions of the equation could be , or it could be In the latter case it has a solution of multiplicity 2. More generally, the fundamental theorem of algebra asserts that the complex solutions of a polynomial equation of degree d always form a multiset of cardinality d.
Особым случаем вышеописанного являются собственные значения матрицы, кратность которых обычно определяется как их кратность в качестве корней характеристического многочлена. Однако для собственных значений естественно определяются еще две кратности: их кратность в качестве корней минимального многочлена и геометрическая кратность, которая определяется как размерность ядра A − λI (где λ — собственное значение матрицы A). Эти три кратности определяют три мультимножества собственных значений, которые могут быть различными: пусть A — матрица n × n в нормальной жордановой форме, имеющая единственное собственное значение. Ее кратность равна n, ее кратность как корня минимального многочлена равна размеру наибольшего жорданова блока, а ее геометрическая кратность равна количеству жордановых блоков.