Скінченна множина — це множина, кількість елементів якої є скінченна, тобто існує натуральне число k, що є числом елементів цієї множини. В протилежному випадку множина є нескінченною.
Визначення 2. Множина, що не має рівнопотужної з нею власної підмножини, а також порожня множина, називається скінченною
Формальне визначення
Нехай — множина, що складається з перших
цілих чисел. Множина
називається скінченною, якщо вона еквівалентна
при деякому
.
Число називається кількістю елементів множини
позначається
.
Дві множини та
називаються еквівалентними, якщо існує бієктивне відображення однієї на іншу. Якщо множини еквівалентні, то цей факт записують
або
і кажуть, що множини мають однакові потужності.
Порожня множина є скінченною множиною, кількість елементів якої дорівнює 0: .
Існує декілька основних теорем для скінченних множин.
Основні теореми
Основна теорема про скінченні множини
Скінченна множина не рівнопотужна жодній власній підмножині і власній надмножині.
Доведення. Кожне з двох тверджень теореми (про нерівнопотужності підмножини і надмножини) легко випливає з іншого, оскільки, якщо та
то зі скінченності однієї з множин A і B, як було зазначено раніше, випливає скінченність іншої. Доведемо, наприклад, що скінченна множина A не рівнопотужна її власній підмножині. Для порожньої множини A = 0 теорема вірна, оскільки порожня множина зовсім не має власних підмножин. Нехай
. Тоді за визначенням скінченної множини, множина A рівнопотужна (принаймні одному) відрізку натурального ряду | 1, n |. Доведемо індукцією по числу n, що A не можна взаємно однозначно відобразити на її власну підмножину B. Для n = 1 це очевидно, оскільки A ~ | 1, 1 | і містить лише один елемент. Єдиною її власною підмножиною буде B = 0, причому A не рівнопотужна B. Припустимо, що теорема доведена для натурального числа n, і доведемо її для числа n+1. Отже, нехай A ~ | 1, n +1 |, і f є взаємно однозначним відображенням A на B. Пронумерувавши елементи A відповідними їм числами, отримаємо: A = {a1, a2, …, an+1}. Для B = 0 твердження вірне. Якщо
, то без обмеження спільності можна припустити, що
. Інакше беремо єлемент
та будуємо нову множину
, отриману з B заміною елемента b на
, і нове відображення
, яке збігається з f для всіх елементів множини A, окрім елементів a з властивістю f (a) = b, причому для цього елемента a вважаємо
. Тоді
буде взаємно однозначним відображенням A на власну підмножину
, що містить
. Далі, без обмеження спільності можна вважати, що
. Інакше, нехай
і
. Тоді будуємо нове відображення
, яке збігається з f для всіх елементів A, крім
та
, причому вважаємо
і
. Отже, нехай
та
, нехай також A' = A \ {
} і B' = B \ {
}. Оскільки B — власна підмножина A, то існує елемент
. Оскільки
, то
. Тому
. Отже, B' є власною підмножіною A'. Оскільки
, то відображення
встановлює рівнопотужність множин A 'і B', але A '= {
} ~ | 1, n |. Ми одержали протиріччя з припущенням індукції, тим самим нашого твердження, а значить, і вся теорема доведена.
З цієї теореми легко слідує наступна теорема.
Всіляка непорожня скінченна множина рівнопотужна одному і тільки одному відрізку натурального ряду
Доведення:
За визначенням скінченної множини непорожня скінченна множина A рівнопотужна принаймні одному відрізку натурального ряду. Якби вона була рівнопотужна двом різним відрізкам,
, тоді за властивостями рівнопотужності буде:
, що суперечить теоремі 1, оскільки один з двох різних відрізків натурального ряду є власною підмножиною іншого. Однозначно визначене для даної непорожньої скінченної множини A натуральне число n таке, що
, називається числом елементів множини A. Числом елементів порожньої множини називається число 0. З властивостей рівньопотужності випливає, що дві скінченні множини тоді і тільки тоді рівнопотужні, коли вони мають одне і те ж число елементів. Тому число елементів можна прийняти за визначення потужності скінченної множини.
Будь-яка підмножина скінченної множини сама скінченна. Будь-яка надмножина нескінченної множини сама нескінченна
Доведення:
Кожне з двох тверджень теореми випливає з іншого. Так, якщо перше твердження вірне, то вірне і друге, оскільки якщо A нескінченно та , то і B нескінченне, тому що якщо б B була скінченною, то по першій половині теореми і A було б скінченним. Досить тому довести перше твердження. Отже, нехай A скінченне та
.Якщо
, то і
, теорема справедлива. Нехай
. Тоді
для деякого числа n. Застосуємо індукцію щодо n. При n = 1 теорема правильна, оскільки A містить один елемент, і або B = 0, або B = A. Нехай твердження вірне для деякого n. Доведемо його для числа n + 1. Отже, нехай f - взаємно однозначне відображення A на відрізок | 1, n +1 |. Якщо B = A, то B скінченне. Нехай
. Існує елемент
. Можна вважати, що f (a) = n + 1. Інакше f (a ') = n + 1, де
та
. Якщо тоді f (a) = i, то будуємо нове відображення f1, вважаючи f1 (a) = n + 1, f1 (a ') = i і f1 = f для решти елементів множини A. Отже, нехай f (a) = n + 1. Покладемо A '= A \ {a}. Тоді f визначає взаємно однозначне відображення множини A ' на відрізок | 1, n |, і
.Отже, за припущенням індукції B скінченне. Теорема доведена. Згідно з теоремою 3 поняття про число елементів має сенс для будь-якої підмножини даної скінченної множини. При цьому має місце Теорема 4(див. нижче).
Число елементів скінченної множини A завжди більше від числа елементів його власної підмножини B.
Доведення:
Нехай m - число єлементів з множини A, n - число елементів з множини B. Зауважимо, що . Оскільки
, то
,
,
. Також і
, отже
(1). При взаємно однозначному відображенні A на відрізок |1, m| множина B відображається також взаємно однозначно на деяку власну підмножина B' відрізка |1, m|, таким чином,
(2). З
та
слідує
(3). Проте з (1) та (2) слідує
, що в силу (3) суперечить теоремі 1, т. я. відрізок |1, n| виявляється рівнопотужним своїй власній підмножині B '.
Властивості
- Скінченна множина не еквівалентна жодній власній підмножині;
— скінченні множини що попарно не перетинаються (тобто
), тоді
;
— скінченні множини, тоді
;
- Нехай
— скінченна множина, тоді потужність булеана рівна
Посилання
- Соболева Т. С., Чечкин А. В. (2006). Дискретная математика. Академия. ISBN .
Див. також
![]() | Це незавершена стаття з теорії множин. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Skinchenna mnozhina ce mnozhina kilkist elementiv yakoyi ye skinchenna tobto isnuye naturalne chislo k sho ye chislom elementiv ciyeyi mnozhini V protilezhnomu vipadku mnozhina ye neskinchennoyu Viznachennya 2 Mnozhina sho ne maye rivnopotuzhnoyi z neyu vlasnoyi pidmnozhini a takozh porozhnya mnozhina nazivayetsya skinchennoyuFormalne viznachennyaNehaj Jn 1 2 n displaystyle J n 1 2 dots n mnozhina sho skladayetsya z pershih n displaystyle n cilih chisel Mnozhina X displaystyle X nazivayetsya skinchennoyu yaksho vona ekvivalentna Jn displaystyle J n pri deyakomu n displaystyle n Chislo n displaystyle n nazivayetsya kilkistyu elementiv mnozhini X displaystyle X poznachayetsya n X displaystyle n X Dvi mnozhini X displaystyle X ta Y displaystyle Y nazivayutsya ekvivalentnimi yaksho isnuye biyektivne vidobrazhennya odniyeyi na inshu Yaksho mnozhini ekvivalentni to cej fakt zapisuyut X Y displaystyle X sim Y abo X Y displaystyle X Y i kazhut sho mnozhini mayut odnakovi potuzhnosti Porozhnya mnozhina ye skinchennoyu mnozhinoyu kilkist elementiv yakoyi dorivnyuye 0 0 displaystyle emptyset 0 Isnuye dekilka osnovnih teorem dlya skinchennih mnozhin Osnovni teoremiOsnovna teorema pro skinchenni mnozhini Skinchenna mnozhina ne rivnopotuzhna zhodnij vlasnij pidmnozhini i vlasnij nadmnozhini Dovedennya Kozhne z dvoh tverdzhen teoremi pro nerivnopotuzhnosti pidmnozhini i nadmnozhini legko viplivaye z inshogo oskilki yaksho A B displaystyle A sim B ta A B displaystyle A supset B to zi skinchennosti odniyeyi z mnozhin A i B yak bulo zaznacheno ranishe viplivaye skinchennist inshoyi Dovedemo napriklad sho skinchenna mnozhina A ne rivnopotuzhna yiyi vlasnij pidmnozhini Dlya porozhnoyi mnozhini A 0 teorema virna oskilki porozhnya mnozhina zovsim ne maye vlasnih pidmnozhin Nehaj A 0 displaystyle A neq 0 Todi za viznachennyam skinchennoyi mnozhini mnozhina A rivnopotuzhna prinajmni odnomu vidrizku naturalnogo ryadu 1 n Dovedemo indukciyeyu po chislu n sho A ne mozhna vzayemno odnoznachno vidobraziti na yiyi vlasnu pidmnozhinu B Dlya n 1 ce ochevidno oskilki A 1 1 i mistit lishe odin element Yedinoyu yiyi vlasnoyu pidmnozhinoyu bude B 0 prichomu A ne rivnopotuzhna B Pripustimo sho teorema dovedena dlya naturalnogo chisla n i dovedemo yiyi dlya chisla n 1 Otzhe nehaj A 1 n 1 i f ye vzayemno odnoznachnim vidobrazhennyam A na B Pronumeruvavshi elementi A vidpovidnimi yim chislami otrimayemo A a1 a2 an 1 Dlya B 0 tverdzhennya virne Yaksho B 0 displaystyle B neq 0 to bez obmezhennya spilnosti mozhna pripustiti sho an 1 B displaystyle a n 1 in B Inakshe beremo yelement b B displaystyle b in B ta buduyemo novu mnozhinu B1 displaystyle B 1 otrimanu z B zaminoyu elementa b na an 1 displaystyle a n 1 i nove vidobrazhennya f1 displaystyle f 1 yake zbigayetsya z f dlya vsih elementiv mnozhini A okrim elementiv a z vlastivistyu f a b prichomu dlya cogo elementa a vvazhayemo f1 a an 1 displaystyle f 1 a a n 1 Todi f1 displaystyle f 1 bude vzayemno odnoznachnim vidobrazhennyam A na vlasnu pidmnozhinu B1 displaystyle B 1 sho mistit an 1 displaystyle a n 1 Dali bez obmezhennya spilnosti mozhna vvazhati sho f an 1 an 1 displaystyle f a n 1 a n 1 Inakshe nehaj f i an 1 displaystyle f i a n 1 i f an 1 aj displaystyle f a n 1 a j Todi buduyemo nove vidobrazhennya f1 displaystyle f 1 yake zbigayetsya z f dlya vsih elementiv A krim ai displaystyle a i ta ai 1 displaystyle a i 1 prichomu vvazhayemo f ai aj displaystyle f a i a j if an 1 an 1 displaystyle f a n 1 a n 1 Otzhe nehaj an 1 B displaystyle a n 1 in B ta f an 1 an 1 displaystyle f a n 1 a n 1 nehaj takozh A A an 1 displaystyle a n 1 i B B an 1 displaystyle a n 1 Oskilki B vlasna pidmnozhina A to isnuye element a B A displaystyle a in B A Oskilki an 1 B displaystyle a n 1 in B to a an 1 displaystyle a neq a n 1 Tomu a A B displaystyle a in A B Otzhe B ye vlasnoyu pidmnozhinoyu A Oskilki f an 1 an 1 B displaystyle f a n 1 a n 1 in B to vidobrazhennya f displaystyle f vstanovlyuye rivnopotuzhnist mnozhin A i B ale A a1 a2 an displaystyle a 1 a 2 a n 1 n Mi oderzhali protirichchya z pripushennyam indukciyi tim samim nashogo tverdzhennya a znachit i vsya teorema dovedena Z ciyeyi teoremi legko sliduye nastupna teorema Vsilyaka neporozhnya skinchenna mnozhina rivnopotuzhna odnomu i tilki odnomu vidrizku naturalnogo ryadu Div takozh Naturalni chisla Dovedennya Za viznachennyam skinchennoyi mnozhini neporozhnya skinchenna mnozhina A rivnopotuzhna prinajmni odnomu vidrizku naturalnogo ryadu Yakbi vona bula rivnopotuzhna dvom riznim vidrizkamA 1 m displaystyle A sim 1 m A 1 n displaystyle A sim 1 n m n displaystyle m neq n todi za vlastivostyami rivnopotuzhnosti bude 1 m 1 n displaystyle 1 m sim 1 n sho superechit teoremi 1 oskilki odin z dvoh riznih vidrizkiv naturalnogo ryadu ye vlasnoyu pidmnozhinoyu inshogo Odnoznachno viznachene dlya danoyi neporozhnoyi skinchennoyi mnozhini A naturalne chislo n take sho A 1 n displaystyle A sim 1 n nazivayetsya chislom elementiv mnozhini A Chislom elementiv porozhnoyi mnozhini nazivayetsya chislo 0 Z vlastivostej rivnopotuzhnosti viplivaye sho dvi skinchenni mnozhini todi i tilki todi rivnopotuzhni koli voni mayut odne i te zh chislo elementiv Tomu chislo elementiv mozhna prijnyati za viznachennya potuzhnosti skinchennoyi mnozhini Bud yaka pidmnozhina skinchennoyi mnozhini sama skinchenna Bud yaka nadmnozhina neskinchennoyi mnozhini sama neskinchenna Dovedennya Kozhne z dvoh tverdzhen teoremi viplivaye z inshogo Tak yaksho pershe tverdzhennya virne to virne i druge oskilki yaksho A neskinchenno ta A B displaystyle A subseteq B to i B neskinchenne tomu sho yaksho b B bula skinchennoyu to po pershij polovini teoremi i A bulo b skinchennim Dosit tomu dovesti pershe tverdzhennya Otzhe nehaj A skinchenne ta B A displaystyle B subseteq A Yaksho A 0 displaystyle A 0 to i B 0 displaystyle B 0 teorema spravedliva Nehaj A 0 displaystyle A supset 0 Todi A 1 n displaystyle A sim 1 n dlya deyakogo chisla n Zastosuyemo indukciyu shodo n Pri n 1 teorema pravilna oskilki A mistit odin element i abo B 0 abo B A Nehaj tverdzhennya virne dlya deyakogo n Dovedemo jogo dlya chisla n 1 Otzhe nehaj f vzayemno odnoznachne vidobrazhennya A na vidrizok 1 n 1 Yaksho B A to B skinchenne Nehaj B A displaystyle B subset A Isnuye element a A B displaystyle a in A B Mozhna vvazhati sho f a n 1 Inakshe f a n 1 de a A displaystyle a in A ta a a displaystyle a neq a Yaksho todi f a i to buduyemo nove vidobrazhennya f1 vvazhayuchi f1 a n 1 f1 a i i f1 f dlya reshti elementiv mnozhini A Otzhe nehaj f a n 1 Poklademo A A a Todi f viznachaye vzayemno odnoznachne vidobrazhennya mnozhini A na vidrizok 1 n i B A displaystyle B subseteq A Otzhe za pripushennyam indukciyi B skinchenne Teorema dovedena Zgidno z teoremoyu 3 ponyattya pro chislo elementiv maye sens dlya bud yakoyi pidmnozhini danoyi skinchennoyi mnozhini Pri comu maye misce Teorema 4 div nizhche Chislo elementiv skinchennoyi mnozhini A zavzhdi bilshe vid chisla elementiv jogo vlasnoyi pidmnozhini B Dovedennya Nehaj m chislo yelementiv z mnozhini A n chislo elementiv z mnozhini B Zauvazhimo sho n m displaystyle n geq m Oskilki A B displaystyle A supset B to A 0 displaystyle A neq 0 n gt 0 displaystyle n gt 0 A 1 m displaystyle A sim 1 m Takozh i m n gt 0 displaystyle m geq n gt 0 otzhe B 1 n displaystyle B sim 1 n 1 Pri vzayemno odnoznachnomu vidobrazhenni A na vidrizok 1 m mnozhina B vidobrazhayetsya takozh vzayemno odnoznachno na deyaku vlasnu pidmnozhina B vidrizka 1 m takim chinom B b displaystyle B sim b 2 Z B 1 m displaystyle B subset 1 m ta m n displaystyle m leq n sliduye B 1 n displaystyle B subset 1 n 3 Prote z 1 ta 2 sliduye B 1 m displaystyle B sim 1 m sho v silu 3 superechit teoremi 1 t ya vidrizok 1 n viyavlyayetsya rivnopotuzhnim svoyij vlasnij pidmnozhini B VlastivostiSkinchenna mnozhina ne ekvivalentna zhodnij vlasnij pidmnozhini X1 Xn displaystyle X 1 dots X n skinchenni mnozhini sho poparno ne peretinayutsya tobto Xi Xj displaystyle X i cap X j emptyset todi X1 X2 Xn X1 X2 Xn displaystyle X 1 cup X 2 cup dots cup X n X 1 X 2 dots X n X1 Xn displaystyle X 1 dots X n skinchenni mnozhini todi X1 X2 Xn X1 X2 Xn displaystyle X 1 times X 2 times dots times X n X 1 times X 2 times dots times X n Nehaj X displaystyle X skinchenna mnozhina todi potuzhnist buleana rivna 2X 2 X displaystyle 2 X 2 X PosilannyaSoboleva T S Chechkin A V 2006 Diskretnaya matematika Akademiya ISBN 5 7695 2823 0 Div takozhPortal Matematika Zlichenna mnozhina Kombinatorika Potuzhnist mnozhini Ce nezavershena stattya z teoriyi mnozhin Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi