Требуется доказать, что множество натуральных чисел § равномощно декартову произведению §´§. Для этого построим взаимно однозначное соответствие 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

Назад