Мощность множеств

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

Определение. Говорят, что множество A эквивалентно множеству B, если существует биективное отображение f:A --> B.

Под словами "биективное отображение" понимают взаимнооднозначное отображение "на". Если биекция построена, то пишут A ~ B.

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

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

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

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

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

Доказательство. а) Необходимость. Пусть два конечных множества имеют одинаковую мощность |A| = |B| = n, т.е.

Отображение f:A --> B определенное по формуле f(a_k) = b_k, k = 1,..,n является биекцией и следовательно A ~ B.

b) Достаточность. Пусть A ~ B и f:A --> B биекция, устанавливающая эту эквивалентность. Если

и элементы f(a_k) попарно различны. Следовательно, |A| = |B| = n. Доказательство утверждения завершено.

Определение. Множество A называется счетным, если оно эквивалентно множеству натуральных чисел: A ~ .

В этом случае говорят, что множество A имеет счетную мощность.

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

Доказательство. а) Необходимость. Пусть множество A счетно. Это означает, что A ~ . По определению эквивалентности существует биекция f: --> A. Положим a_n = f(n), n Î . Тогда

и тем самым мы перенумеровали элементы множества A.

b) Достаточность. Пусть элементы множества A перенумерованы, т.е.

Определим отображение f: --> A f(n) = a_n, n Î очевидно, что f - биекция и поэтому ~ A Доказательство утверждения завершено.

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

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

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

КАРТИНКА

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

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