Множества. Основные операции над множествами и их свойства. Диаграммы Венна. Декартово произведение множеств
Понятие мощности множества. Сравнение мощностей. Теорема Кантора-Берштейна. Операции над кардинальными числами
жүктеу/скачать 318 Kb.
|
1. Теория множеств
| Понятие мощности множества. Сравнение мощностей. Теорема Кантора-Берштейна. Операции над кардинальными числами.
Множества А и В называются эквивалентными (А~В), если существует биекция f: А↔В. Свойства отношения эквивалентности: А~А (поскольку idA: А↔А); если А~В, то В~А (т.к. из f: А↔В следует f-1: В↔А); если А~В и В~С, то А~С (т.к. из 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 – разнозначные отображения, А0=А, А1=g(B) и Аn+2=(f•g)(An). Индукцией по n легко показать, что , . Пусть и . Очевидно, что и при i≠j. Т.к. f•g разнозначно отображает Mi на Мi+2 для любого , то отображение h: А→А, определенное следующим образом: является разнозначным отображением А на . Т.к. |B|=|A1|, |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, то |AB|=mn. Некоторые свойства бесконечных кардиналов: ω2~ω; ω~ ; |Q|=ω; |P(U)|=2|U|; |U|<2|U|; если |A|>ω и |B|≤ω, то |A\B|=|A|; 2ω~10ω~ωω; жүктеу/скачать 318 Kb. Достарыңызбен бөлісу:
|