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

Пусть А и В – произвольные множества и |A|, |B| – их мощности. Априори возможны 4 случая:

1) А эквивалентно некоторому подмножеству множества В, и В эквивалентно некоторому подмножеству множества А.

2) А эквивалентно некоторому подмножеству из В и В не эквивалентно никакому подмножеству из А.

3) В эквивалентно некоторому подмножеству из А и А не эквивалентно никакому подмножеству из В.

4) Множество А не эквивалентно никакому подмножеству из В и В не эквивалентно никакому подмножеству из А.

Замечание: Можно показать, что случай 4 невозможен, а случаи 1,2,3 записываются, как: |A|=|B|, |A|?|B|, |A|?|B|.

Теорема: (Кантора-Бернштейна): Если множество А эквивалентно подмножеству В1 множества В и множество В эквивалентно некоторому подмножеству А1 множества А, то множества А и В эквивалентны, то есть имеют одинаковую мощность.
Коротко. |A|?|B|&|B|?|A|?|A|=|B|.

Следствие: Если A принадлежит B, то |A|?|B|

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