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

Определение Множества, эквивалентные по числу элементов множеству N={1, 2, 3, 4, …} называются счетными множествами.

Примеры счетных множеств:

{2, 4, 6, 8, …}; ;{1, 4, 9, 16, 25, …}; {1, 8, 27, 64, 125, …}

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

Теорема 1. Для того, чтобы множество А было счетным, необходимо и достаточно, чтобы его можно было представить в виде А={a₁, a₂, a₃,…} (т.е. в так называемой форме последовательности)

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

Любое условие, из которого следует наше утверждение, называется достаточным условием.

Соотношение между этими понятиями может быть пояснено и таким рисунком.

Можно написать и так:

Дост. условие Ì утверждение Ì необх. условие.

То, что нам надо доказать, выглядит теперь так:

Ну, а теперь

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

Достаточность Пусть А можно представить в форме последовательности А={a₁, a₂, a₃,…}. тогда следующее правило дает взаимно-однозначное соответствие между А и N.

Следовательно А – счетно.

Необходимость. Пусть А счетно. Тогда есть правило, устанавливающее взаимно-однозначное соответствие между А и N. Пусть числу nÎN поставлен в соответствие элемент из А, который мы обозначим через a_n. Тогда А можно представить в виде А={a₁, a₂, a₃,…}, т.е. в форме последовательности. < (знак< означает конец доказательства).

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

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

Пусть А – бесконечное множество. Возьмем произвольный элемент а₁ÎА. тогда множество А\{а₁} будет по-прежнему бесконечным.

Из множества А\{а₁} возьмем произвольный элемент а₂ÎА\{а₁}. Множество А а₂ÎА\{а₁, a₂} будет по-прежнему бесконечным.

Из множества А\{а₁, a₂} возьмем произвольный элемент а₃Î А\{а₁,a₂}. Множество А а₂ÎА\{а₁, a₂, а₃} будет по-прежнему бесконечным.

Продолжая этот процесс до бесконечности, мы получим счетное множество В={a₁, a₂, a₃,…}, для которого очевидно, что ВÌА, т.е. В является подмножеством А.<

Теорема 3. Всякое бесконечное подмножество счетного множества тоже счетно.

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

Пусть А – счетное множество и ВÌА также содержит бесконечное число элементов. Представим А в форме последовательности: А={a₁, a₂, a₃,…}. Будем рассматривать элементы множества А по порядку, т.е. а₁, затем а₂,а₃ и т.д. При этом мы иногда будем “наталкиваться” на элементы подмножества В. Будем ставить этим элементам множества В в соответствие “номер встречи с ним”. Тем самым, будет установлено взаимно-однозначное соответствие между В и N, что и говорит о счетности В.<

Суть теорем 2 и 3 можно сформулировать так: счетное множество есть самое маленькое из всех бесконечных множеств.

Теорема 4. Сумма конечного числа счетных множеств есть также счетное множество.

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

Пусть для простоты имеются два счетных множества А и В.

А={a₁, a₂, a₃,…}.

В={b₁, b₂, b₃,…}.

Представим их сумму в виде

АÈВ={a₁, b₁, a₂, b₂, a₃, b₃,…}.

Из теоремы 1 следует, что АÈВ есть счетное множество.<

Замечание. Заметим, что представление АÈВ в виде

АÈÈВ= {а₁, a2, a₃, … b₁, b₂, b₃,…} не доказывало бы нашу теорему. Почему?