Элементы теории множеств 2 (стр. 2 из 4)
Y = {X|XÏX}
Если множество Yсуществует, то мы должны иметь возможность ответить на следующий вопрос: YÎY? Пусть YÎY, тогда должно выполняться свойство, задающее множество Y, то есть YÏY. Пусть YÏY, то, поскольку выполняется свойство, задающее Y, приходим к тому, что YÎY, а это противоречит предположению. Получается неустранимое логическое противоречие. Вот три способа избежать этого парадокса.
1. Ограничить используемые характеристические предикаты видом
P(x) = xÎA & Q(x),
где A – известное, заведомо существующее множество (универсум). Обычно при этом используют обозначение {xÎА |Q(x)}. Для Yуниверсум не указан, а потому Yмножеством не является;
2. Теория типов. Объекты имеют тип 0, множества имеют тип 1, множества множеств — тип 2 и т. д. Yне имеет типа и множеством не является;
3. Характеристическое свойство P(x) задано в виде вычислимой функции (алгоритма). Способ вычисления значения свойства XÎXне задан, а потому Yмножеством не является.
Последний из перечисленных способов лежит в основе так называемого конструктивизма — направления в математике, в рамках которого рассматриваются только такие объекты, для которых известны процедуры (алгоритмы) их порождения. В конструктивной математике исключаются из рассмотрения некоторые понятия и методы классической математики, чреватые возможными парадоксами.
1.3 Количество элементов в множестве
Мощность множества – это обобщение понятия количества (числа элементов множества), которое имеет смысл для всех множеств, включая бесконечные.
Существуют большие, есть меньшие бесконечные множества, среди них счётное множество является самым маленьким.
В теории множеств счётное множество есть бесконечное множество, элементы которого возможно занумеровать натуральными числами. Более формально: множествоX является счётным, если существует биекция
, где 
обозначает множество всех натуральных чисел. Другими словами, счётное множество — это множество, равномощное множеству натуральных чисел.Счётное множество является «наименьшим» бесконечным множеством, т. е. в любом бесконечном множестве найдётся счётное подмножество.
Свойства:
1. Любое подмножество счётного множества конечно или счётно;
2. Объединение конечного или счётного числа счётных множеств счётно;
3. Прямое произведение конечного числа счётных множеств счётно;
4. Множество всех конечных подмножеств счётного множества счётно;
5. Множество всех подмножеств счётного множества континуально и, в частности, не является счётным.
Несчётное множество – такое бесконечное множество, которое не является счётным. Таким образом, любое множество является либо конечным, либо счётным, либо несчётным. Множество рациональных чисел и множество алгебраических чисел счётны, однако множество вещественных чиселконтинуально и, следовательно, несчётно. Два множества называются равномощными, если между ними существует биекция. Существование биекции между множествами есть отношение эквивалентности, а мощность множества — это соответствующий ему класс эквивалентности.
Свойства
· Два конечных множества равномощны тогда и только тогда, когда они состоят из одинакового числа элементов. Т.е. для конечного множества понятие мощности совпадает с привычным понятием количества.
· Для бесконечных множеств мощность множества может совпадать с мощностью его собственного подмножества, например
Z (множество целых чисел) = {-3,-2,-1,0,1,2,3…};
N (множество натуральных чисел) = {1,2,3,4,5,6,7...};
0,1,-1,2,-2,3,-3… целых чисел столько же, сколько и натуральных1,2, 3,4, 5, 6, 7…
· Теорема Кантора гарантирует существование более мощного множества для любого данного: Множество всех подмножеств множества A мощнее A, или | 2A | > | A | .
· С помощью канторова квадрата можно также доказать следующее полезное утверждение: Декартово произведение бесконечного множества A с самим собой равномощно A.
Следуя Кантору, мощность множества называется кардинальным числом и обозначается мощность такого множества A через | A | (сам Кантор использовал обозначение
). Иногда встречается обозначение 
.Мощность множества натуральных чисел
обозначается символом 
(«алеф-нуль»). Множество называется бесконечным, если его мощность 
, таким образом, счётные множества — это «самые маленькие» из бесконечных множеств. Следующие кардинальные числа в порядке возрастания обозначаются 
.Про множества, равномощные множеству всех вещественных чисел, говорят, что они имеют мощность континуума, и мощность таких множеств обозначается символом c(continuum). Континуум-гипотеза утверждает, что
.Для мощностей, как и в случае конечных множеств, имеются понятия: равенство, больше, меньше. Т.е. для любых множеств A и B возможно только одно из трёх:
1. | A | = | B | или A и B равномощны;
2. | A | > | B | или A мощнее B, т. е. A содержит подмножество, равномощное B, но A и B не равномощны;
3. | A | < | B | или B мощнее A, в этом случае B содержит подмножество, равномощное A, но A и B не равномощны.
Ситуация, в которой A и B не равномощны и ни в одном из них нет части, равномощной другому, невозможна. Это следует из теоремы Цермело. Иначе это означало бы существование несравнимых между собой мощностей (что в принципе возможно, если не принимать аксиому выбора).
Ситуация, в которой | A | > | B | и | A | < | B | , невозможна по теореме Кантора — Бернштейна.
Два множества называются эквивалентными, если их элементы можно разбить на пары, так, чтобы вне этих пар не останется ни одного элемента из этих множеств.
Множество правильных положительных дробей содержит столько же элементов, сколько и натуральных чисел.
Глава 2. Операции над множествами
Над множествами, как и над многими другими математическими объектами, можно совершать различные операции. В результате операций из исходных множеств получаются новые.
2.1 Сравнение множеств
множество элемент аксиоматический принадлежность
Множество A содержится во множестве B (множество B включает множество A), если каждый элемент A есть элемент B:
.Если
и 
, то A называется собственным подмножеством В. Заметим, что 
. По определению 
.Два множества называются равными, если они являются подмножествами друг друга:
Теорема о сравнении множеств. Для любых множеств A и B существует одна и только одна из следующих возможностей: |A| = |B|, |A|<|B|, |A|>|B|.
2.2 Основные операции над множествами
Ниже перечислены основные операции над множествами:
· объединение:
· пересечение:
· разность:
· симметрическая разность:
· дополнение:
Операция дополнения подразумевает некоторый универсум (множество U, которое содержит A):
Для лучшего понимания смысла этих операций используются диаграммы Эйлера — Венна, на которых представлены результаты операций над геометрическими фигурами как множествами точек.
Объединением двух множеств AÈB (рис. 2.2.1) – называется третье множество, каждый элемент которого принадлежит хотя бы одному из множеств A и B
Рис. 2.2.1
Пересечением множеств А∩В (рис 2.2.2), является множество, состоящее из всех тех элементов, которые принадлежат одновременно всем данным множествам.
Рис 2.2.2
Разностью множеств A \ B = A – B (рис. 2.2.3) – называется такое множество, каждый элемент которого принадлежит множеству A, но не принадлежит множеству B.
Рис. 2.2.3
Симметрическая разность ADB (рис. 2.2.4)
Рис. 2.2.4
Дополнение к множеству A называется множество всех элементов, не входящих в множество A (рис 3.2.5)