Безкрайна логика

2023 Автор: Noah Black | [email protected]. Последно модифициран: 2023-08-25 04:38

Навигация за влизане

• Съдържание за участие
• библиография
• Академични инструменти
• Friends PDF Preview
• Информация за автора и цитирането
• Върнете се в началото

Безкрайна логика

Публикувана за първи път Sun Jan 23, 2000; съществена ревизия Пет февруари 26, 2016

Традиционно изразите във формалните системи се разглеждат като означаващи крайни надписи, които поне - по принцип могат да бъдат действително изписани в примитивна нотация. Фактът обаче, че формулите (от първи ред) могат да бъдат идентифицирани с естествени числа (чрез „номериране на Гьодел“) и следователно с ограничени набори, вече не е необходимо формулите да се разглеждат като надписи и предполага възможността да се създават „езици“някои чиито формули биха били естествено идентифицирани като безкрайни множества. Такъв „език“се нарича инфинитарен език: в тази статия обсъждам тези инфинитарни езици, които могат да бъдат получени направо от езици от първи ред, като позволяват на конюнктури, дизъюнкции и по възможност количествени последователности да бъдат безкрайни дължина. В хода на дискусията ще се види, че макар изразителната сила на такива езици далеч да надхвърля тази на техните финални (първи ред) колеги, много малко от тях притежават „привлекателните” характеристики (напр. Компактност и пълнота) на последната. Съответно инфинитарните езици, които действително притежават тези характеристики, заслужават специално внимание.

В §1 са залегнали основният синтаксис и семантика на инфинитарните езици; тяхната изразителна сила след това се показва чрез примери. §2 е посветен на онези инфинитарни езици, които позволяват само ограничени количествени последователности: тези езици се оказват сравнително добре поведени. §3 е посветен на обсъждане на проблема за компактността на инфинитарните езици и връзката му с чисто зададени теоретични въпроси, отнасящи се до „големи“кардинални числа. В §4 е начертан аргумент, който показва, че повечето „безкрайни количествени“езици имат характер от втори ред и са, ipso facto, силно непълни. §5 предоставя кратък преглед на определен специален клас под езици на инфинитарните езици, за които може да се докаже задоволително обобщение на теоремата за компактност. Този раздел включва подраздел за определянето на допустимите групи. Исторически и библиографски забележки са дадени в §6.

• 1. Определение и основни свойства на инфинитарните езици
• 2. Езици с краен количествен показател
• 3. Свойството за компактност
• 4. Непълнота на езиците за безкрайно количествено определяне

• 5. Подезици на L (ω ₁, ω) и теоремата за баридна компактност

  5.1 Определение на концепцията за допустим набор

• 6. Исторически и библиографски бележки
• библиография
• Академични инструменти
• Други интернет ресурси
• Свързани записи

1. Определение и основни свойства на инфинитарните езици

Като имаме двойка κ, λ от безкрайните кардинали, така че λ ≤ κ, ние дефинираме клас инфинитарни езици, във всеки от които можем да образуваме съединения и дизъюнкции от набори от формули на кардиналност <κ, и количествени оценки върху последователности от променливи с дължина < λ.

Нека L - (окончателният) основен език - е произволен, но фиксиран език от първи ред с произволен брой екстралогични символи. Инфинитарният език L (κ, λ) има следните основни символи:

• Всички символи на L
• Множество Var от отделни променливи, където кардиналността на Var (написано: | Var |) е κ
• Логичен оператор ∧ (инфинитарна връзка)

Класът на преформули на L (κ, λ) се определя рекурсивно, както следва:

• Всяка формула на L е преформула;
• ако φ и ψ са преформули, тогава са ∧ψ∧ψ и φ¬;
• ако Φ е набор от преформули, така че | Φ | <κ, тогава ∧Φ е преформа;
• ако φ е преформула и X ⊆ Var е такава, че | X | <λ, тогава ∃ X φ е преформула;
• всички формули са дефинирани от горните клаузи.

Ако Φ е набор от преформули, индексирани с множество I, да речем Φ = {φ _i: i ∈ I}, тогава ние се съгласяваме да напишем ∧Φ за:

∧ _{i ∈ I}  φ

или, ако аз съм набор от естествени числа, пишем ∧Φ за:

φ ₀ ∧ φ ₁ ∧…

Ако X е набор от отделни променливи, индексирани с порядъчен α, да речем X = {x _ξ: ξ <α}, ние се съгласяваме да напишем (∃ x _ξ) _{ξ <α} φ за ∃ X φ.

Логическите оператори ∨, →, ↔ са дефинирани по обичайния начин. Ние също така въвеждаме операторите ∨ (инфинитарна дисункция) и ∀ (универсално количествено определяне) чрез

∨Φ = _df ¬∧ {¬φ: φ ∈ Φ}

∀Xφ = _df ¬∃X¬φ,

и използват подобни конвенции като за ∧, ∃.

По този начин L (κ, λ) е инфинитарен език, получен от L, като позволява съединения и дизъюнкции на дължина <κ и количествено определяне ^[1] на дължина <λ. Езиците L (κ, ω) се наричат езици с краен квантор, останалите езици за безкрайно количествено определяне. Забележете, че L (ω, ω) е само L.

Забележете следната аномалия, която може да възникне на инфинитарен език, но не и на окончателен. В езика L (ω ₁, ω), който позволява безкрайно безкрайни връзки, но само ограничени количествени показатели, има преформули с толкова много свободни променливи, че те не могат да бъдат „затворени“в изречения от L (ω ₁, ω) чрез префиксиране на количествени характеристики. Такъв е случаят например с L (ω ₁, ω) -преформа

x ₀ <x ₁ ∧ x ₁ <x ₂ ∧… ∧ x _n <x _{n +1} …,

където L съдържа символа на двоичното отношение <. Поради тази причина правим следното

Определение. Формула на L (κ, λ) е преформула, която съдържа <λ свободни променливи. Множеството от всички формули на L (κ, λ) ще бъде обозначено с Form (L (κ, λ)) или просто Form (κ, λ) и множеството от всички изречения от Sent (L (κ, λ)) или просто изпратено (κ, λ).

В тази връзка, имайте предвид, че по принцип нищо няма да се получи, като се имат предвид „езиците“L (κ, λ) с λ> κ. Например, в „езика“L (ω, ω ₁) формулите ще имат само крайно много свободни променливи, докато има множество „безполезни“квантори, които могат да свържат безкрайно много свободни променливи. ^[2]

След като дефинирахме синтаксиса на L (κ, λ), следваща скица на неговата семантика. Тъй като екстралогичните символи на L (κ, λ) са точно тези на L и именно тези символи определят формата на структурите, в които трябва да се интерпретира даден език от първи ред, естествено е да се определи L (κ, λ) -структура е просто L-структура. Представата за формула на L (κ, λ), изпълнена в L-структура A (чрез поредица от елементи от домейна на A), е дефинирана по същия индуктивен начин, както за формулите на L, с изключение на това, че трябва да добавим две допълнителни клаузи, съответстващи на клаузите за ∧Φ и ∃Xφ в дефиницията на preformula. В тези два случая ние естествено определяме:

∧Φ е удовлетворено в A (чрез дадена последователност) ⇔ за всички φ ∈ Φ, φ е удовлетворено в A (от последователността);

∃ X φ е изпълнено в А ⇔ има последователност от елементи от областта на А в биективен съответствие с X, който отговаря МФ в А.

Тези неформални дефиниции трябва да бъдат затегнати в строго развитие, но значението им трябва да бъде ясно за читателя. Вече стават достъпни обичайните понятия за истинност, валидност, удовлетворимост и модел за формули и изречения на L (κ, λ). По-специално, ако A е L-структура и σ ∈ Sent (κ, λ), ще напишем A ⊨ σ за A е модел на σ, а ⊨ σ за σ е валиден, тоест за всички A, A ⊨ σ. Ако Δ ⊆ Sent (κ, λ), ще напишем Δ ⊨ σ за σ е логично следствие от Δ, тоест всеки модел на Δ е модел на σ.

Сега даваме няколко примера, предназначени да покажат изразителната сила на инфинитарните езици L (κ, λ) с κ ≥ ω ₁. Във всеки случай е добре известно, че въпросното понятие не може да бъде изразено на нито един език от първи ред.

Характеристика на стандартния модел на аритметика в L (ω ₁, ω). Тук стандартният модел на аритметика е структурата N = ⟨N, +, ·, s, 0⟩, където N е множеството от естествени числа, +, · и 0 имат своите обичайни значения, а s е операция-приемник. Нека L е първият ред език подходящи за N. Тогава класът на L-структури, изоморфен на N, съвпада с класа на моделите на съединението на следните L (ω ₁, ω) изречения (където 0 е име на 0):

∧ _{m ∈ω} ∧ _{n ∈ω} s ^m 0 + s ⁿ 0 = s ^{m + n} 0

∧ _{m ∈ω} ∧ _{n ∈ω} s ^m 0 · s ⁿ 0 = s ^{m · n} 0

∧ _{m ∈ω} ∧ _{n ∈ω− {m}} s ^m 0 ≠ s ⁿ 0

∀ x ∨ _{m ∈ω} x = s ^m 0

Термините s ⁿ x се определят рекурсивно от

s 0 x	=	х
s n +1 x	=	s (s n x)

Характеристика на класа на всички крайни множества в L (ω ₁, ω). Тук основният език няма екстралогични символи. Класът на всички крайни множества след това съвпада с класа на моделите на L (ω ₁, ω) -разсъдък

∨ _{n ∈ω} ∃ v ₀ … ∃ v _n ∀ x (x = v ₀ ∨… ∨ x = v _n).

Дефиниция на истината в L (ω ₁, ω) за изброим основен език L. Нека L е счетлив език от първи ред (например езикът на аритметичната или теорията на множествата), който съдържа име n за всяко естествено число n, и нека σ ₀, σ ₁,… е изброяване на изреченията му. Тогава L (ω ₁, ω) -формула

Tr (x) = _df ∨ _{n ∈ω} (x = n ∧ σ _n)

е предикат за истина за L, тъй като изречението

Tr (n) ↔ σ _n

е валидно за всяко n.

Характеристика на подреждането на кладенеца в L (ω ₁, ω ₁). Основният език L тук включва двоичен предикат символ ≤. Нека σ ₁ е обичайното L-изречение, характеризиращо линейни подреждания. Тогава класът на L-структури, в които интерпретацията на ≤ е добре подредена, съвпада с класа на моделите на L (ω ₁, ω ₁) изречение σ = σ ₁ ∧ σ ₂, където

σ ₂ = _df (∀ v _n) _{n ∈ω} ∃ x [∨ _{n ∈ω} (x = v _n) ∧ ∧ _{n ∈ω} (x ≤ v _n)].

Забележете, че изречението σ ₂ съдържа безкраен количествен показател: той изразява по същество твърдение от втори ред, че всяко подчитано подмножество има най-малко член. В действителност може да се покаже, че наличието на този безкраен количествен показател е от съществено значение: класът на добре подредените структури не може да бъде характеризиран в нито един език с ограничен количествен номер. Този пример показва, че езиците за безкрайно количествено измерване като L (ω ₁, ω ₁) се държат по-скоро като езици от втори ред; ще видим, че те споделят дефектите на късмет (непълнота), както и някои от техните предимства (силна изразителна сила).

Много разширения на езици от първи ред могат да бъдат преведени на инфинитарни езици. Например, помислете за обобщения език за количествено измерване L (Q ₀), получен от L, като добавите нов символ за квантификатор Q ₀ и интерпретирате Q ₀ x φ (x), тъй като има безкрайно много х такива, че φ (x). Лесно се вижда, че изречението Q ₀ x φ (x) има същите модели като L (ω ₁, ω) -разрешение

¬∨ _{n ∈ω} ∃ v ₀ … ∃ v _n ∀ x [φ (x) → (x = v ₀ ∨… ∨ x = v _n)].

По този начин L (Q ₀) е в естествен смисъл преводим в L (ω ₁, ω). Друг език, който може да се превежда на L (ω ₁, ω) в този смисъл, е слабият език от втори ред, получен чрез добавяне на счетлив набор от монадични предикатични променливи към L, които след това се интерпретират като обхват на всички крайни групи от индивиди.

Могат да бъдат въведени и езици с произволно дълги връзки, дизюнкции и (възможно) количествено определяне. За фиксиран безкраен кардинал λ езикът L (∞, λ) се дефинира, като се посочва неговият клас формули, Form (∞, λ), който ще бъде обединението за всички κ ≥ λ на множествата Form (κ, λ). По този начин L (∞, λ) позволява произволно дълги връзки и дизюнкции, в смисъл, че ако Φ е произволен подмножество на Form (∞, λ), тогава и ∧Φ и ∨Φ са членове на Form (∞, λ). Но L (∞, λ) допуска само количествено определяне на дължина <λ: всичките му формули имат <λ свободни променливи. Езикът L (∞, ∞) се дефинира от своя страна чрез определяне на неговия клас формули, Form (∞, ∞), който да бъде обединението за всички безкрайни кардинали λ, на класовете Форма (∞, λ). Така L (∞, ∞) позволява произволно дълги количествени оценки в допълнение към произволно дълги съединения и дизюнкции. Обърнете внимание, че Form (∞, λ) и Form (∞, ∞) са правилни класове по смисъла на теорията на множествата на Gödel-Bernays. Удовлетворението на формулите на L (∞, λ) и L (∞, ∞) в една структура може да бъде определено чрез очевидно разширение на съответното понятие за L (κ, λ).

2. Езици с краен количествен показател

Забелязахме, че езиците за безкрайно количествено измерване като L (ω ₁, ω ₁) наподобяват езици от втори ред, доколкото позволяват количествено определяне на безкрайните групи от индивиди. Фактът, че това не е разрешено в езиците с ограничен количествен показател, подсказва, че те може да са в известна степен по-близки до техните колеги от първи ред, отколкото може да е очевидно на пръв поглед. Ще видим, че това наистина е така, особено в случая на L (ω ₁, ω).

Езикът L (ω ₁, ω) заема специално място сред инфинитарните езици, тъй като - подобно на езиците от първи ред - той дава ефективен дедуктивен апарат. Всъщност нека добавим към обичайните аксиоми и правила за извод от първи ред новата схема на аксиомите

∧Φ → φ

за всяко счетно множество ⊆ ⊆ форма (ω ₁, ω) и всяко φ ∈ Φ, заедно с новото правило на извода

φ 0, φ 1,…, φ n,…

∧ n ∈ω φ n

и позволяват на удръжките да бъдат счетлива дължина. Записвайки ⊢ * за изводимост в този смисъл, тогава имаме

L (ω ₁, ω) - Теорема за пълнота. За всяко σ ∈ Sent (ω ₁, ω), ⊨ σ ⇔ ⊢ * σ

Като непосредствено следствие извеждаме, че този дедуктивен апарат е адекватен за приспадане от преброени масиви помещения в L (ω ₁, ω). Тоест, с очевидното разширение на нотацията имаме за всяко счетно множество Δ ⊆ изпратено (ω ₁, ω)

(2.1) Δ ⊨ σ ⇔ Δ⊢ * σ

Тази теорема за пълнота може да бъде доказана чрез промяна на обичайното доказателство за пълнота на Хенкин за логика от първи ред или чрез използване на булеви алгебрични методи. Подобни аргументи, приложени за подходящи допълнителни увеличения на аксиомите и правилата на извода, дават аналогични теореми за пълнота за много други езици с ограничен количествен показател.

Ако са допуснати само изваждания с преброена дължина, тогава не може да се настрои дедуктивен апарат за L (ω ₁, ω), който е адекватен за удръжки от произволни масиви помещения, тоест за които (2.1) би важил за всеки набор Δ ⊆ Изпратен (ω ₁, ω), независимо от сърдечността. Това следва от простото наблюдение, че има език от първи ред L и неизчисляем набор Γ от L (ω ₁, ω) -значения, така че Γ няма модел, но всеки подчиним подмножество от Γ прави. За да видите това, нека L е езикът на аритметиката, допълнена от ω ₁ нови постоянни символи { c _ξ: ξ <ω ₁ }, и Γ е множеството от L (ω ₁, ω) -сенценции {σ} ∪ { c_ξ ≠ c _η: ξ ≠ η}, където σ е L (ω ₁, ω) -разрешение, характеризиращо стандартния модел на аритметика. Този пример показва също, че теоремата за компактност се проваля за L (ω ₁, ω) и така също за всеки L (κ, λ) с κ ≥ ω ₁.

Друг резултат, който важи в случая от първи ред, но не успява за L (κ, ω) с κ ≥ ω ₁ (а също и за L (ω ₁, ω ₁), въпреки че това е по-трудно да се докаже), е нормалната форма на пренекс теорема. Изречение е предварителен, ако всичките му количествени показатели се появят отпред; даваме пример за L (ω ₁, ω) -разсъд, който не е еквивалентен на съвкупност от предложки изречения. Нека L е езикът от първи ред без екстралогични символи и σ е L (ω ₁, ω) -разсъждение, което характеризира класа от крайни множества. Да предположим, че σ е еквивалентен на конюнкция

