Кінцева підмножина. Значення слова підмножина. Порівняльний аналіз можливостей людини та машини

На простому прикладі нагадаємо, що називається підмножиною, які бувають підмножини (власні та невласні), формулу знаходження числа всіх підмножин, а також калькулятор, який видає безліч усіх підмножин.

приклад 1. Дано безліч А = (а, с, р, о). Випишіть усі підмножини
даної множини.
Рішення:

Власні підмножини:(а), (с), (р), (о), (а, с), (а, р), (а, о), (с, р), (с, о) ∈, (р, о), (а, с, р), (а, с, о), (с, р, о).

Невласні:(а, с, р, про), Ø.

Всього: 16 підмножин.

Пояснення. Множина A є підмножиною множини B якщо кожен елемент множини A міститься також у B.

Порожня множина ∅ є підмножиною будь-якої множини, називається невласною;
. будь-яка множина є підмножиною самого себе, також називається невласною;
. У будь-якої n-елементної множини рівно 2 n підмножин.

Останнє твердження є формулою для знаходження числа всіх підмножинбез перерахування кожного.

Висновок формули:Припустимо, у нас є безліч з n-елементів. При складанні підмножин перший елемент може належати підмножини або належати, тобто. перший елемент можемо вибрати двома способами, аналогічно для всіх інших елементів (всього n-елементів), кожен можемо вибрати двома способами, і за правилом множення отримуємо: 2∙2∙2∙ ...∙2=2 n

Для математиків сформулюємо теорему і наведемо суворий доказ.

Теорема. Число підмножин кінцевої множини, що складається з n елементів, дорівнює 2 n.

Доведення.Безліч, що складається з одного елемента a, має два (тобто 2 1) підмножини: ∅ та (a). Безліч, що складається з двох елементів a та b, має чотири (тобто 2 2) підмножини: ∅, (a), (b), (a; b).
Множина, що складається з трьох елементів a, b, c, має вісім (тобто 2 3) підмножин:
∅, (a), (b), (b; a), (c), (c; a), (c; b), (c; b; a).
Можна припустити, що додавання нового елемента подвоює кількість підмножин.
Завершимо доказ застосуванням методу математичної індукції. Сутність цього методу в тому, що якщо твердження (властивість) справедливе для деякого початкового натурального числа n 0 і якщо припущення, що воно справедливе для довільного натурального n = k ≥ n 0 можна довести його справедливість для числа k + 1, то це властивість справедливо для всіх натуральних чисел.

1. Для n = 1 (база індукції) (і навіть n = 2, 3) теорема доведена.

2. Припустимо, що теорема підтверджена для n = k, тобто. число підмножин множини, що складається з елементів, дорівнює 2 k .

3. Доведемо, що число підмножин множини B, що складається з n = k + 1 елемента, дорівнює 2 k+1 .
Вибираємо деякий елемент b множини B. Розглянемо безліч A = B \ (b). Воно містить елементи k. Всі підмножини множини A - це підмножини множини B, що не містять елемента b і, за припущенням, їх 2 k штук. Підмножини множини B, що містять елемент b, стільки ж, тобто. 2 к
штук.

Отже, всіх підмножин множини B: 2 k + 2 k = 2 ⋅ 2 k = 2 k+1 штук.
Теорему доведено.

У прикладі 1 безліч А = (а, с, р, о)складається з чотирьох елементів, n=4, отже, число всіх підмножин дорівнює 24 =16.

Якщо вам необхідно виписати всі підмножини, або скласти програму для написання безлічі всіх підмножин, то є алгоритм для вирішення: представляти можливі комбінації у вигляді двійкових чисел. Пояснимо на прикладі.

приклад 2.Є безліч (ab c), у відповідність ставляться такі числа:
000 = (0) (порожня множина)
001 = (c)
010 = (b)
011 = (b c)
100 = (a)
101 = (a c)
110 = (a b)
111 = (a b c)

Калькулятор безлічі всіх підмножин.

