Элементы теории множеств

   2. Рефлексивность.

   

   Отношение рефлексивно.

   3. Транзитивность.

   

   Отношение транзитивно.

   => Отношение эквивалентно.

   Построим  классы эквивалентности для данного  отношения эквивалентности.

   

   Отношение называется предпорядком, если оно рефлексивно и транзитивно. Симметрический предпорядок является отношением эквивалентности.

   Пример:

   

    - предпорядок.

   Рефлексивное, транзитивное и антисимметричное отношение  на множестве А называется частичным предпорядком на множестве А. Частичный предпорядок обозначается , а обратное ему отношение - . Отношение < называется строгим порядком и определяется следующим образом: . Это отношение не является частичным порядком, так как не удовлетворяет условию рефлексивности . Если во множестве А есть элементы и , о которых нельзя сказать, что , то такие элементы называются несравнимыми.

   Частичный порядок называется линейным порядком, если любые 2 элемента сравнимы, то есть . Непустое множество А, на котором зафиксирован некоторый частичный (линейный) порядок, называется частично (линейно) упорядоченным множеством. Элемент частично упорядоченного множества называется максимальным (минимальным), если из следуем .

   Элемент называется наибольшим (наименьшим), если  для всех . Наибольший элемент обозначается , а наименьший - .

   Этих  элементов у множества может  и не быть. Например линейно-упорядоченное  множество рациональных чисел  не имеет наименьшего элемента, а максимальный равен 1.

   Верхней (нижней) гранью подмножества В частично упорядоченного множества А называется всякий элемент  для любых . Точной верхней (нижней) гранью подмножества В множества А называется наименьшая верхняя (наибольшая нижняя)  грань В. Точная верхняя и нижняя грани обозначается через и (супремум – верхняя, инфиум – нижняя).

   Линейный  порядок  на множестве А называется полным, если каждое непустое подмножество множества А имеет наименьший элемент. В этом случае А называется вполне упорядоченным. Рассмотрим непустое конечное частично упорядоченное множество А. Говорят, что покрывает , если и не существует такого , что . Если , то существуют такие элементы , что , где покрывает . Любое частично упорядоченное множество можно представить в виде схемы, в которой каждый элемент изображается точкой на плоскости, и если покрывает , то точки и   соединяют отрезком, причем точку, соответствующую , располагают ниже . Такие схемы называются диаграммами Хассе.

   Пример:

    - линейно упорядоченное множество  с обычным отношением порядка  на множестве  , не превосходящих 7.

   Элементы  этого упорядоченного обычным отношением частичного порядка  . Тогда диаграмма Хассе будет иметь вид:

     
 
 
 
 
 
 
 

§1.3 Эквивалентные множества

   Множества А и В называются эквивалентными, если существует биекция  . Биекция осуществляет взаимно однозначное соответствие между элементами множеств А и В. Обозначение - .

   Эквивалентность обладает свойствами:

   1. Рефлексивность.

   

   2. Симметричность.

   

   3. Транзитивность.

   

   При сравнении  множеств по числу содержащихся в  них элементов возникает понятие  мощности множеств.

   Мощностью множества А называется класс  всех множеств, эквивалентных множеству  А. Обозначение: . Множество А называется конечным, если

   Таким образом, мощностью конечного множества  является число его элементов. Если , то множества А и В имеют одинаковую мощность.

   Множества, не являющиеся конечными, называются бесконечными.

   Если  , то множество А называется счетным. Счетное множество – это такое множество А, все элементы которого могут быть занумерованы в бесконечную последовательность так, чтобы при этом каждый элемент получил лишь один номер и каждое натуральное число было бы номером лишь одного элемента множества А. таким образом, счетное множество – это множество значений какой-нибудь последовательности . Пустое множество относится к счетным. Мощность счетных множеств будем обозначать (алиф-нуль). Мощности произвольных множеств называются кардинальными числами. Кардинальные числа конечных множеств называются конечными, для бесконечных множеств – бесконечными.

   Теорема 1

   Всякое  подмножество счетного множества конечно  или счетно.

   Теорема 2

   Объединение счетного числа счетных множеств счетно.

   Теорема 3

   Всякое  бесконечное множество А содержит счетное множество В, при том  такое, что  есть бесконечное множество.

   Теорема 4

   Всякое  бесконечное множество А содержит подмножество , причем есть бесконечное множество.

   Пусть даны множества А и В. При их сравнении возможны случаи:

   1. Существует  взаимно однозначное соответствие  между множествами А и В. 

   2. Существует  взаимно однозначное соответствие  между множествами А и  и нет взаимно однозначного соответствия между В и .

   3. Существует  взаимно однозначное соответствие  между множествами А и , а также взаимно однозначное соответствие между В и .

   Третий  случай возможен для счетных множеств и невозможен, если А и В конечные. 

   Теорема 5 (Кантера-Бернштейна)

   Если  из двух множеств А и В каждое эквивалентно части другого, то эти  множества эквивалентны между собой.

   Теорема 6

   Множество всех подмножеств произвольного  непустого множества А имеет  мощность множества А. Если , то мощность имеет 1, в то время, как . Множество А называется несчетным, если его мощность больше мощности множества . 