∧ _{i ∈ I} σ _i

на пренекс L (ω ₁, ω) -разрешения σ _i. Тогава всяко σ _i е от формата

Q ₁ x ₁ … Q _n x _n φ _i (x ₁,…, x _n),

където всеки Q _k е ∀ или ∃ и φ _i е (вероятно инфинитарна) конюнкция или дизъюнкция на формулите от формата x _k = x _l или x _k ≠ x _l. Тъй като всяко σ _i е изречение, във всяко φ _i има само крайно много променливи и е лесно да се види, че след това всяко φ _i е еквивалентно на формула от първи ред. Съответно всяко σ _i може да се приеме за изречение от първи ред. Тъй като σ се приема, че е еквивалентен на свързването на σ _i, следва, че σ и множеството Δ = {σ _i: i ∈ I} имат същите модели. Но очевидно σ, а оттам и Δ, имат модели на всички крайни кардиналности; теоремата за компактност за множества изречения от първи ред сега предполага, че Δ, а оттам и σ, има безкраен модел, противоречащ на дефиницията на σ.

Обръщайки се към теоремата на Левенхайм-Сколем, установяваме, че низходящата версия има адекватни обобщения на L (ω ₁, ω) (и всъщност на всички инфинитарни езици). Всъщност човек може да покаже по почти същия начин, както за множествата изречения от първи ред, че ако Δ ⊆ изпратено (ω ₁, ω) има безкраен модел на кардиналност ≥ | Δ |, то има модел на кардиналност, по-голям от ℵ ₀, | Δ |. По-специално, всяко L (ω ₁, ω) -разрешение с безкраен модел има счетлив модел.

От друга страна, възходящата теорема на Левенхайм-Сколем в обичайната си форма се проваля за всички инфинитарни езици. Например, L (ω ₁, ω) -разрешението, характеризиращо стандартния модел на аритметика, има модел на кардиналност ℵ _0, но няма модели на никаква друга кардиналност. Тук обаче всичко не се губи, както ще видим.

Определяме числото Hanf h (L) на език L да е най-малкото кардинално κ такова, че ако L -разсъдът има модел на кардиналност κ, той има модели на произволно голяма кардиналност. Съществуването на h (L) лесно се установява. За всяка L- присъда σ, която не притежава модели на произволно голяма кардиналност, нека κ (σ) е най-малкото кардинално κ, така че σ няма модел на кардиналност κ. Ако λ е върхът на всички κ (σ), тогава, ако изречението на L има модел на кардиналност λ, то има модели на произволно голяма кардиналност.

Определете кардиналите μ (α) рекурсивно чрез

μ (0)	=	ℵ 0
μ (α + 1)	=	2 μ (α)
μ (λ)	=	∑ α <λ μ (α), за граница λ.

Тогава може да се покаже това

h (L (ω ₁, ω)) = μ (ω ₁),

подобни резултати важат за други езици с ограничен количествен показател. Стойностите на Hanf числата на безкрайно количествените езици като L (ω ₁, ω ₁) са чувствителни към присъствието или по друг начин на големи кардинали, но във всеки случай трябва значително да надвишават стойностите на L (ω ₁, ω).

Резултат за L, който се обобщава на L (ω ₁, ω), но на никой друг инфинитарен език не е този

Теорема за интерполация на Крейг: Ако σ, τ ∈ Sent (ω ₁, ω) са такива, че ⊨ σ → τ, тогава има θ ∈ Sent (ω ₁, ω), така че ⊨ σ → θ и ⊨ θ → τ, и всяка екстралогичен символ, възникващ в θ, се среща както в σ, така и τ.

Доказателството е сравнително ясно разширение на делото от първи ред.

Накрая споменаваме още един резултат, който се обобщава добре на L (ω ₁, ω), но на никой друг инфинитарен език. Добре известно е, че ако A е някаква крайна L-структура със само крайно много отношения, има L-изречение σ, характеризиращо A до изоморфизъм. За L (ω ₁, ω) имаме следното обобщение, известно като

Теорема за изоморфизма на Скот. Ако A е изброимо L-структура само с countably много отношения, а след това има една L (ω ₁, ω) -sentence чийто клас броими модели съвпада с класа на L-структури изоморфни с A.

Ограничаването на преброените структури е от съществено значение, тъй като счетливостта по принцип не може да бъде изразена с L (ω ₁, ω) -разположение.

Езикът L (∞, ω) може също да се счита за език с ограничен количествен номер. Понятието за еквивалентност на структурите по отношение на този език е от особено значение: наричаме две (подобни) структури A и B (∞, ω) - еквивалентни, написани A ≡ _∞ω B, ако едни и същи изречения на L (∞, ω) задържане в двете а и Б. Тази връзка на първо място може да се характеризира по отношение на понятието частичен изоморфизъм. Частичен изоморфизъм между A и B е непразно семейство P от карти, така че:

• За всяко p ∈ P, dom (p) е подструктура на A, ran (p) е подструктура на B, и p е изоморфизъм на своя домейн върху неговия обхват; и
• Ако p ∈ P, a ∈ A, b ∈ B, тогава съществуват r, s ∈ P и двете, простиращи се p, така че a ∈ dom (r), b ∈ ran (s) („назад и напред“).

Ако съществува частична изоморфизъм между А и Б, ние казваме, че A и B са частично изоморфно и запис А ≅ _р B. Тогава имаме

Теорема за частичния изоморфизъм на Карп.

За всички подобни структури А, В, А ≡ _∞ω B ⇔ А ≅ _р B.

Съществува и версия на теоремата за изоморфизма на Скот за L (∞, ω), а именно,

(2.2) Като се има предвид всяка структура A, има L (∞, ω) -разрешение σ такова, че за всички структури B, A ≅ _p B ⇔ B ⊨ σ.

Частичният изоморфизъм и (∞, ω) -еквивалентност са свързани с понятието булев изоморфизъм. За да определим това, трябва да въведем идеята за булев модел на теорията на множествата. Като се има предвид пълна булева алгебра B, Вселената V ^(B) от множества, оценявани по B, позната още като B-разширение на Вселената V на множествата, се получава чрез първоначално дефиниране, рекурсивно на α,

V _α ^(B) = {x: x е функция ∧ обхват (x) ⊆ B ∧ ∃ξ <α [домейн (x) ⊆ V _ξ ^(B)]}

и след това настройка

V ^(B) = {x: ∃α (x ∈ V _α ^(B))}.

Членовете на V ^(B) се наричат множества с B стойност. Вече лесно се вижда, че B-оценяваният набор е точно B-стойностна функция с домейн набор от B-оценени набори. Сега нека L е езикът от първи ред на теорията на множествата и L ^(B) е езикът, получен чрез добавяне към L име за всеки елемент от V ^(B) (ще използваме същия символ за елемента и неговото име), Вече може да се изгради картографиране [·] ^(B) на (изреченията на) езика L ^(B) в B: за всяко изречение σ на L ^(B), елементът [σ] ^(B) на B е „ Булева стойност на истината”от σ в V ^(B), Това картографиране [·] ^(B) е дефинирано така, че да изпраща всички теореми на теорията за множествата на Цермело-Френкел до горния елемент 1 на B, т.е. до "истината"; съответно V ^(B) може да се разглежда като булев модел на теорията на множествата. Като цяло, ако [σ] ^(B) = 1, казваме, че σ е валиден във V ^(B), и пишем V ^(B) ⊨ σ.

Сега всеки x ∈ V има каноничен представител x в V ^(B), удовлетворяващ

x = y iff V ^(B) ⊨ x = y

x ∈ y iff V ^(B) ⊨ x ∈ y

Ние казваме, че две подобни структури A, B са булева изоморфна, написана A ≅ _b B, ако за някаква пълна булева алгебра B имаме V ^(B) ⊨ A ≅ B, тоест ако има булево разширение на Вселена от множества, в които каноничните представители на A и B са изоморфни с булева стойност 1. След това може да се покаже, че:

(2.3) А ≡ _∞ω B ⇔ А ≅ _б B.

Този резултат може да се засили чрез категорично-теоретична формулировка. За това ни е необходима концепцията за (n) (елементарен) топос. За да въведем това понятие, започваме с фамилната категория Set of set и mappings. Set има следните ключови свойства:

1. Има "терминален" обект 1, такъв, че за всеки обект X има уникална карта X → 1 (за 1 можем да вземем всеки един елемент, по-специално {0}).
2. Всеки чифт обекти X, Y има декартово изделие X × Y.
3. за всеки чифт обекти човек може да формира „експоненциален” обект Y ^X на всички карти от X → Y.
4. Има обект „стойност на истината“Ω, така че за всеки обект X има естествена кореспонденция между подобекти (подмножества) на X и карти X → Ω. (За Ω можем да вземем множеството 2 = {0,1}; картите X → Ω са характерни функции на X.)

И четирите от тези условия могат да бъдат формулирани на теоретичен език за категория - категория, която ги удовлетворява, се нарича топос. Категорията Set е топос; също са (i) категорията набор ^(B) на булевите стойности и набори във всяко булево разширение V ^(B) на вселената на множествата; (ii) категорията на снопове на набори в топологично пространство; (iii) категорията на всички диаграми на карти от групи

X ₀ → X ₁ → X ₂ →…

Обектите на всяка от тези категории могат да се разглеждат като множества, които се различават по някакъв начин: в случай (i) над булева алгебра; в случай (ii) над топологично пространство; в случай (iii) над (дискретно) време. Топосът може да бъде замислен като вселена от "променливи" множества. Познатата категория Set е специалният ограничаващ случай на топос, при който „вариацията“на обектите е сведена до нула.

Точно както в теорията на множествата, „логическите оператори“могат да бъдат дефинирани върху обекта стойност на истината във всеки топос. Това са карти ¬: Ω → Ω; ∧, ∨, ⇒: Ω × Ω → Ω, съответстващи на логическите операции на отрицание, съединение, дизъюнкция и импликация. С тези операции Ω се превръща в алгебра на Хейтинг, като по този начин въплъщава като цяло законите не на класическата, а на интуиционистичната логика. В този смисъл интуиционистичната логика е „интернализирана” в топос: интуиционистичната логика е логиката на променливите множества. (Разбира се, класическата логика е интернализирана в определени топоси, например Set и Set ^(B) за всяка пълна булева алгебра B.)

Всеки топос може да бъде замислен като възможна „вселена на дискурса“, в която могат да се интерпретират математически твърдения и да се извършват математически конструкции. Математическите твърдения се правят интерпретируеми в топос Е чрез изразяване във вътрешния език на Е - типово-теоретична версия на обичайния език на теорията на множествата. По начин, аналогичен на булева валидност, може да се въведе подходящо понятие за валидност в Е на изречение σ от вътрешния му език. Отново пишем E ⊨ σ за „σ е валидно в E“.

За топос Е се казва, че е пълен, ако за всеки набор I, I-кратната сила ^[3] ∐ _I 1 на крайния му обект съществува в Е. ∐ _I 1 може да се смята за каноничен представител в Е на множеството Аз; съответно, пишем го просто както аз. (Във V ^(B) това съвпада с I, както е дефинирано по-горе.) Всички споменати по-горе топоси са пълни.

А сега нека E е пълен топос. Ако A = (A, R, …) е структура, напишете A за (A, R, …). За две структури A и B се казва, че са топос изоморфни, написани A ≅ _t B, ако за някои топоси E, определени по категорията на множествата, имаме E ⊨ A ≅ B. С други думи, две структури са топос изоморфни, ако техните канонични представители са изоморфни във вътрешния език на някои топоси. Тогава може да се покаже това

(2.4) А ≡ _∞ω B ⇔ А ≅ _т B.

Съответно (∞, ω) -еквивалентността може да се разглежда като изоморфизъм в изключително общия контекст на вселени на „променливи“множества. В това отношение (∞, ω) -еквивалентността е „инвариантно“понятие за изоморфизъм.

3. Свойството за компактност

Както видяхме, теоремата за компактност в обичайната си форма се проваля за всички инфинитарни езици. Независимо от това, е от интерес да се определи дали инфинитарните езици отговарят на някаква подходящо модифицирана версия на теоремата. Оказва се, че този т. Нар. Проблем с компактността има естествена връзка с чисто зададени теоретични въпроси, включващи „големи“кардинални числа.

Конструираме следното определение. Нека κ е безкраен кардинал. Език L се казва κ-компактен (респ. Слабо κ -компакт), ако винаги, когато Δ е набор от L- изрази (съответно набор от L- изрази на кардиналност ≤ κ) и всеки подмножество от Δ на кардиналност < κ има модел, така е и Δ. Забележете, че обичайната теорема за компактност за L е именно твърдението, че L е ω-компактен. Една от причините за значимостта на свойството κ-компактност е следната. Обадете се L κ- пълно (съответно слабо κ- пълно), ако има дедуктивна система P за L с изваждания на дължина <κ така, че ако Δ е P- съвместим ^[4] набор от L- изрази (съответно такива, че | Δ | ≤ κ), тогава Δ има модел. Обърнете внимание, че такъв Р ще бъде адекватен за приспадане от произволни масиви помещения (на кардиналност ≤ κ) по смисъла на §2. Лесно се вижда, че ако L е κ-пълен или слабо κ-пълен, тогава L е κ-компактен или слабо κ-компактен. По този начин, ако можем да покажем, че даден език не е (слабо) κ-компактен, тогава не може да има дедуктивна система за него с изваждания на дължина <κ, достатъчна за удръжки от произволни набори от помещения (на кардиналност ≤ κ).

Всъщност се оказва, че повечето езици L (κ, λ) не успяват да са дори слабо κ-компактни, а за тези, които са, κ трябва да са изключително голям кардинал. Ще се нуждаем от някои определения.

За безкраен кардинал κ се казва, че е слабо недостъпен, ако

(a) λ <κ → λ ⁺ <κ, (където λ ⁺ означава кардиналния наследник на λ), и

б) | I | <κ и λ _i <κ (за всички i ∈ I) ⇒ ∑ _{i ∈ I} λ _i <κ.

Ако в допълнение

в) λ <κ ⇒ 2 ^λ <κ,

тогава се казва, че κ е (силно) недостъпен. Тъй като ℵ ₀ е недостъпен, нормална практика е да се ограничи вниманието към онези недостъпни или слабодостъпни кардинали, които надвишават ℵ ₀. Съответно, непристъпни или слабодостъпни кардинали винаги ще се считат за неизчислими. Ясно е, че такива кардинали - ако съществуват - трябва да са изключително големи; и наистина теоремата за непълнота на Гьодел предполага, че съществуването на дори слабо недостъпни кардинали не може да бъде доказано от обичайните аксиоми на теорията на множествата.

Нека наречем кардинал κ компактен (съответно слабо компактен), ако езикът L (κ, κ) е κ-компактен (респ. Слабо κ-компактен). Тогава имаме следните резултати:

(3.1) ℵ ₀ е компактен. Това, разбира се, е само кратък начин за изразяване на теоремата за компактност за езиците от първи ред.

(3.2) κ е слабо компактен ⇒ L (κ, ω) е слабо κ- компактен ⇒ κ е слабо недостъпен. Съответно е последователно (с обичайните аксиоми на теорията на множествата) да се приеме, че никой език L (κ, ω) с κ ≥ ω _{1 не} е слабо κ-компактен, или, a fortiori, слабо κ-пълен.

(3.3) Да предположим, че κ е недостъпен. Тогава κ е слабо компактен ⇔ L (κ, ω) е слабо κ-компактен. Също така, κ е слабо компактен ⇒ има набор от κ недостъпни преди κ. Следователно слабо компактен недостъпен кардинал е изключително голям; по-специално тя не може да бъде първата, втората, …, n ^-та, … недостъпна.

(3.4) κ е компактен ⇒ κ е недостъпен. (Но в резултат непосредствено отгоре обратното се проваля.)

Нека Констр да отстоява аксиомата на Гьодел за конструируемост; припомнете, че Constr е в съответствие с обичайните аксиоми на теорията на множествата.

(3.5) Ако Constr държи, няма компактни кардинали.

(3.6) Да приемем Constr и нека κ е недостъпен. Тогава κ е слабо компактен ⇔ L (ω ₁, ω) е слабо κ- компактен за всички L.

(3.7) Ако Constr се държи, тогава няма кардинали κ, за които L (ω ₁, ω) е компактен. Съответно е в съответствие с обичайните аксиоми на теорията на множествата да се предположи, че няма кардинал κ такъв, че всички езици L (ω ₁, ω) да са κ-пълни. Този резултат трябва да се контрастира с факта, че всички езици от първи ред са ω-пълни.

