Лекции по дискретке (1021001), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

а₁ = 2, а₂ = 4, а₃ = 8,… .

4. Множество всех рациональных чисел. Каждое рациональное число записывается в виде  = , q > 0, p и q – взаимно простые целые числа.

Назовем сумму |p| + q высотой рационального числа . Ясно, что число дробей с данной высотой n конечно. Например, высоту 1 имеет только число , высоту 2 – два числа и , высоту 3 – четыре числа: , , , и т.д. Таким образом, каждому рациональному числу можно сопоставить некоторый порядковый номер. Следовательно, множество рациональных чисел счётно.

Определение.

Бесконечное множество, не являющееся счётным, называется несчётным множеством.

Теорема.

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

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

Пусть А – счётное множество, В – его подмножество. Занумеруем элементы множества А: а₁, а₂, а₃,…, а_n,…. Пусть – те из них, которые входят в В. Если среди чисел есть наибольшее, то В – конечно, в противном случае В – счётно, так как его члены занумерованы числами .

Теорема.

Сумма любого конечного или счётного множества счётных множеств есть снова счётное множество.

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

Пусть – счётные множества. Не нарушая общности, будем считать, что они попарно не пересекаются, в противном случае следует рассмотреть множества и т.д. Эти множества являются также не более, чем счётными, так как всякое подмножество счётного множества конечно или счётно, а сумма этих множеств равна сумме множеств .

Итак, рассмотрим множества . Элементы этих множеств можно записать в виде бесконечной таблицы

,

где в i-той строке стоят элементы множества . Занумеруем элементы множеств “по диагоналям”, то есть за первый элемент примем , за второй - , за третий – и т.д., двигаясь по стрелкам:

.

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

Теорема.

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

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

Пусть М – бесконечное множество. Выберем в нём произвольный элемент а₁. Так как множество М – бесконечно, в нём , а также а₃, отличный от а₁ и а₂ и т.д. Продолжая этот процесс, получаем счётное подмножество {а₁, а₂ …} множества М, что и требовалось доказать.

Определение.

Два множества М и N называются эквивалентными (М  N), если между их элементами можно установить взаимно однозначное соответствие.

Определение.

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

Ясно, что два множества, эквивалентные третьему, эквивалентны между собой.

Примеры.

1. Множества точек на любых двух отрезках и эквивалентны между собой (рис. 1.5).

Рис. 1.5. Точки p и q соответствуют друг другу, так как они являются проекциями одной и той же точки r вспомогательного отрезка ef.

1. Множество всех точек на плоскости  множеству точек на сфере (рис. 1.6).

Рис. 1.6. Биекция устанавливается с помощью стереографической проекции.

1. Множество всех чисел в интервале эквивалентно множеству всех точек на прямой (рис. 1.7).

Рис. 1.7. Биекция устанавливается, например, с помощью функции .

Замечания.

Иногда бесконечное множество оказывается эквивалентным своей истинной части, например:

1. Натуральные числа эквивалентны множеству всех целых чисел.

2. Натуральные числа эквивалентны множеству рациональных чисел.

3. На интервале столько же точек, сколько и на всей прямой.

Теорема.

Всякое бесконечное множество эквивалентно некоторому своему собственному подмножеству.

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

Согласно известной теореме: из всякого бесконечного множества М можно выбрать счётное подмножество. Пусть – такое подмножество. Разобьём множество А на два счётных подмножества: и .

Между А и можно установить биекцию:

, где .

Рассмотрим множества:

1. ; 2. .

Установив взаимно однозначное соответствие между А и , легко продолжить это соответствие на рассматриваемые множества, отнеся каждому элементу множества сам этот элемент. Таким образом, установлено взаимнооднозначное соответствие между множествами М и . Теорема доказана.

Теорема Кантора.

Для любой последовательности { } действительных чисел из любого интервала I существует точка p из I такая, что при всех n.

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

 много способов доказательства этой теоремы. Рассмотрим один из них.

Возьмем отрезок такой, что . Затем берём отрезок такой, что . Продолжая процесс по индукции, выберем в отрезок такой, что . Полученная последовательность вложенных отрезков имеет непустое пересечение. Если , то и при всех n, что и требовалось доказать.

Следствие из теоремы Кантора.

Ни один интервал не является счётным множеством.

Впервые доказательство нёсчетности этого множества Кантор привёл в 1873 г.

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

1. Множество всех точек любого отрезка или интервала .

2. Множество всех точек на прямой.

3. Множество всех точек плоскости, пространства, поверхности сферы, точек, лежащих внутри сферы и т.д.

4. Множество всех прямых на плоскости.

5. Множество всех непрерывных функций одного или нескольких переменных.

8.Аксиома выбора. Теорема Цермело.

Аксиома выбора, называемая также аксиомой Цермело, возникшая в рамках наивной теории множеств, восходящей к Кантору и Цермело, вместе с другими вопросами, такими как континуум-гипотеза, то есть вопрос о совпадении мощности континуума с первой несчётной мощностью , привела к многочисленным работам по математической логике и основаниям математики. Были построены аксиоматические теории множеств Гёделя-Бернайса и Цермело-Френкеля, в которых были установлены непротиворечивость и независимость аксиомы выбора.

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

Теорема Цермело.

Каждое множество может быть вполне упорядочено.

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

Пусть А – некоторое множество индексов  и пусть для каждого  задано некоторое произвольное множество . Тогда можно построить функцию  на А, относящую каждому некоторый элемент из соответствующего , то есть можно составить некоторое множество, выбрав из каждого по одному и только одному элементу (см. рис. 1.13).

Рис. 1.13. Иллюстрация аксиомы выбора.

Замечание.

Теорема Цермело эквивалентна аксиоме выбора. Так, если предположить, что каждое из множеств вполне упорядочено, то для построения функции , существование которой утверждается аксиомой выбора, достаточно в каждом взять первый элемент.

Сформулируем еще некоторые предложения, эквивалентные аксиоме выбора.

Определение.

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

Определение.

Цепь называется максимальной, если она не содержится в качестве собственного подмножества ни в какой другой цепи, принадлежащей М, где М – частично упорядоченное множество.

Определение.

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

Определение.

Пусть М – частично упорядоченное множество. Если множество верхних граней А подмножества имеет наименьший элемент , то называется точной верхней гранью множества .

Определение.

Пусть М – частично упорядоченное множество. Элемент называется нижней гранью подмножества , если любой элемент следует за , то есть .

Определение.

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

Определение.

Частично упорядоченное множество, всякое непустое конечное подмножество которого обладает точной верхней гранью и точной нижней гранью, называется решеткой, или структурой.

Теорема Хаусдорфа.

В частично упорядоченном множестве всякая цепь содержится в некоторой его максимальной цепи.

Лемма Цорна.

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

9.Примеры задач и упражнений.

Пример 1. Задать различными способами множество А всех четных чисел 2, 4, 6, …., не превышающих 1000.

Решение. 1. Перечислением: А={2, 4, 6, 8, 10, …, 998, 1000};

Описанием: А={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}?

Характеристики

Список файлов лекций