Соответствие между множествами А и В называется подмножество их декартова произведения

Иными словами, пары задают соответствие между множествами А={ } и В={ }, если указано правило R, по которому для элемента множества А выбирается элемент из множества В.

Если элементу поставлен в соответствие некоторый элемент , b называется образом элемента а и записывается так: b= R (a). Тогда - прообраз элемента , который обладает свойствами единственности и полноты:

1. Каждому прообразу соответствует единственный образ;

2. Образ должен быть полным, так же как полным должен быть и прообраз.

Пример. Если А – множество парабол, В – множество точек плоскости, а R – соответствие “вершина параболы”, то R (а) – точка, являющая вершиной параболы a, а состоит из всех парабол с вершиной в точке b (рис. 6)

Образ множества А при соответствии R называется множеством значений этого соответствия и обозначается R (A), если R (A) состоит из образов всех элементов множества А.

Прообраз множества В при некотором соответствии R называют областью определения этого соответствия и обозначают . В свою очередь является обратным соответствием для R.

Так, для соответствия R, заданного точками координатной плоскости, областью определения является множество точек оси абсцисс, а множеством значений – проекции точек на ось ординат (рис.7). Поэтому для некоторой точки

М (х, у) у является образом, а х – прообразом при некотором соответствии R: У=R (x), Соответствие между множествами Х, удобно в виде точки на плоскости с помощью метода декартовых координат.

Пусть задано соответствие R и Y=R (X). Ему соответствуют точки М с координатами (х; у) (рис. 7). Тогда множество точек плоскости, выделяемое отображением R, будет графиком.

Для описания соответствий между множествами используют понятие отображение (функции) одного множества на другое.

Для задания отображения необходимо указать:

1. Множество, которое отображается (область определения данного отображения, часто обозначаются );

2. Множество, в (на) которое отображается данная область определения (множество значений этого отображения, часто обозначается );

3. Закон или соответствие между этими множествами, по которому для элементов первого множества (прообразов, аргументов) выбраны элементы (образы) из второго множества.

Обозначения: .

Способы задания отображений: аналитический (в виде формул), табличный , графический (диаграммы или графы).

Различают два основных вида однозначных отображений (функций). По мощности они делятся на сюръективные и инъективные .

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

2. Соответствие, при котором каждому элементу множества А соответствует единственный элемент множества В, а каждому элементу В соответствует не более одного прообраза из А, называется отображением множества А во множество В (инъекция).

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

Введение в теорию множеств и комбинаторику

Практическая работа № 8. Отображения. Виды отображений

Вопросы к работе

1. Что такое «отображение множества в множество»?
2. Что такое «образ», что такое «прообраз» при данном отображении?
3. Что такое полный f - образ, что такое полный f - прообраз, при отображении f ?
4. Назовите типы отображений, дайте их определения и приведите примеры.
5. Какие два множества называются эквивалентными? Приведите примеры.
6. Какое множество называется счетным? Приведите примеры.

Образцы решения заданий

Пример 1. Пусть А = {1; 2; 3; 4; 5; 6; 7; 8; 9} N и В ={0; 1} Z Поставим в соответствие каждому числу x A его остаток при делении на 2.

Является ли это соответствие отображением? Какой тип у этого отображения? Какой элемент является образом элемента 6, 7? Найдем полный прообраз элемента 1.

Решение. Изобразим заданное соответствие с помощью графа:

Видим, что:

1) каждый элемент множества А , является точкой исхода;

2) у каждой точки исхода, имеется только по одной точке прибытия. (Значит, указанное соответствие является отображением множества А в множество В);

3) Каждый элемент множества В является точкой прибытия. (Значит, это отображение «на»).

Так как в множестве В есть элемент (например, 0), для которого прообразом является ни один элемент из А , то это отображение не является взаимооднозначным.

Образом числа 6 является число 0 В , образом числа 7 – число 1 В . Полный прообраз числа 1 В есть множество чисел {1; 3; 5; 7; 9} А .

Пример 2. Пусть Х – множество треугольников плоскости, Y = R. Выберем единицу измерения длин и сопоставим каждому треугольнику число – периметр этого треугольника. Будет ли это соответствие отображением? Какой тип у заданного отображения? Каков полный прообраз числа у R ?

