Предел Фрэссе

В математической логике , особенно в дисциплине теории моделей , предел Фрэссе (также называемый конструкцией Фрэссе или амальгамацией Фрэссе ) — это метод, используемый для построения (бесконечных) математических структур из их (конечных) подструктур . концепции прямого ограничения категории . Это частный пример более общей Метод был разработан в 1950-х годах его тезкой, французским логиком Роланом Фрэссе .

Основная цель конструкции Фрэссе — показать, как можно аппроксимировать ( счетную ) структуру ее конечно порожденными подструктурами. Учитывая класс $\mathbf {K}$ конечных реляционных структур , если $\mathbf {K}$ удовлетворяет определенным свойствам (описанным ниже), то существует единственная счетная структура $\operatorname {Flim} (\mathbf {K} )$, называемый пределом Фрэссе $\mathbf {K}$, который содержит все элементы $\mathbf {K}$ в качестве подструктур .

Общее исследование пределов Фрэссе и связанных с ним понятий иногда называют теорией Фрэссе . Эта область нашла широкое применение в других разделах математики, включая топологическую динамику , функциональный анализ и теорию Рамсея .

подструктуры и

Исправить язык ${\mathcal {L}}$. По ${\mathcal {L}}$-структура , мы имеем в виду логическую структуру , имеющую подпись ${\mathcal {L}}$.

Учитывая ${\mathcal {L}}$-структура ${\mathcal {M}}$ с доменом $M$и подмножество $A\subseteq M$, мы используем $\langle A\rangle ^{\mathcal {M}}$ наименьшей подструктуры для обозначения ${\mathcal {M}}$ чей домен содержит $A$ (т.е. закрытие $A$ под всеми функциональными и постоянными символами в ${\mathcal {L}}$).

Подструктура ${\mathcal {N}}$ из ${\mathcal {M}}$ тогда называется конечно порожденным, если ${\mathcal {N}}=\langle A\rangle ^{\mathcal {M}}$ для некоторого конечного подмножества $A\subseteq M$. Возраст ​ ${\mathcal {M}}$, обозначенный $\operatorname {Age} ({\mathcal {M}})$, — класс всех конечно порожденных подструктур ${\mathcal {M}}$.

Можно доказать, что любой класс $\mathbf {K}$ то есть возраст некоторой структуры удовлетворяет следующим двум условиям:

Наследственная собственность (HP)

Если $A\in \mathbf {K}$ и $B$ является конечно порожденной подструктурой $A$, затем $B$ изоморфна некоторой структуре в $\mathbf {K}$.

Совместное вложение собственности (JEP)

Если $A,B\in \mathbf {K}$, то существует $C\in \mathbf {K}$ такой, что оба $A$ и $B$ встраиваются в $C$.

Теорема Фрэссе

иллюстрирующая Коммутативная диаграмма, свойство амальгамации.

Как и выше, мы отметили, что для любого ${\mathcal {L}}$-структура ${\mathcal {M}}$, $\operatorname {Age} ({\mathcal {M}})$ удовлетворяет HP и JEP. Фрэссе доказал своего рода обратный результат: когда $\mathbf {K}$ — любое непустое счетное множество конечно порожденных ${\mathcal {L}}$-структуры, обладающей двумя вышеуказанными свойствами, то это возраст некоторой счетной структуры.

Кроме того, предположим, что $\mathbf {K}$ случается, что он удовлетворяет следующим дополнительным свойствам.

Объединенное имущество (AP)

Для любых конструкций $A,B,C\in \mathbf {K}$, такие, что существуют вложения $f:A\to B$, $g:A\to C$, существует структура $D\in \mathbf {K}$ и вложения $f':B\to D$, $g':C\to D$ такой, что $f'\circ f=g'\circ g$ (т.е. они совпадают по образу A в обеих структурах).

Существенная счетность (EC)

С точностью до изоморфизма в $\mathbf {K}$.

