Функція Геделя та її основна властивість

Функцiя Геделя G дозволяє кодувати одним натуральним числом довiльну скiнченну послiдовнiсть натуральних чисел. Функцiя Геделя визначається так:

G (x, y) = mod (l (x), 1+(y +1) × r (x)).

Отже, функція G є ПРФ.

Теорема (про основну властивість функції Геделя). Для довiльної скiнченної послiдовностi натуральних чисел b₀, b ₁ ,..,b_n знайдеться натуральне число t, таке, що G (t, i)= b_i для всiх i Î{0,..., n }.

Індукцiєю по n доведемо твердження, відоме як китайська теорема про остачі:

Лeма. Для довiльних натуральних чисел b₀, b ₁ ,.., b_n, для довiльних попарно взаємно простих чисел p₀, p ₁ ,.., p_n, таких, що p_i>b_i для всiх i Î{0,..., n }, знайдеться натуральне число M, таке, що M < p ₀ × ... × p_n та mod (M,p_i)= b_i для всiх i Î{0,..., n }.

1) n =1. Для довiльних взаємно простих p, q

{ mod (i × p, q) | i Î{0,..., q -1}}={0,..., q -1}.

Справдi, для j, i таких, що q>j >i ³ 0, маємо mod (j × p, q) ¹ mod (i × p, q), iнакше (j - i) × p дiлиться на q, що суперечить взаємнiй простотi p та q. Тому для довiльних натуральних b ₀, b ₁ та для довiльних взаємно простих p ₀, p ₁, таких, що p ₀ > b ₀ та p ₁ > b ₁, iснують натуральнi a₀, a₁ такi, що a₀ < p ₀, a₁ < p ₁, mod (a₁ × p ₁, p ₀) = b₀ і mod (a₀ × p ₀, p ₁)= b ₁. Узявши k = =a₀ × p ₀ + a₁ × p ₁, маємо mod (k, p ₀)= b ₀ та mod (k, p ₁) = b ₁. Тодi M ₁= mod (k, p ₀ × p ₁) - шукане M для випадку n =1. Справдi, M ₁< p ₀, p ₁, mod (M ₁, p ₀)= b ₀, mod (M ₁, p ₁)= b ₁, бо k =a × p ₀ × p ₁ +M ₁ для деякого aÎ N.

2) n = k Þ n = k +1. Нехай твердження леми правильне для n = k. Вiзьмемо n = k +1. Маємо натуральнi b ₀, b ₁ ,.., b_{k +1} тa попарно взаємно простi p ₀, p ₁ ,.., p_{k +1}, такi, що p_i>b_i для всiх i Î{0,..., k+ 1}. Покладемо c ₀= M ₁, c ₁ =b ₂,..., c_k=b_{k +1}, q ₀= p ₀ × p ₁, q ₁= p ₂,..., q_k = p_{k +1}. Тодi числа q ₀, q ₁ ,.., q_k попарно взаємно простi та q_i>c_i для всiх i Î{0,..., k }, тому за припущенням iндукцiї знайдеться натуральне число M, таке: M < q ₀ × q ₁ × ... × q_k та mod (M, q_i)= c_i для всiх i Î{0,..., k }. Звiдси дістаємо M < p ₀ × ... × p_{k+ 1}, mod (M,p_i)= b_i для всiх i Î{0,..., k+ 1} та mod (M, p ₀ × p ₁)= M ₁. Останнє означає, що M =a × p ₀ × p ₁ +M ₁ для деякого aÎ N. Звiдси mod (M ₁, p ₀)= mod (M, p ₀)= b ₀ та mod (M ₁, p ₁)= mod (M, p ₁)= b ₁.

Отже, твердження леми правильне i для n = k +1.

Доводимо тепер теорему. Знайдемо числа M та b такi, що t = C (M, b) - шукане, тобто G (t,i)= mod (М, 1+(і +1) × b))= b_i для всiх i Î{0,..., n }.

Покладемо b =(1+ n + b ₀+...+ b_n)!. Залишилось знайти число M. Позначимо p_i =1+(і +1) × b. Тодi p_i>b_i для всiх i Î{0,..., n }. Крiм того, числа p₀, p ₁ ,.., p_n попарно взаємно простi. Справдi, припустимо супротивне: iснує просте q >1, таке, що для деяких i, j, таких, що j>i, числа p_i та p_j дiляться на q. Тодi p_i - p_j =(j - i) × b дiлиться на q. Але j - i < n, тому j - i входить як множник у число b, звiдки i дiлиться на q, тобто b = g × q для деякого gÎ N. Звiдси числа p_i =1+(і +1) × g × q та p_j =1+(j +1) × g × q не дiляться на q, a це суперечить припущенню.

Умови леми виконанi, тому знайдеться натуральне число M, таке, що M < p ₀ × ... × p_n і mod (M,p_i)= mod (М, 1+(і +1) × b))= b_i для всiх i Î{0,..., n }.

Поиск по сайту: