Счетные множества. Теорема о существовании подмножества в бесконечном множестве

Множество A называется счётным, если оно эквивалентно множеству всех натуральных чисел. Иначе говоря, для счетного множества A существует биекция , а зто означает, что элементы множества А можно записать в виде последовательности a₁, a₂,... a_n... в которой нет равных членов, и каждый элемент из A равен одному из членов последовательности.

Пример: Множество всех целых чисел счетно,так как eгo можно записать в виде следующей последовательности: 0,1,-1,2,-2,..n,-n,... Счетны также множества , {2, 2²,2³,...2ⁿ...}, {1³,2³,...n³,...}.

Теорема 1: Множество всех пар натуральных чисел счетно, то есть .

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

Доказательство проиллюстрируем следующим рисунком (в отличие от русской матем.символики здесь "/" обозначает не дробь, а стоит вместо запятой, обозначая упорядоченную пару-элемент N*N):

В результате расстановки, указанной стрелками, все элементы приобретут номер, и, значит, это множество- счётное.

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

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

Пусть множество B бесконечно. Тогда оно содержит хотя бы один элемент a₁. В силу бесконечности B в нём найдется элемент a₂, отличный от a₁. Так как злементы a₂ и a₁ не исчерпывают всего множества B, то в нём найдется элемент a₃, отличный и от a₂ и от a₁. Если уже выделено n элементов a₁, a₂,...a_n, то в силу бесконечности B в нём найдётся еще один элемент, который обозначим a_n+1, отличный от всех ранее выбранных элементов. Таким образом, для каждого натурального числа n можно выделить элемент a_n из B, причём все выделенные элементы попарно различны. Выделенные элементы образуют последовательность a₁, a₂,...a_n.... Множество её членов по определению счётно, и это множество есть часть B.

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

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

Пусть множество A счётно, а B - его бесконечное подмножество. По предыдущей теореме множество B содержит счётное подмножество C. Так как множества A и C оба счётны, то они эквивалентны: A~C. Кроме того, . По теореме 4 главы 1 B~A, то есть множество B эквивалентно счётному множеству и потому само счётно.

Теорему 4 можно перефразировать следующим образом: 4': Всякое подмножество счётного множества конечно или счётно.

Дата добавления: 2015-07-24