О теореме Левенгейма-Сколема-Мальцева для HF-структур

Алгебра и логика, 43, N 6 (2004), 748—757

УДК 510.5

О ТЕОРЕМЕ ЛЕВЕНГЕЙМА–СКОЛЕМА–МАЛЬЦЕВА ДЛЯ HF-СТРУКТУР∗) В. Г. ПУЗАРЕНКО

Проблема существования элементарных расширений вида HF(M) сколь угодно большой мощности для наследственно конечных надстроек поставлена в [1], где приведено одно достаточное условие для позитивного решения данной проблемы. Ожидать ответа, аналогичного теореме Левенгейма–Сколема–Мальцева классической теории моделей, нельзя. Например, серия наследственно конечных надстроек над счетными моделями конечной сигнатуры, приведенная в [2], не имеет элементарных расширений вида HF(M). Более того, даже наличие несчетного элементарного расширения вида HF(M) для наследственно конечной надстройки над моделью не более чем счетной сигнатуры не влечет существование расширения произвольной мощности. Примером может служить наследственно конечная надстройка HF(R) над полем R действительных чисел. Все модели вида HF(R′ ) теории Th(HF(R)) (в силу определимости в наследственно конечной надстройке свойства архимедовости) являются подмоделями модели HF(R), а последняя, в свою очередь, несчетна. В § 1 содержатся сведения, необходимые для формулировки и доказательства основных результатов. Все понятия, которые не определяются, но используются в данной работе, можно найти в [1, 3, 4]. В § 2 дается пол∗)

Работа выполнена при частичной финансовой поддержке Российского фонда фун-

даментальных исследований, проекты NN 01-01-04003, 02-01-00540, и Совета по грантам Президента РФ и государственной поддержке ведущих научных школ, проекты N 0015-96184, НШ-2069.2003.1, МК-2452.2003.01.

c Сибиpский фонд алгебpы и логики, 2004

О теореме Левенгейма–Сколема–Мальцева для HF-структур

749

ное описание класса теорий наследственно конечных надстроек, имеющих наследственно конечные надстройки над моделями сколь угодно большой мощности, а также наследственно конечные надстройки, имеющие элементарные расширения вида HF(M) сколь угодно большой мощности. Показано также, что классы диаграмм наследственно конечных надстроек фиксированной мощности и теорий наследственно конечных надстроек языков фиксированной мощности имеют число Ханфа. В § 3 найдено число Ханфа для счетного случая.

§ 1. Предварительные сведения Пусть σ — произвольная сигнатура, а σ ∗ = σ ∪ {U, ∅, ∈} — сигнатура наследственно конечных надстроек над моделями сигнатуры σ. Через Lσω, ω обозначается множество всех (конечных) формул сигнатуры σ, через Lσ∞, ω — класс всех бесконечных формул сигнатуры σ от конечного числа переменных. Пусть Lσω1 , ω — множество всех бесконечных формул сигнатуры σ от конечного числа переменных, в которых допускаются лишь счетные конъюнкции и дизъюнкции. В языке наследственно конечных надстроек будем различать два сорта переменных: прапеременные v0 , v1 , . . . , vn , . . . , которые могут принимать значения только из праэлементов, и общие x0 , x1 , . . . , xn , . . . , принимающие произвольные значения. ∗

Каждому языку Lσω,ω можно сопоставить фрагмент языка Lσω1 ,ω по некоторому правилу ϕ(vi0 , . . . , vik−1 ) 7→ ϕ∗ (vi0 , . . . , vik−1 ), где 0 6 k < ω (ϕ является предложением в случае k = 0), так, что HF(M) |= ϕ(vi0 , . . . , vik−1 )[γ] ⇔ M |= ϕ∗ (vi0 , . . . , vik−1 )[γ] для любых модели M сигнатуры σ и означивания γ : FV(ϕ) → |M|. Ввиду громоздкости определения данного преобразования [1, § 3.4], здесь оно приводиться не будет; важно лишь то, что в подходящем допустимом множестве A выполняется соотношение ∗

∗

(Lσω, ω )∗ ∪ {(Lσω, ω )∗ } ⊆ A,

750

В. Г. Пузаренко

а также замкнутость этого фрагмента относительно взятия подформул. Для доказательства понадобятся некоторые утверждения из [3]. Сначала введем несколько определений. ОПРЕДЕЛЕНИЕ 1.1 [3]. Для кардинала κ индукцией по α определим кардинал i0 (κ) = κ; iα+1 (κ) = 2iα (κ) ; iλ (κ) =