Решение. Каждый треугольник на плоскости имеет однозначно определенный периметр. Поэтому каждому треугольнику из множества Х сопоставляется единственное число из R , т. е. это соответствие является отображение Х в R . При этом у двух разных треугольников может быть одинаковый периметр. Другими словами, отображение не является взаимооднозначным. Кроме того, не существует треугольника, периметр которого равен отрицательному числу, т.е. отображение не является отображением «на». Пусть у R . Тогда:

1. у > 0, полный образ – множество всех треугольников плоскости, периметр которых равняется числу у , это множество бесконечное.
2. у ≤ 0, полный образ – пустое множество.

Пример 3. Х = {0; 1; 2; 3; 4} N , Y = Z. Отображение f множества Х в множество Y задано следующим образом:

Определим тип этого отображения и построим его график.

Решение. Для каждого x X найдем образ y Y. Соответствующие результаты запишем в таблицу:

y=f(x)	–2

Множество значений отображения f есть множество

A = {–2; 1; 4; 7; 10} Y и В ≠ Y . У каждого элемента y В в Х имеется только по одному прообразу. Мы имеем, следовательно, отображение взаимооднозначное множества Х в множество Y .

Пары значений (x ; у ) из таблицы образует график данного отображения f: Х→Y . В прямоугольной системе координат этот график имеет вид:

Пример 4. Даны два множества слов: Х = {красный; синий; зеленый; желтый} и Y = {галстук; свет; платок; лист}. Эквивалентны ли эти множества?

Решение. Эти множества эквивалентны, т. к. для них можно установить взаимооднозначное отображение "на".

Например:

Пример 5. Даны множества: А = { x | x = 2 n , n N } и

В = { x | x = , n N }. Эквивалентны ли эти множества?

Решение. Эти множества эквивалентны, т. к. можно подобрать взаимооднозначное отображение множества A на множество В .

Например: f: А В

x = 2 n y = .

Упражнения

1. Между множеством имя Х = {Андрей; Борис; Михаил; Алексей; Константин; Василий; Валентина; Клара; Семен; Мария; Софья; Олег; Трофим4 Юрий; Яков} и множеством Y (букв русского алфавита) установлено соответствие, при котором каждому имени сопоставляется его первая буква. Будет ли это соответствие отображением Х в Y ? Если "да", то какого типа? Найдите образ множества Х . Найдите полные прообразы букв А , Б, К, Л. Постройте граф указанного соответствия.

2. Каждой точке М отрезка АВ поставим в соответствие ее проекцию М на данную прямую L . Будет ли это соответствие отображением? Каким? Опишите область определения, область значений этого отображения.

3. Множество Х состоит из всех квадратов на плоскости, а множество Y из всех окружностей на той же плоскости. Поставим в соответствие каждому квадрату вписанную в него окружность. Является ли это соответствие отображением Х на Y ?

4. Можно ли задать отображение следующим образом: множество А из отрезков, на Y – из треугольников; каждому отрезку ставится в соответствие треугольник, для которого этот отрезок является средней линией?

5. Верно ли, что соответствие f: Z Z

X у = –5 х + 2

есть отображение "на"?

6. Пусть Х – множество вещественных чисел. Каждому числу х Х поставим в соответствие его квадрат. Можно ли это соответствие назвать обратимым отображением?

7. Покажите, что следующие множества счетны:

а) множество нечетных натуральных чисел;

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

в) множество квадратов натуральных чисел;

г) множество натуральных чисел, кратных 5;

д) множество кубов натуральных чисел.

8. Даны два множества: A = {Париж; Москва; Варшава; Краков; Лондон; Саранск; Владимир; Марсель} и B = {Франция; Россия; Англия; Польша; Швеция; Австрия}. Зададим соответствие между ними: «город x A находится в стране ». Построим графики этого соответствия. Будет ли это соответствие отображением? Какого типа?

9. Эквивалентны ли множества А изображений населенных пунктов на карте и множество B населенных пунктов местности, изображенной на карте?

Индивидуальное задание

1. Среди указанных соответствий выбрать отображения. Указать их тип, построить график.

2. Изобразите в прямоугольной декартовой системе координат графики следующих отношений в Z . Для каждого отношения выясните, является ли оно отображением Z в Z , отображением Z на Z , взаимооднозначным отображением, наложением:

