Образовательный блог – всё для учебы

Пусть А есть некоторое множество и P(A) есть множество всех подмножеств множества А. Очевидно, что P(A) и потому мощность |A|?|P(A)|.

Теорема: (Кантора). |A|<|P(A)|.

Доказательство: Покажем, что |A|?|P(A)|. Допустим противное. Мощность |A|=|P(A)|. Тогда существует P(A). Пусть множество А₁={a принадлежит множеству А: а принадлежит множеству ?(а)} , А₂={a принадлежит множеству А: а не принадлежит множеству ?(а)} , тогда А₂=А – А₁. Множество А₂ принадлежит P(A). ?(b) для некоторого b из множества А.

Каждый элемент из А попадает либо в А₁, либо в А₂, b принадлежит ?(b) = A₂.

Но по построению А₁. Противоречие: b принадлежит A₁ и A₂. Если b принадлежит A₂, то b не принадлежит ?(b) = A₂ . Противоречие: b принадлежит A₂ и не принадлежит A₂ одновременно. Следовательно, наше предположение |A| = |P(A)|неверно и потому мощности не равны и |A| < |P(A)|.

Замечание: Иногда множество P(A) всех подмножеств множества А обозначается через 2^A, тогда |P(A)| через 2^|A|. Тогда по теореме |A| < 2^|A|. По теореме Кантора, начиная от множества А, можно построить возрастающую последовательность кардинальных чисел: |A| < 2^|A| < 2^2|A|<.... Начиная с множества натуральных чисел N, можно построить возрастающую последовательность кардиналов. Она обозначается N₀ (алеф «ноль»).
N₀ < 2^N₀ = C = N₁ < 2^N₁ = N₂ < 2^N₂ = N₃ < ... , где N₀, N₁=C, N₂=2^C, N₃=2² (N – алеф, С – готическое «це») есть последовательная счетная мощность, континуум, гипер-континуум, гипер-гипер-континуум. Кантор поставил вопрос о существовании промежуточной мощности между счетной и континуумом и о существовании промежуточной мощности между N₀ и N₁ (континуум гипотезы). Гедель и Коэн показали, что обе гипотезы не могут быть доказаны (Гедель) и опровергнуты (Коэн) в аксиоматической теории множеств, то есть обе гипотезы не зависят от аксиом теории множеств.

1. Сравнение мощностей. Теорема Кантора-Бернштейна.
2. Мощность континуума
3. Булевы решетки и булевы алгебры
4. Верхняя и нижняя оценки для хроматического числа. Внутренне и внешне устойчивые множества вершин графа
5. отношения. Отношение эквивалентности, фактор-множество
6. Множества и операции над ними
7. Правило суммы и правило произведения
8. Линейные рекуррентные уравнения(ЛРУ) однородные и неоднородные с переменными коэффициентами
9. Подсчет числа размещений, перестановок, сочетаний без повторов и с повторами
10. Функции и отношения, их свойства
11. Многочлен циклов (цикловой индекс), теорема Пойа
12. Функции алгебры логики
13. Подпространство четных подграфов
14. Равномерно интегрируемые случайные величины
15. Матричная теорема Кирхгофа о деревьях
16. СДНФ и СКНФ
17. Потоки в транспортных сетях