1.4. Эквивалентные, конечные и бесконечные множества Множества A и B называются эквивалентными, если существует биекция B A f : Как известно, биекция осуществляет взаимно однозначное соответствие между элементами множеств A и B . Эквивалентные или равномощные множества обозначаются B A . По определению эквивалентность обладает свойствами: 1) рефлексивности A A id A A A :
; 2) симметричности: если B A
, то A B
(так как если B A f : , то A B f : 1 ); 3) транзитивности: если B A
и C B
, то C A
(так как если B A f : и C B g : , то C A g f : , см. подразд. 1.2). При сравнении множеств по числу содержащихся в них элементов возникает понятие мощности множества. Мощностью множества A называется класс всех множеств, эквивалентных множеству A . Обозначение мощности A . Множество A называется конечным, если существует N n такое, что n A ,..., 2 , 1
Тогда n A . Таким образом, мощностью конечного множества является число его элементов. Если B A
, то множества A и B имеют одинаковую мощность. Множество, не являющееся конечным, называется бесконечным. Если N A
, то множество A называется счетным. Счетное множество – это такое множество A , все элементы которого могут быть занумерованы в бесконечную последовательность ,..., , 2 1 n a a a так, чтобы при этом каждый элемент получил лишь один номер n и каждое натуральное число n было бы номером лишь одного элемента множества A . Таким образом, счетное множество это множество значений какой-нибудь последовательности B N f : Пустое множество по определению относится к счетным. Мощность счетных множеств
12 принято обозначать через 0 . Мощности произвольных множеств называются кардинальными числами. Кардинальные числа конечных множеств называются конечными, для бесконечных множеств – бесконечными. Рассмотрим некоторые результаты, относящиеся к счетным множествам. Теорема 1.2. Всякое подмножество счетного множества конечно или счетно. Доказательство. Пусть A - счетное множество, A B . Если B , то оно счетно по определению. Пусть B . На основании определения счетного множества все элементы множества A занумерованы, а само множество может быть представлено в виде бесконечной последовательности ,... ,..., , 2 1 n a a a Если A B , то 1 n a - первый элемент множества B , являющийся одновременно членом последовательности ,... ,..., , 2 1 n a a a , 2 n a - второй элемент и так далее. Возможны два случая, либо после конечного числа шагов все элементы множества B будут исчерпаны, либо получится бесконечная последовательность ,... ,..., , 2 1 k n n n a a a В первом случае множество B будет конечным, во втором – счетным. Теорема 1.3. Объединение счетного числа счетных множеств счетно. Пример 1. Пусть дан некоторый алфавит A , т. е. набор знаков, называемых буквами. Любая конечная последовательность букв называется словом. Пустое слово обозначается символом . Если алфавит конечен, то множество B всех слов алфавита A счетно. Пусть 1 , ,..., , 2 1 k A A A k A . Определим последовательность B N f : таким образом: 0 f , если 0 m , то 1 2 1 n n n n A A A A m f m m , где i n A - i -й разряд записи слова в k -ичной системе счисления. Очевидно, что произвольное слово 1 2 1 n n n n A A A A m m является значением функции m f при значении аргумента m m m m k n k n k n n 1 1 1 2 1 , т. е. B R f . Итак, B N f : , B R f , следовательно, множество B счетно, так как B эквивалентно счетному множеству N Пример 2. Множество всех рациональных чисел Q счетно. Всякое рациональное число записывается в виде несократимой дроби n m , где m - целое число, n - положительное целое число. Следовательно, множество Q эквивалентно множеству таких дробей. Множество дробей вида n m является, в свою очередь, подмножеством всех слов в алфавите / , , 9 ,..., 2 , 1 , 0 . Таким образом, Q , являясь подмножеством счетного множества, счетно. Теорема 1.4. Всякое бесконечное множество A содержит счетное множество B , притом такое, что B A \ есть бесконечное множество. Теорема 1.5. Всякое бесконечное множество A содержит подмножество A B , причем B A \ есть бесконечное множество. Так как никакое конечное множество не содержит части, эквивалентной всему множеству, то последняя теорема выражает свойство, присущее лишь бесконечным множествам и только им и может служить условием, поясняющим определение бесконечных множеств. В случае бесконечных множеств понятие мощности является обобщение понятия количества элементов конечного множества. Однако любые количества либо равны, либо одно из них больше другого, поэтому возникает вопрос о сравнимости мощностей. Пусть даны два множества A и B . При их сравнении возможны следующие случаи: а) существует взаимно однозначное соответствие между A и B ; - первая буква древнееврейского алфавита, называется «алеф», выражение 0 читается: «алеф-нуль».
13 б) существует взаимно однозначное соответствие между A и B C и нет взаимно однозначного соответствия между B и A D ; в) существует взаимно однозначное соответствие между A и B C , а также взаимно однозначного соответствия между B и A D Третий случай невозможен, если A и B - конечные множества, для счетных множеств этот случай может осуществляться. Теорема 1.6. (Кантора – Бернштейна ) Если из двух множеств A и B каждое эквивалентно части другого, то эти два множества эквивалентны между собой, т. е. если B A и A B , то B A . Доказательство. Пусть B B A 1
и A A B 1
. Тогда, если 1 B A , то 2 1 A B и 2 1 A A A в силу взаимно однозначного соответствия при эквивалентности. Одновременно 1 A B . Таким образом, показав, что 1 A A , докажем, что B A , так как B A 1 . Итак, рассмотрим какое- нибудь взаимно однозначное отображение f . Так A 1 A 2 A B 1 B как 2 1 1
,
A B B A , 2 A A f и 2 A A . Аналогично 3 A 2 3 1 A A A A f и 3 1 A A , 3 4 1 2 A A A A f и 4 2 A A и так далее. В силу того же взаимно однозначного соответ- Рис. 1.11. ствия 3 2 1 \ \ A A A A f , 4 3 2 1 \ \ A A A A f , 5 4 3 2 \ \ A A A A f (см. рис 1.11). Но тогда
\ \ \ 5 4 3 2 1 A A A A A A \ \ \
7 6 5 4 3 2 A A A A A A Введем вспомогательное множество 3 2 1 A A A A D , тогда \ \ 2 1 1 A A A A D A , \ \ 3 2 2 1 1 A A A A D A , так как 2 1 1 2 1 A A A A A A A A 2 1 1 3 1 2 1 1 3 2 1 A A A A A A A A A A A A A A 1 1 3 1 1 2 1 2 1 1 3 1 2 A A A A A A A A A A A A A A A A A A A A A A A A A A A A 2 1 3 2 1 3 2 1 2 2 , аналогично выражается 1 A . Но равенства для A и 1 A можно переписать следующим образом \ \ \ \ 3 2 1 4 3 2 1 A A A A A A A A D A , 4 3 2 1 1 \ \ A A A A D A \ \ 5 4 3 2 A A A A . В этих выражениях первые скобки в правых частях одинаковы, а во вторых скобках стоят эквивалентные множества. Устанавливая между элементами множеств \ \ 3 2 1 A A A A и \ \ 5 4 3 2 A A A A взаимно однозначное соответствие и заставляя соответствовать самому себе каждый элемент множества \ \ 4 3 2 1 A A A A D , получим взаимно однозначное соответствие между элементами множеств A и 1 A , т. е. B A и B A Мы уже упоминали о том, что мощности бесконечных множеств должны быть сравнимы между собой, т. е. должны существовать различные бесконечные мощности. Это действительно так, для каждого множества A существует множество, мощность которого больше мощности множества A Георг Кантор (1845 – 1918) – немецкий математик. Сергей Натанович Бернштейн (1880 – 1966) – советский математик.
14 Теорема 1.7. Множество всех подмножеств произвольного непустого множества A имеет мощность большую, чем мощность множества AЭта теорема верна и для пустого множества A. Для A множество всех подмножеств имеет вид , т. е. имеет мощность 1, в то время как 0 Рассмотрим множество всех отображений множества N в множество 1 , 0 MВсякое такое отображение, ставя каждому натуральному числу в соответствие 0 или 1, приводит к построению бесконечной последовательности ,... ,..., , 2 1 niii, где 0 ni или 1, т. е. бесконечной десятичной дроби ,... ,..., , , 0 2 1 niii Таким образом, множество всех бесконечных двоичных дробей имеет мощность, равную мощности всех подмножеств множества N. Так как 0 N, тогда мощность множества всех бесконечных двоичных дробей равна 0 2 (см. задачу 1.3.13 б). Множество A называется несчетным, если его мощность больше мощности множества N. Нам известно, что множество всех рациональных чисел счетно (пример 2), далее мы покажем, что множество всех действительных чисел несчетно. Если 0 2 A, то множество A называется континуальным или континуумом и обозначается через c . Эта мощность несчетна ( 0 0 2 ). Теорема 1.8. Множество всех действительных чисел имеет мощность континуума 0 2 c и, следовательно, несчетно. Доказательство. Сначала докажем, что множество действительных чисел R находится во взаимно однозначном соответствии с действительными числами интервала 1 , 0 Рассмотрим две функции tgxxf 1 и xabaxf 2 . Очевидно, что Rtgxxf 1 2 π , 2 π , аналогично, 2 π , 2 π 1 , 0 2 xabaxf при 2 π a, 2 π b. Таким образом, 2 π , 2 π R, 1 , 0 2 π , 2 π , т. е. 1 , 0 RОбратим еще раз внимание на процесс разложения действительных чисел в двоичные дроби. Нами уже показано, что мощность множества всех бесконечных двоичных дробей равна мощности всех подмножеств множества N, т. е. мощности континуума (см. комментарий к теореме 1.7). Рассмотрим процесс последовательного разбиения интервала 1 , 0 на две равные части ;... 1 , 4 3 , 4 3 , 2 1 , 2 1 , 4 1 , 4 1 , 0 ; 1 , 2 1 , 2 1 , 0 Длины этих отрезков, равные n2 1 , обозначим через niii,..., , 2 1 , где niii,..., , 2 1 независимо друг от друга принимают значение 0 или 1, при этом 0 , ,..., , 1 2 1 niii и 1 , ,..., , 1 2 1 niii - левая и правая половина 1 2 1 ,..., , niii. Возьмем любое 1 , 0 x. Пусть сначала x не равен Nmmn , 2 , т. е. не совпадает с концом или началом какого-нибудь отрезка. Тогда x представимо в виде ,..., , 2 1 niii, где 0 ki или 1, а последовательность ,..., , 2 1 niii есть последовательность двоичных знаков числа x . Пусть теперь 1 , 0 x и nmx2 , где дробь nm2 несократима. Тогда x является общим концом двух отрезков, следовательно, x можно представить в виде двух последовательностей двоичных знаков ,... 1 , 1 , 1 , 0 , ,..., , 1 2 1 niii и ,... 0 , 0 , 0 , 1 , ,..., , 1 2 1 niii Continuum – непрерывное (лат.), поэтому мощность всех действительных чисел 0 2 c называется мощностью континуума. 15 Таким образом, каждое действительное число 1 , 0 x имеет либо одно двоичное разложение 0 2 1 niii, либо два двоичных разложения 0111 0 1 2 1 niii и 1000 0 1 2 1 niii, причем второй случай наступает тогда и только тогда, когда число x двоично-рационально. Так как 1 , 0 R, а множество двоично- рациональных чисел счетно (см. пример 2), то достаточно доказать, что множество всех не двоично-рациональных чисел интервала 1 , 0 имеет мощность c (см. задачу 1.5.?). Но это множество находится во взаимно однозначном соответствии с множеством непериодических бесконечных двоичных дробей вида 0 2 1 niii, которое имеет мощность континуума. Таким образом, c R1.5. Практическое занятие № 2. Кардинальные числа 1.5.1. Доказать, что а) всякое подмножество конечного множества конечно; б) объединение конечного числа конечных множеств конечно. 1.5.2. Доказать, что множество тогда и только тогда бесконечно, когда оно эквивалентно некоторому собственному подмножеству. 1.5.3. Доказать, что а) если A бесконечно и B - конечное или счетное множество, то ABA ; б) если A бесконечно и несчетно, B конечно или счетно, то ABA\ 1.5.4. Доказать, что множество целых чисел счетно. 1.5.5. Доказать, что множество многочленов от одной переменной с целыми коэффициентами счетно. 1.5.6. Доказать, что а) 1 , 0 1 , 0 1 , 0 1 , 0 ; б) dcba, , , где dcba , 1.5.7. Доказать , что множества точек двух окружностей эквивалентны. 1.5.8. Доказать, что множество всех подмножеств AP множества A имеет мощность, большую чем A1.5.9. Доказать, что не существует множества, содержащего все множества. 1.5.10. Пусть A - счетное множество точек на действительной прямой. Можно ли выбрать a так, чтобы AAxax? 1.6. Аксиомы теории множеств Теория множеств является универсальным фундаментом для сего здания математики. Область исследования каждой математической дисциплины можно представить в виде набора множеств заданной структуры. Однако свободное использование понятий интуитивного теоретико-множественного универсума иногда приводит к противоречиям. Приведем в качестве примера два из них. Парадокс Рассела заключается в следующем. Пусть R есть множество всех множеств, которые не являются элементами самих себя, т. е. xxxR . Тогда для любого множества x будет xxRx . Если Бертран Артур Уильям Рассел (1872 – 1970) – английский математик. 16 подставить R вместо x , получится противоречие: оказывается RR выполняется тогда и только тогда, когда RR Парадокс Кантора также связан с множеством всех множеств. Обозначим его A, тогда AP - семейство всех подмножеств данного множества A и AAP , т. е. AAP Но с другой стороны для любого множества A AAP . Тогда по теореме Кантора – Бернштейна должно быть AAP , что противоречит теореме 1.7. Во многом эти парадоксы следствие аксиоматической теории множеств. Как известно, в любой аксиоматической теории сначала выбирают основные понятия, которые лишь поясняются, ибо должны быть интуитивно понятны, а затем составляются аксиомы для этих понятий. Основным понятием теории множеств является понятие самого множества. Множество образуется путем отбора определенных объектов и полностью ими определяется, при этом элементами множеств могут быть объекты любой природы. Можно конкретизировать первичное понятие элемента множества и наложить на него некоторые ограничения, которые позволят избежать парадоксов. Например, парадоксов можно избежать, если ввести совокупности объектов двух сортов, одну из них называть классами, другую – множествами, причем множествами будут только те из классов, которые сами могут быть элементами других классов. Кроме того, следует считать, что множества строятся по шагам. Для каждого текущего шага предшествующие шаги, если они имеются, осуществляются раньше (в логическом, а не во временном смысле) текущего шага. Таким образом, отношение «раньше» упорядочивает шаги. Каждое множество будет построено после некоторого количества шагов и лишь после этого может быть использовано. Когда же множество еще строится путем выбора его элементов, то оно еще не готово как объект и его нельзя использовать в качестве элемента, например, самого себя. Ограничения подобного рода позволяют избежать парадоксов, однако целесообразнее ограничиться рассмотрением только тех множеств, существование которых может быть доказано на основе некоторой системы аксиом. Такая система предложена Э. Цермело в 1908 году, затем она была несколько расширена А. Френкелем и носит название системы аксиом Цермело-Френкеля (ZF). В систему ZF входят следующие аксиомы. 1) Аксиома объемности (экстенсиональности). Всякое множество полностью определяется своими элементами. Два множества равны тогда и только тогда, когда они состоят из одинаковых элементов: BABxAxx 2) Аксиома объединения (суммы). Объединение всех элементов любого множества Aесть множество, т. е. для любого множества A существует множество A , состоящее в точности из всех элементов, принадлежащим элементам множества A. Если A , то AbbaaA некоторого для / 3) Аксиома степени (аксиома множества всех подмножеств). Совокупность всех подмножеств произвольного множества A является множеством. Если A , то ABBAP 4) Аксиома подстановки (замены). Для каждого множества A и функции f, определенной на A, существует множество, содержащее в точности объекты xf для Ax xfyAxyB Эрнст Фридрих Фердинанд Цермело (1871 – 1953) – немецкий математик. Абрахам Адольф Френкель (1891 – 1965) – израильский математик. 17 5) Аксиома регулярности (фундирования). Множество A называется фундированным, если каждое множество, содержащее A, имеет минимальный элемент. Всякое непустое множество A имеет элемент Aa , для которого Aa, т. е. этот элемент минимален. Действительно, пусть Aa ; если a и A не пересекаются, то a и есть искомый минимальный элемент множества A. Эту аксиому можно сформулировать и таким образом: не существует бесконечно убывающей последовательности множеств 2 1 aa6) Аксиома бесконечности. Она гарантирует существование бесконечного множества – множества натуральных чисел ,... ,..., 2 , 1 , 0 nN , где 0 , nnn 1 7) Аксиома выделения. Для любого множества A и свойства F такого, что для любого Aa утверждение xF либо истинно, либо ложно, существует множество 1 aFAaaB, состоящее в точности из тех элементов множества A, для которых F истинно. Название аксиомы объясняется тем, что мы выделяем такие Aa , которые удовлетворяют xF, из всех элементов множества AИногда вместо аксиомы выделения в систему аксиом включают две аксиомы: а) аксиому существования пустого множества и б) аксиому существования пары: если A и B , то BA, . Эти две аксиомы можно легко вывести из приведенных семи основных аксиом. Например, xxx . Пусть A - произвольное множество. Оно существует по аксиоме бесконечности. Тогда Axxxx и по аксиоме выделения Axxxx , Для того, чтобы система аксиом теории множеств была полной, т. е. адекватно формализовала все известные приемы математических рассуждений, необходимо к аксиомам системы ZF добавить еще одну из двух конкурирующих друг с другом аксиом: а) аксиому выбора (AC) или б) аксиому детерминированности (AD). Система аксиом ZF с добавленной аксиомой выбора называется системой аксиом ZFC. Аксиома выбора предложена Э. Цермело в 1904 году. Пусть для каждого Xx задано множество xA. Выбрав в каждом из множеств xA некоторый элемент xAy , получим функцию f, определенную на X и такую, что xAxf для всех Xx , т. е. yxf . Эта функция называется функцией выбора. Аксиома выбора. Для всякого семейства непустых множеств xA существует функция выбора, т. е. xA xxAAPf : , что XXf для XAXx, . Наиболее «прозрачная» формулировка аксиомы выбора такова: для любого непустого множества xA попарно непересекающихся множеств существует некоторое множество, содержащее в качестве своих аргументов ровно по одному элементу из каждого элемента множества xAЭта аксиома вызвала много споров и серьезные возражения крупных математиков. Основные возражения касались неконструктивного характера самой аксиомы: о функции выбора, существование которой постулируется аксиомой, в общем случае ничего не известно, и нельзя сказать, чему равно значение xf для конкретных Xx . Тем не менее, аксиома выбора играет ключевую роль в системе аксиом. Кроме того, она неявно присутствует в доказательстве многих важных утверждений из математического анализа и теории меры, например, в таком: если x - предельная точка множества действительных чисел X , то существует последовательность ,... ,..., , 1 0 nxxx точек множества X , сходящихся к x . Этот пример показывает, что два стандартных определения предельной точки (одно через окрестности, а другое через последовательности) не будут эквивалентными, если нет аксиомы выбора. 18 Альтернативной аксиоме выбора является предложенная в 1962 году Мычельским и Штейнгаузом аксиома детерминированности (AD). Рассмотрим множество A бесконечных последовательностей натуральных чисел, определяющих следующую бесконечную игру A G для двух игроков. Игрок I пишет натуральное число 0 n , затем игрок II пишет натуральное число 1 n и так далее по очереди. Если получающаяся в результате игры последовательность ,... ,..., , 1 0 k n n n принадлежит множеству A , то выигрывает игрок I, в противном случае игрок II. Игра A G называется детерминированной, если либо игрок I, либо игрок II имеют выигрывающую стратегию. Аксиома детерминированности. Всякое множество I A детерминировано. Здесь I - бэровское пространство (множество всех бесконечных последовательностей натуральных чисел). Аксиома детерминированности создана с целью получить более привлекательные следствия, чем те, что дает аксиома выбора. В целом эти две конкурирующие аксиомы дают противоположные следствия в тех областях, где они применимы. Ян Мычельский (р.????) –польско-американский математик. Гуго Дионисий Штейнгауз (1887 - 1972) – австрийско-польский математик. Рене Луи Бэр (1874 – 1932) – французский математик.
18 Аксиома выбора имеет ряд следствий, являющихся в определенной степени нежелательными, или приводят к «парадоксальным» примерам множеств, противоречащим нашей интуиции, вроде парадокса Банаха – Тарского : используя аксиому выбора, можно разбить шар на конечное число частей, которые затем можно переставить так, что получится два шара такого же размера, как и исходный шар. Однако эта аксиома оказывает четкое организующее влияние на бесконечные мощности, делает более «регулярной» структуру бесконечных множеств, сравнивая их по величине и располагая такие мощности в иерархию алефов. Ее роль особенно важна при изучении наиболее общих топологических пространств, произвольных множеств и порядковых чисел, где она становится органически включенной в структуру большинства рассуждений и построений. Аксиома детерминированности (AD) противоречит аксиоме выбора (AC). В свою очередь AD в отличие от AC не дает ясной картины бесконечных мощностей и почти не используется в топологии. Зато многие следствия AD укладываются в естественный эвристический принцип: если нет «индивидуальных» примеров множеств с каким-либо свойством, то AD влечет отсутствие множеств, обладающих этим свойством. Кроме того, эта аксиома широко применяется в задачах из теории проективных множеств, неразрешимых с помощью AC. Выбор между аксиомой детерминированности и аксиомой выбора возможен, очевидно, лишь со временем, путем сравнения красоты и богатства теорий, построенных на этих аксиомах. |