У калькуляторі вже набрано елементи множини А = (а, с, р, о), достатньо натиснути кнопку Submit. Якщо вам необхідне вирішення свого завдання, то набираємо елементи множини на латиниці, через кому, як показано в прикладі.

Належні $A$, також належить $B$. Формальне визначення:

$(A\; \backslash subset\; B)\; \backslash Leftrightarrow\; \backslash forall\; x.\; (x\; \backslash in\; A\; \backslash Rightarrow\; x\; \backslash in\; B).$

Безліч $B$називається надмножиноюбезлічі $A$, якщо $A$- підмножина $B$.

Існує два символічні позначення для підмножин:

Обидві системи позначень використовують символ $\backslash subset$у різних сенсах, що може призвести до плутанини. У цій статті ми будемо використовувати останню систему позначень.

Те, що $B$називається надмножиною $A$, часто записують $B\; \backslash supset\; A$.

Безліч всіх підмножин множини $A$позначається $\backslash mathcal(P)(A)$і називається булеаном.

Власна підмножина

Будь-яка безліч $B$є своєю підмножиною. Якщо ми хочемо виключити $B$з розгляду ми користуємося поняттям власного

Безліч $A$є власним підмножиною множини $B$, якщо $A\; \backslash subset\; B$і $A\; \backslash ne\; B$.

Порожня множина є підмножиною будь-якої множини. Якщо ми також хочемо виключити з розгляду порожню безліч, ми користуємося поняттям нетривіальногопідмножини, що визначається так:

Безліч $A$є нетривіальним підмножиною множини $B$, якщо $A$є власним підмножиною $B$і $A\; \backslash ne\; \backslash varnothing$.

Приклади

• Безліч $\backslash varnothing,\; \backslash (0\backslash ),\; \backslash (1,3,4\backslash ).$ $\backslash \{\; 0,1,2,3,4,5\backslash \}$
• Безліч $\backslash (\backslash varnothing,\; \backslash uparrow,\; moose\backslash ),\; \backslash (\$,\%,*,\backslash uparrow\backslash ),\; \backslash (\backslash varnothing\backslash ),\; \backslash varnothing$є підмножинами множини $\backslash (\$,\; \%,\; \backslash varnothing,\; \backslash uparrow,\; *,\; moose\; \backslash )$
• Нехай $A\; =\; \backslash (a,b\backslash )$тоді $\backslash mathcal(P)(A)\; =\; \backslash (\backslash varnothing,\; \backslash (a\backslash ),\; \backslash (b\backslash ),\; \backslash (a,b\backslash )\; \backslash )$.
• Нехай $A\; =\; \backslash \; (1,2,3,4,5\; \backslash ),\; \backslash ;\; B\; =\; \backslash \; (1,2,3\; \backslash ),\; \backslash ;\; C\; =\; \backslash \; (4,5,6,7)$. Тоді $B\; \backslash subset\; A,\backslash ;\; C\; \backslash not\backslash subset\; A$.

Властивості

Ставлення підмножини має цілу низку властивостей.

• Відношення підмножини є ставленням часткового порядку:
  • Відношення підмножини рефлексивно: $B\; \backslash subset\; B$
  • Відношення підмножини антисиметрично: $(A\; \backslash subset\; B\; \backslash ;\; \backslash and\; \backslash ;\; B\; \backslash subset\; A)\; \backslash Leftrightarrow\; (A\; =\; B)$
  • Ставлення підмножини транзитивно: $(A\; \backslash subset\; B\; \backslash ;\backslash and\; \backslash ;\; B\; \backslash subset\; C)\; \backslash Rightarrow\; (A\; \backslash subset\; C)$
• Порожня множина є підмножиною будь-якого іншого, тому вона є найменшою множиною щодо відношення підмножини: $\backslash varnothing\backslash subset\; B$
• Для будь-яких двох множин $A$і $B$наступні твердження еквівалентні:
  • $A\; \backslash subset\; B.$
  • $A\; \backslash \; cap\; B\; =\; A.$
  • $A\; \backslash cup\; B\; =\; B.$
  • $B^(\backslash complement)\; \backslash subset\; A^(\backslash complement).$

