Математический журнал. Алматы. 2010. Том ?. � 1. C. 1 — 4

УДК 510.67

ДП-МИНИМАЛЬНЫЕ И УПОРЯДОЧЕННО СТАБИЛЬНЫЕ УПОРЯДОЧЕННЫЕ СТРУКТУРЫ

В. В. Вербовский

Институт проблем информатики и управления МОН РК 050010 Казахстан, Алматы, Пушкина ул., 125, vvv@ipic.kz

В статье доказывается, что дп-минимальные теории являются упорядоченно стабильными.

1. Введение.

Пусть M = (M, <, …) — линейно упорядоченная структура, а A и B — подмножества для M. Как обычно, будем писать A < B, если a < b для любых a ∈ A и b ∈ B. Разбиение ⟨C, D⟩ множества M называется сечением, если C < D. Если дано сечение ⟨C, D⟩, то можно построить частичный тип {c < x < d : c ∈ C, d ∈ D}, который так же будем называть сечением и будем обозначать символом s_{⟨C,D⟩}.

Повсюду в статье под теорией будем понимать полную теорию логики предикатов первого порядка.

Пусть T — теория языка L, а φ(x̄, ȳ) — некоторая формула. Про формулу φ говорят, что она обладает свойством независимости (относительно T), если для любого n < ω существует модель M ⊧ T и две последовательности (ā_{i} : i < n) и (b̄_{J} : J ⊆ n) в M, такие что M ⊧ φ(ā_{i}, b̄_{J}) в том и только в том случае, когда i ∈ J. Теория T обладает свойством независимости, если некоторая формула обладает свойством независимости относительно T.

Пусть q — частичный n-тип, A — множество. Тогда

S_{q}^{n}(A) ≜ {p ∈ S^{n}(A) : p ∪ q совместно}

Заметим, что q может и не быть частичным типом над множеством A.

О п р е д е л е н и е 1 (Б. Байжанов, В. Вербовский [4])

1. Линейно упорядоченная структура M называется упорядоченно стабильной в λ, если для любого подмножества A ⊆ M мощности не больше λ и для любого сечения s = s_{⟨C,D⟩} в M существует самое большее λ 1-типов над A, которые совместны с сечением s, то есть |S_{s}^{1}(A)| ≤ λ.

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

3. Теория T называется упорядоченно стабильной, если существует бесконечный кардинал λ в котором теория T упорядоченно стабильна.

Keywords: Model Theory, totally ordered structure, dp-minimal, o-stable 2000 Mathematics Subject Classification: 03B10, 03C52, 03C64 \begin{matrix}c \\ ◯ \end{matrix} В. В. Вербовский, 2010.

4. Теория T упорядоченно суперстабильна, если существует такой кардинал λ, что теория T упорядоченно стабильна во всех μ ≥ λ.

О п р е д е л е н и е 2 Линейно упорядоченная структура M = (M, <, …) обладает свойством строгого порядка внутри сечения, если существует формула ϕ(x, ȳ), такая что для любого натурального числа n существуют кортежы ā_{1}, …, ā_{n} и сечение s_{n} = s_{⟨C_{n},D_{n}⟩} в M, такие что в некотором |M|^{+}-насыщенном элементарном расширении N модели M имеет место следующее:

ϕ(N , ā_{1}) ∩ s_{n}(N) ⊂ ϕ(N , ā_{2}) ∩ s_{n}(N) ⊂ ⋯ ⊂ ϕ(N , ā_{n}) ∩ s_{n}(N)

Теория обладает свойством строгого порядка внутри сечения, если некоторая ее модель обладает этим свойством.

Т е о р е м а 1 [6] Пусть язык L содержит символ �<”, а теория T языка L содержит аксиомы линейного порядка для предиката x < y. Теория T упорядоченно стабильна в том и только в том случае, когда она не обладает ни свойством независимости, ни свойством строгого порядка внутри сечения.

О п р е д е л е н и е 3 (Шелах) 1. Паттерном независимого разбиения длины κ называется такая последовательность пар ⟨(φ^{α}(x̄; ȳ^{α}), k^{α}) : α < κ⟩ формул и натуральных чисел, для которой существует такая матрица (b̄_{i}^{α} : α < κ, i < ω) кортежей b̄_{i}^{α}, что строка {φ^{α}(x̄; b̄_{i}^{α}) : i < ω} является k^{α}-несовместной для любого α < κ, но путь {φ^{α}(x̄; b̄_{η(α)}^{α}) : α < κ} совместен при любой η ∈ ω^{κ}.

2. Теория T называется пнр-минимальной, если не существует паттерна независимого разбиения длины 2 для случая одной свободной переменной x, то есть для формул вида φ(x; ȳ).

О п р е д е л е н и е 4 [3] Теория называется дп-минимальной, если она пнр-минимальна и не обладает свойством независимости.

Некоторые свойства дп-минимальных теорий можно найти в работах [2, 3]. Заметим, что при помощи стандартных аргументов Ердоша-Радо, не умаляя общности, можно предположить, что каждая последовательность ⟨b̄_{i}^{α} : i < ω⟩ является неразличимой над множеством остальных кортежей: {b̄_{i}^{β} : β ≠ α, i < ω}. Некоторые детали, касающиеся этого вопроса можно найти в [1]. Если же мы работаем в упорядоченных структурах, как в данной статье, то можно предположить также, что каждая последовательность ⟨b̄_{i}^{α} : i < ω⟩ является возрастающей.

Л е м м а 1 Пусть M — линейно упорядоченная структура, чья элементарная теория является пнр-минимальной. Тогда для любой формулы φ(x, ȳ) существует натуральное число n = n_{φ}, такое что для любого сечения s = s_{⟨C,D⟩} структуры M число кортежей ā_{1}, …, ā_{k}, таких что s(x) ∪ {φ(x, ā_{i})} совместно для каждого i = 1, …, k и что s(x) ⊢ ¬∃x(φ(x, ā_{i}) ∧ φ(x, ā_{j})) для любых 1 ≤ i < j ≤ k, не превышает числа n.

Доказательство. Предположим противное, что для каждого натурального числа n существует сечение s_{n}(x) и кортежи ā_{1}^{n}, …, ā_{k_{n}}^{n}, такие что k_{n} ≥ n и s(x) ∪ {φ(x, ā_{i}^{n})} совместно для каждого i = 1, …, k_{n} и что s(x) ⊢ ¬∃x(φ(x, ā_{i}^{n}) ∧ φ(x, ā_{j}^{n})) для любых 1 ≤ i < j ≤ k_{n}. Обогатим язык структуры M, добавив в него предикаты P (x) и R(x, y), которые проинтерпретируем следующим образом. Отношение P (M) — некоторое счетное подмножество множества M, будем считать, что оно реализуется множеством {b_{n} : n < ω}, а для каждого b_{n} ∈ P (M) отношение R(M, b_{n}) = C_{n}, где s_{⟨C_{n},D_{n}⟩} — это сечение s_{n}. Для элементов c ∉ P (M) отношение R(M, c) пусто. Таким образом, в новом языке множество рассматриваемых сечений s_{n} равномерно формульно.

Тогда в обогащенном языке можно записать следующее множество формул, которое в силу наших предпосылок, будет локально совместным:

p(x̄_{n} : n < ω; y) := {P (y)} ∪
∪ {∀u, v(R(u, y) ∧ ¬R(v, y) → ∃t[φ(t, x̄_{n}) ∧ u < t < v]) : n < ω} ∪
∪ {∃u, v(R(u, y) ∧ ¬R(v, y) ∧ ¬∃t(φ(t, x̄_{n}) ∧ φ(t, x̄_{k}) ∧ u < t < v)) :
0 ≤ n < k < ω}

Существует ℵ_{1}-насыщенное элементарное расширение N^{+} модели M^{+} в новом языке, реализующее тип p(x̄_{n} : n < ω; y). Рассмотрим обеднение N полученной модели до исходного языка. В этой модели есть сечение s = s_{⟨C,D⟩} и кортежы b̄_{i}, где i < ω, которые удовлетворяют следующему свойству: s(x)∪{φ(x, b̄_{i})} совместно для каждого i < ω и s(x) ⊢ ¬∃x(φ(x, b̄_{i})∧φ(x, b̄_{j})) для любых 0 ≤ i < j < ω. Так как формула φ(x, b̄_{j}) совместна с сечением s, она реализуется сколь угодно большими элементами из множества C или сколь угодно малыми из множества D. Так как рассматриваемое множество формул бесконечно, не умаляя общности, можно считать, что все эти формулы реализуются сколь угодно большими элементами из множества C.

