В первой лекции говорилось о мощности конечных множеств, при этом мощностью конечного множества называлось число его элементов. Теперь перейдем теперь к множествам с бесконечным числом элементов. Как сравнивать такие множества априори непонятно - и в том и в другом множестве имеется бесконечно много элементов. Какая из двух бесконечностей больше? Поэтому, когда сравнивают бесконечные множества, обычно прибегают к такому трюку: пытаются построить отображение одного множества на другое, и если это удается, да еще отображение оказывается взаимно-однозначным, то множества объявляют "равными".

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

Говорят, что множество A эквивалентно множеству B, если существует биективное отображение f:  (см.: Л.3, опр.4).

Под словами "биективное отображение" понимают взаимно-однозначное отображение "на". Эту биекцию записывают как  A~B .

ПРИМЕР 3.

1. Множество N и множество четных натуральных чисел эквивалентны. Необходимая биекция задается формулой f(n)=2n, .

2. Множества (0,1) и R эквивалентны. Этот пример немного неожиданен, поскольку утверждается, что число точек открытого интервала (0,1) равно числу точек всей вещественной прямой. Нужная нам биекция строится следующим образом (рис. 1). Представим интервал (-1,1) в виде некоторой полуокружности. Множество действительных чисел представим некоторой прямой. Из центра полуокружности проведем любую прямую линию в некоторую точку (m_i) на прямой R. Очевидно, что прямые линии, соединяют единственную точку  на полуокружности с единственной точкой  вещественной прямой и задают биекцию между точками интервала (0,1) и точками всей прямой, являющейся множеством R.

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

Теорема 3.

Два конечных множества имеют одинаковую мощность тогда и только тогда, когда они эквивалентны.

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

Необходимость. Пусть два конечных множества имеют одинаковую мощность |A|=|B|= n, т.е. A = {a₁, a₂,..., a_n}, B = {b₁, b₂,..., b_n}. Отображение f: A B, определенное по формуле f(a_k) = b_k, k = 1, ..., n, является биекцией и, следовательно, A~B.

Достаточность. Пусть A~B и f: A B – биекция, устанавливающая эту эквивалентность. Если A = {a₁, a₂,..., a_n }, то B = { f(a₁), f(a₂),..., f(a_n)}и элементы f(a_k) попарно различны. Следовательно, |A|=|B|= n. Доказательство завершено.

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

Множество A называется счетным, если оно эквивалентно множеству натуральных чисел: A~N . В этом случае говорят, что множество A имеет счетную мощность.

Теорема 4.

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

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

Необходимость. Пусть множество A счетно. Это означает, что A~N. По определению эквивалентности существует биекция f: . Положим, что a_n= f(n), . Тогда A={a₁, a₂,... }, и тем самым мы перенумеровали элементы множества A.

Достаточность. Пусть элементы множества A перенумерованы, т.е. A={a₁,a₂,...}. Определим отображение f:  или f(n)=a_n, . Очевидно, что f – биекция и поэтому N~A. Доказательство завершено.

Теорема 5.

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

Теорема 6.

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

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

Итак, мы познакомились с конечными и бесконечными множествами. Было показано, что надо понимать под мощностью множеств в каждом из рассмотренных случаев. Однако возникает вполне естественный вопрос – а существуют множества с мощностью большей, чем счетная?

3. Мощность континуума

Теорема 7.

Множество M = (0,1) несчетно.

Предположим, что множество M - счетно и, следовательно, элементы этого множества можно перенумеровать, используя все натуральные числа, т.е. M = {x₁,x₂,... }. Запишем числа  в виде десятичных дробей (без 9 в периоде):

...

здесь ; верхний индекс обозначает номер числа, а нижний – порядковый номер знака. Теперь образуем новое число   по следующему правилу: , если , и 0, если . Тогда очевидно, что , но образованное таким образом новое число не совпадает ни с одним из пересчитанных чисел x_i. Следовательно, интервал (0,1) содержит, как минимум, на 1 точку больше, чем есть натуральных чисел, и его мощность не равна мощности множества натуральных чисел. Мы доказали, что множество точек интервала (0,1) не счетно.

Множество A имеет мощность континуума, если оно эквивалентно множеству точек интервала (0,1). Мощность континуума обозначают буквой c.

ПРИМЕР 4.

Пусть a<b – два действительных числа. Покажем, что интервал (a,b) имеет мощность континуума. В качестве биекции, устанавливающей эквивалентность множеств (a,b) и (0,1), можно рассматривать функцию f(x) = (b-a)x+a: (0,1) (a,b).

Теорема 8.

Существуют иррациональные числа. Более того, множество иррациональных чисел имеет мощность континуума.

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

Поскольку  и , а , мы получаем, что .

Заключение

В лекции заканчивается тема «Дискретная математика», однако на протяжении всего курса к ней необходимо будет возвращаться с целью расширения объема понятий и знаний. С целью лучшего восприятия остальных тем высшей математики объединим некоторые разделы дискретной математики с остальными темами. При этом нам придется столкнуться с такими разделами дискретной математики, как «Теория графов», «Логика», «Векторные пространства» и др. Важно целостное понимание всех разделов высшей математики на основе пройденного материала. Отметим следующее:

- функция – это множество пар, у которых одному первому элементу соответствует единственный второй элемент;

- как и у отношений, у функций есть обратная функция;

- суперпозиция функции есть «сложная функция» в классическом понимании;

- бесконечные множества имеют мощность;

- мощность . 

Литература

1. Яблонский Я. В. Введение в дискретную математику. – М.: Высшая школа, 2001. – 384 с.

2. Москинова Г.И. Дискретная математика. – М.: Логос, 2002. – 240 с.

3. Ильин В.А., Позняк Э.Г. Линейная алгебра. – М.: Физматлит, 2001.

4. Самсонов Б.Б. и др. Компьютерная математика. – Ростов-на-Дону: Феникс, 2002. – 512 с.