Вносът на тези резултати е, че теоремата за компактност се проваля много лошо за повечето езици L (κ, λ) с κ ≥ ω ₁.

Тук са наред някои исторически забележки. През 30-те години математиците изследват различни версии на така наречения проблем с мерките за множествата - проблем, възникнал във връзка с теорията за мярката на Лебес върху континуума. По-специално беше формулирано следното много просто понятие за мярка. Ако X е съвкупност, (с добавена стойност две двузначни нетривиални) мярка за X е карта μ на множеството на мощност P X към множеството {0, 1}, отговарящо на:

(a) μ (X) = 1, (b) μ ({x}) = μ (∅) = 0 за всички x ∈ X, и

в) ако A е някакво счетоводно семейство на взаимно разединяващи се подмножества от X, тогава μ (∪ A) = ∑ {μ (Y): Y ∈ A }.

Очевидно дали даден набор поддържа такава мярка зависи само от неговата кардиналност, така че е естествено да се определи един кардинал κ, който да бъде измерим, ако всички набори от кардиналност κ поддържат мярка от този вид. Бързо се разбра, че измерим кардинал трябва да бъде недостъпен, но лъжливостта на обратното е установена чак през 60-те години на миналия век, когато Тарски показа, че измеримите кардинали са слабо компактни и неговият ученик Ханф показа, че първият, вторият и т.н. непристъпни не са слабо компактен (вж. (3.3)). Въпреки че изводът, че измеримите кардинали трябва да бъдат чудовищно понастоящем, обикновено се доказва, без да се извършва обиколка чрез слаба компактност и инфинитарни езици, остава фактът, че тези идеи бяха използвани за установяване на резултата на първо място.

4. Непълнота на езиците за безкрайно количествено определяне

Вероятно най-важният резултат относно езиците от първи ред е теоремата за пълнота на Гьодел, която разбира се казва, че множеството от всички валидни формули на всеки език от първи ред L може да бъде генерирано от обикновен набор от аксиоми с помощта на няколко прави правила на извод. Основно следствие от тази теорема е, че ако формулите на L са кодирани като естествени числа по някакъв конструктивен начин, тогава наборът от (кодове на) валидни изречения е рекурсивно изброяващ. По този начин, пълнотата на език от първи ред предполага, че множеството от валидните му изречения може да се определи по особено прост начин. Следователно би било разумно, като се има предвид произволен език L, да се обърне това значение и да се предложи, ако съвкупността от валиден L-разсъжденията не могат да се определят по някакъв прост начин, тогава не може да се установи смислен резултат за пълнота за L или, както ще кажем, че L е непълен. В този раздел ще използваме това предложение за очертаване на доказателство, че „повечето“безкрайни количествени езици са непълни в този смисъл.

Нека първо представим официалното понятие за дефинируемост, както следва. Ако L е език, А на L -структура, и X подгрупа на домен А на А, да кажем, че X е дефинирани в А от формула φ (X, Y ₁, …, у _п) на L ако има е последователност ₁, …, а _п елементи на а, така че X е подгрупата на всички елементи х ∈ A, за които φ (х, на ₁, …, а _п) притежава в а.

Сега напишете Val (L) за множеството от всички валидни L- изрази, т.е. тези, които се съдържат във всяка L- структура. За да присвоим значение на израза „Val (L) е определим“, трябва да уточним

1. структура C (L) -кодираща структура за L;
2. конкретна една-една карта -кодиращата карта -набор от формули на L в областта на C (L).

Тогава, ако идентифицираме Val (L) с неговото изображение в C (L) под кодиращата карта, ще интерпретираме изявлението „Val (L) е определим“като изявлението „Val (L), разглеждано като подмножество на домейн на C (L), може да се определи в C (L) чрез формула на L."

Например, когато L е аритметичен език от първи ред, Гьодел първоначално е използвал като кодираща структура стандартния модел на аритметиката ℕ и като кодиране карта на добре познатата функция, получена от основната теорема за факторизация за естествените числа. Рекурсивната избродимост на Val (L) тогава означава просто, че наборът от кодове („номера на Гьодел“) на членове на Val (L) може да се определи в ℕ чрез L-формула на формата ∃ y φ (x, y), където φ (x, y) е рекурсивна формула.

Друга, еквивалентна, кодираща структура за аритметичния език от първи ред е структурата ^[5] ⟨H (ω), ∈ ⨡ H (ω)⟩ на наследствено ограничени множества, където множество x е наследствено ограничено, ако x, неговите членове, членовете на членовете и т.н., всички са ограничени. Тази структура на кодиране отчита факта, че формулите от първи ред естествено се считат за крайни множества.

Ако се обърнем към случая, в който L е инфинитарен език L (κ, λ), каква би била подходяща структура на кодиране в този случай? В началото отбелязахме, че инфинитарните езици са подсказани от възможността да мислим за формули като теоретично зададени обекти, така че нека се опитаме да получим нашата кодираща структура, като мислим за това какъв набор теоретични обекти трябва да вземем инфинитарни формули. Като се има предвид фактът, че за всяка φ∈ форма (κ, λ), φ и нейните подформули, суб-формули и т.н., всички са с дължина <κ, ^[6]мигновено размишление разкрива, че формулите на L (κ, λ) „съответстват“на множествата x наследствено на кардиналност <κ, в смисъл, че x, нейните членове, членовете на членовете и т.н., всички са от кардиналност <κ. Колекцията от всички такива множества е написана H (κ). H (ω) е съвкупността от наследствено ограничени множества, въведени по-горе, а H (ω ₁) тази на всички наследствено преброени множества.

За простота нека предположим, че единственият екстралогичен символ на основния език L е двоичният предикатен символ ∈ (дискусията лесно се разширява до случая, в който L съдържа допълнителни екстралогични символи). Водени от забележките по-горе, като кодираща структура за L (κ, λ) приемаме структурата,

H (κ) = _df ⟨H (κ), ∈ ⨡ H (κ)⟩.

Сега можем да определим кодиращата карта на Form (κ, λ) в H (κ). Първо, на всеки основен символ s от L (κ, λ) присвояваме кодов обект ^⌈ s ^⌉ ∈ H (κ), както следва. Нека {v _ξ: ξ <κ} е изброяване на отделните променливи на L (κ, λ).

символ	Кодов обект	нотация
¬	1	⌈ ¬ ⌉
∧	2	⌈ ∧ ⌉
∧	3	⌈ ∧ ⌉
∃	4	⌈ ∃ ⌉
∈	5	⌈ ∈ ⌉
=	6	⌈ = ⌉
v ξ	⟨0, ξ⟩	⌈ v ξ ⌉

Тогава към всеки φ ∈ Форма (κ, λ) ние приписваме кодовия обект ^⌈ φ ^⌉ рекурсивно, както следва:

^⌈ об _ξ = о _{г |} ^⌉ = _DF ⟨ ^⌈ об _ξ ^⌉, ^⌈ = ^⌉, ^⌈ о _{г |} ^⌉ ⟩, ^⌈ об _ξ ∈ V _{г |} ^⌉ = _DF ⟨ ^⌈ об _ξ ^⌉, ^⌈ ∈ ^⌉, ^⌈ о _{г |} ^⌉ ⟩;

за φ, ψ ∈ форма (κ, λ),

^⌈ ф ∧ ф ^⌉ = _DF ⟨ ^⌈ ф ^⌉, ^⌈ ∧ ^⌉, ^⌈ ф ^⌉ ⟩

^⌈ ¬φ ^⌉ = _DF ⟨ ^⌈ ¬ ^⌉, ^⌈ ф ^⌉ ⟩

^⌈ ∃ X ф ^⌉ = _DF ⟨ ^⌈ ∃ ^⌉ { ^⌈ х ^⌉: х ∈ X}, ^⌈ ф ^⌉ ⟩;

и накрая, ако ⊆ ⊆ Форма (κ, λ) с | Φ | <κ,

^⌈ ∧Φ ^⌉ = _DF ⟨ ^⌈ ∧ ^⌉ { ^⌈ ф ^⌉: φ ∈ Φ}⟩.

Картата φ ↦ ^⌈ φ ^⌉ от Форма (κ, λ) в H (κ) лесно се вижда, че е едно цяло и е необходимата кодираща карта. Съответно ние се съгласяваме да идентифицираме Val (L (κ, λ)) с неговото изображение в H (κ) под тази кодираща карта.

Кога Val (L (κ, λ)) е дефинируем подмножество на H (κ)? За да отговорим на този въпрос, се нуждаем от следните определения.

L-формула се нарича Δ ₀ - формула, ако е еквивалентна на формула, в която всички количествени характеристики са във формата ∀ x ∈ y или ∃ x ∈ y (т.е. ∀ x (x ∈ y →…) или ∃ x (x ∈ y ∧…)). L-формулата е Σ ₁ - формула, ако е еквивалентна на тази, която може да бъде изградена от атомни формули и техните отрицания, използвайки само логическите оператори ∧, ∨, ∀ x ∈ y, ∃ x. За подмножество X от множество A се казва, че е Δ ₀ (съответно Σ ₁) на A, ако е определим в структурата ⟨A, ∈ ⨡ A⟩ по Δ ₀ - (респ. Σ ₁ -) формула на L, Например, ако идентифицираме множеството естествени числа с множеството H (ω) на наследствено ограничени множества по обичайния начин, тогава за всеки X ⊆ H (ω) имаме:

X е Δ ₀ за H (ω) ⇔ X е рекурсивен

X е Σ ₁ на H (ω) ⇔ X е рекурсивно изброяващ.

Следователно понятията Δ ₀ - и Σ _{1 -} могат да се разглеждат като обобщения на понятията рекурсивно и рекурсивно изброяващо множество.

Теоремата за пълнота за L предполага, че Val (L) - считан за подмножество на H (ω) - е рекурсивно изброяващ и следователно Σ ₁ върху H (ω). По подобен начин теоремата за пълнота за L (ω ₁, ω) (виж §2) предполага, че Val (L (ω ₁, ω)) - считан за подмножество на H (ω ₁) - е Σ ₁ на H (ω ₁). Това приятно състояние обаче се срива напълно веднага щом L (ω ₁, ω ₁) бъде достигнато. Защото може да се докаже

Теоремата на Недефинираност на Скот за L (ω ₁, ω ₁). Val (L (ω ₁, ω ₁)) не може да се определи в H (ω ₁) дори чрез формула L (ω ₁, ω ₁); следователно a fortiori Val (L (ω ₁, ω ₁)) не е Σ ₁ върху H (ω ₁).

Тази теорема е доказано в много по същия начин, както и на добре познатия резултат, че наборът от (кодове) валидни изречения на езика от втори ред на arithemetic L ² не е от втори ред се дефинира в своята структура за кодиране ℕ. За да получите този последен резултат едно първо отбелязва, че ℕ се характеризира с една единствена L ² -sentence, а след това показва, че, ако резултатът беше фалшива, а след това "истина в ℕ" за L ² -sentences биха били определими от L ² -формула, като по този начин нарушава теоремата на Тарски за неопределяемостта на истината.

Съответно, за да се докаже теоремата за неопределяемост на Скот по горните линии, трябва да се установи:

(4.1) Характеристика на кодиращата структура H (ω ₁) в L (ω ₁, ω ₁): има L (ω ₁, ω ₁) -размер τ _0, така че за всички L-структури A, A ⊨ τ ₀ ⇔ A ≅ H (ω ₁).

(4.2) Неопределимост на истината за L (ω ₁, ω ₁) - изречения в кодиращата структура: няма L (ω ₁, ω ₁) -формула φ (v ₀), така че за всички L (ω ₁, ω ₁) -разрешения σ, H (ω ₁) ⊨ σ↔φ (^⌈ σ ^⌉).

(4.3) Съществува термин t (v ₀, v ₁) на L (ω ₁, ω ₁) такъв, че за всяка двойка изречения σ, τ от L (ω ₁, ω ₁), H (ω ₁) ⊨ [t (^⌈ σ ^⌉, ^⌈ τ ^⌉) = ^⌈ σ → τ ^⌉].

(4.1) се доказва чрез анализ на теоретично зададеното определение на H (ω ₁) и показва, че той може да бъде „вътрешно“формулиран в L (ω ₁, ω ₁). (4.2) е установен по същия начин като теоремата на Тарски за неопределяемостта на истината за езици от първи или втори ред. (4.3) се получава чрез формализиране на дефиницията на кодиращата карта σ ↦ ^⌈ σ ^⌉ в L (ω ₁, ω ₁).

Въоръжени с тези факти, можем да получим теоремата за неопределяемост на Скот по следния начин. Да предположим, че е невярно; тогава ще има L (ω ₁, ω ₁) -формула θ (v ₀) такава, че за всички L (ω ₁, ω ₁) -разрешения σ,

(4.4) H (ω ₁) ⊨ θ (^⌈ σ ^⌉) ^iff σ ∈ Val (L (ω ₁, ω ₁)).

Нека τ ₀ е изречението, дадено в (4.1). Тогава имаме за всички L (ω ₁, ω ₁) -разрешения σ,

H (ω ₁) ⊨ σ iff (τ ₀ → σ) ∈ Val (L (ω ₁, ω ₁)),

така че чрез (4.4),

H (ω ₁) ⊨ σ iff H (ω ₁) ⊨ θ (^⌈ τ ₀ → σ ^⌉).

Ако t е терминът, даден в (4.3), това следва

H (ω ₁) ⊨ σ↔θ (t (^⌈ τ ₀ ^⌉, ^⌈ σ ^⌉)).

Сега напишете φ (v ₀) за L (ω ₁, ω ₁) -формула θ (t (^⌈ τ ₀ ^⌉, ^⌈ σ ^⌉)). Тогава

H (ω ₁) ⊨ σ↔φ (^⌈ σ ^⌉),

противоречащи (4.2) и допълващи доказателството.

По този начин Val (L (ω ₁, ω ₁)) не може да се определи дори чрез L (ω ₁, ω ₁) - формула, така че fortiori L (ω ₁, ω ₁) е непълна. Подобни аргументи показват, че теоремата за неопределяемост на Скот продължава да се държи, когато ω ₁ е заменен от всеки наследник кардинал κ ⁺; съответно всички езици L (κ ⁺, κ ⁺) са непълни. ^[7]

5. Подезици на L (ω ₁, ω) и теоремата за баридна компактност

Предвид това, което сега знаем за инфинитарните езици, изглежда, че L (ω ₁, ω) е единственото, което може да се държи разумно добре. От друга страна, провалът на теоремата за компактност да се обобщи по L (ω ₁, ω) по какъвто и да е полезен начин е сериозен недостатък, що се отнася до приложенията. Нека се опитаме да анализираме този провал по-подробно.

Спомнете си от §4, че можем да кодираме формулите на език от първи ред L като наследствено ограничени множества, т.е. като членове на H (ω). В този случай всеки краен набор от (кодове на) L-изречения също е член на H (ω) и от това следва, че теоремата за компактност за L може да бъде посочена във формата:

(5.1) Ако Δ ⊆ изпратено (L) е такова, че всяко подмножество Δ ₀ ⊆ Δ, Δ ₀ ∈ H (ω) има модел, така и Δ.

Сега е добре известно, че (5.1) е непосредствено следствие от обобщената теорема за пълнота на L, която, заявена във форма, подобна на тази на (5.1), се превръща в твърдението:

(5.2) Ако Δ ⊆ Sent (L) и σ ∈ Sent (L) удовлетворяват Δ ⊨ σ, тогава има изваждане D на σ от Δ, така че D ∈ H (ω). ^[8]

В §2 отбелязахме, че теоремата за компактност за L (ω ₁, ω) се проваля много силно; всъщност ние построихме набор Γ ⊆ изпратен (ω ₁, ω) такъв, че

(5.3) Всяко подчитано подмножество от Γ има модел, но Γ не.

Спомнете си също, че въведохме понятието за приспадане в L (ω ₁, ω); Тъй като такива удръжки са с преброима дължина, от (5.3) бързо следва, че

(5.4) Има изречение ^[9] σ ∈ Sent (ω ₁, ω) такова, че Γ ⊨ σ, но няма изваждане на σ в L (ω ₁, ω) от Γ.

Сега формулите на L (ω ₁, ω) могат да бъдат кодирани като членове на H (ω ₁), и е ясно, че H (ω ₁) е затворен под образуването на преброими подмножества и последователности. Съответно (5.3) и (5.4) могат да бъдат написани:

(5.3 бис) Всеки Γ ₀ ⊆ Γ такъв, че Γ ₀ ∈ H (ω ₁) има модел, но Γ не;

(5.4 бис) Има изречение σ ∈ Sent (ω ₁, ω) такова, че Γ ⊨ σ, но няма изваждане D ∈ H (ω ₁) на σ от Γ.

