Требуется доказать, что множество натуральных чисел § равномощно декартову произведению §´§. Для этого построим взаимно однозначное соответствие f ' §´§«§, То есть, каждой паре натуральных чисел (i,j)Χ´§ поставим в соответствие f(i,j)Χ так, чтобы для любого nΧ существовала единственная пара натуральных чисел (i,j) такая, что f(i,j)=n. Иными словами, требуется занумеровать все пары натуральных чисел (i,j).
Идейно нумерацию пар (i,j) построим следующим образом. Все пары (i,j) разобъем на группы с постоянной суммой i+j=N. Внутри группы будем нумеровать (i,j) по порядку возрастания i, то есть, номер пары (i,j) в группе i+j=N будет равен i. После того, как занумерованы все пары (i,j), для которых i+j=N, будем нумеровать пары (i,j), для которых i+j=N+1 и так далее.
Теперь явно определим функцию f(i,j), задающую эту нумерацию. Сначала определим последовательность {an} так, что aN - это число пар (i,j), для которых i+j£N. Так как число пар (i,j), для которых i+j=N+1 равно N (это пары (1,N), (2,N-1), ..., (N,1)), то aN+1 = aN+N. Так как число пар (i,j), для которых i+j=1 равно 0, то a1 = 0. Следовательно, последовательность {an} можно определить рекурсивно:
a1 = 0, ai+1 = ai+i " iΧ (1)
Номер пары натуральных чисел (i,j), для которой i+j=N, равен числу всех пар (i1,j1), для которых i1+j1£N-1 плюс номер пары (i,j) в группе i+j=N. Поэтому определим
f(i,j) = ai+j-1 + i (2)
Теперь осталось доказать, что определенная нами функция f задает взаимно однозначное соответствие f ' §´§«§, то есть,
" (i,j)Χ´§ Ð f(i,j)Χ (3)
" nΧ $! (i,j)Χ´§: f(i,j)=n (4)
Для проверки условия (3) заметим, что из (1) по индукции следует условие
" nΧ Ð an³0,
которое вместе с (2) доказывает условие (3).
Теперь осталось доказать условие (4). То есть, по номеру n требуется найти пару (i,j), занумерованную этим номером: f(i,j)=n. А затем доказать, что такая пара единственна.
Для определения пары (i,j) по номеру n сначала выясним, к какой группе относится эта пара, то есть, чему равна сумма i+j=N. Так как номера пар этой группы начинаются с номера aN-1+1 и кончаются номером aN, то N нужно определять из неравенств
aN-1+1 £ n £ aN (4)
Для доказательства существования такого N рассмотрим множество L номеров N таких, что n£aN. Поскольку из (1) по индукции следует, что
" nΧ Ð an³n-1,
то n+1ÎL, следовательно, множество L не пусто. Определим N = min L. Тогда NÎL и N-1ÏL. Следовательно, существует N, удовлетворяющее неравенствам (4). Покажем, что такое N единственно, то есть, если числа N>1, N1>1 удовлетворяют неравенствам (4) и
aN1-1+1 £ n £ aN1 (5)
то N=N1.
Для этого заметим, что последовательность {an} нестрого возрастает (это следует из (1)). Поэтому, если N<N1, то из (4), (5) получаем n£aN£aN1-1£n-1 - противоречие. Аналогично получается противоречие в случае N1<N. Поэтому число N определяется неравенствами (4) однозначно.
Итак по номеру n однозначно определяется сумма i+j=N для пары (i,j) с номером n=f(i,j). Из (2) следует, что равенства i = n-aN-1, j = N-i однозначно определяют пару (i,j) по ее номеру n. 0