Пусть множество X̧ бесконечно. Покажем, что X - счетное множество. Из бесконечности множества X следует, что для любого NΧ множество {k: kÎX и k>N} не пусто. Так как это множество состоит из натуральных чисел, то существует минимальный элемент этого множества. Следовательно, существует последовательность {mn} такая, что

" NΧ Ð mN = min {k: kÎX и k>N}

Рекурсивно определим последовательность {an}:

a1 = min X,    ai+1 = mai  " iΧ

Следовательно, " iΧ Ð ai+1 = min {k: kÎX и k>ai}     (1)

Итак, мы определили последовательность, каждый следующий член которой ai+1 равен минимальному среди элементов множества X, больших предыдущего члена ai.

Так как последовательность натуральных чисел {an} строго возрастает, то " n Ð an³n. Следовательно, для любого NÎX существует n: an³N. Поэтому множество натуральных чисел {n: an³N} не пусто. Через n0 обозначим минимальный элемент этого множества. Тогда an0³N. Покажем, что an0£N.

Если n0=1, то неравенство an0£N следует из условий a1 = min X, NÎX. Если n0>1, то из неравенства n0-1<n0 получаем, что n0-1Ï{n: an³N}, то есть, an0-1<N, а значит, NÎ{k: kÎX и k>an0-1}. Отсюда и из (1) следует, что an0 = min {k: kÎX и k>an0-1} £ N.

Из неравенств an0³N и an0£N следует, что an0=N. Тем самым доказано, что для любого NÎX существует индекс n такой, что an=N. Из строго возрастания последовательности {an} следует единственность такого индекса.

Поэтому последовательности {an} задает взаимно однозначное соответствие множеств § и X. Следовательно, множество X счетно.   0

Назад