Арифметичний предикат - Велика Енциклопедія Нафти та Газа
Арифметичний предикат
Арифметичний предикат S завжди може бути записаний у префіксній нормальній формі як рекурсивний предикат R з деяким префіксом кванторів [5, стор. у префіксі. [1]
Арифметичним предикатом називається предикат, аргументи якого мають набувати десяткові числові значення. У мові є такі арифметичні предикати. [2]
Якого роду арифметичний предикат може задовольняти умові, що R (х, у) ефективно вирішимо. [3]
У змістовному розумінні арифметичний предикат є довільним (не обов'язково конструктивно визначеним) предикатом на безлічі всіх негативних чисел. Побудована формальна арифметична система дає спосіб конструктивного завдання деяких арифметичних предикатів. [4]
Звідси випливає, що арифметичні предикати та функції, що цілком відповідають метаматематичним, визначеним за допомогою Dn 1 - Dn 13а § 51 (див. лему 191 § 52) і Df 1 - Df 15 § 56 (див. лему III), є елементарними. Справді, у цих метаматематичних, визначеннях узагальненої арифметик рекурсії служать лише запровадження функцій предикатів, що представляють. Зокрема, 5n (Df 13) і, отже, (С) Тп (передує формулюванню теореми IV) та U (Df 15) елементарні. [5]
Зауважимо, що CF ( e x ) не збігається з цілком відповідним арифметичним предикатом для E f ( E, х), тому що він є істинним, коли е або х не є геделівським номером. Але це не відіграє ролі, тому що (е) г входить також у F e), a (d) 2t - у V((d) sa), які відповідають умовам зі Шп9, що С – формула, а х – змінна. [6]
Крім того, в LDL підтримуються предикати рівності та нерівності та кілька арифметичних предикатів. [7]
Для кожного з предикатів та функцій, визначених за допомогою Dfl - Dfl5, цілком відповідний арифметичний предикат або арифметична функція примітивно-рекурсивні. [8]
Тепер ми розглянемо на прикладі арифметики, які можливості описаної мови для представлення властивостей арифметичних предикатів і термів. Звуження ж сигнатури полегшує модальну логіку, але може призвести до зменшення виразних можливостей. [9]
Так само розглядаються визначення інших предикатів зі списку Dnl - Dnl3, DnlSa, крім зазначених вище випадків рекурсії по двом змінним і пунктів, помічених зірочками. Визначається арифметичний предикат , що у результаті перекладу ( подібного переходу від ( 1) до ( 2)), істинний лише геделевских номерів як аргументів, оскільки у кожному пункті початкового визначення кожна змінна річ має задовольняти раніше розглянутому предикату чи слідувати речами, які фіксовані або задовольняють раніше розглянутим чи визначеним предикатам. [10]
Найпростіші обмежено арифметичні предикати. [11]
Арифметичним предикатом називається предикат, аргументи якого мають набувати десяткові числові значення. У мові є такі арифметичні предикати. [12]
Якщо ми перейдемо від речей до їхніх геделівських номерів, то предикат чи функція речей стає предикатом чи функцією геделівських номерів. Ми говоримо, що арифметичний предикат або функція, отримані шляхом розширення визначення цього предикату навсі натуральні числа відповідає початковому предикату або функції. [13]
Ми говоримо, що предикат S є рекурсивним, якщо S рекурсивно дозволимо. Говорять, що S - арифметичний предикат тоді і тільки тоді, коли S отриманий з деякого рекурсивного предикату навішуванням кванторів. [14]
Є спеціальний випадок, коли застосовність закону виключеного третього все ж таки може бути доведена інтуїціоністськи, а саме (у разі індуктивного визначення класу), коли порядок, в якому згідно з індуктивними пунктами з'являються елементи цього класу, збігається з тим порядком, в якому ці елементи породжуються відповідно фундаментального індуктивного визначення. З цієї другої форми ми отримуємо цілком відповідний арифметичний предикат (Ey) [Pf(y) & (y) 0 d] (див. Dn 12), який має вигляд (Ey) R (d y), де предикат R примітивно-рекурсивний. [15]