1) х + у = 3; 7) у < х + 2;

2) х – у ≤ 5; 8) у ≤ х + 2;

3) х + у = 4, x > 0; 9) у = 4;

4) x = y , – 4 ≤ х ≤ 6; 10) ху = 24, –6 ≤ х ≤ 6.

5) = у , – 4 ≤ х ≤ 6;

6) x > у ;

Задания для самоконтроля

Соедините следующие пары множеств знаком «=», если они равны, и знаком «~», если они эквивалентны:

1) А – множество сторон треугольника,

В - множество углов треугольника;

2) А - множество букв в слове «колос»,

В = {о; к; с; л};

3) А – множество колец на пне дерева,

В – множество лет, прожитым деревом;

4) множество материков на Земле и множество государств

ОТОБРАЖЕНИЯ МНОЖЕСТВ §1. Основные определения

Определение. Пусть А и В – два множества. Говорят, что задано отображение f множества А в В, если указан закон, по которому любому элементу а из А ставится в соответствие единственный элементb из множества В:

Отображения также называют функциями .

Будем использовать следующие обозначения:

ƒ : А→ В. Отображение f множество А переводит в В;

А f В. Множество А отображается в В при отображении f.

Если элемент а при отображении f переходит в элемент b, то пишут f(a)=b (левая запись) или af=b (правая запись). Элемент b называется образом элемента а при отображении f; элемент а – прообразом b при

этом отображении. Множество { f (a ) | a A } = f (A ) – образ множества А при отображении f. Отметим, что

f (A ) B .

А B

f f(A)

А – область определения отображения f; В – область значений отображения f (иногда –например, в школьной математике – областью значений считается f(A), но мы будем ею считать В).

Отметим, что мы рассматриваем только однозначные отображения.

Из всех отображений особо выделяют следующие виды :

1. Сюръекция (отображение «на») – это отображение f : A → B такое, что f (A ) = B . При сюръекции у каждого элемента из множества В существует хотя бы один прообраз.

2. Инъекция – отображение, при котором разные элементы переходят в разные, т.е. если a , a 1 A и a ≠ a 1 , то f (a ) ≠ f (a 1 ) .

				f(a1 )

3. Биекция, или взаимно однозначное отображение – это отображение, которое одновременно является инъекцией и сюръекцией.

Примеры отображений:.

1. Пусть А – любое множество и В – множество, состоящее из одного элемента, т.е. B={b}.

А . b

Отображение f (a ) = b , a A является сюръекцией, т.к. f(A)=B.

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

А а

φ(а) В

Обозначим это отображение через φ. Очевидно,

ϕ (a ) ≠ ϕ (a 1 ), a , a 1 A , a ≠ a 1 .

Следовательно, отображение φ – инъекция (но не является сюръекцией).

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

т.е. f – биекция.

Отметим, что именно так в математике доказывается, что «количество» точек на гипотенузе и катете одинаково (точнее, эти множества имеют одинаковую мощность).

Замечание. Нетрудно придумать отображение, которое не является ни сюръекцией, ни инъекцией, ни биекцией.

4. Если f – любая функция действительного переменного, то f – отображение R в R.

§2. Умножение отображений

Пусть А, В, С – три множества и заданы два отображения f : A → B и ϕ : B → C .

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

ϕ f

Возможны два варианта записи.

1. Левая запись.
ƒ (a)=b, ϕ (b)=c.		обозначить ϕ f :
Тогда произведение f и φ будет	переводить а в с, его следует
(ϕ f ) (a ) = ϕ (f (a ) ) = ϕ (b ) = c , ϕ f : A → C (см. выше рисунок).
По определению (ϕ f ) (a ) = ϕ (f (a ) ) ,	т.е. произведение отображений –	это сложная функция,
заданная на А.

2. Правая запись.

aƒ =b, bϕ =c. Тогда a (f ϕ ) = (af ) ϕ = b ϕ = c ,

f ϕ : A → C.

Мы будем пользоваться левой записью (отметим, что в книге используется правая). Произведение отображений ниже мы будем обозначать через f ϕ .

Замечание 1 . Из определения умножения отображений следует, что перемножать можно не любые отображения, а только те, у которых «средние» множества одинаковые. Например, если f : A → B ,ϕ : D → C , то при В=D можно перемножать отображения f и φ, а при В≠D нельзя.

