yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->6.3. Арифметические функции и отношения

Математическая логика

6.3. Арифметические функции и отношения

Арифметическими функциями называют функции, у которых область определения и множество значений состоят из натуральных чисел, а арифметическим отношением является всякое отношение, заданное на множестве натуральных чисел. Так, умножение есть арифметическая функция с двумя аргументами, а выражение х+у<z определяет некоторое арифметическое отношение с тремя аргументами.

Термы   0,   0`,   0`` ,   0``` ....   в   дальнейшем   будем   называть   цифрами   и обозначать    жирными    символами    0,    1,    2,    3,...,    и    для    любого    целого неотрицательного n соответствующую цифру будем обозначать через n.

 Определение   6.1.   Арифметическое   отношение    R(x1,...,xn)    называется разимым в теории S, если существует формула A(x1,...,xn) теории S с n свободными переменными такая, что для любых натуральных чисел k1,.,,kn.

(1)   если R(kl,...,kn) истинно, то |-s A(kl,,…,kn),

(2)   если R(k1,...,kn) ложно, то |-s ¬A(k1,…,kn).

Так, например, отношение равенства между натуральными числами разимо в S формулой x1=x2. В самом деле, если k1=k2, то термы k1, и k2, совпадают, и тогда  |-s k1 =k2. Аналогично, если k1k2, то |-s kik2. В свою средь формулой х12 выразимо в S отношение "меньше". Если k1<k2, то существует отличное от нуля число n такое, что k2=k1+n, И тогда |-sk2=k1+n, в силу (S3') и n0, |-sn0. Следовательно, в S можно вывести формулу  т. е. k1<k2. Если же k1 k2, то k1=k2 или k2<k1 причем в этом последнем случае, так же как и для случая k1<k2, доказывается |-sk2<k1,. Наконец, если k1 = k2, то |-sk1=k1. Итак, в обоих случаях |-sk2 k1 и тогда,

|-sk1 k2.

Определение 6.2. Арифметическая функция f(x1,...,xn) называется представимой в S, если существует формула A(xl,...,xn+l) теории S со свободными переменными xl,…,xn+l такая, что для любых натуральных чисел k1,…,kn+1

(1) если f(k1,..,kn)=kn+l, то |-s A(k1,…,kn,kn+1),

(2) |-s1xn+1A(k1,…,kn,kn+1),

Если в этом определении условие (2) заменить условием

(2') |-s1xn+1A(x1,…,xn,xn+1)

то мы получим определение сильно представимой в S функции. Заметим, что, в силу правил Gen и А4 из (2'), следует (2). Следовательно, всякая сильно представимая функция является также представимой функцией.

Примеры. (а) Нуль-функция Z(x)=0 сильно представима э S с помощью формулы x1=x2 &x2=0. В самом деле, если Z(k1)=k2, то k2=0 и- k,=ki&0=0 т. е. выполнен пункт (1) определения сильно представимой функции. Кроме того, очевидно | -lx1(xl=x1&x2=0), т. е, выполнен и пункт (2') этого определения.

(b) Функция N(x)=x + l сильно представима в S формулой х2=x1.Действительно, при любом k1, из N(k1)=k2, т.е. из k2=k1+l, следует, что термы k2 и (k1)' совпадают и потому |-k2=(k1)'. Кроме того, |-1х22=x1 )?.

(c) Проектирующая функция Uin(x1…xn)=xi сильно представима в S с помощью формулы xl=x1&...&xn=xn&xn+1=xi. Если Uin(k1,...,kn)=kn+1, то kn+1=kl и kn+1=k1. Следовательно, |-k,= k1&...&kn = kn&kn+1 = ki, и условие (1) выполнено. Кроме того, |-1хn+11=x1&...&хnnn+1=xi), т.е. выполнено и условие (2') определения сильно представимой в S функции.

(d) Предположим, что функции g(x1,...,xm), h(x1,...,xn), ..., hm(x1,...,xn) (сильно) представимы в S соответственно формулами B(х1,...,хmm+1), A11,..,хn+1), ..., Am(x1,..,xn+1). Зададим новую функцию f равенством f(x1,...,xn)=g(h1(x1,...,xn), ..., hm(x1,..,xn)). Говорят, что функция f получена из g, h1, .... hm с помощью подстановки. Функция f также (сильно) представима в S, например, с помощью формулы

Определение 6. 3. Характеристической функцией данного отношения R(x1,...,xn.) называется функция СR1,...,хn), задаваемая условиями: CR(x1,...,xn)=0, если R(x1,...,xn)=T и CR((x1,...,xn)=l если R(x1,...,xn)=F.

Теорема 6.1. Если отношение R(x1,...,xn) выразимо, в S1 то характеристическая функция СR1,...,хn) этого отношения сильно представила в S, а если функция СR1,...,хn) представима в S, то в S выразимо и отношение R(х1,..,хn).

Доказательство. Не составляет труда поверить, что

1) если отношение R(х1...хn) выразимо в S с помощью формулы A(xl,..,xn) то функция СR1,....хn) сильно представима в S с помощью формулы (A(x1,...,xn)&xn+1=0v(¬A(x1,....,xn,)&xn+1=l),  и

2) если функция CR(x1,..,,xn) представима в S с помощью формулы B(х1,...,хnn+1), то отношение R(х1,...,хn) выразимо в S с помощью формулы B(х1,..,хn,0).

 

39