В этом случае мы говорим, что K — класс Фрэссе и существует единственная (с точностью до изоморфизма) счетная однородная структура. $\operatorname {Flim} (\mathbf {K} )$ чей именно возраст $\mathbf {K}$. Эта структура называется пределом Фрэссе . $\mathbf {K}$.

Здесь однородный означает, что любой изоморфизм $\pi :A\to B$ между двумя конечно порожденными подструктурами $A,B\in \mathbf {K}$ может быть продолжено до автоморфизма всей структуры.

Примеры

Типичным примером является класс $\mathbf {FCh}$ всех конечных линейных порядков , для которых предел Фрэссе представляет собой плотный линейный порядок без концов (т. е. нет ни наименьшего, ни наибольшего элемента ). По теореме Кантора об изоморфизме с точностью до изоморфизма это всегда эквивалентно структуре $\langle \mathbb {Q} ,<\rangle$, т.е. рациональные числа обычного порядка.

В качестве примера отметим, что ни $\langle \mathbb {N} ,<\rangle$ ни $\langle \mathbb {Z} ,<\rangle$ являются пределом Фрэссе $\mathbf {FCh}$. Это связано с тем, что, хотя они оба счетны и имеют $\mathbf {FCh}$ в зависимости от возраста ни один из них не является однородным. Чтобы убедиться в этом, рассмотрим подструктуры ${\big \langle }\{1,3\},<{\big \rangle }$ и ${\big \langle }\{5,6\},<{\big \rangle }$, и изоморфизм $1\mapsto 5,\ 3\mapsto 6$ между ними. Это не может быть распространено на автоморфизм $\langle \mathbb {N} ,<\rangle$ или $\langle \mathbb {Z} ,<\rangle$, поскольку нет элемента, которому мы могли бы сопоставить $2$, сохраняя при этом порядок.

Другой пример — класс $\mathbf {Gph}$ всех конечных графов , пределом Фрэссе которых является граф Радо .

Для любого простого числа p предел Фрессе класса конечных полей характеристики p — это алгебраическое замыкание ${\overline {\mathbb {F} }}_{p}$.

Предел Фрессе класса конечных абелевых p -групп равен $\mathbb {Z} (p^{\infty })^{(\omega )}$ (прямая сумма счетного числа копий группы Прюфера ). Предел Фрэссе класса всех конечных абелевых групп равен $\bigoplus _{p{\text{ prime}}}\mathbb {Z} (p^{\infty })^{(\omega )}\simeq (\mathbb {Q} /\mathbb {Z} )^{(\omega )}$.

Пределом Фрэссе класса всех конечных групп является универсальная группа Холла .

Предел Фрэссе класса нетривиальных конечных булевых алгебр — это единственная счетная безатомная булева алгебра.

ω-категоричность и устранение кванторов

Класс $\mathbf {K}$ рассматриваемое явление называется равномерно локально конечным, если для любого $n$, существует единая граница размера $n$-порожденные (подструктуры) структуры в $\mathbf {K}$. Предел Фрэссе $\mathbf {K}$ является ω-категоричным тогда и только тогда, когда $\mathbf {K}$ равномерно локально конечен. Если $\mathbf {K}$ равномерно локально конечен, то предел Фрессе $\mathbf {K}$ имеет устранение квантора .

Если язык $\mathbf {K}$ конечно и состоит только из отношений и констант, то $\mathbf {K}$ автоматически равномерно локально конечен.

Например, класс конечномерных векторных пространств над фиксированным полем всегда является классом Фрэссе, но он равномерно локально конечен только в том случае, если поле конечно.Класс конечных булевых алгебр равномерно локально конечен, тогда как классы конечных полей заданной характеристики или конечных групп или абелевых групп не являются таковыми, поскольку 1-порожденные структуры в этих классах могут иметь сколь угодно большой конечный размер.

См. также

• Структурная теория Рамсея
• Хрушовское строительство