Мои Конспекты
Главная | Обратная связь


Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

Следствия.



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

2. Множеств с максимально возможной мощностью не существует, поскольку для любого множества М всегда можно рассмотреть множество его подмножеств [М]. В теории множеств доказана теорема Цермело, которая утверждает, что для произвольных множеств А и В всегда есть только три возможности:
а) ½А½<½В½; б) ½А½>½В½; в) ½А½ = ½В½.Отсюда следует, что несравнимых по мощности множеств не существует.

Определение. Множествами мощности континуум называют множества, эквивалентные множеству вещественных чисел на отрезке [0,1]. Обозначается данный вид мощности С либо À.

Можно показать путем построения соответствующего взаимно однозначного отображения, что между мощностями счетного множества и множества мощности континуум существует следующая связь: ½[N = 2N = C.

В отличие от счётных, множества мощности континуум нельзя упорядочить. Множество вещественных чисел на отрезке [0;1] является как бы эталоном для других множеств мощности континуум, с которым их сравнивают путём построения взаимно однозначных отображений. Г.Кантором дано прямое доказательство несчетности данного множества с помощью диагональной процедуры.

Теорема 2.5 (Г.Кантор). Множество вещественных чисел на отрезке [0;1] несчетно.

Доказательство. Любое из этих чисел можно задать в виде конечной либо бесконечной десятичной дроби α=01α2α3… , где 0≤ αi ≤9. Представим каждую конечную дробь α=01α2α3… αk в бесконечной форме: α=0, 01α2α3…(αk-1)99…. Для числа 1 получаем: 1 = 0,99… .

Допустим, рассматриваемое множество счетно. При этом все вещественные числа на отрезке [0; 1] могут быть упорядочены в виде счетного списка, в который каждое из них входит ровно один раз и представлено бесконечной последовательностью десятичных знаков:

β1=0, β11 β12 β13 β14…

β2=0, β21 β22 β23 β24

β3=0, β31 β32 β33 β34…

β4=0, β41 β42 β43 β44…

Построим бесконечную дробь γ=0,γ1γ2γ3… по следующему правилу: еcли βii=1, то γi = 2, а еслиβii≠1, то γi = 1. Из алгоритма построения следует, что дробь γ не совпадает ни с одним из чисел βi, посколькуγi βii . Следовательно, вещественное число γ, принадлежащее отрезку [0; 1], не содержится в списке. Получаем противоречие с допущением о возможности упорядочения всех вещественных чисел из данного отрезка.

Пример 4. Найти мощность множества R вещественных чисел на всей числовой оси (–¥;+¥).

Решение. Очевидно,½R½ ³ С, поскольку отрезок [0;1] Ì R. Докажем строгое равенство ½R½= С путем построения взаимно однозначного отображения f множества А = [0;1]на R. С помощью одних линейных отображений невозможно взаимно однозначно отобразить конечный отрезок на бесконечную область. Данным свойством обладает тригонометрическая функция у = tg(х). Но она действует на отрезке [–p/2; +p/2],поэтому вначале необходимо взаимно однозначно отобразить отрезок [0;1] (множество А) на отрезок [–p/2; +p/2] (который обозначим множеством В), а затем множество В взаимно однозначно отобразить на R.

Первая задача может быть решена с помощью линейного отображения. Поскольку оно имеет два неизвестных коэффициента (С01), то их можно найти, подставив в уравнение связи
b = С0 a + С1две пары значений из множеств А и В, которые должны взаимно однозначно отображаться друг в друга. Если взять в качестве таких пар минимальные и максимальные значения на отрезках (0 « –p/2; 1« + p/2), то множества точек, лежащие между ними, взаимно однозначно отобразятся друг на друга и задача будет выполнена. Подставляя выделенные пары в уравнение связи, получим систему двух уравнений:

– p/2= С0 × 0+ С1;

+p/2= С0 × 1+ С1.

Решая систему (например, методом исключения), получим:

С0 = p ; С1 = –p/2.

Взаимно однозначное отображение множества А на В (обозначим его g: А® В) примет вид: a Î A, g(а) = pа – p/2 = b Î B.

Для взаимно однозначного отображения множества В на R (обозначим его h: В ® R) используем функцию tg: b Î B, h(b) =
=
tg(b) = r Î R.

Итоговое отображение f: A® R представим в виде композиции f = h g. Так как h и g взаимно однозначны, то и f по свойству композиций будет взаимно однозначным. Подставляя уравнение b(а)в зависимость r(b), найдем уравнение для отображения f, связывающее элементы аÎA с элементами rÎR: r = tg(pa – p/2).

Из факта построения взаимно однозначного отображения f:A® R по определению следует эквивалентность множеств A и R. Отсюда получим:½R½ = ½A½ = С.

С точки зрения мощности, множество всех точек, лежащих внутри и на границе квадрата[0;1] ´ [0;1], эквивалентно мощности всех точек на отрезке[0;1].

Теорема 2.6 (Г.Кантор).Множество всех точек декартова квадрата[0;1] ´ [0;1] имеет мощность континуум.

Доказательство. Построим взаимно однозначное отображение всех точек из квадрата [0;1] ´ [0;1] на множество вещественных точек отрезка[0;1].

Как и при доказательстве Теоремы 2.5, каждое из вещественных чисел, задающих координаты точек квадрата [0;1] ´ [0;1] или отрезка[0;1],представим в виде бесконечной десятичной дроби α = 0, α1 α2 α3…, где 0 ≤ αi9. Все конечные дроби α = 0, α1 α2 α3 … αk для единообразия задаем в эквивалентной бесконечной форме: α = 0, α1 α2 α3 …(αk-1)99…. В том числе: 1 = 0,99… .

При выбранном способе представления каждой точке отрезка соответствует одна бесконечная десятичная дробь х = 0, х1 х2 х3…, задающая ее координату на отрезке. Каждой точке квадрата — две дроби х = 0, х1 х2 х3 … и у = 0, у1 у2 у3…, которые равны ее декартовым координатам по осям.

Искомое взаимно однозначное отображение строим следующим образом. Каждой бесконечной десятичной дроби х = 0, х1 х2 х3 …, задающей координату точки на отрезке [0;1], ставим в соответствие две дроби х´ = 0, х1´ х2´ х3´ и у´= 0, у1´ у2´ у3´, которые однозначно задают точку квадрата [0;1] ´ [0;1], по следующему правилу:

х1´= х1, у1´= х2, х2´= х3 , у2´= х4 ,…, хn´= х2n-1 , уn´= х2n.

Отображение является однозначным, имеет обратное отображение (х´,у´х, которое также однозначно. Следовательно, оно является взаимно однозначным и | [0;1] ´ [0;1]| = С, ч.т.д.

Аналогично можно доказать мощность континуум для всех точек куба [0;1] 3 = [0;1] ´ [0;1] ´ [0;1]и других более высоких декартовых степеней [0;1]n множества [0;1].

Полученный результат был удивителен для всех математиков, в том числе — для самого Г.Кантора, поскольку он входил в противоречие с понятием пространственной размерности объектов. Однако построенное отображение не является непрерывным в обе стороны, что является в математике достаточным условием для сохранения размерности.

Пример 5. Найти мощность множества R2 точек на декартовой плоскости.

Решение. Используя отображение вида r = tg(pa -p/2) из Примера 4, можно взаимно однозначно отобразить все точки декартовой плоскости на декартов квадрат [0;1] ´ [0;1], мощность которого, как доказано в Теореме 2.6, равна континууму. Следовательно, | R2| = С.

Замечание. Так как процесс порождения множеств с большей мощностью бесконечен, то рассмотрев множество [А]всех подмножеств континуального множества А, получим множество2А, мощности большей, чем континуум:½[А = 2C > С. Мощность 2C имеет, в частности, множество всех функций, определённых на R .

Применение теоремы Кантора-Бернштейна значительно упрощает доказательство эквивалентности множеств мощности континуум одинаковой размерности. Для этого проще всего воспользоваться масштабным изменением размеров объектов, которое можно выполнить линейными преобразованиями с ненулевыми линейными коэффициентами, задающими взаимно однозначные отображения.

Пример 6. Найти мощность множества A точек, принадлежащих кругу радиуса r = 0,5 с центром в точке (1;1) на декартовой плоскости.

Рис.2.4

Решение. Докажем эквивалентность А множеству точек квадрата [0;1] ´ [0;1] (множество В, рис.2.4).

1. Вначале докажем эквивалентность А некоторому подмножеству В. Используя взаимно однозначное отображение х¢ = 1 · х - 0,5; у¢ = 1·у - 0,5, отобразим круг А на круг А¢, расположенный внутри В. Отсюда следует: |A¢| =|A| , A¢ Ì B.

2. Докажем, что В эквивалентно подмножеству А. При помощи взаимно однозначного отображения х¢ = 0,5·х + 0,75; у¢ = 0,5·у + 0,75, квадрат В отобразим на квадрат меньшего размера В¢, расположенный внутри круга A. Отсюда следует: |В¢| = |В| , В¢ Ì А.

По теореме Кантора-Бернштейна из 1 и 2 следует: |А| = |В| . Отсюда с учетом результатов Теоремы 2.6 получим: |A| = С.

ЗАДАЧИ

1. Найти мощность:

а) всех вещественных чисел в интервале [5;10];

б) множества вещественных чисел (–¥;– r] È (r; +¥), где r — некоторое положительное вещественное число;

в) множества вещественных чисел в объединении отрезков вида [2i;2i+1), где i Î Z;