Свойства умножения отображений

Определение 2 . Отображения f и g называются равными , если у них совпадают области определения и области значений, т.е. f : A → B , g : A → B и выполняется условие: a A справедливо

равенство f (a ) = g (a ) .

1. Умножение отображений некоммутативно. Другими словами, если fφ и φf существуют, то они не обязательно равны.

Пусть, например, множества A=B=C=R, f (x ) = sin x ,ϕ (x ) Рассмотрим произведения:

(ϕ f ) (x ) = ϕ (f (x )) = ϕ (sin x ) = e sin x ,

(f ϕ ) (x ) = f (ϕ (x )) = f (e x ) = sin(e x ).

Следовательно, функции fφ и φf различны.

2. Умножение отображений ассоциативно.

Пусть f : A → B , ϕ : B → C , ψ : C → D . Докажем, что (ψϕ ) f

E x , f : R → R, ϕ : R → R .

и ψ (ϕ f ) существуют и равны,т.е.(ψϕ ) f =

ψ (ϕ f ) . (1)

Очевидно, что (ψϕ ) f : A → D ,ψ (ϕ f ) : A → D .

Для доказательства равенства (1) в силу определения равенства отображений требуется проверить, чтоa A : ((ψϕ ) f ) (a ) = (ψ (ϕ f )) (a ) (2). Пользуясь определением умножения отображений (в левой записи)

((ψϕ )f )(a ) = (ψϕ )(f (a ) )= ψ (ϕ (f (a ) )),

(ψ (ϕ f ))(a ) = ψ ((ϕ f )(a ) )= ψ (ϕ (f (a ) )). (4)

Т.к. в равенствах (3) и (4) равны правые части, то равны и левые, т.е. справедливо равенство (2), а тогда выполняется и (1).

Замечание 2. Ассоциативность умножения позволяет однозначно определить произведение трех, а затем и любого конечного числа множителей.

несколько прообразов в А, либо вообще не быть прообразов. Однако для биективного отображения f обратное определить можно.

Пусть f : A → B – биекция, f (a ) = b , a A , b B . Тогда для любого элемента b B по определению биекции существует единственный прообраз при отображении f – это элемент а. Теперь можно определить f − 1 : B → A , полагая f − 1 (b ) = a (b B ) . Нетрудно видеть, что f − 1 – биекция.

Итак, у всякого биективного отображения имеется обратное.

§3. Преобразования множеств

Всякое отображение f : A → A называется преобразованием множества А. В частности, любая

функция действительной переменной является преобразованием множества R.

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

Так как преобразования – это частный случай отображений, то для них справедливо всё сказанное выше об отображениях. Но умножение преобразований множества А имеет и специфические свойства:

1. для любых преобразований f и φ множества А произведения fφ и φf существуют;

2. существует тождественное преобразование множества А ε : ε (a ) = a , a A .

Нетрудно видеть, что для любого преобразования f этого множества f ε = ε f = f , так как, например, (f ε ) (a ) = f (ε (a ) ) = f (a ) . Значит, преобразование ε играет роль единичного элемента при умножении преобразований.

равенства легко проверяются. Тем самым обратное преобразование играет роль обратного элемента при умножении преобразований.

Рассмотрим еще один важный частный случай общего понятия соответствия - отображения множеств. При соответствии R между множествами Х и Y образ элемента а Х может оказаться пустым, а может содержать и несколько элементов.

Отношение между элементами множеств Х и Y называется отображением Х в Y , если каждому элементу х из множества Х соответствует только один элемент множества Y . Этот элемент называют образом элемента х при данном отображении: f(x). На графе такого отображения из каждой точки множества Х будет выходить только одна стрелка (рис. 29).

Рассмотрим следующий пример. Пусть Х - множество студентов в аудитории, а Y - множество стульев в той же аудитории. Соответствие «студент х сидит на стуле у » задает отображение Х в Y . Образом студента х является стул.

Пусть Х = Y = N - множество натуральных чисел. Соответствие «десятичная запись числа х состоит из у цифр» определяет отображение N в N . При этом отображении числу 39 соответствует число 2, а числу 45981 - число 5(39 - двузначное число, 45981 - пятизначное).

