Введение

Бесконечная логика — это логика, допускающая бесконечно длинные формулы и/или бесконечно длинные доказательства. Эта концепция была введена Цермело в 1930-х годах. Некоторые бесконечные логики могут обладать свойствами, отличными от свойств стандартной логики первого порядка. В частности, бесконечные логики могут не быть компактными или полными. Понятия компактности и полноты, эквивалентные в конечноточной логике, в бесконечных логиках таковыми могут не являться. Поэтому для бесконечных логик определяются понятия сильной компактности и сильной полноты. В данной статье рассматриваются бесконечные логики типа Гильберта, поскольку они получили широкое изучение и представляют собой наиболее прямое расширение конечноточной логики. Тем не менее, это не единственные бесконечные логики, которые были сформулированы или исследованы. Изучение вопроса о полноте определённой бесконечной логики, известной как логика Ω, может пролить свет на гипотезу континуума.

Несколько слов о нотации и аксиоме выбора

Поскольку рассматривается язык с бесконечно длинными формулами, записать такие формулы явно невозможно. Чтобы обойти эту проблему, используются различные обозначения, которые, строго говоря, не входят в формальный язык. Эта нотация используется для указания бесконечно длинного выражения. Если это неясно, длина последовательности указывается позднее. В случаях, когда эта нотация становится неоднозначной или запутанной, применяются суффиксы, такие как , для обозначения бесконечной дизъюнкции по множеству формул мощности . Та же нотация может быть применена и к кванторам, например, , что означает бесконечную последовательность кванторов: квантор для каждого , где . Все случаи использования суффиксов и не являются частью формальных бесконечно-языковых систем. Аксиома выбора предполагается (как это часто делается при обсуждении бесконечной логики), поскольку она необходима для корректных законов дистрибутивности.

Полнота, компактность и сильная полнота

Теория — это любое множество предложений. Истинность утверждений в моделях определяется рекурсивно и согласуется с определением для финитарной логики, где оба определения применимы. Для заданной теории T предложение считается валидным для теории T, если оно истинно во всех моделях T.

Логика в языке является полной, если для каждого предложения S, валидного во всех моделях, существует доказательство S. Она является сильно полной, если для любой теории T для каждого предложения S, валидного в T, существует доказательство S из T. Инфинитарная логика может быть полной, не будучи сильно полной. Кардинал является слабо компактным, если для каждой теории T, содержащей не более формул, если каждое S, являющееся следствием T и имеющее кардинальность меньше , имеет модель, то T имеет модель. Кардинал является сильно компактным, если для каждой теории T, без ограничений на размер, если каждое S, являющееся следствием T и имеющее кардинальность меньше , имеет модель, то T имеет модель.

Полная бесконечная логика

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