§1.4 Аксиомы теории множеств

   Область исследования каждой математической дисциплины можно представить в виде набора множеств с заданной структурой. Рассмотрим в качестве примера 2 из них:

   1. Парадокс Рассела. Заключается в следующем: Пусть R есть множество всех множеств, которые не являются эквивалентами самих себя. , то есть , тогда . Если подставить вместо , получится противоречие. Оказывается, выполняется тогда и только тогда, когда .

   2. Парадокс Кантера также связан с множеством всех множеств. Обозначим его через А. Тогда - это семейство всех подмножеств данного множества А и: , . С другой стороны, для любого множества А . Тогда по теореме Кантера-Бернштейна должно быть, что , что противоречит теореме 6 (см. §1.3).

   Эти парадоксы  являются следствиями аксиоматической  теории множеств. В любой аксиоматической  теории сначала выбирают основные понятия, которые лишь поясняются, так как  они должны быть интуитивно понятны, а затем составляются аксиомы  для этих понятий. Основным понятием теории множеств является понятие самого множества. Множество образуется путем отбора определенных объектов и полностью ими определяется, при этом элементами множества могут быть объекты любой природы. Можно конкретизировать первичное понятие элемента множества и наложить на него некоторые ограничения, которые позволят избежать парадоксов. Например парадоксов можно избежать, если ввести совокупности объектов двух сортов: одну из них назвать множествами, причем множествами будут только те из классов, которые сами могут быть элементами других классов. Следует считать, что множества строятся по шагам. Для каждого текущего шага предшествующие шаги, если они имеются, осуществляются раньше текущего шага. Отношение «раньше» упорядочивает шаги. Каждое множество будет построено после некоторого количества шагов, и лишь после этого может быть использовано. Когда множество еще строится, путем отбора его элементов, то оно не готово как объект и его нельзя использовать в качестве элемента, например самого себя.

   Ограничения подобного рода помогают избежать парадоксов, однако целесообразнее ограничиться рассмотрением  только тех множеств, существование  которых может быть доказано на основе некоторой системы аксиом. Такая  система была предложена в 1908 году немецким математиком Цермелла, затем она  была несколько расширена израильским  математиком Френкелем и носит  название системы Цермелла-Френкеля .

   В систему  ZF входят следующие аксиомы:

   1. Аксиома объемности.

   Всякое  множество полностью определяется своими элементами. Два множества  равны тогда и только тогда, когда  они состоят из одинаковых элементов, то есть . 
 
 

   2. Аксиома объединения (суммы).

   Объединения всех множеств любого множества А  есть множество, то есть для любого множества А существует множество, объединенное с А, состоящее в  точности из всех элементов, принадлежащих  элементам множества А.

    .

   3. Аксиома степени (аксиома множества всех подмножеств).

   Совокупность  всех подмножеств произвольного  множества А есть множество.

    .

   4. Аксиома подстановки (замены).

   Для каждого  множества А и функции  , определенной на А, существует множество, содержащее в точности объекты для .

    .

   5. Аксиома регулярности (фундирования).

   Множество А называется фундированным, если каждое множество, содержащее А, имеет минимальный  элемент. Всякое непустое множество  А имеет элемент  , для которого элемент , то есть этот элемент минимален. Действительно, если и не пересекается с А, то есть искомый минимальный элемент А. Данную аксиому можно сформулировать  иначе: не существует бесконечно убывающей последовательности множества .

   6. Аксиома бесконечности.

   Она гарантирует  существование бесконечного множества. Это множество , где , а .

   7. Аксиома выделения.

   Для любого А из свойства F такого, что утверждение F(x) истинно либо ложно   и , состоящее в точности из тех элементов А, для которых F истинно. Название аксиомы объясняется тем, что выделяются такие , которые удовлетворяют F(x) из всех его элементов множества А. Иногда вместо аксиомы выделения в систему аксиом включаются две аксиомы: аксиома существования и аксиома существования пары .

   Для того, чтобы система аксиом теории множеств была полной, необходимо к аксиомам системы ZF добавить еще одну из двух конкурирующих друг с другом аксиом: аксиому выбора (AC) или аксиому детерминированности (AD). Система аксиом ZF с добавленной аксиомой выбора называется ZFC.

   Аксиома выбора впервые была предложена Цермелла в 1904 году.

   Пусть для каждого задано множество . Выбрав в каждом из множеств некоторый элемент , получим функцию , определенную на Х такую что для всех , то есть . Эта функция называется функцией выбора.

   Аксиома выбора.

   Для всякого  множества непустых множеств существует функция выбора, то есть , что для любого .

   Альтернативной  аксиоме выбора является предложенная в 1967 году Мычельским и Штейнгаузом  аксиома детерминированности.

    Рассмотрим  множество А бесконечных последовательностей  натуральных чисел, определяющее  следующую бесконечную игру  для двух игроков: игрок 1 пишет натуральное число , затем игрок 2 пишет натуральное число и так далее, по очереди. Если получающаяся в результате игры последовательность , то выигрывает игрок 1, в противном случае – игрок 2. Игра называется детерминированной, если либо игрок 1, либо игрок 2 имеет выигрывающую стратегию.

   Аксиома детерминированности.

    детерминировано, где  - это бэровское пространство (множество всех бесконечных последовательностей натуральных чисел).

   Аксиома детерминированности создана, чтобы  получить более привлекательное  следствие, чем те, которые дает аксиома  выбора. В общем случае, эти две  конкурирующие аксиомы дают противоположные  следствия в тех областях, где  они применимы.