Канторовские нумерации

Множество можно занумеровать с помощью функции , т.е.

ТЕОРЕМА. Отображение – биекция.

Доказательство. Пусть . Найдем максимальное натуральное m такое, что и положим

Тогда , т.е.

Пусть Пусть для определенности Тогда

Отсюда

Замечание. Канторовская нумерация вычислима по Тьюрингу.

Упражнения

1. Найти пару c номером 20.

2. Найти номер пары

Решение (1).

Ответ:

Пример. Найти проекцию числа 121.

Решение. С (1, 14) = 121

Канторовская нумерация троек, n -ок вводится по правилу

Пример.

С (1, 4, 0) = 121. Это следует из того, что С (1, 14) = 121 и С (4, 0) = 14.

Множество занумеруем по формуле

Таким образом, мы занумеровали все конечные наборы чисел.

Пример.