г) множества вещественных чисел (¥;0]È (1;+¥);

д) интервалов (r1; r 2), где r1 и r 2 - рациональные числа;

е) множества всех точек на окружности радиуса 1 с центром в точке (0; 0);

ж) множества точек на параболе у = (х–2)2 при ¥ < х < +¥ .

2. Построить пример взаимно однозначного отображения:

а) множества N10целых чисел, кратных 10, на множество N2четных чисел;

б) множества вещественных чисел [0;4] на множество вещественных чисел [0;4] È (7;10];

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

3. Построить взаимно однозначное отображение отрезка [0;1] на положительную полуось [0;+¥).

4. Существует ли взаимно однозначное отображение:

а) множества всех вещественных чисел R на множество всех целых чисел Z?

б) множества всех рациональных вещественных чисел на множество всех целых чисел?

5. Привести примеры счетных подмножеств на множествах:

а) всех прямых на плоскости;

б) шаров в пространстве;

в) векторов в n-мерном пространстве.

6. Будут ли иметь одинаковую мощность:

а) множества N3 и N4 всех натуральных чисел, кратных соответственно 3 и 4?

б) множества N33 и N34 всех трехзначных в десятичной системе счисления натуральных чисел, кратных 3 и 4?

7. Доказать с применением теоремы Кантора-Бернштейна эквивалентность множеств точек:

