Аксиоматизируемые классы

Доказать, что класс $K_{\sigma }$ аксиоматизируем.

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

Пусть $K$ --- аксиоматизируемый класс, $\mathfrak {M} \in K$ и $\mathfrak {M}'$ изоморфна $\mathfrak {M}$. Показать, что $\mathfrak {M}' \in K$.

Пусть $K$ --- аксиоматизируемый класс, $\left\{ i \mid i \in I, \mathfrak {M}_{i} \in K\right\} \in D$, где $D$ ультрафильтр над $I$. Доказать, что $\prod_{i \in I} \mathfrak {M}_{i} / D \in K$.

Доказать, что если класс $K$ алгебраических систем аксиоматизируем, то класс $K'$ всех бесконечных систем из $K$ также аксиоматизируем.

Пусть $K$ --- аксиоматизируемый класс, содержащий конечные системы со сколь угодно большим числом элементов. Построить бесконечную систему из класса $K$. Доказать, что $K$ содержит бесконечную систему мощности континуума.

Доказать, что не являются аксиоматизируемыми:

Доказать, что класс полей конечной характеристики неаксиоматизируем.

Пусть $\mathfrak {M}_{0} = \langle M_{0}; \leq \rangle$, $\mathfrak {M}_{1} = \langle M_{1}; \leq \rangle , \ldots$ --- семейство вполне упорядоченных множеств такое, что $\left|M_{k + 1}\right| \geq k + 1$. Доказать, что ультрапроизведение $\prod_{i \in \mathbb {N}} \mathfrak {M}_{i} / D$ вполне упорядоченно относительно $\leq$ тогда и только тогда, когда $D$ --- главный ультрафильтр. Вывести отсюда, что класс вполне упорядоченных множеств неаксиоматизируем.

Доказать, что класс $K$ аксиоматизируем тогда и только тогда, когда он замкнут относительно ультрапроизведений и элементарной эквивалентности.

Доказать, что элементарная теория $T$ имеет модель тогда и только тогда, когда выполнимо каждое конечное подмножество $T_{0} \subseteq T$ (локальная теорема Мальцева).

Доказать, что любая непротиворечивая теория имеет модель (теорема о существовании модели).

Доказать, что для того, чтобы класс $K$ был конечно аксиоматизируем, необходимо и достаточно, чтобы $K$ и его дополнение $K_{\sigma } \backslash K$ были аксиоматизируемы.

Пусть $K$ --- конечно аксиоматизируемый класс и $\prod_{i \in I} \mathfrak {M}_{i} / D \in K$, где $D$ --- ультрафильтр над $I$. Доказать, что $\left\{ i \mid \mathfrak {M}_{i} \in K\right\} \in D$.

Пусть $K$ --- аксиоматизируемый класс, содержащий конечные системы со сколь угодно большим числом элементов. Доказать, что класс бесконечных систем из $K$ не является конечно аксиоматизируемым.

Доказать, что не являются конечно аксиоматизируемыми классы:

Доказать, что класс полей характеристики 0 не является конечно аксиоматизируемым.

Пусть теория $T$ имеет бесконечную модель. Доказать, что для любого бесконечного кардинального числа $m$ существует модель для $T$, мощность которой больше, чем $m$ (теорема Мальцева о расширении).

Пусть для любого $n \in \mathbb {N}$ теория $T$ имеет модель мощности, большей $n$. Доказать, что для любого бесконечного кардинального числа $m$ существует модель для $T$, мощность которой больше, чем $m$.

Доказать, что если каждое конечное обеднение конечной подмодели модели $\mathfrak {M}$ изоморфно вложимо в некоторую модель из класса $K$, то $\mathfrak {M}$ изоморфно вложима в подходящее ультрапроизведение моделей из $K$.

Пусть $D(\mathfrak {M})$ есть диаграмма системы $\mathfrak {M} = \langle M; \sigma \rangle$ и $\mathfrak {M}' = \langle M'; \sigma \cup M \rangle$ --- модель для $D(\mathfrak {M})$. Доказать, что $\mathfrak {M}$ изоморфно вложима в $\langle M'; \sigma \rangle$.

Пусть $\mathfrak {M} = \langle M; \sigma \rangle$ --- конечная алгебраическая система конечной сигнатуры. Доказать, что существует $\exists$-предложение $A$ сигнатуры $\sigma$ такое, что для любой системы $\mathfrak {M}'' = \langle M''; \sigma \rangle$ $A$ истинно в $\mathfrak {M}''$ тогда и только тогда, когда $\mathfrak {M}$ изоморфно вложима в $\mathfrak {M}''$.

