Кіріспе
математикалық ұғым. Математикалық жиын қайталануға рұқсат етіледі. Математикада көп жиынтық (немесе қап, немесе мсет) — жиынтық ұғымының өзгерткіші, ол жиынтықтан айырмашылығы, әрбір элементі үшін бірнеше данаға мүмкіндік береді. Әрбір элемент үшін берілген даналар саны сол элементтің көп жиынтықтағы көптігі деп аталады. Осының салдарынан, тек a және b элементтерін қамтитын, бірақ элементтерінің көптігі бойынша өзгеше болатын шексіз көп көп жиынтықтар бар: Жиынтықта тек a және b элементтері бар, егер ол көп жиынтық ретінде қарастырылса, әрқайсысының көптігі 1-ге тең. Көп жиынтықта [a, a], элемент a-ның көптігі 2-ге, ал b-ның көптігі 1-ге тең. Көп жиынтықта [a, a, a, b], a және b элементтерінің екеуінің де көптігі 3-ке тең. Бұл нысандардың барлығы көп жиынтық ретінде қарастырылғанда әртүрлі, бірақ олардың барлығы бірдей элементтерден тұратындықтан, олар бірдей жиынтық. Жиынтықтардағыдай, ал тізімдемелерден айырмашылығы, элементтердің тізілу тәртібі көп жиынтықты ажырату үшін маңызды емес, сондықтан [a, b] және [b, a] бірдей көп жиынтықты білдіреді. Жиынтықтар мен көп жиынтықтарды ажырату үшін кейде квадрат жақшаларды қолданатын белгі пайдаланылады: көп жиынтық [a, a, b] деп белгіленеді. Көп жиынтықтың кардиналдығы — оның барлық элементтерінің көптіктерінің қосындысы. Мысалы, көп жиынтықта [a, a, b, b, b, c], a, b және c мүшелерінің көптігі сәйкесінше 2, 3 және 1-ге тең, сондықтан бұл көп жиынтықтың кардиналдығы 6-ға тең. Дональд Кнуттың айтуынша, Николас Говерт де Брюйн 1970 жылдары «көп жиынтық» сөзін енгізген. Алайда, көп жиынтықтар туралы түсінік «көп жиынтық» сөзінің пайда болуына дейін көп ғасырлар бұрын пайда болған. Кнуттың өзі көп жиынтықтарды зерттеудің алғашқысын шамамен 1150 жылы көп жиынтықтың өрнектерін сипаттаған үнді математигі Бхаскарачарьяға жатқызады. Бұл ұғым үшін басқа атаулар да ұсынылған немесе қолданылған, соның ішінде тізім, топ, қап, үйірме, үлгі, салмақталған жиынтық, жинақ және топтама. Осы және осыған ұқсас нысандар жиынтығын көп жиынтық деп қарастыруға болады, өйткені сызықтар, санау белгілері немесе бірліктер бір-бірінен ажыратылмайды. Бұл адамдар математика пайда болғанға дейін көп жиынтықты пайдаланғанын көрсетеді. Бұл құрылымның практикалық қажеттілігі көп жиынтықты бірнеше рет қайта ашуға себеп болды, олар әдебиетте әртүрлі атаулармен пайда болды. Мысалы, олар ертедегі жасанды интеллект тілдерінде маңызды болды, мысалы QA4, онда олар Питер Дойчқа жатқызылған «қаптар» деп аталды. Көп жиынтық жиынтық, үйірме, топтама, үлгі, салмақталған жиынтық, пайда болу жиынтығы және от жиынтығы (шекті қайталанушы элементтер жиынтығы) деп те аталады. Көп жиынтықтар ежелгі заманнан бері жасырын түрде қолданылса да, олардың нақты зерттеуі көп кешікті. Көп жиынтықты зерттеудің алғашқы белгілі жұмысы шамамен 1150 жылы үнді математигі Бхаскарачарьяға тиесілі, ол көп жиынтықтың өрнектерін сипаттады. Афанасий Киршер бір элементті қайталауға болатын көп жиынтықтың өрнектерінің санын тапты. Жан Престе 1675 жылы көп жиынтықтың өрнектері үшін жалпы ережені жариялады. Джон Уоллис 1685 жылы бұл ережені егжей-тегжейлі түсіндірді. Көп жиынтықтар Ричард Дедекиндтің жұмысында айқын көрінді. Басқа математиктер көп жиынтықты формалдап, оларды 20 ғасырда нақты математикалық құрылымдар ретінде зерттеуге кірісті. Мысалы, Уитни (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-ге тең, минималды көпмүшенің түбірі ретіндегі көптігі ең үлкен Джордан блогының өлшеміне тең, ал геометриялық көптігі Джордан блоктарының санына тең.