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

 

Определение натурального множества. Всякое множество, удовлетворяющее свойствам

1. 1ÎN
2. "n, nÎN Þ n + 1ÎN
3. "n, nÎN, n¹1 Þ $ yÎN, n = y +1

называется множеством натуральных  чисел.

 

Множество N удовлетворяет аксиомам Пеано:

1. 1ÎN.
2. "n, nÎN Þ n’ÎN.
3. "nÎN Þ n’¹1.
4. "nÎN, mÎN, n’=m’ Þ n=m.
5. .

Где n’ = n+1.

 

Данное множество – множество  натуральных чисел N = {1, 2, 3, …}.

Замечание. Множество ={0, 1, 2, 3…} называют расширением натурального множества.

Стандартные обозначения некоторых  множеств.

N – множество всех натуральных чисел.

Z – множество всех целых чисел.

Z⁺ – множество целых неотрицательных чисел.

Z^– – множество целых неположительных чисел.

Q – множество всех рациональных чисел.

R – множество всех действительных чисел.

R⁺ – множество неотрицательных действительных чисел.

R^– – множество неположительных действительных чисел.

 

3.3. Конечные и бесконечные множества

 

Конечное множество - множество, состоящее  из конечного числа элементов.

Пример. A = {1, 2, 3, 4, 5}.

Основной характеристикой конечного множества является число его элементов. Теория конечных множеств изучает правила: как, зная количество элементов некоторых множеств, вычислить количество элементов других множеств, которые составлены из первых с помощью некоторых операций.

Бесконечное множество - непустое множество, не являющееся конечным.

Пример. Множество натуральных чисел является бесконечным.

 

3.4. Счетные множества и их свойства

 

Определение взаимнооднозначного  соответствия. Пусть А и В два множества. Правило j которое каждому элементу а множества А соотносит один и только один элемент b множества В, причем каждый элемент bÎВ оказывается соотнесенным одному и только одному аÎА, называется взаимнооднозначным соответствием между множеством А и множеством В.

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

Определение счетного множества. Пусть N множество всех натуральных чисел N={1, 2, 3, . . .}, тогда всякое множество А эквивалентное множеству N будет называться исчислимым, или счётным множеством.

Пример. А={1, 4, 9, 16, . . . ,n , . . .}; B={3, 6, 9, 12, . . . ,3n, . . . }.

 

Наименьшей бесконечной мощностью  является (алеф ноль) — мощность множества натуральных чисел.

Теорема (необходимое и достаточное условие счетности множества). Для того чтобы множество Х было счётным необходимо и достаточно, чтобы его можно было представить в форме последовательности:

Х={x

, x , x , …, x , …} (*).

Доказательство необходимости. Пусть множество Х счетное, то из определения счётного множества следует существование взаимно однозначного соответствия j между множеством Х и множеством натуральных чисел N. Достаточно обозначить через х_п, тот из элементов множества Х, который в соответствии с j отвечает числу n,чтобы получить представление множества Х в форме (*).

Доказательство достаточности. Если множество Х представлено в форме (*), то достаточно каждому его элементу х, соотнести индекс n этого элемента, чтобы получить взаимно однозначного соответствия j между множеством Х и множеством натуральных чисел N, так что из определения счётного множества следует, что множество Х счётное.

 

Замечание. Все счетные множества эквивалентны между собой.

Свойства счетных множеств:

1. Всякое подмножество счетного множества конечно либо счетно.
2. Объединение конечного либо счетного множества счетных множеств конечно либо счетно.
3. Всякое бесконечное множество содержит счетное подмножество.
4. Если к бесконечному множеству А присоединить конечное либо счетное множество В, то от этого мощность множества не изменится: АÈВ ~ А.

 

3.5. Примеры счетных множеств

 

Множество целых чисел Z является счетным (Z ~ N).

Доказательство. Пронумеруем числа из Z:

 

N	1	2	3	4	…
Z	0	-1	1	2	…

 

Рациональные числа R образуют счётное множество.

Доказательство.

Любое рациональное число можно представить в виде : , mÎZ, nÎN.

Введем понятие высоты h рационального числа: h = |m| + n.

Каждой высоте соответствует конечное число рациональных чисел:

h = 1: .

h = 2: .

h = 3: .

h = 4 …

 

Приписывая последовательно этим рациональным числам номера 1, 2, 3… мы пронумеруем все рациональные числа. Следовательно, множество рациональных чисел счетно согласно определению.

 

3.6. Несчетные множества. Мощность континуума

 

Теорема. Мощность действительных чисел отрезка [0;1] больше чем счетное.

Доказательство (от противного).

Предположим, мощность отрезка  [0;1] счетна. Т.е. можно установить взаимнооднозначное соответствие:

1 ~ 0.3751…

2 ~ 0.2151…

3 ~ 0.2216…

…

Построим число a из пронумерованных чисел согласно правилам:

1. Из первого числа возьмем первую цифру после запятой, из второго числа – вторую, из третьего – третью и так далее.
2. Если текущая цифра равна единице, то заменим ее на двойку. В противном случае цифру заменим на единицу.

В результате получим: a = 0.122…

a Î [0;1] и числу a соответствует nÎN.

Это противоречит тому, что, когда  мы изменили a, мы изменили цифру, стоящую на n-ном десятичном месте. Следовательно, a не может стоять на n-ном месте. Следовательно, мы пришли к противоречию и, значит, мощность множества действительных чисел несчетна.

Мощность множества всех действительных чисел (или, что то же, множества всех точек числовой оси) обозначается символом c (“континуум”). Поскольку множество всех действительных чисел несчётно, то א₀ < c.

