Понятие мощности множества. Сравнение мощностей. Теорема Кантора-Берштейна. Операции над кардинальными числами.

Множества А и В называются эквивалентными (А~В), если существует биекция f: А↔В.

Свойства отношения эквивалентности:

1. А~А (поскольку id_A: А↔А);

2. если А~В, то В~А (т.к. из f: А↔В следует f^-1: В↔А);

3. если А~В и В~С, то А~С (т.к. из f: А↔В, g: В↔С следует f•g: А↔С).

Мощностью множества А называется класс всех множеств, эквивалентных множеству А (|А|).

Эквивалентные множества А и В называются равномощными: |A|=|B|.

Если А~n для некоторого , т.е. А имеет ровно n элементов, то множество А называется конечным (|A|=n).

Множество, не являющееся конечным, называется бесконечным. Если А~ω, то множество А называется счетным: |A|=ω. Если А~2^ω, то множество А называется континуальным или континуумом: |A|=2^ω.

Мощности множеств также иногда называют кардинальными числами.

Сравнение мощностей:

Говорят, что мощность множества А не превосходит мощности множества В: |A|≤|B|, если А эквивалентно некоторому подмножеству множества В

Теорема Кантора-Бернштейна:

Если |A|≤|B| и |B|≤|A|, то |A|=|B|.

Доказательство: Пусть f: A→B, g: B→A – разнозначные отображения, А₀=А, А₁=g(B) и А_n+2=(f•g)(A_n). Индукцией по n легко показать, что , . Пусть и . Очевидно, что и при i≠j. Т.к. f•g разнозначно отображает M_i на М_i+2 для любого , то отображение h: А→А, определенное следующим образом:

является разнозначным отображением А на . Т.к. |B|=|A₁|, |B|=|A|.

Следствие: Для любых множеств А и В выполняется только одно из соотношений: |A|=|A|, |A|<|B|, |B|<|A|.

Операции над кардинальными числами:

Пусть |A|=α, |B|=β. Тогда

1) ;

2) ;

3) .

Для конечных кардинальных чисел справедливы следующие три правила, используемые в комбинаторике:

Правило суммы: Если |A|=m, |B|=n, то .

Правило произведения: Если |A|=m, |B|=n, то .

Правило степени: Если |A|=m, |B|=n, то |A^B|=mⁿ.

Некоторые свойства бесконечных кардиналов:

ω²~ω; ω~ ; |Q|=ω; |P(U)|=2^|U|; |U|<2^|U|; если |A|>ω и |B|≤ω, то |A\B|=|A|; 2^ω~10^ω~ω^ω;

6. Yandex.RTB R-A-252273-3
   Содержание

   • Множества. Основные операции над множествами и их свойства. Диаграммы Венна. Декартово произведение множеств.
   • Отношения и бинарные отношения, область определения, область значения, обратные отношения. Произведение отношений.
   • Функции. Инъекции, сюръекции, биекции. Понятие последовательности.
   • Множество натуральных чисел. Два подхода к определению множества натуральных чисел. Аксиомы Дедекинда-Пеано. Принцип математической индукции.
   • Понятие мощности множества. Сравнение мощностей. Теорема Кантора-Берштейна. Операции над кардинальными числами.
   • Конечные, счетные, континуальные множества. Мощность булеана.
   • Матрицы бинарных отношений и их свойства. Специальные бинарные отношения.
   • Отношения эквивалентности и разбиения. Фактор-множества. Матрица отношения эквивалентности.
   • Отношения порядка. Максимальные и минимальные, наибольший и наименьший элементы частично упорядоченного множества. Диаграммы Хассе. Линейно и вполне упорядоченные множества.
   • Алгебраические системы: определение и примеры. Понятие полугруппы, моноида, группы; задание с помощью таблицы Кэли.
   • Морфизмы алгебраических систем.
   • Подсистемы. Термы сигнатуры ∑. Подсистема, порожденная множеством, ее структура.
   • Конгруэнции, фактор-алгебры, теорема о гомоморфизме.
   • 17.Многообразия. Теорема Биркгофа.
   • Решетки. Дистрибутивные решетки. Критерий дистрибутивности.
   • Булевы алгебры. Теорема Стоуна. Принцип двойственности для булевых алгебр.
   • Булево кольцо.
   • 18. Алгебры отношений. Реляционные алгебры.
   • 27. Виды и способы задания графов.
   • 28. Подграфы и части графа. Операции над графами. N-Мерные кубы.
   • Объединение: .
   • 29. Маршруты, циклы, цепи. Достижимость и связность (матрицы достижимости, контрдостижимости, связности).
   • 30. Расстояние в графах. Центральные и периферийные вершины.
   • 31. Взвешенное расстояние. Алгоритм Форда-Беллмана.
   • 32. Степени вершин. Эйлеровы графы, циклы, цепи. Алгоритм построения эйлерова цикла.
   • 33. Гамильтоновы графы. Постановка задачи коммивояжера.
   • 34. Деревья, леса. Остовы графов. Цикломатическое число, коранг. Алгоритм построения остова минимального веса. Обходы графов по глубине и ширине.
   • 35. Упорядоченные и бинарные деревья. Соответствия между ними.
   • 36. Фундаментальные циклы, разрезы. Матрицы фундаментальных циклов, разрезов.
   • 37. Раскраска графов. Планарные графы.
   • 38. Формулы алгебры логики, их таблицы истинности.
   • 39. Булевы функции, способы их задания. Представления булевых функций формулами.
   • 40. Эквивалентность формул.
   • 41. Двухэлементная булева алгебра. Алгебра булевых функций. Фактор-алгебра алгебры формул.
   • 42. Дизъюнктивные и конъюнктивные нормальные формы. Алгоритм приведения формулы к днф и кнф.
   • 43. Теорема Шеннона. Теорема о функциональной полноте. Способы построения сднф и скнф.
   • 44. Импликанты, простые импликанты. Сокращенные, тупиковые, минимальные нормальные формы. Алгоритм Квайна построения мднф.
   • 45. Карты Карно. Построение мднф с помощью карт Карно.
   • 46. Принцип двойственности. Самодвойственные функции.
   • 47. Теорема Жегалкина. Способы построения полиномов Жегалкина. Линейные функции.
   • 48. Классы Поста. Полные системы булевых функций. Теорема Поста. Базисы.
   • 49. Логические сети. Реализация булевых функций контактными схемами и схемами из функциональных элементов.

   Yandex.RTB R-A-252273-4