Каталог книг:


Проблемы Гильберта (100 лет спустя) - Содержание - Счетные и несчетные множества

Счетные и несчетные множества

Рассмотрим следующую цепочку: . ( - это множество целых чисел, а - множество рациональных чисел, т. е. множество чисел вида p/q, где p и q - целые, q≠ 0.) Все эти множества бесконечны. Рассмотрим вопрос об их эквивалентности.

Установим взаимно однозначное соответствие между и : образуем пары вида (n,2n) и (-n,2n+1), n, а также пару (0,1) (на первое место в каждой паре ставится число из , а на второе - из ).

Есть и другой способ установить это соответствие, например, выписать все целые числа в таблицу, как показано на рисунке, и, обходя ее по стрелочкам, присваивать каждому целому числу некоторый номер. Таким образом, мы " пересчитаем" все целые числа: каждому z сопоставляется некоторое натуральное число (номер) и для каждого номера есть такое целое число, которому этот номер приписывается. При этом явную формулу выписывать не обязательно.

Таким образом, эквивалентно .

Всякое множество, эквивалентное множеству натуральных чисел, называется счетным. Такое множество можно "пересчитать": пронумеровать все его элементы натуральными числами.

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

Выпишем все элементы + в такую таблицу: в первой строке - все числа со знаменателем 1 (т. е. целые), во второй - со знаменателем 2 и т. д. (см. рисунок). Каждое положительное рациональное число обязательно встретится в этой таблице, и не однажды (например, число 1====... встречается в каждой строке этой таблицы).

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

Итак, мы указали способ пронумеровать все числа из +, т. е. доказали, что + счетно.

Заметим, что этот способ нумерации не сохраняет порядка: из двух рациональных чисел большее может встретиться раньше, а может - и позже.

Как же быть с отрицательными рациональными числами и нулем? Так же как с космозоологами и филателистами в бесконечной гостинице. Пронумеруем + не всеми натуральными числами, а только четными (давая им номера не 1, 2, 3, ..., а 2, 4, 6, ...), нулю присвоим номер 1, а всем отрицательным рациональным числам присвоим (по такой же схеме, что и положительным) нечетные номера, начиная с 3.

Теперь все рациональные числа занумерованы натуральными, следовательно, счетно.

Возникает естественный вопрос: Может быть, все бесконечные множества счетны?

Оказалось, что - множество всех точек на числовой прямой - несчетно. Этот результат, полученный Кантором в прошлом веке, произвел очень сильное впечатление на математиков.

Докажем этот факт так же, как это сделал Кантор: с помощью диагонального процесса.

Как мы знаем, каждое действительное число x можно записать в виде десятичной дроби:

x=A,12...n...,

где A - целое число, не обязательно положительное, а 1, 2, ..., n, ... - цифры (от 0 до 9). Это представление неоднозначно: например,

½=0,50000...=0,49999...

(в одном варианте записи, начиная со второй цифры после запятой, идут одни нули, а в другом - одни девятки). Чтобы запись была однозначной, мы в таких случаях всегда будем выбирать первый вариант. Тогда каждому числу соответствует ровно одна его десятичная запись.

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

x1=A,1234...
x2=B,1234...
x3=C,1234...
x4=D,1234...

Чтобы прийти к противоречию, построим такое число y, которое не сосчитано, т. е. не содержится в этой таблице.

Для любой цифры a определим цифру следующим образом:

=

Положим (у этого числа k-я цифра после запятой равна 1 или 2, в зависимости от того, какая цифра стоит на k-м месте после запятой в десятичной записи числа xk).

Например, если

x1=  2,1345...
x2=  -3,4215...
x3=  10,5146...
x4=  -13,6781...
.....................
то =0,2112...

Итак, с помощью диагонального процесса мы получили действительное число y, которое не совпадает ни с одним из чисел таблицы, ведь y отличается от каждого xk по крайней мере k-й цифрой десятичного разложения, а разным записям, как мы знаем, соответствуют различные числа.

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

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





Это интересно!

Полезные ссылки