Установили биективное соответствие между { 8k + 1} и N (натуральными числами) .
Тогда множество { 8k + 1 } равномощно множеству N.
Множество N счетно. Поскольку было установлено биективное соответствие, то и { 8k + 1 } - счетно.
{ 8k + 1 } - бесконечно, т. к. счетно.
Для простоты обозначим A = { 8k + 1 }.
Теперь поступим следующим образом разобьем множество A на два множества:
P - множество простых чисел представимых в виде { 8k + 1 }
S - множество составных чисел представимых в виде { 8k + 1}
A = P U S
Пересечение множеств P и S пусто ( т. к. любое число не может быть одновременно простым и составным )
Заметим: два множества одновременно не являются конечными (т. к. объединение двух конечных множеств конечно, а наше множество счетно) .
Значит как минимум одно из множеств счетно.
A = P U S
Теперь поступим следующим образом:
1) Возьмем наименьшее простое число из P и поставим ему в соответствие наименьшее составное число из S
2) Возьмем наименьшее простое число из оставшихся в P ( после (1) - "операции" ) и поставим ему в соответствие наименьшее составное число из оставшихся в S ( после (1) - "операции" )
....
Между P и S установили биективное соответствие. (множества P и S - равномощны)
A = P U S - счетно
Получаем объединение двух равномощных множеств счетно. Такое возможно, когда каждое множество счетно.
P - бесконечно, т. к. счетно.