Континуум – не самая большая  из бесконечных мощностей. Так, мощность множества всех подмножеств точек  числовой оси больше, чем мощность самого множества всех точек оси. Она обозначается 2^c и называется гиперконтинуумом.

 

ГЛАВА 4

АКСИОМАТИКА ТЕОРИИ МНОЖЕСТВ

 

4.1. Аксиомы теории множеств

 

Современная теория множеств строится на системе аксиом — утверждений, принимаемых без доказательства, из которых выводятся все теоремы  и утверждения теории множеств.

Система аксиом Цермело — Френкеля (ZF) является стандартной системой аксиом для теории множеств. Эта и подобные ей системы аксиом любопытны потому, что любая математическая теория может быть «переведена» на язык теории множеств таким образом, что теоремы этой теории станут теоремами о множествах, доказуемыми из аксиом ZF.

 

1. Аксиома объемности. Если два множества имеют одни и те же элементы, они тождественны.

"A, B: A=B Û "c, cÎAÛ cÎB.

2. Аксиома пустого множества. Существует пустое множество Æ, которое не содержит элементов.

$Æ: "a, aÏÆ.

3. Аксиома пары. Для любых множеств A и B существует множество C такое, что A и B являются его единственными элементами. Множество C обозначается {A, B} и называется неупорядоченной парой A и B. Если A = B, то C состоит из одного элемента.

"A, "B, $C: "D, DÍCÛ(D=A Ú D=B).

4. Аксиома объединения. Для любого множества A существует множество B=a₁Èa₂È…Èa_n – объединение всех элементов множества A, состоящее из тех и только тех элементов, которые содержатся в элементах множества А.

"A, $B: "C, CÍB Û $D, (CÍD Ù DÍA).

5. Аксиома бесконечности. Существует множество, которое содержит ∅ в качестве своего элемента, и такое, что если а есть элемент этого множества, тогда последовательность aÈ{a} есть также элемент этого множества.

$w: ÆÎw Ù "x, xÎw Þ {x,{x}}Îw.

6. Аксиома регулярности. Если A – непустое множество, тогда имеется подмножество В множества A, такое, что не имеется множеств, которые принадлежат обоим множествам А и В.

7. Аксиома выделения. Любому множеству A и свойству j отвечает множество B, элементами которого являются те и только те элементы A, которые обладают свойством j.

"A $B: "c, cÎB Û (cÎA Ù j(c)).

8. Аксиома основания. Каждое непустое множество S содержит подмножество A такое, что SÇA=Æ.

"S, S¹Æ Þ $A, AÍS Ù AÇS=Æ.

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

 

Приведенный список аксиом не является каким-то каноническим. Возможны другие перечни и другие аксиомы.

Математики и философы, как уже  было отмечено, расходятся в понимании  основной цели аксиоматизации теории множеств. Многие полагают (это стало  “учебной” точкой зрения), что суть аксиоматизации состоит в ограничении области множеств, с которыми математики уже имели и имеют дело, с целью недопущения парадоксов.

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

 

4.2. Парадоксы теории множеств

 

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

 

Аксиома Фреге. Для любого свойства Р существует множество {x | Р(x)} всех объектов х, обладающих свойством Р.

Парадокс Рассела. Пусть X - множество всех множеств, которые не являются собственными элементами. Тогда X в том и только том случае является собственным элементом, когда оно не является собственным элементом.

Доказательство. Предположим, что XÎX. Тогда X является собственным элементом и, значит, не входит в X по определению X. Таким образом, XÎXÞXÏX. С другой стороны, если XÏX то X не является собственным элементом и, значит, входит в X по определению X. Таким образом. XÏXÞ XÎX.

 

Классические формулировки парадокса Рассела.

Парадокс Рассела можно сформулировать и не используя теорию множеств. Вот три классические формулировки этого парадокса.

Парадокс парикмахера. Вождь афинской демократии Клисфен повелел, чтобы единственный парикмахер города брил тех и только тех граждан Афин, которые не бреются сами. Должен ли парикмахер брить себя?

Парадокс каталога. Библиотека Борхеса решила составить библиографический каталог, в который входят те и только те каталоги, которые не включают себя. Включает ли такой каталог себя?

Парадокс самоуважения. Имеет ли профессор Конте самоуважение, если он уважает только тех, кто не уважает себя?

 

Объяснение логических парадоксов. Легко видеть, что в действительности все эти парадоксы не содержат в себе ничего парадоксального и математики повседневно сталкиваются с подобными ситуациями. Чтобы объяснить, в чем тут дело, дадим еще одну эквивалентную формулировку парадокса Рассела.

 

Парадокс Пиглета. Пусть п - такое целое число, которое одновременно больше и меньше нуля. Тогда п в том и только том случае является положительным, когда оно является отрицательным.

Но ведь такого числа не существует. Именно так: все “логические парадоксы” (не путать с “лингвистическими” или “семантическими” парадоксами, типа парадокса лжеца) построены по следующей схеме: предположим, что существует некоторый объект X. Тогда этот объект X одновременно обладает и не обладает некоторым свойством. Но это в точности и значит, что требуемого объекта X не существует, именно так устроены доказательства от противного, например, доказательство иррациональности числа или бесконечности множества простых чисел. Единственная разница состоит в том, что в парадоксе Пиглета противоречивость условия очевидна сразу, а в парадоксе Рассела условие не кажется противоречивым - хотя и является таковым. Таким образом, парадокс Рассела всего лишь доказывает (от противного), что не существует множества Y = {X | XÏX} всех множеств, не являющихся собственными элементами, и, тем самым, не для любого свойства Р обязано существовать множество {х | Р(х)}. Но никто из серьезных математиков никогда и не утверждал, что любое свойство должно определять множество.