Определимость

Определимость — это логико-методологическое понятие дедуктивных наук, которое указывает на выразимость в рамках некоторой формальной системы одних её понятий через другие. Определимость, как правило, подразумевает те условия, при которых можно считать, что значение того или иного термина полностью или частично определено некоторой совокупностью предложений. Поскольку имена и предметные функторы выразимы посредством соответствующих предикатов, то вопрос об определимости дескриптивных терминов может быть сведён к вопросу об определимости предикатов.

Впервые вопрос об определимости был поднят в связи с рассмотрением отношения между евклидовой и неевклидовыми геометриями в работах А. Падоа. В дальнейшем в чёткой форме понятие определимости было введено А. Тарским. Большое значение для теории определимости сыграли интерполяционная теорема Крейга и теорема Э. Бета. В этих работах была показана тесная связь понятия определимости с понятием выводимости. В результате ряд важных проблем, относящихся к определимости, удалось свести к хорошо разработанным проблемам логического вывода (см. Логический вывод).

Различают синтаксическое (см. Синтактика) и семантическое (см. Семантика) понятия явной и неявной определимости. Подразумевается, что в теории T предикат P(x₁, … x_n) явно синтаксически определим, если в языке, на котором сформулирована теория T, найдётся такая формула A(x₁, … x_n), содержащая в точности переменные x₁, … x_n и не содержащая предиката P, что оказывается доказуемо следующее утверждение: T ⊦ ∀x₁… ∀x_n (P(x₁, … x_n) ≡ A(x₁, … x_n)).

При тех же условиях подразумевается, что предикат P(x₁, … x_n) явно семантически определим в теории T, если семантически можно обосновать утверждение: ∀M (M ⊫ T ⇒ M ⊫ ∀x₁… ∀x_n (P(x₁, … x_n) ≡ A(x₁, … x_n)), то есть каждая возможная реализация теории T, являющаяся её моделью, является моделью и для формулы ∀x₁… ∀x_n (P(x₁, … x_n) ≡ A(x₁, … x_n)). Для первопорядковой логики, в силу адекватности её семантики и синтаксиса, эти два понятия оказываются эквивалентными.

Понятие неявной синтаксической определимости задаётся следующим условием. Пусть Pʹ(x₁, … x_n) — n-местный предикат, не содержащийся в теории T. Пусть далее Tʹ будет теорией, образованной из теории T, заменой в каждом предложении всех вхождений предиката P(x₁, … x_n) на предикат Pʹ(x₁, … x_n). Тогда: предикат P(x₁, … x_n) неявно синтаксически определим в теории T, если T ∪ Tʹ ⊦ ∀x₁… ∀x_n (P(x₁, … x_n) ≡ Рʹ(x₁, … x_n)), то есть в теории, которая является объединением двух теорий T и Tʹ, доказуемо утверждение об эквивалентности двух указанных предикатов. Наконец, предикат P(x₁, … x_n) неявно семантически определим в теории T, если любые две возможные реализации, которые приписывают одно и то же значение всем предикатам, отличным от предиката P(x₁, … x_n), припишут одинаковые значения и самому предикату P(x₁, … x_n).

А. Падоа доказал метатеорему, согласно которой если предикат P(x₁, … x_n) явно семантически определим в теории, то он и неявно семантически определим в ней. Э. Бет доказал обратную теорему. Вообще, для первопорядковой логики показана эквивалентность всех указанных понятий определимости.

В логической литературе кроме указанных рассматриваются и другие виды определимости. Их введение обусловлено типом определений, посредством которых в состав теории вводятся те или иные термины. К ним относятся явные и неявные условные определимости, а также более их общий случай — определимости по случаям. Последний вид определимости играет большую роль при определении операциональных (диспозиционных) терминов. Рассматриваются также различные виды неполной (частичной) определимости, играющие значительную роль при рассмотрении отношений между теоретическими терминами и терминами наблюдения в составе прикладных теорий — дизъюнктивная, условно-параметрическая и параметрическая определимость. Для всех них доказан аналог теоремы Э. Бета. Для случая контекстуального определения терминов рассматривается особый вид контекстуальной определимости.

Часто в логике термин «определимость» употребляется ещё в одном смысле, а именно — в смысле выразимости внелингвистических объектов (отношений, свойств, функций) средствами некоторого языка. Понятие определимости в этом смысле было введено А. Тарским и обобщено А. Мостовским. Именно с этим кругом понятий существенно связаны метатеоремы об ограниченности формализмов.

Пусть K — непротиворечивый и замкнутый относительно выводимости класс формул языка L. Тогда n-местное отношение R(x₁, x₂, … x_n) считается синтаксически K-определимым (выразимым) в языке L, если и только если в этом языке существует формула A, содержащая в точности и попарно различных переменных x₁, x₂, … x_n, удовлетворяющая условию: для любой n-ки объектов k₁, k₂, … k_n имеет место:

1. (R(k₁, k₂, … k_n) ⊃ A(Dk₁, Dk₂, … Dk_n) ∈ K);
2. (¬ R(k₁, k₂, … k_n) ⊃ ¬ A(Dk₁, Dk₂, … Dk_n) ∈ K);

Где Dk_i — это терм, обозначающий объект k_i. Формула A в этом случае называется K-определяющей n-местное отношение R(x₁, x₂, … x_n).

Если в некоторой теории класс общезначимых формул (истинных предложений) Tr непротиворечив и замкнут, то в качестве класса K может выступить класс Tr и мы получаем понятие семантической определимости (выразимости) n-местного отношения R(x₁, x₂, … x_n).

Пусть в некоторой теории класс теорем T непротиворечив и замкнут. Тогда в случае K = T мы получаем понятие рекурсивной определимости (T-определимости). Формула A в этом случае рекурсивно определяет n-местное отношение R(x₁, x₂, … x_n). Понятия формальной дедуктивной системы и эффективно заданной операции оказываются, таким образом, внутренне связанными. Язык выступает как подлинный аналитический метод, как механизм исследования конструирующих мыслительных процедур.

Доказано, что если отношение R T-определимо в достаточно богатой системе (например, в формальной первопорядковой арифметике — P), то оно общерекурсивно, и обратно. Понятие T-определимости в P является абсолютным в том смысле, что им охватываются все разрешимые предикаты и эффективно вычислимые функции. Поэтому для достаточно богатой системы (например, той же системы P) такие синтаксические понятия (понятия метаязыка), как «переменная», «предложение», «аксиома», «формальное доказательство» и другие определимы в языке P, то есть синтаксические понятия теории выразимы в самой теории. Однако семантические понятия теории не могут быть описаны в языке теории (метатеорема Тарского).

Введение понятия K-определимости даёт своеобразный единый метод доказательства ограничительных метатеорем — теорем Тарского, Чёрча-Россера, Гёделя и позволяет вскрыть определённую внутреннюю связь теорем об ограниченностях формализмов.