Введение
Понятие в формальной логике
В формальной логике невыразимость в логике первого порядка – это невозможность адекватно представить высказывание естественного языка формулой логики первого порядка. В частности, высказывание является невыразимым в логике первого порядка, если не существует формулы логики первого порядка, которая была бы истинна в модели тогда и только тогда, когда это высказывание верно в этой модели. Высказывания, невыразимые в логике первого порядка, иногда приводятся как свидетельство неадекватности логики первого порядка для передачи тонкостей значений в естественном языке. Термин был введен Джорджем Булосом в его статье "Быть – значит быть значением переменной (или быть некоторыми значениями некоторых переменных)". Куайн утверждал, что такие предложения требуют символизации второго порядка, которую можно интерпретировать как квантификацию по множествам в той же области, что и квантификаторы первого порядка, без постулирования отдельных "объектов второго порядка" (свойств, множеств и т.д.).
In formal logic, nonfirstorderizability is the inability of a natural language statement to be adequately captured by a formula of first order logic. Specifically, a statement is nonfirstorderizable if there is no formula of first order logic which is true in a model if and only if the statement holds in that model. Nonfirstorderizable statements are sometimes presented as evidence that first order logic is not adequate to capture the nuances of meaning in natural language. The term was coined by George Boolos in his paper "To Be is to Be a Value of a Variable (or to Be Some Values of Some Variables)". Quine argued that such sentences call for second order symbolization, which can be interpreted as plural quantification over the same domain as first order quantifiers use, without postulation of distinct "second order objects" (properties, sets, etc. ).
Окончательность области
Нет формулы А в логике первого порядка с равенством, которая была бы истинна для всех и только моделей с конечными областями определения. Иными словами, не существует формулы первого порядка, способной выразить утверждение "существует лишь конечное число объектов". Это следует из теоремы о компактности следующим образом. Предположим, существует формула А, которая истинна во всех и только моделях с конечными областями определения. Для любого положительного целого числа n мы можем выразить предложение "в области определения содержится не менее n элементов". Для заданного n обозначим формулу, выражающую наличие не менее n элементов, как Bn. Например, формула B3 имеет вид:
которая выражает, что в области определения содержится не менее трех различных элементов. Рассмотрим бесконечное множество формул
Любое конечное подмножество этих формул имеет модель: для заданного подмножества найдите наибольшее n, для которого формула Bn входит в это подмножество. Тогда модель с областью определения, содержащей n элементов, будет удовлетворять A (поскольку область определения конечна) и всем формулам B из подмножества. Применяя теорему о компактности, все бесконечное множество также должно иметь модель. В силу нашего предположения об А, эта модель должна быть конечной. Однако эта модель не может быть конечной, поскольку если модель содержит только m элементов, она не удовлетворяет формуле Bm+1. Это противоречие показывает, что не может существовать формула А с предположенным нами свойством.
Другие примеры
Понятие тождества нельзя определить в языках первого порядка, лишь неделимость. Архимедово свойство может быть использовано для идентификации действительных чисел среди действительно замкнутых полей. Теорема о компактности влечет за собой, что связность графа не может быть выражена в логике первого порядка.