1611678155-8e243485e0094ed4164786c6208411db (П.Е. Алаев - Краткий конспект лекций), страница 6

. , xk }, тоA |= A(ā) ⇔ для всех b ∈ A выполняется A |= B(ā, b).Можно заметить, что в этом списке отсутствуют ещё два пункта: случаи, когдаA(x1 , . . . , xk ) равна ∃xi B или ∀xi B для некоторого i 6 k. Поскольку xi в этом случаене является свободной переменной A(x̄), значение ai просто отбрасывается: можнопереобозначить формулу как A(x1 , . . . , xi−1 , xi+1 , .

. . , xk ) и использовать пункт (7)или (8). Приведём для ясности формальное определение:7’) если A(x1 , . . . , xk ) = ∃xi B(x1 , . . . , xk ), тоA |= A(a1 , . . . , ak ) ⇔ существует b ∈ A такой, что A |= B(a1 , . . . , ai−1 , b, ai+1 , . . . , ak );8’) если A(x1 , . . . , xk ) = ∀xi B(x1 , . . . , xk ), тоA |= A(a1 , . . . , ak ) ⇔ для всех b ∈ A выполняется A |= B(a1 , . .

. , ai−1 , b, ai+1 , . . . , ak ).25Замечание. Истинность формулы зависит только от системы и значений еёсвободных переменных. В частности, истинность предложения зависит только отсистемы: оно либо является истинным в системе, либо ложным.Предложение (о сохранении формул при изоморфизме). Пусть A, B —две системы сигнатуры Σ, β : A → B — изоморфизм и A(x1 , . . . , xk ) — формула.Если a1 , . . . , ak ∈ A, то A |= A(a1 , . . .

, ak ) ⇔ B |= A(β(a1 ), . . . , β(ak )).Если Γ — бесконечное множество формул, то множество его свободных переменных тоже может быть бесконечным. В такой ситуации удобно использовать понятие означивания. Назовём означиванием переменных в системе A любую функцию γ : V → A, где V — некоторое множество переменных. Как и в случае с ИВ,договоримся, что всякий раз, когда речь идёт о значении терма или формулы приданном означивании, неявно подразумевается условие, что все переменные терма и все свободные переменные формулы получают какие-то значения при этомозначивании.Скажем, что формула A(x1 , . . .

, xk ) истинна в A при означивании γ, если A |=A(γ(x1 ), . . . , γ(xk )). Формула называется тождественно истинной (ложной), если она истинна (ложна) в любой системе при любом означивании. Формулы A иB семантически эквивалентны (A ∼ B), если в любой системе при любом означивании они истинны или ложны одновременно. Множество формул Γ называетсявыполнимым, если существует система и означивание, при которых все формулыиз Γ истинны.Лемма. Для любой формулы A выполняются эквивалентности ¬∃xA ∼ ∀x¬Aи ¬∀xA ∼ ∃x¬A.3.4. Прямые и фильтрованные произведения алгебраических системПусть I — некоторое множество. Семейство подмножеств F ⊆ P (I) называетсяцентрированным, если A1 ∩ A2 ∩ . .

. ∩ An 6= ∅ для любых A1 , . . . , An ∈ F . СемействоF называется фильтром на I, если выполняются условия:1) ∅ 6∈ F и I ∈ F ;2) если A, B ∈ F , то A ∩ B ∈ F ;3) если A ⊆ B ⊆ I и A ∈ F , то B ∈ F .Фильтр F — ультрафильтр, если A ∈ F или I \ A ∈ F для любого A ⊆ I.Теорема (о существовании ультрафильтров). a) Любое непустое центрированное семейство в P (I) может быть расширено до фильтра на I;b) любой фильтр на I может быть быть расширен до ультрафильтра.Пусть {Ai }i∈I — индексированное семейство множеств.

