Теорема 1. 1

Объединение любых двух счетных множеств является счетным множеством.

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

Пусть A и B - счетные множества. Возможны следующие случаи.

1. Если A и B - конечные множества, то A È B состоит из конечного числа разных элементов, т.е. является счетным.

2. Если A - конечное, а B - счетно-бесконечное, и A ={ a ₁,..., a _k }, B = { b ₁,..., b _i,...}, где элементы A и B перечислены в порядке соответствия элементов A и B элементам множества { 1,..., k } и множеству натуральных чисел соответственно.

Удалим из A элементы, содержащиеся в B. В результате получим новое множество { a _{j 1},..., a _jl }, которое может оказаться пустым.

Тогда множество { a _{j 1},..., a _jl, b ₁,..., b _i,...}, в котором элементы перечислены в порядке соответствия возрастающим элементам множества натуральных чисел, является множеством, равномощным N.

3. Множества A и B - счетно-бесконечные. Тогда их можно представить в виде:

A = { a ₁,..., a _i,...}, B = { b ₁,..., b _i,...}.

Рассмотрим процесс последовательного выписывания в один список первых, вторых, третьих и последующих элементов этих множеств: a ₁ и b ₁, a ₂ и b ₂, a ₃ и b ₃ и т.д.

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

Этот процесс позволяет записать все элементы множества A È B в виде счетной бесконечной последовательности c ₁,..., c _j,....

Такая последовательность содержит все элементы A È B по одному разу, в сопоставлении их с натуральными числами, так что элемент c _i соответствует числу i.

Следовательно, A È B - является счетным множеством.