Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Жинақтың элементтер санының анықтамасы
Definition of the number of elements in a set
Математикада жиынның кардиналдылығы – жиынның элементтер санының өлшемі. Мысалы, {a, b, c} жиыны 3 элементтен тұрады, демек, оның кардиналдылығы 3-ке тең. 19 ғасырдың соңынан бастап, бұл ұғым шексіз жиындарға да қатысты кеңейтілді, бұл әртүрлі шексіздік түрлерін ажыратуға және олармен арифметикалық амалдар орындауға мүмкіндік береді. Кардиналдылықты анықтаудың екі тәсілі бар: бірі – жиындарды биекциялар мен инъекциялар арқылы тікелей салыстыру, екіншісі – кардинал сандарды қолдану. Жинақтың кардиналдылығы оның мөлшері деп те аталуы мүмкін, егер басқа мөлшер туралы түсініктермен шатастыру қаупі болмаса. Жинақтың кардиналдылығы әдетте |A| деп белгіленеді, мұнда әр жағында тік сызықтар болады; бұл абсолют мәнмен бірдей белгі, бірақ мағынасы контекстке байланысты. Жинақтың кардиналдылығын card(A), #(A), |A|, немесе басқа да белгілермен көрсетуге болады.
In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set contains 3 elements, and therefore has a cardinality of 3. Beginning in the late 19th century, this concept was generalized to infinite sets, which allows one to distinguish between different types of infinity, and to perform arithmetic on them. There are two approaches to cardinality: one which compares sets directly using bijections and injections, and another which uses cardinal numbers. The cardinality of a set may also be called its size, when no confusion with other notions of size is possible. The cardinality of a set is usually denoted , with a vertical bar on each side; this is the same notation as absolute value, and the meaning depends on context. The cardinality of a set may alternatively be denoted by , , , or .
Тарих
Кардиналдылықтың қарапайым сезімі, заттардың немесе оқиғалардың топтары басқа топтармен салыстырылып, көбірек, аз немесе бірдей санды қамтиды, бұл қазіргі жануарлар түрлерінің әртүрлілігінде байқалады және миллиондаған жылдар бұрын пайда болғандығын көрсетеді. Адамның кардиналдылықты білдіруі 40000 жыл бұрын-ақ байқалған, топтың мөлшерін жазылған ойықтар тобымен немесе таяқтар мен қабықшалар сияқты басқа заттардың өкілдік жиынтығымен теңестіру арқылы. Кардиналдылықтың сан ретінде абстракциясы б.з.д. 3000 жылға дейін Шумер математикасында, нақты бір заттар немесе оқиғалар тобына сілтеме жасамай сандарды қолдану арқылы айқын болды. Б.з.д. VI ғасырдан бастап грек философтарының жазбаларында шексіз жиынтықтардың кардиналдылығына қатысты белгілер бар. Олар шексіздік ұғымын санға 1-ді қайталап қосу сияқты аяқталмайтын әрекеттер тізбегі ретінде қарастырғанмен, сандардың шексіз жиынтығының мөлшерін ешқандай нәрсе деп санамаған. Ежелгі гректердің шексіздік туралы түсінігінде де нәрселерді шексіз қайталап бөлу қарастырылған. Евклидтің «Элементтер» еңбегінде, екі түзу сызық сегментінің (a және b) ұзындығын салыстыру қабілеті өлшенушілік деп сипатталған, егер оларды толық санмен a және b-ге бірнеше рет орналастыруға болатын үшінші, қаншалықты кішкентай болса да, сегмент болса. Бірақ иррационалды сандардың ашылуымен, тіпті барлық рационалды сандардың шексіз жиынтығының өзі әрбір мүмкін сызық сегментінің ұзындығын сипаттауға жеткіліксіз екені анық болды. Дегенмен, шексіз жиынтықтардың кардиналдығы бар деген түсінік болған жоқ. Шексіз жиынтықтарды жақсырақ түсіну үшін, жиынтықтар теориясының негізін қалаушы Георг Кантор шамамен 1880 жылы кардиналдылық ұғымын қалыптастырды. Ол екі жиынтықты біржақты сәйкестік арқылы теңестіру процесін зерттеді, яғни екі жиынтықтың элементтері арасындағы бірегей қатынасқа негізделген бір-бірге сәйкестік. 1891 жылы Кантордың диагональдық аргументін жариялау арқылы ол табиғи сандар жиынымен бір-бірге сәйкестікке келтірілмейтін сандар жиынтығы бар екенін көрсетті, яғни табиғи сандардың шексіз жиынтығындағы элементтерден көп элементтерді қамтитын санаусыз жиынтықтар бар екенін дәлелдеді.
A crude sense of cardinality, an awareness that groups of things or events compare with other groups by containing more, fewer, or the same number of instances, is observed in a variety of present day animal species, suggesting an origin millions of years ago. Human expression of cardinality is seen as early as 40000 years ago, with equating the size of a group with a group of recorded notches, or a representative collection of other things, such as sticks and shells. The abstraction of cardinality as a number is evident by 3000 BCE, in Sumerian mathematics and the manipulation of numbers without reference to a specific group of things or events. From the 6th century BCE, the writings of Greek philosophers show hints of the cardinality of infinite sets. While they considered the notion of infinity as an endless series of actions, such as adding 1 to a number repeatedly, they did not consider the size of an infinite set of numbers to be a thing. The ancient Greek notion of infinity also considered the division of things into parts repeated without limit. In Euclid's Elements, commensurability was described as the ability to compare the length of two line segments, a and b, as a ratio, as long as there were a third segment, no matter how small, that could be laid end to end a whole number of times into both a and b. But with the discovery of irrational numbers, it was seen that even the infinite set of all rational numbers was not enough to describe the length of every possible line segment. Still, there was no concept of infinite sets as something that had cardinality. To better understand infinite sets, a notion of cardinality was formulated c. 1880 by Georg Cantor, the originator of set theory. He examined the process of equating two sets with bijection, a one to one correspondence between the elements of two sets based on a unique relationship. In 1891, with the publication of Cantor's diagonal argument, he demonstrated that there are sets of numbers that cannot be placed in one to one correspondence with the set of natural numbers, i. e. uncountable sets that contain more elements than there are in the infinite set of natural numbers.
Салыстыратын жиынтықтар
Шекті жиынның кардиналдығы оның элементтерінің санымен анықталады, ал шексіз жиынтарға бұл ұғымды кеңейту көбінесе кез келген жиынды салыстыру тәсілін анықтаудан басталады (олардың кейбіреуі шексіз болуы мүмкін).
While the cardinality of a finite set is just the number of its elements, extending the notion to infinite sets usually starts with defining the notion of comparison of arbitrary sets (some of which are possibly infinite).
1- анықтама: =
A және B екі жиынның бірдей кардиналдығы бар, егер A-дан B-ға биекция (яғни, бір-бірге сәйкестік) болса, яғни A-дан B-ға инъективті және сюръективті функция болса. Мұндай жиындар эквипотентті, эквиполлент немесе эквинумерлі деп аталады. Бұл қатынасты A ≈ B немесе A ~ B деп те белгілеуге болады. Мысалы, оңсыз жұп сандар жиыны E = {0, 2, 4, 6, …} табиғи сандар жиыны N = {0, 1, 2, 3, …} сияқты бірдей кардиналдыққа ие, себебі f(n) = 2n функциясы N-ден E-ге биекция (суретті қараңыз). А және В шекті жиындар болғанда, егер A-дан B-ға кемінде бір биекция болса, онда A-дан B-ға кез келген инъективті немесе сюръективті функция биекция болады. Бұл шексіз A және B үшін енді дұрыс емес. Мысалы, g(n) = 4n арқылы анықталған g функциясы N-ден E-ге инъективті, бірақ сюръективті емес, ал h(n) = n – (n mod 2) арқылы анықталған h функциясы N-ден E-ге сюръективті, бірақ инъективті емес. g де, h да f-тің болуымен орнатылған = -ге қарсы келе алмайды.
Two sets A and B have the same cardinality if there exists a bijection (a. k. a., one to one correspondence) from A to B, that is, a function from A to B that is both injective and surjective. Such sets are said to be equipotent, equipollent, or equinumerous. This relationship can also be denoted A ≈ B or A ~ B. For example, the set E = {0, 2, 4, 6, } of non negative even numbers has the same cardinality as the set N = {0, 1, 2, 3, } of natural numbers, since the function f(n) = 2n is a bijection from N to E (see picture). For finite sets A and B, if some bijection exists from A to B, then each injective or surjective function from A to B is a bijection. This is no longer true for infinite A and B. For example, the function g from N to E, defined by g(n) = 4n is injective, but not surjective, and h from N to E, defined by h(n) = n (n mod 2) is surjective, but not injective. Neither g nor h can challenge = , which was established by the existence of f.
2-тариф: ≤
Егер A-дан B-ға инъекциялық функция болса, A-ның кардиналдығы B-ның кардиналдығынан кем немесе тең болады.
A has cardinality less than or equal to the cardinality of B, if there exists an injective function from A into B.
3-тариф:
A-ның кардиналдығы B-нің кардиналдығынан қатаң кем, егер A-дан B-ге инъективті функция болса, бірақ биективті функция болмаса. Мысалы, барлық натурал сандардың N жиынының кардиналдығы өзінің P(N) қуаты жиынынан қатаң кем, себебі g(n) = {n} – N-ден P(N-ге дейінгі инъективті функция, және N-ден P(N-ге дейінгі функциялардың ешқайсысы биективті бола алмайтынын көрсетуге болады (суретті қараңыз). Осыған ұқсас аргумент бойынша, N-нің кардиналдығы барлық нақты сандардың R жиынының кардиналдығынан қатаң кем. Дәлелдер үшін Кантордың диагональдық аргументіне немесе Кантордың бірінші санаусыздық дәлеліне жүгініңіз. Егер ≤ және ≤ болса, онда = (бұл Шрёдер–Бернштейн теоремасы деп аталады). Таңдау аксиомасы кез келген A, B үшін ≤ немесе ≤ деген тұжырымға эквивалентті.
A has cardinality strictly less than the cardinality of B, if there is an injective function, but no bijective function, from A to B. For example, the set N of all natural numbers has cardinality strictly less than its power set P(N), because g(n) = { n } is an injective function from N to P(N), and it can be shown that no function from N to P(N) can be bijective (see picture). By a similar argument, N has cardinality strictly less than the cardinality of the set R of all real numbers. For proofs, see Cantor's diagonal argument or Cantor's first uncountability proof. If ≤ and ≤ , then = (a fact known as Schröder–Bernstein theorem). The axiom of choice is equivalent to the statement that ≤ or ≤ for every A, B.
Түпкілікті, саналатын және саналмайтын жиынтықтар
Егер таңдау аксиомасы орындалса, кардинальдық үшін трихотомия заңы орындалады. Осылайша, мынадай анықтамалар беруге болады:
If the axiom of choice holds, the law of trichotomy holds for cardinality. Thus we can make the following definitions:
Кез келген X жиыны, егер оның кардиналдылығы натурал сандардан кем болса, яғни |X| < |N|, шекті жиын деп аталады. Кез келген X жиыны, егер оның кардиналдылығы натурал сандар жиынымен тең болса, яғни |X| = |N| = ℵ₀, саналатын шексіз жиын деп аталады. Бұған мысал ретінде Гилберттің «Үлкен қонақүй» парадоксын келтіруге болады. Шындығында, Дедекинд шексіз жиынды, оның қатаң ішкі жиынымен (яғни Кантор мағынасында бірдей өлшемде) бір-бірге сәйкестікке келтіріле алатын жиын ретінде анықтады; мұндай шексіздік түсінігі Дедекинд шексіздігі деп аталады. Кантор кардинал сандарды енгізіп, оның биекцияға негізделген өлшем анықтамасына сәйкес, кейбір шексіз жиындар басқаларынан үлкен екенін көрсетті. Ең кіші шексіз кардинал – натурал сандардың кардиналы ℵ₀.
Any set X with cardinality less than that of the natural numbers, or | X | < | N |, is said to be a finite set. Any set X that has the same cardinality as the set of the natural numbers, or | X | = | N | = , is said to be a countably infinite set. One example of this is Hilbert's paradox of the Grand Hotel. Indeed, Dedekind defined an infinite set as one that can be placed into a one to one correspondence with a strict subset (that is, having the same size in Cantor's sense); this notion of infinity is called Dedekind infinite. Cantor introduced the cardinal numbers, and showed—according to his bijection based definition of size—that some infinite sets are greater than others. The smallest infinite cardinality is that of the natural numbers .
Мысалдар мен қасиеттері
Егер X = {a, b, c} және Y = {алмалар, апельсиндер, шабдалылар} болса, мұнда a, b және c өзгеше болса, онда |X| = |Y|, себебі { (a, алмалар), (b, апельсиндер), (c, шабдалылар)} жиыны X және Y жиындары арасындағы биекция болып табылады. X және Y жиындарының әрқайсысының кардиналдығы 3-ке тең. Егер |X| ≤ |Y| болса, онда |X| = |Z| және Z ⊆ Y болатын Z жиыны бар. Егер |X| ≤ |Y| және |Y| ≤ |X| болса, онда |X| = |Y|. Бұл тіпті шексіз кардиналдар үшін де орындалады және Кантор – Бернштейн – Шрёдер теоремасы деп аталады. Континуум кардиналдығына ие жиындарға барлық нақты сандар жиыны, барлық иррационал сандар жиыны және аралық кіреді.
If X = {a, b, c} and Y = {apples, oranges, peaches}, where a, b, and c are distinct, then | X | = | Y | because { (a, apples), (b, oranges), (c, peaches)} is a bijection between the sets X and Y. The cardinality of each of X and Y is 3. If | X | ≤ | Y |, then there exists Z such that | X | = | Z | and Z ⊆ Y. If | X | ≤ | Y | and | Y | ≤ | X |, then | X | = | Y |. This holds even for infinite cardinals, and is known as Cantor–Bernstein–Schroeder theorem. Sets with cardinality of the continuum include the set of all real numbers, the set of all irrational numbers and the interval .