Бесконечная логика - Infinitary logic

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

Рассмотрение того, является ли некоторая бесконечная логика, называемая Ω-логикой , полной, обещает пролить свет на гипотезу континуума .

Несколько слов об обозначениях и аксиоме выбора

Поскольку представлен язык с бесконечно длинными формулами, невозможно записать такие формулы явно. Чтобы обойти эту проблему, используется ряд удобных обозначений, которые, строго говоря, не являются частью формального языка. используется для обозначения бесконечно длинного выражения. Если неясно, длина последовательности указывается позже. Если это обозначение становится двусмысленным или сбивающим с толку, используются суффиксы, например , для обозначения бесконечной дизъюнкции над набором формул мощности . Такие же обозначения могут применяться, например, к кванторам . Это предназначено для представления бесконечной последовательности квантификаторов: квантификатора для каждого where . ${\ displaystyle \ cdots}$ ${\ displaystyle \ bigvee _ {\ gamma <\ delta} {A _ {\ gamma}}}$ ${\ displaystyle \ delta}$ ${\ Displaystyle \ forall _ {\ gamma <\ delta} {V _ {\ gamma}:}}$ ${\ displaystyle V _ {\ gamma}}$ ${\ displaystyle \ gamma <\ delta}$

Любое использование суффиксов и не является частью формальных бесконечных языков. ${\ displaystyle \ cdots}$

Допускается аксиома выбора (как это часто делается при обсуждении бесконечной логики), поскольку это необходимо для разумных законов распределенности.

Определение инфинитарных логик гильбертова типа

Бесконечная логика первого порядка L _{α , β} , α регулярная , β = 0 или ω ≤ β ≤ α , имеет тот же набор символов, что и конечная логика, и может использовать все правила для формирования формул конечной логики вместе с некоторые дополнительные:

Дан набор формул, тогда и являются формулами. (В каждом случае последовательность имеет длину .) ${\ Displaystyle А = \ {А _ {\ гамма} | \ гамма <\ дельта <\ альфа \}}$ ${\ Displaystyle (А_ {0} \ лор А_ {1} \ лор \ cdots)}$ ${\ Displaystyle (А_ {0} \ земля А_ {1} \ земля \ cdots)}$ ${\ displaystyle \ delta}$
Учитывая набор переменных и формулу, тогда и являются формулами. (В каждом случае последовательность кванторов имеет длину .) ${\ Displaystyle V = \ {V _ {\ gamma} | \ gamma <\ delta <\ beta \}}$ ${\ displaystyle A_ {0}}$ ${\ displaystyle \ forall V_ {0}: \ forall V_ {1} \ cdots (A_ {0})}$ ${\ Displaystyle \ существует V_ {0}: \ существует V_ {1} \ cdots (A_ {0})}$ ${\ displaystyle \ delta}$

Понятия свободных и связанных переменных одинаково применимы к бесконечным формулам. Как и в финитарной логике, формула, все переменные которой связаны, называется предложением .

Теория T в инфинитарной логике представляет собой набор предложений в логике. Доказательство в бесконечной логике теории T - это последовательность утверждений длины, которая подчиняется следующим условиям: каждое утверждение является либо логической аксиомой, либо элементом T , либо выводится из предыдущих утверждений с использованием правила вывода. Как и раньше, все правила вывода в финитарной логике могут использоваться вместе с одним дополнительным: ${\ displaystyle L _ {\ alpha, \ beta}}$ ${\ displaystyle \ gamma}$

Учитывая набор утверждений , которые ранее встречались в доказательстве, можно сделать вывод об утверждении . ${\ Displaystyle А = \ {А _ {\ гамма} | \ гамма <\ дельта <\ альфа \}}$ ${\ displaystyle \ land _ {\ gamma <\ delta} {A _ {\ gamma}}}$

Схемы логических аксиом, характерные для бесконечной логики, представлены ниже. Глобальные переменные схемы: и такие, что . ${\ displaystyle \ delta}$ ${\ displaystyle \ gamma}$ ${\ Displaystyle 0 <\ дельта <\ альфа}$