Пусть $\sigma$ --- конечная сигнатура, $\mathfrak {M}_{i} = \langle M_{i}; \sigma \rangle$ ($i \in I$) --- система конечных алгебраических систем сигнатуры $\sigma$ и существует $n$ такое, что $\left|M_{i}\right| \leq n$. Доказать, что для любого ультрафильтра $D$ над $I$ существует $i_{0} \in I$ такое, что $\prod_{i \in I} \mathfrak {M}_{i} / D \cong \mathfrak {M}_{i_{0}}$.

Пусть $\mathfrak {M} = \langle M; \sigma \rangle$ --- алгебраическая система, $A$ --- непустое подмножество $M$ и $\mathfrak {M}_{i} = \langle M_{i}; \sigma \rangle$ ($i \in I$) --- семейство всех подсистем в $\mathfrak {M}$ таких, что $M_{i} \supseteq A$. Доказать, что $\mathfrak {M}_{0} = \left\langle \bigcap_{i \in I} M_{i}; \sigma \right\rangle$ есть подсистема в $\mathfrak {M}$, порожденная множеством $A$.

Доказать, что если $\mathfrak {M}_{1} = \langle M_{1}; \sigma \rangle$ есть подсистема системы $\mathfrak {M}$, порожденная множеством $A$, то $M_{1}$ есть множество всех значений термов сигнатуры $\sigma$, когда переменные принимают значения в множестве $A$.

Пусть $\mathfrak {M} = \langle M; \sigma \rangle$, $A$ --- непустое подмножество $M$. Доказать, что подсистема $\mathfrak {M}'$, порожденная множеством $A$, имеет мощность не более чем $\max \left\{ \left|A\right|, \left|\sigma \right|, \aleph_{0}\right\}$.

Доказать, что каждый аксиоматизируемый класс состоит из обеднений алгебраических систем некоторого универсально аксиоматизируемого класса.

Доказать, что каждая система из аксиоматизируемого класса $K$ конечной сигнатуры содержит конечную или счетную $K$-подсистему.

Пусть $K$ --- аксиоматизируемый класс, сигнатура $\sigma$ которого имеет мощность $p$, и пусть $\mathfrak {M} = \langle M; \sigma \rangle$ --- некоторая $K$-система. Доказать, что каждое подмножество $A \subseteq M$, имеющее мощность $m$, содержится внутри подходящей $K$-подсистемы системы $\mathfrak {M}$ мощности не выше $p + m + \aleph_{0}$ (теорема Левенгейма--Скулема).

Доказать, что каждая бесконечная система $\mathfrak {M} = \langle M; \sigma \rangle$ аксиоматизируемого класса $K$ допускает $K$-расширение любой наперед заданной мощности, большей $\left|M\right| + \left|\sigma \right|$.

Построить пример аксиоматизируемого класса $K$ такого, что класс $K$ содержит конечные модели со сколь угодно большим числом элементов, а все бесконечные модели из $K$ имеют мощность не меньше мощности континуума.

Построить пример аксиоматизируемого класса $K$ такого, что в $K$ существует счетная модель, а все отличные от нее модели класса $K$, являющиеся расширениями этой модели, имеют мощность, не меньшую мощности континуума.

Доказать, что если аксиоматизируемый класс $K$ содержит систему мощности $m \geq \aleph_{0}$, то для любого $n \geq 2^{m}$ существует $K$-система мощности $n$.

Предположим, что справедлива обобщенная гипотеза континуума: для любых кардинальных чисел $m, n$ из $m \leq n \leq 2^{m}$ следует, что $m = n$ или $n = 2^{m}$. Доказать, что тогда для любого аксиоматизируемого класса $K$ справедливо в точности одно из следующих условий:

Доказать, что если $\varphi : M \to M'$ --- элементарное отображение, то $\varphi$ одно-однозначно и для каждой формулы $A(x_{1}, \ldots , x_{n})$ и любых $m_{1}, \ldots , m_{n} \in M$ имеем

Пусть $\mathfrak {N} = \langle N; \leq \rangle$, $\mathfrak {M} = \langle M; \leq \rangle$, где $N$ --- множество натуральных чисел, $M$ --- множество положительных целых чисел. Показать, что $\mathfrak {N}$ и $\mathfrak {M}$ элементарно эквивалентны, но $\mathfrak {N}$ не является элементарным расширением $\mathfrak {M}$.

Пусть $M$ --- множество четных чисел, $\mathfrak {M} = \langle M; \leq \rangle$, $\mathfrak {N} = \langle N; \leq \rangle$, где $\leq$ --- обычный порядок. Является ли $\mathfrak {M}$ элементарной подмоделью $\mathfrak {N}$?