S

iα (κ), если λ — предельный.

α<λ

ОПРЕДЕЛЕНИЕ 1.2 [3]. Фрагментом языка Lσ∞,ω называется множество LσA бесконечных формул и переменных такое, что (i) каждая конечная формула (формула Lσω,ω ) лежит в LσA ; (ii) если ϕ ∈ LσA , то каждая подформула и переменная, встречающаяся в ϕ, также принадлежит LσA ; (iii) если ϕ(v) ∈ LσA , t — терм сигнатуры σ, все переменные которого лежат в LσA , то ϕ(v)vt ∈ LσA ; (iv) если ϕ, ψ, v лежат в LσA , то и ¬ ϕ, ∼ ϕ, ∃vϕ, ∀vϕ, (ϕ ∨ ψ), (ϕ ∧ ψ) также лежат в LσA . Символ A в определении фрагмента играет роль индекса. Через ∼ ϕ обозначается формула ¬ ϕ,

W

если ϕ — атомарная; V если ϕ = ( Φ);

¬ ψ,

ϕ∈Φ

∀v ¬ ψ,

ψ, если ϕ = ¬ψ; V ¬ W ψ, если ϕ = ( Φ); ϕ∈Φ

если ϕ = ∃vψ;

∃v ¬ ψ, если ϕ = ∀vψ.

∗

Отметим, что (Lσω, ω )∗ является фрагментом Lσ∞, ω . ОПРЕДЕЛЕНИЕ 1.3 [3]. Пусть A — допустимое множество и σ — сигнатура, которая является ∆1 -множеством, функция местности которой Σ-определима. Тогда LσA = {ϕ ∈ A | A |= ”ϕ — формула Lσ∞, ω “} называется допустимым фрагментом языка Lσ∞, ω , заданным A. В случаях, когда выбор сигнатуры не принципиален, допустимый фрагмент будем обозначать как LA . Нетрудно убедиться в том, что любой допустимый фрагмент языка Lσ∞, ω является фрагментом языка Lσ∞, ω .

О теореме Левенгейма–Сколема–Мальцева для HF-структур

751

ОПРЕДЕЛЕНИЕ 1.4 [3]. Пусть σ имеет бинарный символ < и, возможно, другие символы. Будем говорить, что предложение ϕ(<) допустимого фрагмента языка LA прижимает (pins down в терминологии из [3]) ординал α, если (i) N |= ϕ влечет, что
V

T

прижимает α. ОПРЕДЕЛЕНИЕ 1.5 [3]. Множество предложений T ⊆ LA назовем Σ1 -теорией LA , если T — Σ1 -подмножество в A. Обозначим через hΣ (A) наименьший ординал, который не прижимается никакой Σ1 -теорией произвольного допустимого фрагмента языка LA . ТЕОРЕМА 1.6 [3, VII.4.1]. Пусть A — допустимое множество, κ = card (A), α = hΣ (A), T — Σ1 -теория языка LA . Если для каждого β < α теория T имеет модель мощности, не меньшей iβ (κ), то теория T имеет модель для любого λ > κ. В общем случае, для допустимого множества A справедливо соотношение hΣ (A) < (2card (A) )+ , однако если A счетно, то hΣ (A) = o(A) и, следовательно, hΣ (A) < ℵ1 . ТЕОРЕМА 1.7 [3, VII.4.2]. Пусть A — счетное допустимое множество и T — Σ1 -теория языка LA . Если для каждого β < o(A) теория T имеет модель мощности, не меньшей iβ (ℵ0 ), то T имеет модель любой бесконечной мощности. ОПРЕДЕЛЕНИЕ 1.8 [3]. Пусть LσA — фрагмент Lσ∞, ω , M — модель сигнатуры σ и hX,
752

В. Г. Пузаренко

