Забележка 1. Лесно се проверява, че е в сила следното твърдение: ако f е m-местна функция в D,  g₁, …, g_m са n-местни функции в D и h₁, …, h_n са k-местни функциии в D, където m и n са положителни цели числа, а k е неотрицателно цяло число, то

      Когато f е 0-местна функция в D, а n е положително цяло число, ще означаваме с f⁽ⁿ⁾ и ще наричаме n-местен вариант на f в D онази n-местна функция g в D, която се дефинира чрез равенството

      Забележка 2. Бихме могли да си мислим за n-местния вариант на една 0-местна функция в D като за композиция на тази функция с празна редица от n-местни функции в D. Съответният аналог на твърдението от забележка 1 гласи така: ако f е m-местна функция в D, където m е положително цяло число, и g₁, …, g_m са 0-местни функциии в D, то за всяко неотрицателно цяло число k

      За всеки две цели числа n и i, където 1≤i≤n, ще наричаме i-та n-местна проекционна функция в D онази n-местна функция g в D, която се дефинира чрез равенството

      Нека F е дадено множество от функции в D (допустимо е в F да има функции на различен брой аргументи). За всяко неотрицателно цяло число n ще дефинираме кои n-местни функции в D ще наричаме изразими чрез F. Дефиницията е индуктивна и се състои от следните три точки, като при n=0 втората от тях е неизползваема и поради това може да се пропусне:

1. Всяка n-местна проекционна функция в D е изразима чрез F.
2. За всяка 0-местна функция от F нейният n-местен вариант е изразим чрез F.
3. За всяка m-местна функция f от F, където m>0, суперпозицията на f с коя да е m-орка от n-местни функции в D, които са изразими чрез F, също е изразима чрез F.

      Пример 2. Нека D е пак множеството на реалните числа, но F е множеството, състоящо се от двуместните функции събиране и умножение в D и от 0-местната функция  −1. Тогава пък изразими чрез F са точно полиномите с цели коефициенти.

      Дефиницията, която дадохме, осигурява, че всички функции от множеството F са изразими чрез F. Това е така, защото при n>0 всяка n-местна функция в D е равна на своята суперпозиция с n-орката от n-те n-местни проекционни функции в D, а всяка 0-местна функция в D съвпада с 0-местния си вариант. Ще покажем, че операцията суперпозиция, приложена към функции, изразими чрез F, отново дава функция, изразима чрез F. По-точно, ще докажем следното твърдение.

      Запазване на изразимостта при суперпозиция. Нека n е неотрицателно цяло число и g е n-местна функция в D, която е изразима чрез F. Тогава:
        а) ако n>0, k е неотрицателно цяло число и h₁, …, h_n са k-местни функции в D, изразими чрез F, то функцията g(h₁,…,h_n) също е изразима чрез F;
        б) ако n=0, то за всяко неотрицателно цяло число k функцията g^(k) е изразима чрез F.

      Доказателство. Достатъчно е да покажем, че свойството от заключението на доказваното твърдение е налице за функциите от първите две точки в дефиницията за изразимост чрез F и че това свойство се запазва при образуването на нови функции по начина от третата точка. Ако g е n-местен вариант на някоя 0-местна функция f от F, то заключението на доказваното твърдение е вярно, защото в случая а) функцията g(h₁,…,h_n) ще бъде k-местен вариант на f и същото ще важи за функцията g^(k) в случая б). Ако g е проекционна функция в D, то случаят б) е невъзможен, а в случая а) функцията g(h₁,…,h_n) ще съвпада с някоя от функциите h₁, …, h_n и следователно пак ще бъде изразима чрез F. Да предположим сега, че g = f(g₁,…,g_m), където m>0, f е m-местна функция от F и g₁, …, g_m са n-местни функции в D, които са изразими чрез F и притежават свойството от заключението на доказваното твърдение. Значи в случая а) функциите g₁(h₁, …,h_n),…, g_m(h₁,…,h_n) ще бъдат изразими чрез F, а оттук и от равенството

Последно изменение: 5.12.2006 г.