Читайте также:
|
Пусть К – произвольный класс формул языка Р, удовлетворяющий двум условиям: (1) он непротиворечив и (2) замкнут относительно формальной выводимости.
Класс непротиворечив, если не включает формулу А и формулу не-А.
Класс замкнут, если все, что формально из него выводимо, принадлежит к этому классу.
Р К-определим в языке L, если:
1) Найдется такая формула, которая содержит столько свободных переменных, сколько местен Р.
2) Эта формула должна удовлетворять жестким требованиям:
[(P(n) A(n) K) (P(n) A(n) K)]
В общем виде. Для любого n-местного предиката, он определим в этом языке, если в нем имеется формула, содержащая n свободных переменных. Для всякой n-ки, она выполняет этот предикат, если в этой формуле вместо свободных переменных можно подставить имена этих чисел, то она принадлежит классу К; не выполняет этот предикат, то если в этой формуле вместо свободных переменных можно подставить имена этих чисел, то она принадлежит классу К.
На примере. Для любого объекта универсума рассмотрения (натуральные числа), если этот объект выполняет предикат "быть четны числом" и если его имя ("2") мы подставим в эту формулу, то получим предложение. И это предложение будет принадлежать классу К. А если этот объект не удовлетворяет этому предикату, например – число 3, то формула языка с отрицанием в этом языке будет принадлежать классу К.
m>n
Найдется такая формула в языке, которая имеет такой вид:
z(n+z=m)
Эта формула языка содержит две свободные переменные – n и m. Формула удовлетворяет указанному условию.
Т.е.: P(m,n)
z(q+z=b)
P(n) – знак отрицания здесь означает, что n не обладает свойством P.
A(n) – знак отрицания здесь – это знак самого языка.
Tr – класс истин этого языка. В этом случае предикат будет называться Tr-определимым, или семантически определимым.
[(P(n) A(n) Tr) (P(n) A(n) Tr)]
P(m,n)
z(3+z=5) Tr
После подстановки полученное выражение должно быть истинным.
Формула z(3+z=5)семантически определяет предикат Р.
Т – класс теорем системы. Тогда предикат Р будет Т-определим, или рекурсивно определим (в терминологии Геделя).
[(P(n) A(n) Т) (P(n) A(n) Т)]
Понятие рекурсивной определимости сильнее понятия Tr-определимости. Т.е. все то, что Т-определимо, будет Tr-определимо, но не наоборот.
Формула А рекурсивно определяет предикат Р.
Понятие определимости для функций. Для функций определяющим выражением будет не формула, а термы. Для одноместных функций – термы, содержащие одну свободную переменную, для двухместных функций – две свободные переменные и т.д.
Числовая l-местная функция ψ К-определима в Р, если и только если в Р найдется терм ά, содержащий в точности l попарно различных свободных переменных ά1,…, άl, такой, что он удовлетворяет условию:
На примере. Мы вычисляем значение функции. Например, 100 (если функция арифметическая). Берем терм, обозначающий это число 100 (имя значения функции для n-ки объектов). С другой стороны в наш терм вместо n-ки свободных переменных подставляем имена аргументов. Теперь в нашем терме нет свободных переменных. Тогда и справа и слева стоят термы – один терм обозначает значение функции для данных аргументов, второй терм – результат подстановки. И равенство этих термов (в целом – высказывание) должно принадлежать классу К. Соответственно, Т и Tr.
Дата добавления: 2015-07-16; просмотров: 58 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Анализ парадокса Ришара, причины возникновения, способы устранения. | | | Свойства К-определимых предикатов и функций (теоремы). |