От това следва, че (5.1) и (5.2) се провалят, когато „L“се замени с „L (ω ₁, ω)“, а „H (ω)“с „H (ω ₁)“. Освен това може да се покаже, че множеството Γ ⊆ изпратено (ω ₁, ω) в (5.3 бис) и (5.4 бис) може да се приеме за Σ ₁ на Н (ω ₁). По този начин теоремите за компактност и обобщена пълнота се провалят дори за Σ _1- множества от L (ω ₁, ω) -разсъждения.

От (5.4 бис) виждаме, че причината, поради която обобщената теорема за пълнота не успява за Σ _1- множества в L (ω ₁, ω), е, че грубо казано, H (ω ₁) не се „затваря“при образуването на изводи от Σ _{1 -} набори от изречения в H (ω ₁). Така че за да се коригира това, изглежда естествено да се замени H (ω ₁) с множества A, които в известен смисъл са затворени при формирането на такива изводи и след това да се разгледат само онези формули, чиито кодове са в A.

Сега даваме скица как може да се направи това.

Първо, ние идентифицираме символите и формулите на L (ω ₁, ω) с техните кодове в H (ω ₁), както в §4. За всеки преброен транзитив ^[10] набор A, нека

L _A = Форма (L (ω ₁, ω)) ∩ A.

Казваме, че L _A е подязик на L (ω ₁, ω), ако са изпълнени следните условия:

1. L ⊆ L _A
2. ако φ, ψ ∈ L _A, тогава φ ∧ ψ ∈ L _A и ¬φ ∈ L _A
3. ако φ ∈ L _A и x ∈ A, тогава ∃ x φ ∈ L _A
4. ако φ (x) ∈ L _A и y ∈ A, тогава φ (y) ∈ L _A
5. ако φ ∈ L _A, всяка подформула от φ е в L _A
6. ако Φ ⊆ L _A и Φ ∈ A, след това ∧Φ ∈ L _A.

Понятието за приспадане в L _A се дефинира по обичайния начин; ако Δ е набор от изречения на L _A и ф ∈ L _A, след приспадане на φ от Δ в L _А е приспадане на φ от Δ в L (ω ₁, ω) всяка формула от които е в L _A. Казваме, че φ може да се изведе от Δ в L _A, ако има изваждане D на φ от Δ в L _A; при тези условия пишем Δ ⊢ _A φ. По принцип D няма да бъде член на А; за да се гарантира, че такова приспадане може да се намери в А, ще е необходимо да се наложат допълнителни условия на А.

Нека A е изброимо преходен комплект, така че L _A е sublanguage на L (ω ₁, ω) и нека Δ е съвкупност от изречения на L _A. Казваме, че A (или чрез злоупотреба с терминологията, L _A) е Δ-затворен, ако за която и да е формула φ на L _A, такава, че Δ _A, има изваждане D на φ от Δ, така че D ∈ A. Може да се покаже, че единственият счетлив език, който е Δ-затворен за произволен Δ, е езикът от първи ред L, т.е. когато A = H (ω). J. Barwise обаче откри, че има преброени множества A ⊆ H (ω ₁), чиито съответни езици L _{A се} различават от L и все пак са Δ-затворени за всички Σ ₁- съвкупности от изречения Δ. Такива множества А се наричат допустими множества; грубо казано, те са разширения на наследствено ограничените набори, в които теорията на рекурсията - и следователно теорията на доказателствата - все още е възможна (за пълното определение, вижте раздел 5.1 по-долу).

От резултата на Barwise човек получава незабавно

Теорема за баровска компактност. Нека A е счетливо допустимо множество и Δ е съвкупност от изречения на L _A, което е Σ ₁ на A. Ако всеки Δ '⊆ Δ, такъв че Δ' ∈ A има модел, тогава това прави и Δ.

Наличието на „Σ ₁ “тук показва, че тази теорема е обобщение на теоремата за компактност за рекурсивно изброяващи се групи изречения.

Друга версия на теоремата за компактност на Barwise, полезна за конструирането на модели на теорията на множествата, е следната. Нека ZFC е обичайният набор от аксиоми за теорията на множествата Zermelo-Fraenkel, включително аксиомата по избор. Тогава имаме:

5.5 Теорема. Нека A е счетно преходно множество, такова че A = ⟨A, ∈ ⨡ A⟩ е модел на ZFC. Ако Δ е съвкупност от изречения на L _A, която се дефинира в A чрез формула на езика на теорията на множествата и ако всеки Δ '⊆ Δ такъв, че Δ' ∈ A има модел, то и Δ.

В заключение даваме просто приложение на тази теорема. Нека A = ⟨A, ∈ ⨡ A⟩ е модел на ZFC. Модел B = ⟨B, E⟩ на ZFC се казва, че е правилно крайно разширение на A, ако (i) A ⊆ B, (ii) A ≠ B, (iii) a ∈ A, b ∈ B, bEa ⇒ b ∈ A. Следователно правилното крайно разширение на модел на ZFC е правилно разширение, в което нито един „нов“елемент не идва „преди“, нито един „стар“елемент. Като наше приложение 5,5 доказваме

5.6 Теорема. Всеки преносим преходен модел на ZFC има подходящо разширение за край.

Доказателство. Нека A = ⟨A, ∈ ⨡ A⟩ е преходен модел на ZFC и L е езикът от първия ред на теорията на множествата, допълнен с име a за всеки a ∈ A и допълнителна константа c. Нека Δ е множеството от L _A- изрази, съдържащи:

• всички аксиоми на ZFC;
• c ≠ a, за всеки a ∈ A;
• ∀ x (x ∈ a → ∨ _{b ∈ a} x = b), за всеки a ∈ A;
• a ∈ b, за всеки a ∈ b ∈ A.

Лесно е показано, че Δ е подмножество на A, което се определя в A по формула на езика на теорията на множествата. Също така, всеки подмножество Δ '⊆ Δ, така че Δ' ∈ A има модел. За набор C на всичко ∈ A, за които една среща при Δ "принадлежи на A - тъй като Δ" е така - и това е така, ако ние тълкуваме в като всеки член на (задължително непразно) да заложи - C, тогава A е модел на Δ '. Съответно (5.5) означава, че Δ има модел ⟨B, E⟩. Ако се тълкува всяка константа а като елемент на ∈ A, след това ⟨В, Е⟩ е правилното края на удължаване на A. Доказателството е пълно.

Читателят бързо ще види, че теоремата за компактност от първи ред няма да даде този резултат.

5.1 Определение на концепцията за допустим набор

Непразен преходен набор А се казва, че е допустим, когато са изпълнени следните условия:

1. ако a, b ∈ A, тогава {a, b} ∈ A и ∪ A ∈ A;
2. ако a ∈ A и X ⊆ A е Δ ₀ на A, тогава X ∩ a ∈ A;
3. ако a ∈ A, X ⊆ A е Δ ₀ на A, и ∀ x ∈ a ∃ y (<x, y> ∈ X), тогава за някои b ∈ A ∀ x ∈ a ∃ y ∈ b (<x, y> ∈ X).

Условие (ii) - схемата Δ ₀ - разделяне - е ограничена версия на аксиомата на разделяне на Цермело. Условие (iii) - подобна отслабена версия на аксиомата на заместване - може да се нарече схема на заместване Δ ₀.

Доста лесно е да се види, че ако A е преходен набор, такъв, че <A, ∈ | A> е модел на ZFC, тогава A е допустим. По-общо резултатът продължава да се държи, когато аксиомата на зададената мощност е пропусната от ZFC, така че и H (ω), и H (ω ₁) са допустими. Въпреки това, тъй като последната е неизчислима, теоремата за компактност на Barwise не успява да се приложи към нея.

6. Исторически и библиографски бележки

§§ 1 и 2. Инфинитариалните предложения и езици на предикати изглежда са направили първата си изрична поява в печат с документите на Скот и Тарски [1958] и Тарски [1958]. Теоремата за пълнота за L (ω ₁, ω), както и за други инфинитарни езици, е доказана от Карп [1964]. Изчисленията на броя на Hanf за L (ω ₁, ω) са извършени за първи път от Морли [1965]. Неопределяемостта на подрежданията в езиците с ограничен количествен показател е доказана от Карп [1965] и Лопес-Ескобар [1966]. Интерполационната теорема за L (ω ₁, ω) е доказана от Лопес-Ескобар [1965], а теорията за изоморфизма на Скот за L (ω ₁, ω) от Скот [1965].

Теоремата за частичния изоморфизъм на Карп е доказана за първи път в Карп [1965]; виж също Barwise [1973]. Резултатът (2.2) се появява в Чанг [1968], резултат (2.3) в Елентък [1976] и резултат (2.4) в Бел [1981].