Підмножини кінцевих множин

Якщо вихідна множина звичайно, то у нього існує кінцева кількість підмножин. А саме, у $n$-елементної множини існує $2^n$підмножин (включаючи порожнє). Щоб переконатися в цьому, досить помітити, що кожен елемент може входити або не входити в підмножину, а значить, Загальна кількістьпідмножин буде $n$-кратним твором двійок. Якщо ж розглядати лише підмножини $n$-елементної множини з $k\backslash le\; n$елементів, їх кількість виражається биномиальным коефіцієнтом $\backslash textstyle\backslash binom(n)(k)$. Для перевірки цього факту можна вибирати елементи підмножини послідовно. Перший елемент можна вибрати $n$способами, другий $n-1$способом, і так далі, і, нарешті, $k$-й елемент можна вибрати $n-k+1$способом. Таким чином ми отримаємо послідовність з $k$елементів, і рівно $k!$таким послідовностям відповідає одне підмножина. Значить, найдеться $\backslash textstyle\backslash frac(n(n-1)\backslash dots(n-k+1))(k=\backslash binom\{n\}\{k\}!\}$таких підмножин.

Напишіть відгук про статтю "Підмножина"

Примітки

Література

• Верещагін Н. К., Шень А.Лекції з математичної логіки та теорії алгоритмів. Частина 1. Початки теорії множин. - 3-тє вид., стереотип. – М.: МЦНМО, 2008. – 128 с. - ISBN 978-5-94057-321-0.

Формальна Математична (теоретична, символічна) 2 константи: 0 1 Див. також

Уривок, що характеризує підмножину

