Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа (1976), страница 5

Действительно, если а — Ь означает «а находится в том же классе, что и Ь», то отношение у будет, как легко проверить, рефлексивным, симметричным и транзитивиым. Обратно, пусть ~р — некоторое отношение зквивалентностп между элементами множества М и К,— класс элементов к из М, эквивалентных данному элементу а: х — а. В силу свойства рефлексивности элемент а сам принадлежит классу К,. Покажем, что два класса К, и Кь либо совпадают, либо не пересекаются. Пусть некоторый элемент с принадлежит одновременно и К, и Кь, т.

е. с а и с †„ Ь. Тогда в силу симметричности а — с и в силу транзитивности а — Ь. (1) Если теперь х — произвольный элемент пз К„т. е. х- а, то в силу (1) и свойства транзитивности к Ь, т. е. х ее Км Точно так же доказывается, что всякий элемент уев Кь входит в К,. Таким образом, два класса К, и Кы имеюших хотя бы один общий элемент, совпадают между собой. Мы получили разбиение множества М на классы по заданному отношению эквивалентности. Понятие разбиения множества на классы тесно связано с рассмотренным в предыдушем пункте понятием отображения.

Пусть 1 — отображеяие множества А в множество В. Собрав в один класс все те элементы из А, образы которых в В совпадают, мы получим, очевидно, некоторое разбиение множества А. Обратно, рассмотрим произвольное множество А и некоторое его разбиение на классы. Пусть  — совокупность тех классов, на которые разбито множество А. Ставя в соответствие каждому элементу а еп А тот класс (т. е, тот элемент из В), к которому а принадлежит, мы получим отображение множества А на множество В. Пример ы. 1. Спроектируем плоскость ху на ось х.

Прообразы точек оси х — вертикальные прямые. Следовательно, этому отображению отвечает разбиение плоскости на параллельные прямые. 2. Разобьем все точки трехмерного пространства на классы, объединив в один класс точки, равноудаленпые от начала координат. Каждый класс представляет собой сферу некоторого радиуса. Совокупность всех этих классов можно отождествить с множеством всех точек, лежащих на луче [О, со). Итак, разбие- эя ЭКВИВАЛЕНТНОСТЬ МНОЖЕСТВ. ПОНЯТИЕ МОЩНОСТИ 21 нию трехмерного пространства на концентрические сферы отвечает отображение этого пространства на полупрямую.

3. Объединим в один класс все действительные числа с одинаковой дробной частью. Этому разбиению отвечает отображение прямой линии на окружность единичной длины. Понятие эквивалентности является частным случаем более общего понятия б и н а р н о г о о т н о ш е н и я. Пусть М вЂ” произвольное множество. Обозначим через МХ М или М' совокупность всех упорядоченных пар (а, Ь), где а, Ь еп М. Говорят, что в М задано бинарное отношение р, если в МЕ выделено произвольное подмножество Йч.

Точнее говоря, мы скажем, что элемент а находится в отношении ~р к элементу Ь вЂ” обозначение агрЬ вЂ” в том и только том случае, когда пара (а, Ь) принадлежит АА'ч Примером бинарного отношения может служить отношение тождества е; именно, аеЬ в том и только том случае, если а = Ь; иначе говоря, это — отношение, задаваемое диагональю О в МХ М, т. е. подмножеством пар вида (а, а). Ясно, что всякое отношение эквивалентности ~р в некотором множестве М есть бинарное отношение, подчиненное следующим условиям: !) Диагональ О пРинадлежит )тч (Рефлексивность).

2) Если (а, Ь) еп)т„, то и (Ь, а)ен )тч (симметричность). 3) Если (а, Ь) еп й,р и (Ь, с)я )А'ч, то и (а, с) еп Р.р (транзитивность) . Итак-, эквивалентность — это бинарное отношение, удовлетворяющее условиям рефлексивности, транзитивностп н симметричности. В $4 мы рассмотрим другой важный частный случай бинарного отношения — частичную упорядоченность. й 3. Эквивалентность множеств.

Понятие мощности множества 1. Конечные и бесконечные множества. Рассматривая различные множества, мы замечаем, что иногда можно, если не фактически, то хотя бы примерно, указать число элементов в данном множестве. Таковы, например, множество всех вершин некоторого многогранника, множество всех простых чисел, не превосходящих данного числа, множество всех молекул воды на Земле и т. д. Каждое из этих множеств содержит конечное, хотя, быть может, и неизвестное нам число элементов.

С другой стороны, существуют множества, состоящие из бесконечного числа элементов. Таково, например, множество всех натуральных чисел, множество всех точек на прямой, всех кругов на плоскости, всех многочленов с рациональными коэффициентами и т, д. При этом, говоря, что множество бесконечно, мы имеем в виду, что нз него можно извлечь один элемент, два элемента и т. д., причем после каждого такого шага в этом множестве еще останутся элементы. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ !Гл.

