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

Файл : kursovik.doc (размер : 163,840 байт)

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

N={1, 2, 3, . . .},

тогда всякое множество А эквивалентное множеству N будет называться исчислимым, или счётным множеством.

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

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

Вот несколько примеров счётных множеств:

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

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

C={,};

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

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

Х={x, x, x, . . . ,x, . . . } .

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

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

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

Теорема 2. Рациональные числа R образуют счётное множество.

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

таблице;

- 2 -

1 2 3 4 . . .

. . .

. . .

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

. . . . . . . . . .

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

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

. . .

. . . .

. . . . .

. . . . . .

В результате все рациональные неотрицательные числа оказываются занумерованными, то есть мы доказали, что они образуют счётное множество.

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

1 -1 2 -2 . . .

- EMBED Equation.3 -. . .

- EMBED Equation.3 -. . .

. . . . . . . . . . .

-. . . . . . . .

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

Перенумеровав элементы таблицы тем же способом, что и выше, мы получили, что множество всех рациональных чисел является счётным множество.

III. Сформулируем и докажем несколько теорем характеризующих счетные множества.

- 3 -

Теорема 3. Из всякого бесконечного множества Х можно выделить счетное множество Y.

Доказательство: Пусть множество Х бесконечное множество. Выделим из множества Х произвольный элемент и обозначим его х1. Так множество Х бесконечно, то оно не исчерпывается выделение этого элемента х1. и мы можем выделить элемент х2 из оставшегося множества Х\{ х1}. По тем же соображениям множество Х\{ х1, х2} не пусто, и мы можем и из него выделить элемент х3. Ввиду бесконечности множества Х мы можем продолжать этот процесс неограниченно, в результате чего получим последовательность выделенных элементов х1, х2, х3, . . . , хn, . . . , которая и образует искомое подмножество Y множества Х.