§ 3. Резултатите (3.2) и (3.3) се дължат на Ханф [1964], с някои уточнения от Лопес-Ескобар [1966] и Дикман [1975], докато (3.4) е доказан от Тарски. Резултатът (3.5) се дължи на Скот [1961], (3.6) на Бел [1970] и [1972]; и (3.7) до Бел [1974]. Измеримите кардинали за първи път бяха разгледани от Улам [1930] и Тарски [1939]. Фактът, че измеримите кардинали са слабо компактни, е отбелязан в Tarski [1962].

§ 4. Относно теоремата за неопределяемост за L (ω ₁, ω ₁). Забележка Карол Карп (1964, 166), „На Международния конгрес по логика, методология и философия на науката в Станфордския университет през 1960 г. Дана Скот разпространи очертание на доказателство за невъзможността на пълна дефинируема формална система за (γ +, γ +) езици с един-единствен предикатен символ на две места в допълнение към символа за равенство. “Скот никога не е публикувал резултата си и напълно подробно доказателство се появява за първи път в Karp [1964]. Подходът към приетата тук теорема се основава на сметката, дадена в Дикман [1975].

§ 5. Първоначалната мотивация за резултатите, представени в този раздел, идва от Kreisel; в своята [1965] той посочва, че няма убедителни основания за избор на инфинитарни формули единствено на базата на „дължина“, и предлага вместо това да се използват критерии за определяне или „закриване“. Предложението на Kreisel е възприето с голям успех от Barwise [1967], където е доказана неговата теорема за компактност. Идеята за допустим набор се дължи на Platek [1966]. Теорема (5.6) е взета от Кейслер [1974].

За допълнително четене по темата за инфинитарните езици вижте Aczel [1973], Dickmann [1975], Karp [1964], Keisler [1974] и Makkai [1977]. Полезна информация за връзката между инфинитарните езици и големите кардинали може да бъде намерена в глава 10 на Drake [1974].

библиография

• Aczel, P., 1973, „Инфинитарна логика и теоремата за гостоприемна компактност“, Трудове на Мемориалната конференция на Бертран Ръсел от 1971 г. (Uldum, Дания), J. Bell, J. Cole, G. Priest и A. Slomson (eds.), Лийдс: Мемориална конференция на Бертран Ръсел, 234–277.
• Barwise, J., 1967, Безкрайна логика и допустими набори. Доцент доктор. Теза на университета в Станфорд.
• –––, 1973, „Назад и напред чрез инфинитарна логика. Изследвания в теорията на моделите”, в„ Изследвания по математика”(том 8), Буфало: Математическа асоциация на американците, стр. 5–34.
• –––, 1975 г., Допустими комплекти и структури, Берлин: Springer-Verlag.
• Barwise, J. и S. Feferman (ред.), 1985 г., Наръчник по моделно-теоретична логика, Ню Йорк: Springer-Verlag.
• Baumgartner, J., 1974, „Числото на Hanf за пълни L _{ω 1, ω} изречения (без GCH)“, Journal of Symbolic Logic, 39: 575–578.
• Бел, JL, 1970 г., „Слаба компактност в ограничените езици от втори ред“, Бюлетин на Полската академия на науките, 18: 111–114.
• –––, 1972 г., „За връзката между слабата компактност в L _{ω 1, ω}, L _{ω 1, ω 1 и ограничените езици от втори ред“, Архив за математическа логика, 15: 74–78.}
• –––, 1974, „За компактните кардинали“, Zeitschrift für Mathematical Logik und Grundlagen der Mathematik, 20: 389–393.
• –––, 1981, „Изоморфизъм на структурите в S-топовете“, Journal of Symbolic Logic, 43 (3): 449–459.
• Chang, CC, 1968, „Някои забележки към моделната теория на инфинитарните езици“. в „Синтаксис и семантика на инфинитарните езици“(Бележки от лекции по математика: том 72), J. Barwise (съст.), Springer-Verlag, Berlin, 36-63.
• Dickmann, MA, 1975, Големи инфинитарни езици, Амстердам: Северна Холандия.
• Дрейк, FR, 1974, Теория на множествата: Въведение в големите кардинали, Амстердам: Издателска компания North-Holland.
• Елентук, Е., 1976, „Възстановена категоричност“, сп. „Символична логика“, 41 (3): 639–643.
• Hanf, WP, 1964, Некомпетентност на езици с безкрайно дълги изрази, Амстердам: Северна Холандия.
• Karp, C., 1964, Езици с изрази с безкрайна дължина, Амстердам: Северна Холандия.
• –––, 1965, „Крайно-количествено количествено равностойност“в „Теория на моделите“, J. Addison, L. Henkin и A. Tarski (ред.), Амстердам: Северна Холандия, 407–412.
• Keisler, HJ, 1974 г., Теория на модела за инфинитарна логика, Амстердам: Северна Холандия.
• Keisler, HJ и Julia F. Knight, 2004, „Barwise: Infinitary Logic and допустими набори“, Journal of Symbolic Logic, 10 (1): 4–36
• Kolaitis, P. and M. Vardi, 1992, „Fixpoint Logic vs. Infinitary Logic в теорията на крайните модели“, Proceedings of the VII Year IEEE Symposium on Logic in Computer Science (LICS '92), IEEE, стр. 46-57; достъпен онлайн, doi: 10.1109 / LICS.1992.185518
• Kreisel, G., 1965, „Моделно-теоретични инварианти, приложения към рекурсивни и хиперарифметични операции“, в „Теория на моделите“, J. Addison, L. Henkin, и A. Tarski (ред.), Амстердам: Северна Холандия, 190-205.
• Kueker, D., 1975, „Аргументи за връщане и назад на инфинитарни езици“, в Infinitary Logic: In Memoriam Carol Karp (Бележки от лекции по математика: Том 492), D. Kueker (ed.), Берлин: Springer-Verlag,
• Лопес-Ескобар, EGK, 1965, „Теорема за интерполация за безкрайно дългите изречения“, Fundamenta Mathematicae, 57: 253–272.
• –––, 1966, „За определяне на подрежданията на благополучията“, Fundamenta Mathematicae, 59: 13–21.
• Makkai, М., 1977, „Допустими набори и инфинитарна логика“, Наръчник по математическа логика, J. Barwise (съст.), Амстердам: North-Holland, 233-282.
• Морли, М., 1965, „Пропускане на класовете на елементите“, Теория на моделите, Дж. Аддисън, Л. Хенкин и А. Тарски (ред.), Амстердам: Северна Холандия, 265-273.
• Надел, М. 1985, „L _{ω 1, ω} и допустими фрагменти“, в J. Barwise и S. Feferman (ред.) 1985, 271–287.
• Платек, Р., 1966, Основи на теорията на рекурсията, доктор на науките. Теза на университета в Станфорд.
• Скот, Д., 1961, „Измерими кардинали и конструктивни комплекти“, Бюлетин на Академията на полските науки, 9: 521–524.
• –––, 1965 г., „Логика с неизброимо дълги формули и крайни струни на квантовете“, Теория на моделите, Дж. Аддисън, Л. Хенкин и А. Тарски (ред.), Амстердам: Северна Холандия, 329-341,
• Скот, Д. и А. Тарски, 1958, „Изчислителното смятане с безкрайно дълги изрази“, Colloquium Mathematicum, 16: 166–170.
• Шела, Сахарон, 2012, „Хубава инфинитарна логика“, сп. Американското математическо дружество, 25: 395-427, достъпен онлайн, дои: 10.1090 / S0894-0347-2011-00712-1
• Тарски, А., 1939, “Ideale in völlständingen Mengenkörpern I”, Fundamenta Mathematicae, 32: 140–150.
• –––, 1958 г., „Забележки по логиката на предиката с безкрайно дълги изрази“, Colloquium Mathematicum, 16: 171–176.
• –––, 1962 г., „Някои проблеми и резултати, свързани с основите на теорията на множествата“, в E, Nagel, P. Suppes и A. Tarski (ред.), Логика, методология и философия на науката, Stanford: Stanford University Press, 123-135.
• Ulam, S., 1930, “Zur Masstheorie in der algemeinen Mengenlehre”, Fundamenta Mathematicae, 16: 140–150.

Академични инструменти

	Как да цитирам този запис.
	Вижте PDF версията на този запис в Дружеството на приятелите на SEP.
	Разгледайте тази тема за вписване в интернет философския онтологичен проект (InPhO).
	Подобрена библиография за този запис в PhilPapers, с връзки към неговата база данни.

Други интернет ресурси