парно различных константных символов. Обозначим через σV обогащение сигнатуры σ с помощью символов из CV , а именно, σV = σ ∪ CV . ОПРЕДЕЛЕНИЕ 1.9 [3]. Пусть LσA — фрагмент Lσ∞, ω , M — модель сигнатуры σ, V ⊆ |M|, hX,
< . . . < xn , y1 < . . . < yn имеем (MV , x1 , . . . , xn ) ≡ (MV , y1 , . . . , yn )(LAV ). ТЕОРЕМА 1.10 [3, VII.4.12]. Пусть LA — допустимый фрагмент, κ = card (A), α = hΣ (A). Тогда для любой Σ1 -теории T языка LA справедливо следующее: если для каждого β < α теория T имеет модель мощности, не меньшей iβ (κ), то T имеет модель с бесконечным множеством неразличимых элементов. ОПРЕДЕЛЕНИЕ 1.11 [3]. Пусть LσA — фрагмент языка Lσ∞, ω , C — множество (возможно, пустое) константных символов σ такое, что каждая формула языка LσA содержит лишь конечное число констант из C. (i) LσA назовем сколемовским фрагментом с константами C, если существует 1-1 функция, сопоставляющая каждой формуле языка LA вида ∃xϕ(x, y1 , . . . , yn ), где ϕ не содержит констант из C, а y1 , . . . , yn не находятся под действием кванторов в ϕ, n-арный функциональный символ F∃xϕ сигнатуры σ, не входящий в ϕ; такой символ назовем сколемовским функциональным символом для ∃xϕ(x, y1 , . . . , yn ). (ii) Пусть LσA — сколемовский фрагмент с константами C. Множество, состоящее из всех предложений языка LσA вида ∀y1 . . . ∀yn [∃xϕ(x, y1 , . . . , yn ) → ϕ(F∃xϕ (y1 , . . . , yn ), y1 , . . . , yn )] для всех формул ∃xϕ(x, y1 , . . . , yn ) из (i), назовем сколемовской теорией языка LσA (будем обозначать как TSkolem ). Модель M сигнатуры σ назовем сколемовской моделью языка LσA , если M |= TSkolem . ПРЕДЛОЖЕНИЕ 1.12 [3, VII.2.4]. Пусть LσA — фрагмент Lσ∞,ω . Тогда существует обогащение σ ′ ⊇ σ новыми функциональными символами со следующими свойствами.

О теореме Левенгейма–Сколема–Мальцева для HF-структур

753

(i) Пусть L′A — множество формул, полученных из формул LσA путем подстановки конечного числа термов сигнатуры σ ′ . Тогда L′A — сколемовский фрагмент. Кроме того, card (L′A ) = card (LσA ) и каждый сколемовский функциональный символ лежит в σ ′ \ σ. (ii) Каждая модель M сигнатуры σ имеет обогащение M′ до сколемовской модели языка L′A . (iii) Если LσA — допустимый фрагмент, то можно определить σ ′ ′

так, что LσA будет ∆1 -подмножеством A, а отображение ∃xϕ(x, y1 , . . . , yn ) 7→ F∃xϕ — ′

Σ-функцией на A. В частности, TSkolem ⊆ LσA и TSkolem будет ∆-подмножеством A. ПРЕДЛОЖЕНИЕ 1.13 [3, VII.4.9]. Пусть LA — сколемовский фрагмент с константами, T — теория LA , TSkolem ⊆ T, κ = card (LA ). Если T имеет модель с бесконечным множеством неразличимых элементов для LA , то T имеет модель любой мощности, не меньшей κ.

§ 2. Теоремы о расширениях ТЕОРЕМА 2.1. Пусть T = Th(HF(M)) — теория наследственно конечной надстройки над моделью M сигнатуры σ, κ = max{|σ|, ω}. Тогда равносильны следующие условия: (i) для любого β > κ существует модель Mβ такая, что HF(Mβ ) |= |= T и ||Mβ || > β; (ii) существует модель M0 такая, что HF(M0 ) |= T и ||M0 || = = i(2κ )+ (κ); (iii) существует модель M0 такая, что HF(M0 ) |= T и в некотором сколемовском обогащении HF(M0 ) содержится бесконечное множество X ⊆ |M0 | неразличимых элементов; (iv) существует модель M0 мощности κ такая, что HF(M0 ) |= T и в некотором сколемовском обогащении HF(M0 ) содержится бесконечное множество X ⊆ |M0 | неразличимых элементов.

754

В. Г. Пузаренко ДОКАЗАТЕЛЬСТВО. Импликации (i) ⇒ (ii), (iii) ⇒ (iv) непосред-

