Пусть множество 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