Лекции Русакова, страница 4

Здесь биекция – это: 2n ↔ n, то есть25а1 = 2, а2 = 4, а3 = 8,… .4. Множество всех рациональных чисел. Каждое рациональное числозаписывается в виде α =p, q > 0, p и q – взаимно простые целые числа.qНазовем сумму |p| + q высотой рационального числа α. Ясно, что числодробей с данной высотой n конечно. Например, высоту 1 имеет только число112 1021, высоту 2 – два числа и − , высоту 3 – четыре числа: , , − , − и111 2112т.д. Таким образом, каждому рациональному числу можно сопоставитьнекоторый порядковый номер. Следовательно, множество рациональныхчисел счётно.Определение.Бесконечноемножество,неявляющеесясчётным,называетсянесчётным множеством.Теорема.Всякое подмножество счётного множества конечно, или счётно.Доказательство:Пусть А – счётное множество, В – его подмножество.

Занумеруемэлементы множества А: а1, а2, а3,…, аn,…. Пусть an1 , an 2 ,... – те из них,которые входят в В. Если среди чисел n1, n 2, есть наибольшее, то В –конечно, в противном случае В – счётно, так какего члены an1 , an 2 ,...занумерованы числами 1,2, .Теорема.Сумма любого конечного или счётного множества счётных множествесть снова счётное множество.Доказательство:26ПустьА1 , А2 , – счётные множества.

Не нарушая общности, будемсчитать, что они попарно не пересекаются, в противном случае следуетрассмотреть множества А1 , А2 \ А1 , А3 \ ( А1  А2 ), и т.д. Эти множестваявляются также не более, чем счётными, так как всякое подмножествосчётного множества конечно или счётно, а сумма этих множеств равна суммемножеств А1 , А2 , .Итак, рассмотрим множества А1 , А2 , . Элементы этих множествможно записать в виде бесконечной таблицыа11 а12а21 а22а13а23а14а24а31 а32а41 а42а33а43а34а44,где в i-той строке стоят элементы множества Аi .

Занумеруем элементымножеств “по диагоналям”, то есть за первый элемент примем а11 , за второй- а12 , за третий – а21 и т.д., двигаясь по стрелкам:а11→ а12а13а21↓а22а23а31а32а33а41а42а43    → а14 а24 .а34 а44   Таким образом, каждый элемент каждого из множеств получитопределенный номер,то есть будетустановлено взаимно-однозначноесоответствие между всеми элементами всех множеств А1 , А2 , и всеминатуральными числами. Теорема доказана.27Теорема.Всякое бесконечное множество содержит счётное подмножество.Доказательство:Пусть М – бесконечное множество.

Выберем в нём произвольныйэлемент а1. Так как множество М – бесконечно, в нём ∃a2 ≠ а1 , а также а3,отличный ота1 и а2 и т.д. Продолжая этот процесс, получаем счётноеподмножествоA = {а1, а2 …} множества М, что и требовалось доказать.Определение.Два множества М и N называются эквивалентными (М ∼ N), если междуих элементами можно установить взаимно однозначное соответствие.Определение.Множество М называется счётным, если оно эквивалентно множествунатуральных чисел.Ясно, что два множества, эквивалентные третьему, эквивалентнымежду собой.Примеры.1. Множества точек на любых двух отрезках [a, b] и [c, d ] эквивалентнымежду собой (рис.

1.5).28Рис. 1.5. Точки p и q соответствуют друг другу, так как они являютсяпроекциями одной и той же точки r вспомогательного отрезка ef.2. Множествовсех точек на плоскости ∼ множеству точек на сфере(рис. 1.6).NαzРис. 1.6. Биекция α ↔ z устанавливается с помощью стереографическойпроекции.3. Множество всех чисел в интервале (0,1) эквивалентно множествувсех точек на прямой (рис. 1.7).29Рис. 1.7. Биекция устанавливается, например, с помощью функции11у = arctgx + .π2Замечания.Иногда бесконечное множество оказывается эквивалентным своейистинной части, например:1.

Натуральные числа эквивалентны множеству всех целых чисел.2. Натуральные числа эквивалентны множеству рациональных чисел.3. На интервале (0,1) столько же точек, сколько и на всей прямой.Теорема.Всякое бесконечное множество эквивалентно некоторому своемусобственному подмножеству.Доказательство:Согласно известной теореме: из всякого бесконечного множества Мможно выбрать счётное подмножество. ПустьА = {а1 , а2 ,} – такоеподмножество. Разобьём множество А на два счётных подмножества:A1 = {а1 , а3 , а5 } и A2 = {а2 , а4 , а6 } .Между А и А1 можно установить биекцию:α n ↔ α 2 n−1 , где α n ∈ A, α 2 n−1 ∈ A1 .Рассмотрим множества:301. A  ( М \ А ) = М ; 2.

А1  ( М \ А ) = М \ А2 .Установив взаимно однозначное соответствие между А и А1 , легкопродолжить это соответствие на рассматриваемые множества, отнесякаждому элементу множества М \ А сам этот элемент. Таким образом,установлено взаимнооднозначное соответствие между множествами М иМ \ А2 . Теорема доказана.Теорема Кантора.Для любой последовательности { аn } действительных чисел из любогоинтервала I существует точка p из I такая, что p ≠ an при всех n.Доказательство:∃ много способов доказательства этой теоремы. Рассмотрим один изних.Возьмем отрезок I1 ⊂ I такой, что a1 ∉ I1 . Затем берём отрезок I 2 ⊂ I1такой, что a2 ∉ I 2 .