Его прямое произведеQние i∈I Ai = {α — функция | dom(α) = I и α(i) ∈ Ai при i ∈ I}.26Пусть фиксирована сигнатура Σ, {Ai }i∈I — семейство систем этой сигнатурыQи Ai — носитель Ai . Прямое произведение семейства i∈I Ai — это система A сQносителем i∈I Ai , в которой интерпретация символов из Σ задаётся так:1) P ∈ PrΣ ⇒ P A (α1 , . . . , αn ) = и ⇔ P Ai (α1 (i), . . . , αn (i)) = и для всех i ∈ I;2) f ∈ FnΣ ⇒ f A (α1 , . .

. , αn )(i) = f Ai (α1 (i), . . . , αn (i)) для всех i ∈ I;3) c ∈ CnΣ ⇒ cA (i) = cAi для всех i ∈ I.Пусть теперь на I задан фильтр F . Чтобы определить фильтрованное проQизведение семейства {Ai }i∈I , определим на i∈I Ai бинарное отношение ∼F так:α ∼F β ⇔ {i ∈ I | α(i) = β(i)} ∈ F .Лемма. Отношение ∼F является отношением эквивалентности.Кратко обозначим класс эквивалентности α/∼F как α/F .QПусть A = i∈I Ai — определённое выше прямое произведение. ОпределимA/F , фильтрованное произведение семейства {Ai }i∈I по фильтру F , как систему сQносителем {α/F | α ∈ i∈I Ai }, в которой интерпретация символов из Σ задаётсятак:1) P ∈ PrΣ ⇒ P A/F (α1 /F, . . .

, αn /F ) = и ⇔ {i ∈ I | P Ai (α1 (i), . . . , αn (i)) = и} ∈ F ;2) f ∈ FnΣ ⇒ f A/F (α1 /F, . . . , αn /F ) = f A (α1 , . . . , αn )/F ;3) c ∈ CnΣ ⇒ cA/F = cA /F .Лемма. Указанное определение системы A/F является корректным.QОбозначим построенную систему A/F как Fi∈I Ai . Если F — ультрафильтр наI, то эту систему называют ультрапроизведением семейства {Ai }i∈I по F .Скажем, что формула A(x1 , .

. . , xn ) фильтруется по фильтру F , если для люQбого семейства систем {Ai }i∈I и любых элементов α1 /F, . . . , αn /F ∈ Fi∈I AiQFi∈IAi |= A(α1 /F, . . . , αn /F ) ⇔ {i ∈ I | Ai |= A(α1 (i), . . . , αn (i))} ∈ F .Лемма 1. Атомная формула фильтруется по любому фильтру.Лемма 2. Любая формула A семантически эквивалентна формуле A0 , в которойнет ∨, → и ∀.Теорема Лося. Любая формула фильтруется по любому ультрафильтру.3.5. Теорема компактности МальцеваПусть фиксирована сигнатура Σ.

Напомним, что множество формул Γ называется выполнимым, если существует система A и означивание, при которых всеформулы из Γ истинны. Назовём множество Γ локально выполнимым, если любоеего конечное подмножество выполнимо. Ясно, что выполнимое множество являетсяи локально выполнимым.27Теорема компактности Мальцева. Любое локально выполнимое множествоформул является выполнимым.Пусть Γ — множество предложений, A — алгебраическая система.

Обозначимчерез A |= Γ то, что A |= A для всех A ∈ Γ. Система A называется модельюмножества Γ, если A |= Γ.Предложение. Если для каждого натурального n у множества предложенийΓ есть модель мощности больше или равной n, то у Γ есть бесконечная модель.3.6. Формулировка аксиом ZFC на языке формул ИПОбозначим класс всех множеств как V.

Это класс иногда называют универсумом теории множеств. Мы предполагаем, для любых двух множеств A, B ∈ Vвыполнен ровно один из двух случаев: A ∈ B или A 6∈ B. Заменяя запись A ∈ Bна ∈(A, B) = и, а A 6∈ B — на ∈(A, B) = л, мы можем рассматривать пару (V, ∈)как объект, “похожий” на алгебраическую систему сигнатуры Σ = (∈2 ), где ∈ —предикатный символ.Он не является алгебраической системой, поскольку V не является множеством.Тем не менее некоторые свойства алгебраических систем могут быть перенесенына V. В частности, мы можем говорить об истинности формул сигнатуры Σ в V.Значениями свободных переменных при этом являются элементы V, т.е. произвольные множества.

Истинность атомных формул, которые имеют вид ∈(x, y) и x = y,считается заданной изначально, логические связки определяются стандартно, азначение кванторов ∃x и ∀x понимается в том смысле, что “существует множествоx такое, что . . . ” и “для всех множеств x верно, что . . . ”.Тогда аксиомы ZFC, о которых шла речь выше, могут быть переписаны в видепредложений ИПΣ , истинных в V.

Например, аксиома пары приобретает вид¡¢∀x∀y∃z∀t ∈(t, z) ↔ (t = x ∨ t = y) ,где запись A ↔ B является сокращением для (A → B)&(B → A).Выше мы говорили, что классом множеств может быть названа совокупностьвсех множеств, удовлетворяющих некоторому условию. Теперь можно привести более строгую формулировку: под “условием” мы понимаем свойство, которое можетбыть записано в виде формулы ИПΣ .

В этой формуле можно использовать дополнительные параметры, поэтому общее определение звучит так: (определимый)класс множеств — это совокупность всех множеств b, для которых в V верноA(d, b), где A(z, x) — формула ИПΣ , а d — некоторое фиксированное множество,которое называется параметром.28То же самое относится и к другим упоминаниям о неформальных “условиях”выше.

Например, условие Φ(x, y) из аксиомы подстановки — это любое условие,записанное в виде формулы с параметрами. Тогда точная формулировка аксиомыстановится такой: пусть a, d ∈ V, A(z, x, y) — формула ИПΣ , и для любого b ∈ aсуществует не более одного c ∈ V такого, что A(d, b, c). Тогда существует множествоa0 = {c | существует b ∈ a такой, что A(d, b, c)}.29.