Пусть $\mathfrak {R} = \langle \mathbb {R}; +, \cdot \rangle$ --- поле действительных чисел, $\mathfrak {C} = \langle \mathbb {C}; +, \cdot \rangle$ --- поле комплексных чисел. Является ли $\mathfrak {C}$ элементарным расширением $\mathfrak {R}$?

Доказать, что для любого ультрафильтра $D$ над $I$ каноническое отображение $\varphi : M \to M^{I} / D$, определенное условием $\varphi (b) = f / D$, где $f(i) = b$ для всех $i \in I$, является элементарным вложением $M$ в $M^{I} / D$. Доказать, что если $M$ --- конечная система, то $\varphi$ есть изоморфизм $M$ на $M^{I} / D$.

Пусть $\mathfrak {M}_{n} = \langle M_{n}; \leq \rangle$ --- линейно упорядоченные множества ($n \in \mathbb {N}$); $M_{n}$ содержит $2n + 1$ элемент.

Пусть $FD(\mathfrak {M})$ есть полная диаграмма системы $\mathfrak {M} = \langle M; \sigma \rangle$ и $\mathfrak {M}' = \langle M'; \sigma \cup M \rangle$ --- модель для $FD(\mathfrak {M})$. Доказать, что $\mathfrak {M}$ элементарно вложима в $\langle M'; \sigma \rangle$.

Доказать, что для любой бесконечной системы $\mathfrak {M} = \langle M; \sigma \rangle$ и любого кардинального числа $m$ существует элементарное расширение системы $\mathfrak {M}$ мощности, большей $m$.

Пусть $\mathfrak {M} = \langle M; \sigma \rangle$ есть подсистема системы $\mathfrak {M}' = \langle M'; \sigma \rangle$. Доказать, что для того, чтобы $\mathfrak {M}$ была элементарной подсистемой $\mathfrak {M}'$, необходимо и достаточно, чтобы для любой формулы $A(x_{1}, \ldots , x_{n}, y)$ сигнатуры $\sigma$ и любых $m_{1}, \ldots , m_{n} \in M$ из $\mathfrak {M}' \vDash \exists y \, A(m_{1}, \ldots , m_{n}, y)$ следовало существование такого $m \in M$, что $\mathfrak {M} \vDash A(m_{1}, \ldots , m_{n}, m)$.

Доказать, что каждая бесконечная система конечной или счетной сигнатуры $\sigma$ является элементарным расширением счетной системы сигнатуры $\sigma$.

Пусть $\mathfrak {M} = \langle M; \sigma \rangle$ --- бесконечная система, $X \subseteq M$ и $m$ --- такая мощность, что $\max \left\{ \left|\sigma \right|, \left|X\right|, \aleph_{0}\right\} \leq m \leq \left|M\right|$. Доказать, что существует элементарная подсистема $\mathfrak {M}' = \langle M'; \sigma \rangle$ мощности $m$ такая, что $X \subseteq M'$.

Пусть $\mathfrak {M} = \langle M; \sigma \rangle$ --- бесконечная система и $m \geq \max \left\{ \left|M\right|, \left|\sigma \right|\right\}$. Доказать, что $\mathfrak {M}$ обладает элементарным расширением мощности $m$.

Пусть $\mathfrak {M}_{1}, \ldots , \mathfrak {M}_{n}, \ldots$ --- множество систем таких, что $\mathfrak {M}_{i + 1}$ есть элементарное расширение $\mathfrak {M}_{i}$ для любого $i$. Доказать, что $\bigcup_{i} \mathfrak {M}_{i}$ есть элементарное расширение каждого $\mathfrak {M}_{i}$.

Доказать, что класс $K$ аксиоматизируем тогда и только тогда, когда $K$ является абстрактным, замкнутым относительно ультрапроизведений и замкнутым относительно взятия элементарных подсистем.

Доказать, что класс $K$ систем сигнатуры $\sigma$ универсально аксиоматизируем тогда и только тогда, когда для любой системы $\mathfrak {M}$ сигнатуры $\sigma$ из того, что каждое конечное обеднение каждой конечной подмодели системы $\mathfrak {M}$ изоморфно вложимо в некоторую $K$-систему, следует, что $\mathfrak {M}$ принадлежит $K$.

Показать, что класс $K$ тогда и только тогда универсально аксиоматизируем, когда $K$ является замкнутым относительно ультрапроизведений, абстрактным и наследственным (замкнутым относительно взятия подсистем).

Пусть класс $K$ аксиоматизируем, а $SK$ --- класс систем, изоморфных подсистемам $K$-систем. Доказать, что класс $SK$ универсально аксиоматизируем.