ственно следуют из теоремы Левенгейма–Сколема о спуске, которая выполняется для наследственно конечных надстроек без существенных ограничений. Прежде чем доказывать остальные импликации, приведем конструкцию допустимого множества, в котором будет эффективно задана теория (T)∗ , полученная из T с помощью преобразования, упомянутого выше. Пусть σ = P ∪ F , где P состоит из предикатных символов, а F — из функL L циональных. Положим A = (Hκ+ (L), #), где L = hσ, QL 1 , Q2 i, Q1 = P ,

QL 2 = F , а # : σ → ω ∈ Ord(A) — местность символов из σ (заметим, что # ∈ Hκ+ (L)). Напомним, что Hκ+ (L) — допустимое множество, состоящее из всех элементов a из универсума над |L|, удовлетворяющих условию TC(a) < κ+ [3]. Для символов всевозможных логических связок будем использовать начальный сегмент n ∈ Ord(A) (таких символов лишь конечное число). Переменные будем кодировать элементами ω \ n ⊆ Ord(A). Тогда можно определить допустимый фрагмент языка LσA , элементом которого, V в частности, будет h , (T )∗ i. Вернемся к доказательству теоремы. Докажем сначала (ii) ⇒ (i). Пусть X0 = TC({(T)∗ }) ∪ L. По теореме Левенгейма–Сколема существует допустимое множество A0 4 A такое, что X0 ⊆ A0 , ||A0 || = κ. В силу ∗

полноты теории T язык (Lσω,ω )∗ также является элементом множества A0 . Остается применить теорему 1.6 к допустимому фрагменту языка LA0 и теории (T)∗ . Применяя теорему 1.10 к тем же допустимому фрагменту и теории, получим (i) ⇒ (iii). ∗

Поскольку (Lσω, ω )∗ является фрагментом языка Lσ∞, ω , последовательно применяя предложения 1.12 и 1.13, получим (iv) ⇒ (i). 2 В случае не более чем счетной сигнатуры условие (ii) теоремы 2.1, как было замечено выше, можно заменить на следующее: (ii)′ существует модель M0 такая, что HF(M0 ) |= T и ||M0 || = = i ω1 (ℵ0 ). Если применить теорему 2.1 к элементарной диаграмме D(HF(M)) наследственно конечной надстройки над моделью M (можно предполагать,

О теореме Левенгейма–Сколема–Мальцева для HF-структур

755

∗ что диаграмма является теорией сигнатуры σM ), то получится следующая

ТЕОРЕМА 2.2. Для бесконечной модели M сигнатуры σ и κ = = max{|σ|, ||M||} равносильны следующие условия: (i) для любого β > κ существует модель Mβ такая, что HF(M) 4 4 HF(Mβ ) и ||Mβ || > β; (ii) существует модель M0 такая, что HF(M) 4 HF(M0 ) и ||M0 || = = i(2κ )+ (κ); (iii) существует модель M0 такая, что HF(M) 4 HF(M0 ) и в некотором сколемовском обогащении HF(M0 ) содержится бесконечное множество X ⊆ |M0 | неразличимых над |M| элементов; (iv) существует модель M0 мощности κ такая, что HF(M) 4 4 HF(M0 ) и в некотором сколемовском обогащении HF(M0 ) содержится бесконечное множество X ⊆ |M0 | неразличимых над |M| элементов. Как и в теореме 2.1, если кардинал κ из условия теоремы 2.2 счетный, то (ii) можно заменить условием (ii)′ существует модель M0 такая, что HF(M) 4 HF(M0 ) и ||M0 || = = i ω1 (ℵ0 ).

§ 3. О числе Ханфа для наследственно конечных надстроек Для каждого кардинала α > ω определим два класса: Kα — класс теорий наследственно конечных надстроек над моделями произвольной сигнатуры σ с условием |σ| 6 α; K4 α — класс диаграмм наследственно конечных надстроек над любыми моделями M произвольной сигнатуры σ с условием max{||M||, |σ|} 6 α. ОПРЕДЕЛЕНИЕ 3.1. Пусть α — кардинал, а Sα — один из классов Kα или K4 α . Числом Ханфа H(Sα ) класса Sα называется наименьший кардинал κ такой, что для любой теории T ∈ Sα из существования наследственно конечной надстройки A |= T мощности κ следует существование наследственно конечной надстройки Aβ |= T мощности β для любого β > α. Из теорем 2.1 и 2.2 непосредственно вытекает

756

В. Г. Пузаренко ПРЕДЛОЖЕНИЕ 3.2. Пусть α — кардинал, Sα — один из классов

Kα или K4 α . Тогда H(Sα ) существует и H(Sα ) 6 i(2α )+ (α). Более того, если α = ℵ0 , то H(Sα ) 6 i ω1 (α). Теперь покажем, что H(Kℵ0 ) = H(K4 ℵ0 ) = i ω1 (ℵ0 ), построив для каждого α < ω1 модель Mα конечной сигнатуры мощности iα (ℵ0 ), которая не имеет собственного элементарного расширения M′ такого, что HF(Mα ) 4 HF(M′ ). Кроме того, теория Th(HF(Mα )) не будет иметь наследственно конечной надстройки мощности β при любом β > iα (ℵ0 ). Нижеприведенная конструкция обобщает пример, построенный в [4, док-во предлож. 3.2.11]. Пусть α — произвольный не более чем счетный ординал, ω ′ ⊆ ω — начальный сегмент множества натуральных чисел, равномощный α. Зафиксируем некоторое взаимнооднозначное отображение λ : ω ′ → α множества ω ′ на α. Зададим на множестве ω ′ отношение порядка 60 следующим образом: n 60 m ⇔ λ(n)ελ(m), где ε — естественное отношение порядка на ординалах. Очевидно, λ : hω ′ , 60 i ∼ = hα, ε ↾ α2 i. Модель Mα сигнатуры σ = {0, s2 , 62 , Q3 } будет зада0

на на множестве M ⊇ ω, которое определяется ниже. Первые три символа будем интерпретировать следующим образом: 0Mα ⇌ 0 ∈ ω; sMα = {hm, ni ∈ ω 2 | n = m + 1}; интерпретация символа 60 определена, как и выше. Индукцией по δ 6 α определим семейство множеств Mδ такое, что δ1 < δ2 ⇒ Mδ1

Mδ2 , Mα = M . Кроме того, по индукции будем опреде-

лять некоторую часть отношения QMα : α ⇌ ∅; если δ = 0, то Mδ ⇌ ω, QM δ

если δ — предельный ординал, то Mδ ⇌

S β<δ

α ⇌ Mβ , QM δ

S β<δ

α QM β ;

если δ = δ ′ + 1, то для каждого непустого подмножества A ⊆ Mδ′ возьмем элемент aA 6∈ Mδ′ так, что aA 6= aA′ , если A 6= A′ , и положим ′ α α ⇌ QM Mδ ⇌ Mδ′ ∪ {aA | ∅ 6= A ⊆ Mδ′ }, QM δ δ ′ ∪ {hn, x, yi | λ(n) = δ , x ∈

О теореме Левенгейма–Сколема–Мальцева для HF-структур

757

∈ Mδ′ , y ∈ Mδ \ Mδ′ , y = aA для A с условием x ∈ A}. α В конечном итоге, полагаем M ⇌ Mα , QMα ⇌ QM α .

Требуемые свойства надстройки HF(Mα ) следуют из определимости функции, соспоставляющей ординалам наследственно конечной надстройки соответствующие элементы множества ω, свойств предельных ординалов, а также равномерной определимости семейства множеств Mδ , δ 6 α. Таким образом, справедлива ТЕОРЕМА 3.3. Для каждого α < ω1 существует модель Mα конечной сигнатуры мощности iα (ℵ0 ), для которой выполняются следующие условия: (i) HF(Mα ) не имеет собственных элементарных расширений вида HF(M′ ); (ii) для любой модели M′ из HF(M′ ) |= Th(HF(Mα )) вытекает, что HF(M′ ) вложима в HF(Mα ). В частности, H(Kω ) = H(K4 ω ) = iω1 (ℵ0 ).

ЛИТЕРАТУРА 1. Ю. Л. Ершов, Определимость и вычислимость (Сибирская школа алгебры и логики), Новосибирск, Научная книга (НИИ МИОО НГУ), 1996. 2. В. Г. Пузаренко, О теории моделей на наследственно конечных надстройках, Алгебра и логика, 41, N 2 (2002), 199—222. 3. J. Barwise, Admissible Sets and Structures, Berlin a.o., Springer-Verlag, 1975. 4. Г. Кейслер , Ч. Ч. Чен, Теория моделей, М., Мир, 1977.

Поступило 18 сентября 2002 г. Адрес автора: ПУЗАРЕНКО Вадим Григорьевич, Институт математики СО РАН, пр. Ак. Коптюга, 4, г. Новосибирск, 630090, РОССИЯ. e-mail: [email protected]