${\ displaystyle ((\ land _ {\ epsilon <\ delta} {(A _ {\ delta} \ подразумевает A _ {\ epsilon})}) \ подразумевает (A _ {\ delta} \ подразумевает \ land _ {\ epsilon <\ delta} {A _ {\ epsilon}}))}$
Для каждого , ${\ displaystyle \ gamma <\ delta}$ ${\ displaystyle ((\ land _ {\ epsilon <\ delta} {A _ {\ epsilon}}) \ подразумевает A _ {\ gamma})}$
Законы распределительности Чанга (для каждого ):, где или , и ${\ displaystyle \ gamma}$ ${\ displaystyle (\ lor _ {\ mu <\ gamma} {(\ land _ {\ delta <\ gamma} {A _ {\ mu, \ delta}})})}$ ${\ displaystyle \ forall \ mu \ forall \ delta \ exists \ epsilon <\ gamma: A _ {\ mu, \ delta} = A _ {\ epsilon}}$ ${\ displaystyle A _ {\ mu, \ delta} = \ neg A _ {\ epsilon}}$ ${\ displaystyle \ forall g \ in \ gamma ^ {\ gamma} \ exists \ epsilon <\ gamma: \ {A _ {\ epsilon}, \ neg A _ {\ epsilon} \} \ substeq \ {A _ {\ mu, g (\ mu)}: \ mu <\ gamma \}}$
Для , где этого упорядочение лунки ${\ Displaystyle \ гамма <\ альфа}$ ${\ displaystyle ((\ land _ {\ mu <\ gamma} {(\ lor _ {\ delta <\ gamma} {A _ {\ mu, \ delta}})}) \ подразумевает (\ lor _ {\ epsilon < \ gamma ^ {\ gamma}} {(\ land _ {\ mu <\ gamma} {A _ {\ mu, \ gamma _ {\ epsilon} (\ mu)})}}))}$ ${\ displaystyle \ {\ gamma _ {\ epsilon}: \ epsilon <\ gamma ^ {\ gamma} \}}$ ${\ displaystyle \ gamma ^ {\ gamma}}$

Последние две схемы аксиом требуют аксиомы выбора, потому что определенные наборы должны быть хорошо упорядочиваемыми . Последняя схема аксиом, строго говоря, не нужна, поскольку это подразумевают законы дистрибутивности Чанга, однако она включена как естественный способ допустить естественное ослабление логики.

Полнота, компактность и сильная завершенность

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

Логика является полной , если для каждой фразы S действует в каждой модели существует доказательство S . Это сильно полное , если для любой теории T для каждого предложения S действует в T есть доказательство S от T . Бесконечная логика может быть полной, но не строго завершенной. ${\ displaystyle L _ {\ alpha, \ beta}}$

Кардинал является слабо компактным , когда для каждой теории T в содержащем в большинстве многих формул, если каждый S Т мощности меньше имеет модель, то Т имеет модель. Кардинал является сильно компактным, если для каждой теории T in без ограничения размера, если каждая S T мощности меньше, чем имеет модель, то T имеет модель. ${\ displaystyle \ kappa \ neq \ omega}$ ${\ Displaystyle L _ {\ каппа, \ каппа}}$ ${\ displaystyle \ kappa}$ ${\ displaystyle \ substeq}$ ${\ displaystyle \ kappa}$ ${\ displaystyle \ kappa \ neq \ omega}$ ${\ Displaystyle L _ {\ каппа, \ каппа}}$ ${\ displaystyle \ substeq}$ ${\ displaystyle \ kappa}$

Концепции, выражаемые в бесконечной логике

На языке теории множеств следующее утверждение выражает основу :

{\ displaystyle \ forall _ {\ gamma <\ omega} {V _ {\ gamma}:} \ neg \ land _ {\ gamma <\ omega} {V _ {\ gamma +} \ in V _ {\ gamma}}. \ ,}

В отличие от аксиомы основания, это утверждение не допускает нестандартных интерпретаций. Концепция обоснованности может быть выражена только в логике, допускающей бесконечно много кванторов в отдельном утверждении. Как следствие, многие теории, включая арифметику Пеано , которые не могут быть должным образом аксиоматизированы в финитарной логике, могут быть в подходящей бесконечной логике. Другие примеры включают теории неархимедовых полей и групп без кручения . Эти три теории могут быть определены без использования бесконечной количественной оценки; нужны только бесконечные переходы.

Полная инфинитарная логика

Выделяются своей законченностью две бесконечные логики. Это и . Первая - это стандартная финитная логика первого порядка, а вторая - бесконечная логика, допускающая только утверждения счетного размера. ${\ displaystyle L _ {\ omega, \ omega}}$ ${\ displaystyle L _ {\ omega _ {1}, \ omega}}$

${\ displaystyle L _ {\ omega, \ omega}}$ также является сильно полным, компактным и сильно компактным.

${\ displaystyle L _ {\ omega _ {1}, \ omega}}$ не может быть компактным, но является полным (в соответствии с приведенными выше аксиомами). Более того, он удовлетворяет варианту интерполяционного свойства Крейга .

Если является сильно полным (согласно аксиомам, данным выше), то сильно компактно (потому что доказательства в этих логиках не могут использовать или больше из данных аксиом). ${\ Displaystyle L _ {\ alpha, \ alpha}}$ ${\ displaystyle \ alpha}$ ${\ displaystyle \ alpha}$

Languages

In other projects