II.Определение 1.Пусть N множество всех натуральных чисел

N={1, 2, 3, . . .}, тогда всякое множество А эквивалентное множеству N будет называться исчислимым, или счётным множеством.
Таким образом, если множество А счетное, то между множеством А и множеством натуральных чисел N можно установить взаимно однозначное соответствие, или, как говорят, можно занумеровать элементы множества А, понимая под номером каждого элемента а ( А соответствующее ему при указанном соответствии натуральное число.
Так же из определения счётного множества следует очевиднейший вывод, что все счётные множества эквивалентны между собой.
Вот несколько примеров счётных множеств:

А={1, 4, 9, 16, . . . ,n[pic], . . .};

B={3, 6, 9, 12, . . . ,3n, . . . };

C={[pic],[pic]};

D={1, 8, 27, 64, . . . ,n[pic], . . . };

Теорема 1. Для того чтобы множество Х было счётным необходимо и достаточно, чтобы его можно было «перенумеровать», то есть представить в форме последовательности:

Х={x[pic], x[pic], x[pic], . . . ,x[pic], . . . } .

Доказательство необходимости: Пусть множество Х счетное, то из определения счётного множества следует существование взаимно однозначного соответствия ( между множеством Х и множеством натуральных чисел N.
Достаточно обозначить через х[pic], тот из элементов множества Х, который в соответствии с ( отвечает числу n,чтобы получить представление множества Х в форме (*).

Доказательство достаточности: Если множество Х представлено в форме (*), то достаточно каждому его элементу х, соотнести индекс n этого элемента, чтобы получить взаимно однозначного соответствия ( между множеством Х и множеством натуральных чисел N, так что из определения счётного множества следует, что множество Х счётное.

Следующая теорема даёт интересный пример счётного множества.

Теорема 2. Рациональные числа R образуют счётное множество.
Доказательство: Рассмотрим сначала рациональные неотрицательные числа.
Расположим их в бесконечную таблицу следующим образом: в первую строчку поместим в порядке возрастания в целые числа 0, 1, 2, . . . ; во вторую – все положительные несократимые дроби со знаменателем 2, упорядоченные по величине числителя; вообще в n-ую строчку, n=1, 2, 3, …, - все положительные рациональные числа, записывающиеся несократимой со знаменателем n, упорядоченные по величине числителя. Очевидно, что каждое рациональное неотрицательное число попадёт на какое-то место в получившейся таблице;

- 2 -

0. 1 2 3 4 . . .

[pic] [pic]
[pic] [pic] [pic] . . .

[pic] [pic]
[pic] [pic] [pic] . . .

. . . . . . . . . . . .

[pic] . . . . . . . . . .

. . . . . . . . . . . .

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

. . .

. . . .

. . . . .

. . . . . .
В результате все рациональные неотрицательные числа оказываются занумерованными, то есть мы доказали, что они образуют счётное множество.
Чтобы убедится, что и множество всех рациональных чисел также счётно, достаточно их записать в подобную же таблицу. Это можно сделать, например, поместив в написанную выше таблицу после каждого положительного рационального числа х в туже строчку число - х.

0. 1 -1 2 -2 . . .