Пусть Х - множество четырехугольников, Y - множество окружностей. Соответствие «четырехугольник х вписан в окружность у » не является отображением Х в Y , так как есть четырехугольники, которые нельзя вписать в окружность. Но в этом случае говорят, что получилось отображение из множества Х в множество Y .

Если отображение Х в Y таково, что каждый элемент y из множества
Y соответствует одному или нескольким элементам х из множества Х , то такое отображение называют отображением множества Х на множество Y .

Множество Х называют областью определения отображения f: XY, а множество Y - областью прибытия этого отображения. Часть области прибытия, состоящая из всех образов y из множества Y, называется множеством значений отображения f.

Если y=f(x), то х называют прообразом элемента у при отображении f . Множество всех прообразов элемента у называют его полным прообразом: f (y).

Отображения бывают следующих видов: инъективными, сюръективными и биективными.

Если полный прообраз каждого элемента yY содержит не более одного элемента (может быть и пустым), то такие отображения называют инъективными.

Отображения XY такие, что f(X)=Y , называют отображениями Х на все множество Y или сюръективными (из каждой точки множества Х выходит стрелка, а после изменения направления в каждой точке множества Х заканчивается) (рис. 31).

Если отображение инъективно и сюръективно, то его называют взаимно однозначным или биективным.

Отображение множества Х на множество называется биективным , если каждому элементу х Х соответствует единственный элемент yY, а каждый элемент yY соответствует только одному элементу х Х (рис. 32).

Биективные отображения порождают равномощные (эквивалентные) множества: X~Y.

Пример . Пусть - Х множество пальто в гардеробе, Y - множество крючков там же. Поставим в соответствие каждому пальто крючок, на котором оно висит. Это соответствие является отображением Х в Y. Оно инъективно, если ни на одном крючке не висит более одного пальто или некоторые крючки свободны. Данное отображение сюръективно, если все крючки заняты или на некоторых висят несколько пальто. Оно будет биективным, если на каждом крючке висит только одно пальто.

Изучим теперь некоторые вопросы, связанные с отношениями между множествами.

Будем говорить, что между множествами изаданоотношение (инаходятся в отношении), если некоторым (возможно всем) элементам изсоответствуют некоторые элементы из. Если множествонаходится в отношениис множеством, то будем писать:

Если при этом элементу ставится в соответствие элемент, то обозначать это будем

Определение 1.1.2. Отношение между множествамииназываетсяотображением , если каждому изпоставлен в соответствие один и только один элементиз(см. рис. 1.1.2. и 1.1.3). При специализации природы множествивозникают специальные типы отображений, которые носят особые названия “функция”," вектор-функция", "оператор", "мера", "функционал" и т.д. Мы столкнемся с ними в дальнейшем.

Для обозначения функции (отображения) из вбудем пользоваться записью

Рис.1.1.2. Отображение Рис.1.1.3.Отношение, не являющееся

отображением

Определение 1.1.3 . Если - элемент из, то отвечающий ему элементиз, называется его образом (при отображении), а множество всех тех, для которых, называется прообразоми обозначается(см.рис.1.1.4).

Рис.1.1.4. Прообраз b

Определение 1.1.4. Отображение называетсявзаимно однозначным отображением , если каждый элемент из имеет единственный образ при отображениии каждый элемент изимеет единственный прообраз при этом отображении.

Рис.1.1.5. Взаимно однозначное отображение

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

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

1.7. Мощность множества

При исследовании отношений между множествами большой интерес представляет "объем" множеств, число элементов в них. Но разговор о числе элементов понятен и обоснован, если это число конечное. Множества, состоящие из конечного числа элементов, будем называть конечными . Однако, многие из множеств, рассматриваемых в математике, не являются конечными, например, множество действительных чисел, множество точек на плоскости, множество непрерывных функций, заданных на некотором отрезке и т.д. Для количественной характеристики бесконечных (да и конечных) множеств в теории множеств используется понятие мощности множества .

Будем говорить, что множества иимеютодинаковую мощность , если существует взаимно однозначное отображение множества на множество(заметим, что в этом случае существует и взаимно однозначное отображение множества B на множество A).

Если множества иимеют одинаковую мощность, то будем говорить, что ониэквивалентны , это обозначается: .

Пусть - произвольные множества, тогда