– Я не винен, що розмова зайшла за інших офіцерів. Можливо, не треба було говорити при них, та я не дипломат. Я потім у гусари і пішов, думав, що тут не потрібно тонкощів, а він мені каже, що я брешу… то хай дасть мені задоволення…
- Це все добре, ніхто не думає, що ви боягуз, та не в тому річ. Запитайте у Денисова, схоже це на щось, щоб юнкер вимагав задоволення у полкового командира?
Денисов, закусивши вус, з похмурим виглядом слухав розмову, мабуть не бажаючи вступати до нього. На запитання штаб ротмістра він заперечливо похитав головою.
— Ви при офіцерах кажете полковому командиру про цю гидоту, — вів далі штаб ротмістр. – Богданович (Богдановичем називали полкового командира) вас обложив.
- Не обложив, а сказав, що я неправду говорю.
- Ну так, і ви наговорили йому дурниць, і треба перепросити.
- Нізащо! – крикнув Ростов.
- Не думав я цього від вас, - серйозно і суворо сказав штаб ротмістр. – Ви не хочете вибачитись, а ви, батюшка, не тільки перед ним, а перед усім полком, перед усіма нами, ви навкруги винні. А от як: якби ви подумали та порадилися, як обійтися з цією справою, а то ви прямо, та за офіцерів, і бухнули. Що тепер робити полковому командиру? Потрібно віддати під суд офіцера і забруднити весь полк? За одного негідника весь полк осоромити? Так, чи що, на вашу думку? А на нашу думку, не так. І Богданович молодець, він вам сказав, що ви неправду кажете. Неприємно, та що робити, батюшка, самі наскочили. А тепер, як справу хочуть зам'яти, так ви з-за фанаберії якийсь не хочете вибачитися, а хочете все розповісти. Вам прикро, що ви подежурите, та що вибачитися перед старим і чесним офіцером! Який би там не був Богданович, а все чесний і хоробрий, старий полковнику, так вам прикро; а забруднити полк вам нічого? - Голос штабу ротмістра починав тремтіти. - Ви, батюшка, у полку без року тиждень; нині тут, завтра перейшли кудись до ад'ютантики; вам начхати, що будуть говорити: «Між Павлоградськими офіцерами злодії!» А нам не байдуже. То чи що, Денисов? Не все одно?
Денисов все мовчав і не ворушився, зрідка поглядаючи своїми блискучими чорними очима на Ростова.
– Вам своя фанаберія дорога, вибачитись не хочеться, – продовжував штаб ротмістр, – а нам, старим, як ми виросли, та й померти, Бог дасть, приведеться в полку, то нам честь полку дорога, і Богданович це знає. Ох, як дорога, тату! А це недобре, недобре! Там ображайтеся чи ні, а я завжди скажу правду матку. Не добре!
І штаб ротмістр підвівся і відвернувся від Ростова.
- Пг"авда, чог"т візьми! - Закричав, схоплюючись, Денисов. - Ну, Г"кістя! Ну!
Ростов, червоніючи й блідівши, дивився то на одного, то на іншого офіцера.
– Ні, панове, ні… ви не думайте… я дуже розумію, ви дарма про мене думаєте так… я… для мене… я за честь полку… та що? це насправді я покажу, і для мене честь прапора… ну, все одно, правда, я винен!.. – Сльози стояли в його очах. – Я винен, навкруги винен!… Ну, що вам ще?…
— Оце так, графе, — повертаючись, гукнув штаб ротмістр, ударяючи його. великою рукоюпо плечу.
- Я тобі кажу, - закричав Денисов, - він малий славний.
- Так краще, графе, - повторив штаб ротмістр, ніби за його визнання починаючи звати його титулом. - Ідіть і вибачтеся, ваше сіятельство, та с.
- Панове, все зроблю, ніхто від мене слова не почує, - благаючим голосом промовив Ростов, - але вибачатися не можу, їй Богу, не можу, як хочете! Як я вибачатимуся, точно маленький, прощення просити?
Денисов засміявся.
– Вам гірше. Богданович зла пам'ятний, поплатіться за впертість, – сказав Кірстен.
- Їй Богу, не впертість! Я не можу вам описати, яке почуття не можу…
– Ну, ваша воля, – сказав штаб ротмістр. — Що ж, мерзотник цей куди подівся? - Запитав він у Денисова.
- Дався взнаки хворим, завтга велено пказином виключити, - промовив Денисов.
- Це хвороба, інакше не можна пояснити, - сказав штаб ротмістр.
- Вже там хвороба не хвороба, а не трапляйся він мені на очі - уб'ю! – кровожерно прокричав Денисов.
До кімнати зайшов Жерков.
- Ти як? – раптом звернулися офіцери до того, хто увійшов.
- Похід, панове. Мак у полон здався і з армією, зовсім.
- Брешеш!
– Сам бачив.
– Як? Мака живого бачив? з руками, з ногами?
– Похід! Похід! Дати йому пляшку за таку новину. Ти як сюди потрапив?
– Знову в полк вислали за чорта, за Мака. Австрійський генерал поскаржився. Я його привітав з приїздом Мака… Ти що, Ростов, з лазні?
– Тут, брате, у нас така каша другий день.
Увійшов полковий ад'ютант і підтвердив звістку, привезену Жерковим. На завтра велено було виступати.
- Похід, панове!
- Ну, і слава Богу, засиділися.

Кутузов відступив до Відня, знищуючи за собою мости на річках Інні (у Браунау) та Трауні (у Лінці). 23 жовтня. Російські війська переходили річку Енс. Російські обози, артилерія і колони військ у середині дня тяглися через місто Енс, звідси і з того боку мосту.

У багатьох множинах можна виділити дрібніші групи елементів, об'єднані своєю загальною властивістю. Наприклад, у безлічі натуральних чисел можна виділити підмножина парних чисел, а також підмножина непарних чисел, або підмножина чисел не більше 100 і т.п.

У термінології теорії множин кажуть, що множина B є підмножиною множини A, якщо кожен елемент B є водночас і елементом множини A. Позначається це знаком включення: B ⊂ A.