! Два конечных множества мы можем сравнивать по числу элементов и судить, одинаково это число или же в одном из множеств элементов больше, чем в другом. Спрашивается, можно ли подобным же образом сравнивать бесконечные множества? Иначе говоря, имеет ли смысл, например, вопрос о том, чего больше: кругов на плоскости или рациональных точек на прямой, функций, определенных на отрезке [О, 11, или прямых в пространстве, и т. д.? Посмотрим, как мы сравниваем между собой два конечных множества.

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

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

е. если будет установлена биекция между этими двумя множествами, то это и будет означить, что число элементов в них одинаково. Заметим теперь, что если первый способ (подсчет числа элементов) годится лишь для сравнения ко н е ч н ы х множеств, второй (установление взаимно однозначного соответствия) пригоден и для бес ко н еч н ых. 2. Счетные множества. Простейшим среди бесконечных множеств является множество натуральных чисел.

Назовем счетным множеством всякое множество, элементы которого можно биективно сопоставить со всеми натуральными числами. Иначе говоря, счетное множество — это такое множество, элементы которого можно занумеровать в бесконечную последовательность: аь аь ..., а„, ... Приведем примеры счетных множеств. 1.

Множество всех целых чисел. Установим соответствие между всеми целыми и всеми натуральными числами по следующей схеме: Π— 11 — 22 1 23 45 вообще, неотрицательному числу п О сопоставим нечетное число 2Л+1, а отрицательному л (Π— четное число 2[в[; и 2л+ 1 при п)О, п~ — «21и! при и <О. ан эквиВАлентнОсть множеств. понятие мощнОсти ез 2. Множество всех четных положительных чисел. Соответствие очевидно: и 2п. 3. Множество 2, 4, 8, ..., 2", ... степеней числа 2.

Здесь соответствие также очевидно. Каждому числу 2" сопоставляется число и. 4. Рассмотрим более сложный пример, а именно,. покажем. что множество всех рациональных чисел счетно. Каждое рациональное число однозначно записывается в виде несократимой дроби 22 = р/4/, 4/) О. Назовем сумму !р1+4/ высотой рационального числа и. Ясно, что число дробей с данной высотой и конечно. Например, высоту 1 имеет только число О/1, высоту 2в числа 1/1 и — 1/1, высоту 3 — числа 2/1, 1/2, — 2/1 и — !/2 и т.

д. Будем нумеровать все рациональные числа по возрастанию высоты, т. е. сперва выпишем числа высоты 1, потом — числа высоты 2 и т. д. При этом всякое рациональное число получит некоторый номер, т. е. будет установлено взаимно однозначное соответствие между Всеми натуральными и всеми рациональными числами. Бесконечное множество, не являющееся счетным, называется несчетным множеством. Установим некоторые общие свойства счетных множеств. 1. Всякое подмножество счетного множества конечно или счетно.

Д о к а з а т е л ь с т в о. Пусть А — счетное множество, а В— его подмножество. Занумеруем элементы множества А; аь аь ..., а„... Пусть а„„а„„... — те из них, которые Входят в В. Если среди чисел и1, п2, ... есть наибольшее, то В конечно, в противном случае В счетно, поскольку его члены а„„а„„... занумерованы числами 1, 2,... 2. Сумма любого конечного или счетного множества счетных множеств есть снова счетное множество.

Д о к а з а т е л ь с т в о. Пусть А ь Аъ ... — счетные множества. Мы можем считать, что они попарно не пересекаются, так как иначе мы рассмотрели бы вместо них множества А„А2' А1, Аз''(А! 0 А2), ...— каждое из которых не более чем счетно,— имеющие ту же самую сумму, что и множества А1, Аъ ... Бсе элементы множеств Аь А2, ...

можно записать в виде следующей бесконечной таблицы: а!1 а12 а13 а14 а21 атг а23 а24 а31 а32 1233 а34 1241 а42 а43 а44 ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ 24 !гл ! где в первой строке стоят элементы множества Аь во второй— элементы множества Аз и т. д.

Занумеруем теперь все эти элементы «по диагоналям», т. е. за первый элемент примем ап, за второй ам, за третий аз~ и т. д., двигаясь в порядке, указанном стрелками на следующей таблице: ап -ь ам а~з ь аы г аз1 азз ам ам аз~ азз азз ам аа ачз агз аы Ясно, что при этом каждый элемент каждого из множеств получит определенный номер, т. е. будет установлено взаимно однозначное соответствие между всеми элементами всех множеств Аь А,, ... и всеми натуральными числами. Наше утверждение доказано. У п р а ж н е н н я. Доказать, что множество всех миогочлеиов с рациональными коэффициентами счетно.

2. Число 5 называется алгебраическим, если оно является корнем некоторого многочлена с рациональными коэффициентами, Доказать, что множество всех алгебраических чисел счетно. 3. Доказать, что множество всех рациональных интервалов (т. е. интервалоа с рацноналыгыми концами) на прямой счетно. 4. Доказать, что множество всех точек плоскости, имеющих рациональные координаты, счетно.