т.е. любое множество эквивалентно самому себе; если множество эквивалентно множеству, тоэквивалентно; если, наконец, множествоэквивалентно множеству, которое эквивалентно множеству, тоэквивалентно.

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

Если конечные множества имеют разное число элементов, то ясно, что одно из них содержит меньше элементов, чем другое. А как сравнить в этом смысле бесконечные множества? Будем говорить, что мощность множества меньше мощности множества, если существует подмножество множества, эквивалентное множеству, но сами множестваине являются эквивалентными.

Мощность конечного множества равна числу его элементов. Для бесконечных множеств понятие "мощность" является обобщением понятия "количество элементов".

Укажем некоторые, полезные для дальнейшего, классы множеств.

Множество называется счетным , если оно имеет такую же мощность как и некоторое подмножество множества (множества натуральных чисел). Счетное множество может быть конечным или бесконечным.

Бесконечное множество является счетным тогда и только тогда, когда оно эквивалентно множеству натуральных чисел .

Заметим, что любое множество, мощность которого меньше мощности бесконечного счетного множества, является конечным.

Множество действительных чисел на отрезке от нуля до единицы имеет мощность континуум , и само часто называется континуумом . Мощность этого множества больше мощности бесконечного счетного множества. Возникает вопрос: имеется ли множество, мощность которого больше мощности бесконечного счетного множества, но меньше мощности континуум. Эта задача была сформулирована в 1900 году одним из крупнейших математиков мира Давидом Гильбертом. Оказалось, что эта задача имеет несколько неожиданный ответ: можно считать, что такое множество существует, а можно считать, что его не существует. Получающиеся при этом математические теории будут непротиворечивыми. Доказательство этого факта было доложено американским ученым Коэном в 1965 году на всемирном конгрессе математиков в Москве. Отметим, что ситуация с этой задачей напоминает ситуацию с пятым постулатом Евклида: через точку, лежащую вне данной прямой можно провести только одну прямую, параллельную данной. Как показал Лобачевский, отказ от этого постулата не приводит к противоречиям. Мы можем строить геометрию, для которой этот постулат имеет место, и геометрии, для которых он не верен.

В заключение приведем несколько примеров, демонстрирующих методику доказательства эквивалентности множеств.

Пример 1.11. Множество целых чисел счетное.

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

Для доказательства счетности множества целых чисел надо построить взаимно однозначное отображение между множеством натуральных чисел и рассматриваемым множеством. Требуемое отображение задается правилом: расположим целые числа следующим образом:

и перенумеруем их натуральными числами, присвоив им номера (они указаны рядом с рассматриваемыми целыми числами). Очевидно, что каждое целое число получит свой номер, при этом разные числа получат разные номера. Верно и обратное: для каждого натурального числа (для каждого номера) найдется и при том единственное целое число, стоящее под этим номером. Таким образом, требуемое взаимно однозначное отображение построено.

Пример 1.12 . Множество рациональных чисел счетное.

Известно, что любое рациональное число можно представить в виде несократимой дроби p/q, используя это представление расположим рациональные числа в соответствии со схемой:

. . . . . .

Перенумеруем эти числа примерно так же, как и в предыдущем примере (номера указаны сверху в скобках рядом с числами). Нетрудно убедиться в том, что сформулированное правило нумерации рациональных чисел дает требуемое взаимно однозначное отображение множества натуральных чисел в множество рациональных чисел.

Пример 1.13 . Объединение счетного множества счетных множеств есть множество счетное.

Доказательство этого факта аналогично доказательству утверждения предыдущего примера.

В заключение приведем важное для дальнейшего утверждение. Но для этого нам потребуется еще одна операция над множествами.

Прямым произведением множеств и(декартовым произведением ) называется множество всех упорядоченных пар , гдеи. Это множество обозначается. Таким образом:

Обозначим , произведениесомножителейбудем обозначать.

Теорема 1.1 . для любого бесконечного множестваБолее того.

В частности , т.е. множество точек на прямой имеет такую мощность, что и множество точек на плоскости. Более того, точек в пространстве столько, сколько и на прямой.

На этом мы заканчиваем знакомство с основными понятиями математической логики и теории множеств - основ современной математики. Отметим, что многие аспекты этих теорий остались, к сожалению, за рамками этой главы, познакомиться с ними можно, например, по и .