З підмножини будь-якої множини можна виділити своє підмножина. Наприклад, серед учнів класу можна виділити підмножину дівчаток, а серед дівчаток виділити відмінниць. Тоді можна записати так:

Це означає, що безліч C включено B, а B включено A.

Якщо множини позначити колами, то всередині кола A буде коло B, а всередині нього коло C. Подібні малюнки називають діаграмами Ейлера-Венна.

Якщо дві множини рівні, то для них виконуються співвідношення A ⊂ B і B ⊂ A.

Якщо встановлено, що B ⊂ A, і якийсь елемент x належить B (x ∈ B), це означає, що також x ∈ A. Однак, якщо відомо, що x ∈ A, то не можна робити однозначний висновок про те, що цей елемент належить B. Це може бути не так.

Безліч- Сукупність будь-яких об'єктів. Багато позначають великими літерами латинського алфавіту - від Aдо Z.

Основні числові множини: безліч натуральних чисел і безліч цілих чисел, що завжди позначаються одними і тими ж літерами:

N- безліч натуральних чисел

Z- безліч цілих чисел

Елемент множини- це будь-який об'єкт, що входить до складу множини. Приналежність об'єкта до множини позначається за допомогою знака ∈ . Запис

читається так: 5 належить множині Zабо 5 - елемент множини Z .

Безліч діляться на кінцеві та нескінченні. Кінцева безліч- множина, що містить певну (кінцеву) кількість елементів. Нескінченна безліч- безліч, що містить безліч елементів. До нескінченних множин можна віднести безліч натуральних і цілих чисел.

Для визначення множини використовуються фігурні дужки, в яких через кому перераховуються елементи. Наприклад, запис

L = {2, 4, 6, 8}

означає, що безліч Lскладається з чотирьох парних чисел.

Термін безліч вживається незалежно від цього, скільки елементів воно містить. Множини не містять жодного елемента називаються порожніми.

Підмножина

Підмножина- це безліч, всі елементи якого є частиною іншої множини.

Візуально продемонструвати відношення множини і підмножини, що входить до нього, можна за допомогою кіл Ейлера. Кола Ейлера – це геометричні схеми, що допомагають візуалізувати відносини різних об'єктів, у нашому випадку, множин.

Розглянемо дві множини:

L= (2, 4, 6, 8) та M = {2, 4, 6, 8, 10, 12}

Кожен елемент множини Lналежить і безлічі Mотже, безліч L M. Таке співвідношення множин позначають знаком ⊂ :

L⊂M

Запис L⊂Mчитається так: безліч Lє підмножиною безлічі M .

Безліч, що складаються з тих самих елементів, незалежно від їх порядку, називаються рівнимита позначаються знаком = .

Розглянемо дві множини:

L= (2, 4, 6) та M = {4, 6, 2}

Так як обидва множини складаються з одних і тих же елементів, то L = M.

Перетин та об'єднання множин

Перетин двох множин- це сукупність елементів, що належать кожному з цих множин, тобто їхня загальна частина. Перетин позначається знаком ∩.

Наприклад, якщо

L= (1, 3, 7, 11) та M= (3, 11, 17, 19), то L∩M = {3, 11}.

Запис L∩Mчитається так: перетин множин Lі M .

З цього прикладу випливає, що перетином множин називається множина, яка містить тільки ті елементи, які зустрічаються у всіх множинах, що перетинаються.

Об'єднанням двох множинназивається безліч, що містить всі елементи вихідних множин в єдиному екземплярі, тобто якщо один і той же елемент зустрічається в обох множинах, то в нову множину цей елемент буде включений лише один раз. Об'єднання означає знак ∪ .

Наприклад, якщо

L= (1, 3, 7, 11) та M = {3, 11, 17, 19},

то L∪M = {1, 3, 7, 11, 17, 19}.

Запис L∪Mчитається так: об'єднання множин Lі M .

При об'єднанні рівних множин об'єднання дорівнюватиме кожному з даних множин:

якщо L = M, то L∪M = Lі L∪M = M.