а) шара c радиусом R>0 и соответствующей ему сферы,

б) 3-мерного пространства и прямой линии в нем.


Глава 3. БИНАРНЫЕ ОТНОШЕНИЯ НА МНОЖЕСТВАХ

Определение и способы задания отношений

Определение. n-местным (n-арным) отношением rна множествах X1, X2,…, Xn называют любое подмножество их декартова произведения X1´ X2´´ Xn .

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

Задание отношения rэквивалентно введению на X1´ X2´´Xn некоторого предиката Р(х1, х2, …, хn)(логического условия), для которого: (Р(х1, х2, …, хn) = true)Û ((х1, х2, …, хn)Îr ).

При n = 1отношение называют унарным, смысл его заключается в задании подмножества исходного множества X.

В случае n = 2отношение называют бинарным, оно задает на декартовом произведении X1 ´ X2 множество упорядоченных пар (х,у), где х Î X1, у Î X2.

Поскольку наиболее распространёнными являются бинарные отношения, у которых X1= X2= X, в дальнейшем будут рассматриваться только отношения на декартовом квадрате X2= X ´ X. При необходимости исходное множество дополнительно указывается нижним индексом:rX .

Для обозначения бинарных отношений применяется инфиксная система записи, при которой знак отношения помещается между элементами пары. Если пара (х, у) (х Î X, у Î X)принадлежит отношению r, то это обозначается как хrX у, если (х,у) не принадлежит r – то ( хØrX у).

Определение. Полным называют отношение, содержащее весь декартов квадрат X2 = X ´ X. Обозначается оно UX.

Диагональным называют бинарное отношение, содержащее все пары вида (х, х), где х Î X. Обозначается оно idX.

Для единичного исходного множества (÷X÷ = 1) idX = UX. При ÷X÷ >1 всегда справедливо строгое включение: idX Ì UX.

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