Доказать, что для того, чтобы $\mathfrak {M}$ и $\mathfrak {M}_{1}$ были элементарно эквивалентны, необходимо и достаточно, чтобы существовал такой ультрафильтр $D$ над подходящим множеством $I$, для которого существует элементарное отображение $\mathfrak {M}$ в $\mathfrak {M}_{1}^{I} / D$.

Доказать, что если $\mathfrak {M}$ и $\mathfrak {M}_{1}$ элементарно эквивалентны и $\mathfrak {M}$ конечна, то $\mathfrak {M}_{1}$ конечна и изоморфна $\mathfrak {M}$.

Доказать, что для того, чтобы непротиворечивая теория $T$ была полной, необходимо и достаточно, чтобы все ее модели были элементарно эквивалентны.

Показать, что класс моделей категоричной теории состоит (с точностью до изоморфизма) из одной конечной системы. (Теория называется категоричной, если все ее модели изоморфны.)

Пусть $T$ --- элементарная теория, не имеющая конечных моделей, которая $m$-категорична в некоторой бесконечной мощности $m$. Доказать, что $T$ --- полная теория. (Теория называется $m$-категоричной, если все ее модели мощности $m$ изоморфны.)

Доказать, что теория плотно упорядоченных множеств (см. задачу I.5.13 из 5 части I) без наименьшего и наибольшего элемента является полной.

Пусть $\Gamma$ --- полное множество предложений сигнатуры $\sigma$, $\Gamma_{0} \supseteq \Gamma$, $\Gamma_{1} \supseteq \Gamma$ --- два непротиворечивых множества предложений таких, что все предметные константы из $\Gamma_{0}$ и все функциональные и предикатные символы из $\Gamma_{1}$ входят в $\sigma$. Доказать, что множество $\Gamma_{0} \cup \Gamma_{1}$ непротиворечиво.

Пусть $\Gamma$ --- полное множество предложений сигнатуры $\sigma$, $A$ --- предложение, все предметные константы которого входят в $\sigma$, $\Gamma \cup \left\{ A\right\}$ непротиворечиво. Доказать, что если $\Gamma$ выполнимо в системе $\mathfrak {M} = \langle M; \sigma \rangle$, то множество $\left\{ A\right\} \cup FD(\mathfrak {M})$ непротиворечиво.

Пусть $\mathfrak {M} = \langle M; \sigma \rangle$ есть обеднение системы $\mathfrak {M}_{1} = \langle M_{1}; \sigma \rangle$, $\mathfrak {M}_{2} = \langle M_{2}; \sigma \rangle$ --- элементарное расширение $\mathfrak {M}$. Доказать, что существует элементарное расширение $\mathfrak {M}_{3} = \langle M_{3}; \sigma_{1} \rangle$ системы $\mathfrak {M}_{1}$ такое, что $\langle M_{3}; \sigma \rangle$ есть элементарное расширение $\mathfrak {M}_{2}$.

Пусть $\Gamma$ --- полное множество предложений сигнатуры $\sigma$, $A$ --- предложение сигнатуры $\sigma_{1} \supseteq \sigma$, $B$ --- предложение сигнатуры $\sigma_{2} \supseteq \sigma$ и $\sigma_{1} \cap \sigma_{2} = \sigma$, причем все предметные константы $A$ и все предметные константы $B$ входят в $\sigma$. Доказать, что если $\Gamma \cup \left\{ A\right\}$ и $\Gamma \cup \left\{ B\right\}$ непротиворечивы, то $\Gamma \cup \left\{ A, B\right\}$ непротиворечиво.

Пусть $\Gamma$ --- полное множество предложений сигнатуры $\sigma$, $A$ --- предложение сигнатуры $\sigma_{1} \supseteq \sigma$, $B$ --- предложение сигнатуры $\sigma_{2} \supseteq \sigma$ и $\sigma_{1} \cap \sigma_{2} = \sigma$. Доказать, что если $\Gamma \cup \left\{ A\right\}$ и $\Gamma \cup \left\{ B\right\}$ непротиворечивы, то $\Gamma \cup \left\{ A, B\right\}$ непротиворечиво.

Пусть $A$ --- предложение сигнатуры $\sigma_{1}$, $B$ --- предложение сигнатуры $\sigma_{2}$ и $\vdash (A \supset B)$ в ИП, а $\neg A$ и $B$ невыводимы в ИП. Доказать, что $\sigma = \sigma_{1} \cap \sigma_{2}$ непусто и существует предложение $C$ сигнатуры $\sigma$ такое, что $\vdash (A \supset C)$ и $\vdash (C \supset B)$ в ИП (интерполяционная теорема для ИП).