Нумерації. Теореми про нерухому точку

1. КОДУВАННЯ ТА НУМЕРАЦІЇ. КАНТОРОВІ НУМЕРАЦІЇ

Під кодуванням множини А на множині В будемо розуміти ін’єктивне та сюр’єктивне відображення : А→В таке, що існують алгоритми A та B:

для кожного аА A(а)(а);

для кожного bB B(b) -1(b).

Нумерацiєю множини А називають сюр’єктивне функцiональне вiдображення : N →А.

Однозначною нумерацiєю множини А називають бієктивне вiдображення : N →А.

Нумерацiю : N →А називають ефективною, якщо iснують алгоритми A та B такі:

для кожного аА A(а)1(а);

для кожного nN B(п)(п).

Таким чином,: N →А ефективна нумерація1: А→N кодування А на N.

Введемо однозначні ефективні нумерацiї пар та n-ок натуральних чисел, які називаються канторовими нумераціями.

Всi пари натуральних чисел розташуємо в послiдовнiсть так:

пара (x, y) передує парі (u, v) x+y
Номер пари (x, y) в такiй послiдовностi позначають C(x, y) та називають канторовим номером пари (x, y).

Неважко переконатись, що C(x, y) = [(x+y+1)(x+y)/2]+x

Лiву та праву компоненти пари з номером n позначають вiдповiдно l(n) та r(n). Функцiї l(n) та r(n) називають вiдповiдно лiвою та правою координатними функцiями.

Функцiя C(x, y) задає бiєкцiю NN→N, пара функцiй (l(n), r(n)) задає бiєкцiю N→NN. При цьому функцiї C, l та r зв’язaнi такими тотожностями:

C(l(n), r(n)=n; l(C(x, y))=x; r(C(x, y))=y.

Маючи нумерацiю пар натуральних чисел, можна ввести нумерацiю n-ок натуральних чисел для довiльного n>2:

Cп(x1, x2,..., xп)=Cп1(C(x1, x2), x3,..., xп)=C(...С(C(x1, x2), x3),...), xп).

Координатнi функцiї Cn1 , ..., Cnn вводимо так:

Нехай Cп(x1, x2,..., xп)=m; тоді Cn1(m)=x1; Cn2(m)=x2; ... , Cnn(m)=xn.

Для функцiй Cп, Cn1 , ..., Cnn справджуються такi тотожностi:

Cп(Cn1(x), ..., Cnn(x))=x;