А затем упорядочить из в последовательность

                                        (4)

Пара  стоит в этой последовательности на месте . Пара, стоящая на месте , встречается в таблице (3) в строке с номерами  и столбце с номером .

Примечание.

- биноминальный коэффициент (см. Т. и Г. Корн “Справочник по математике” стр. 638).

В частности

.

2. Отображение множества  на .

Определим по индукции последовательность взаимно однозначных функций так, чтобы -я функция в этой последовательности, обозначается , взаимно однозначно отображала множество  на . Отождествляя каждую одночленную последовательность с её существенным членом, положим

 для

 для

Теорема 3. Функция  взаимно однозначно отображает  на .

Д о к а з а т е л ь с т в о. Для  теорема очевидна. Предположим, что она верна для . Если , то , откуда  и по определению  отображает  в . Взаимная однозначность функции  следует из импликаций.

.

Осталось доказать, что для каждого  существует такая последовательность , что .

По предположению индукции существует такая последовательность , что . Искомой последовательностью  будет последовательность, у которой первые  члены совпадают с , а последним членом является . Действительно, для такой последовательности  верно .

3. Отображение множества всех конечных последовательностей натуральных чисел на .

Обозначим для

.

Эта функция взаимно однозначно отображает множество всех непустых конечных последовательностей натуральных чисел на множество . Отсюда легко следует теорема.

Теорема 4. Существует функция , отображающая взаимно однозначно множество  всех конечных последовательностей натуральных чисел на множество  и удовлетворяющая условию .

Достаточно для непустых последовательностей  положить  и .

4. Отображение множества  на  и  на .

Пусть - натуральное число. Положим для :

, , .

Таким образом, если  и  - последовательности длины  с членами  и  соответственно, , то  - последовательность длины  с членами , , а  и  - последовательности с членами  и , .

Аналогичные определения принимаем и для бесконечных последовательностей натуральных чисел. Пусть . Положим

, , .

Таким образом,  - бесконечная последовательность,  у  которой -й член равен , а  и  - бесконечные последовательности, -е члены которых соответственно равны  и .

Теорема 5. Сужение функции  на множество  взаимно однозначно отображает это множество на . Функция  взаимно однозначно отображает множество  на .

Теорема 6. Для любого  и любого  имеют место равенства , .

Доказать самостоятельно.

5. Отображение множества  на .

Положим для  и

,

т.е. - последовательность

Теорема 7. Функция  (ставящая в соответствие последовательности  последовательность ) взаимно однозначно отображает множество  на множество .

Д о к а з а т е л ь с т в о. Очевидно, что  для каждого . Функция  взаимно однозначна, т.к. из равенства  следует, что  для каждого натурального . Тогда  для любых  и . В частности, для  и  имеем  для всех . Наконец, каждый элемент множества  или, другими словами, каждую бесконечную последовательность , членами  которой являются элементы множества  ( - произвольное натуральное число), можно представить в виде при надлежащем выборе . В самом деле, если  задать равенствами , то  будет последовательностью с n-ым членом , т.е.  для всех . Следовательно, .