Так как модель N достаточно насыщенна, существуют элементы γ ∈ C и δ ∈ D, такие что множество формул {φ(x, b̄_{n}) ∧ γ < x < δ : n < ω} попарно несовместно.

Пусть элементы c_{n}^{1} ∈ C реализуют формулы φ(x, b̄_{n}) ∧ x > γ. Поскольку модель N достаточно насыщенна, существуют элементы d_{0} и d_{1} из C, такие что

d_{0} < inf{c_{n}^{1} : n < ω} ≤ sup{c_{n}^{1} : n < ω} < d_{1}

Предположим, что элемент d_{k} уже найден. Пусть элементы c_{n}^{k+1} ∈ C реализуют формулы φ(x, b̄_{n}) ∧ x > d_{k}. Поскольку модель N достаточно насыщенна, существует элемент d_{k+1} из C, такой что

d_{k} < inf{c_{n}^{k+1} : n < ω} ≤ sup{c_{n}^{k+1} : n < ω} < d_{k+1}

В результате получили, что и множество формул {φ(x, b̄_{n}) : n < ω} и множество интервалов {d_{n} < x < d_{n+1} : n < ω} попарно несовместны, но каждая формула из первого множества совместна с каждой формулой из второго. Таким образом, мы построили паттерн независимого разбиения длины 2, что противоречит исходным посылкам. □

Т е о р е м а 2 Если элементарная теория линейно упорядоченной структуры является дп-минимальной, то она является и упорядоченно стабильной.

Доказательство. Предположим, что теория T является дп-минимальной, но не является при этом упорядоченно стабильной. Так как в силу условий теория T не обладает свойством независимости, то по теореме 1 она обладает свойством строгого порядка внутри сечения. Пусть формула φ(x; ȳ) обладает свойством строгого порядка внутри сечения s = s_{⟨C,D⟩} некоторой достаточно насыщенной модели M теории T. Пусть последовательность кортежей ā_{n}, где n < ω, будет такой, что

s(x) ⊢ φ(x; ā_{i}) → φ(x; ā_{j}) для любых i < j < ω

Определим формулу

ψ(x, ā_{i}, ā_{i+1}) := ¬φ(x, ā_{i}) ∧ φ(x, ā_{j})

Тогда формула ψ(x, ā_{i}, ā_{i+1}) совместна с сечением s при каждом i < ω, но при этом данное множество формул попарно несовместно, что противоречит лемме 1. □

Т е о р е м а 3 Существует упорядоченно стабильная теория, которая не является дпминимальной.

Доказательство. Рассмотрим элементарную теорию T группы (ℝ, <, +, 0, Q), в которой одноместный предикат Q проинтерпретирован множеством рациональных чисел. Очевидно, что эта теория не является дп-минимальный в силу леммы 1, так как класс смежности ℚ+r формулен и совместен с любым сечением каким бы ни было вещественное число r. В работе [6] было доказано, что эта теория является упорядоченно стабильной. Доказательство этого факта следует из того, что теория T допускает элиминацию кванторов. □

Список литературы

[1] Adler H. Strong theories, burden, and weight, preprint, 2007.

[2] Goodrick J. A monotonicity theorem for dp-minimal densely ordered groups // The Journal of Symbolic Logic, V. 75, N 1, 2010. P. 221–238.

[3] Onshuus A., Usvyatsov A. On dp-minimality, strong dependence, and wight, submitted, 2008.

[4] Байжанов Б., Вербовский В. Упорядоченно стабильные теории // подано в печать, 2010.

[5] Вербовский В. О зависимости упорядоченно стабильных теорий // Вестник инженерной академии Республики Казахстан. 2008. N. 1, С. 16–20.

[6] Вербовский В. Критерий упорядоченной стабильности зависимой теории // Вестник Карагандинского государственного университета. 2008. N. 2, С. 16–23.

[7] Вербовский В. Упорядоченно стабильные группы // Математические труды. 2010. В печати.

Dp-minimal and o-stable ordered structures Viktor Verbovskiy Abstract In the paper I prove that a dp-minimal theory with total order is o-stable. Дп-минималды реттелген теорияларды? о-стабиль