Продолжая процесс по индукции, выберем в I n−1 отрезокI n такой, что an ∉ I n . Полученная последовательность вложенных отрезковI n имеет непустое пересечение. Если p ∈  I n , то p ∈ I и p ≠ an при всех n,nчто и требовалось доказать.Следствие из теоремы Кантора.Ни один интервал не является счётным множеством.Впервые доказательство нёсчетности этого множества Кантор привёлв 1873 г.Примеры несчётных множеств.1. Множество всех точек любого отрезка [a , b] или интервала (а , b) .2.

Множество всех точек на прямой.3. Множество всех точек плоскости, пространства, поверхности сферы,точек, лежащих внутри сферы и т.д.314. Множество всех прямых на плоскости.5. Множество всех непрерывных функций одного или несколькихпеременных.1.08. Аксиома выбора. Теорема Цермело.Аксиома выбора, называемая также аксиомой Цермело, возникшая врамках наивной теории множеств, восходящей к Кантору и Цермело, вместес другими вопросами, такими как континуум-гипотеза, то есть вопрос осовпадении мощности континуума с первой несчётной мощностью ℵ1 ,привела к многочисленным работам по математической логике и основаниямматематики.

Были построены аксиоматические теории множеств ГёделяБернайсаиЦермело-Френкеля,вкоторыхбылиустановленынепротиворечивость и независимость аксиомы выбора.При сравнении вполне упорядоченных множеств по мощностивозникает вопрос: можно ли всякое множество вполне упорядочить какимлибо образом. Положительный ответ означал бы, в частности, чтонесравнимых мощностей нет.Теорема Цермело.Каждое множество может быть вполне упорядочено.Аксиома выбора.Пусть А – некоторое множество индексов α и пусть для каждого αзадано некоторое произвольное множество M α . Тогда можно построитьфункцию ϕ на А, относящую каждому a ∈ A некоторый элемент mα изсоответствующего M α ,то есть можно составить некоторое множество,выбрав из каждого M α по одному и только одному элементу (см. рис. 1.13).32Рис. 1.13. Иллюстрация аксиомы выбора.Замечание.ТеоремаЦермелоэквивалентнааксиомевыбора.Так,еслипредположить, что каждое из множеств M α вполне упорядочено, то дляпостроения функции ϕ, существование которой утверждается аксиомойвыбора, достаточно в каждом M α взять первый элемент.Сформулируем еще некоторые предложения, эквивалентные аксиомевыбора.Определение.ПустьМ–частичноупорядоченноемножество.Всякоеегоподмножество А, в котором любые два элемента сравнимы между собой всмысле введенной в М частичной упорядоченности, называется цепью.Определение.Цепь называется максимальной, если она не содержится в качествесобственного подмножества ни в какой другой цепи, принадлежащей М, гдеМ – частично упорядоченное множество.Определение.Пусть М – частично упорядоченное множество.

Элемент a ∈ Mназывается верхней гранью подмножества M ′ ⊂ M , если любой элементa′ ∈ M ′ подчинен a , то есть a′ ≤ a .Определение.33Пусть М – частично упорядоченное множество. Если множествоверхних граней А подмножества M ′ ⊂ M имеет наименьший элемент a , то aназывается точной верхней гранью множества M ′ .Определение.Пусть М – частично упорядоченное множество. Элемент a ∈ M называется нижней гранью подмножества M ′ ⊂ M , если любой элемент a′ ∈ M ′следует за a , то есть a′ ≥ a .Определение.Пусть М – частично упорядоченное множество. Если множествонижних граней А множества Ì ′ ⊂ Ì имеет наибольший элемент à , то àназывается точной нижней гранью множества Ì ′ .Определение.Частично упорядоченное множество, всякое непустое конечноеподмножество которого обладает точной верхней гранью и точной нижнейгранью, называется решеткой, или структурой.Теорема Хаусдорфа.В частично упорядоченном множестве всякая цепь содержится внекоторой его максимальной цепи.Лемма Цорна.Если всякая цепь в частично упорядоченном множестве М имеетверхнююгрань,товсякийэлементизМподчиненнекоторомумаксимальному.1.09.

Примеры задач и упражнений.Пример 1. Задать различными способами множество А всех четныхчисел 2, 4, 6, …., не превышающих 1000.Решение. 1. Перечислением: А={2, 4, 6, 8, 10, …, 998, 1000};34Описанием: А={x|x∈N и х/2∈N, N≤1000};(N – множествонатуральных чисел 1, 2, 3, ….)Порождающей процедурой: а) 2∈А; б) если х∈А, то (х+2)∈А;в) х≤1000.Пример 2. Верно ли, что: 1). {{1,2}, {2,3}}={1,2,3}? 2).{{1,2}}={1,2}?Решение. 1).

Нет, так как элементами первого множества являютсяподмножества {1,2} и {2,3}, а второго – элементы 1,2,3.2). Нет, так как первое множество одноэлементное, состоящее изодного элемента - подмножества, а второе имеет два элемента 1 и 2.Пример 3. Перечислить элементы следующих множеств:1). А={a|a⊆B, B={1,2,3}};2). A={a|a∈B, B={1,2,3}}.Решение. 1). Так как а⊆В, а В – трехэлементное множество, то имеется23=8 подмножеств: А={{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}, ∅}.2).