Axiomatizable Classes

Prove that the class $K_{\sigma }$ is axiomatizable.

Prove that the union and intersection of axiomatizable classes are axiomatizable.

Let $K$ be an axiomatizable class, $\mathfrak {M} \in K$, and $\mathfrak {M}'$ isomorphic to $\mathfrak {M}$. Show that $\mathfrak {M}' \in K$.

Let $K$ be an axiomatizable class, and $\left\{ i \mid i \in I, \mathfrak {M}_{i} \in K\right\} \in D$, where $D$ is an ultrafilter over $I$. Prove that $\prod_{i \in I} \mathfrak {M}_{i} / D \in K$.

Prove that if a class $K$ of algebraic systems is axiomatizable, then the class $K'$ of all infinite systems from $K$ is also axiomatizable.

Let $K$ be an axiomatizable class containing finite systems with arbitrarily large numbers of elements. Construct an infinite system from the class $K$. Prove that $K$ contains an infinite system of cardinality the continuum.

Prove that the following are not axiomatizable:

Prove that the class of fields of finite characteristic is not axiomatizable.

Let $\mathfrak {M}_{0} = \langle M_{0}; \leq \rangle$, $\mathfrak {M}_{1} = \langle M_{1}; \leq \rangle , \ldots$ be a family of well-ordered sets such that $\left|M_{k + 1}\right| \geq k + 1$. Prove that the ultraproduct $\prod_{i \in \mathbb {N}} \mathfrak {M}_{i} / D$ is well-ordered with respect to $\leq$ if and only if $D$ is a principal ultrafilter. Deduce that the class of well-ordered sets is not axiomatizable.

Prove that a class $K$ is axiomatizable if and only if it is closed under ultraproducts and elementary equivalence.

Prove that an elementary theory $T$ has a model if and only if every finite subset $T_{0} \subseteq T$ is satisfiable (Mal'tsev's local theorem).

Prove that every consistent theory has a model (the model existence theorem).

Prove that, for a class $K$ to be finitely axiomatizable, it is necessary and sufficient that $K$ and its complement $K_{\sigma } \backslash K$ be axiomatizable.

Let $K$ be a finitely axiomatizable class and $\prod_{i \in I} \mathfrak {M}_{i} / D \in K$, where $D$ is an ultrafilter over $I$. Prove that $\left\{ i \mid \mathfrak {M}_{i} \in K\right\} \in D$.

Let $K$ be an axiomatizable class containing finite systems with arbitrarily large numbers of elements. Prove that the class of infinite systems of $K$ is not finitely axiomatizable.

Prove that the following classes are not finitely axiomatizable:

Prove that the class of fields of characteristic 0 is not finitely axiomatizable.

Let the theory $T$ have an infinite model. Prove that for every infinite cardinal number $m$ there exists a model for $T$ of cardinality greater than $m$ (Mal'tsev's extension theorem).

Suppose that for every $n \in \mathbb {N}$ the theory $T$ has a model of cardinality greater than $n$. Prove that for every infinite cardinal number $m$ there exists a model for $T$ of cardinality greater than $m$.

Prove that if every finite impoverishment of every finite submodel of a model $\mathfrak {M}$ is isomorphically embeddable in some model of the class $K$, then $\mathfrak {M}$ is isomorphically embeddable in a suitable ultraproduct of models from $K$.

Let $D(\mathfrak {M})$ be the diagram of the system $\mathfrak {M} = \langle M; \sigma \rangle$ and let $\mathfrak {M}' = \langle M'; \sigma \cup M \rangle$ be a model for $D(\mathfrak {M})$. Prove that $\mathfrak {M}$ is isomorphically embeddable in $\langle M'; \sigma \rangle$.

Let $\mathfrak {M} = \langle M; \sigma \rangle$ be a finite algebraic system of finite signature. Prove that there exists an $\exists$-sentence $A$ of signature $\sigma$ such that, for every system $\mathfrak {M}'' = \langle M''; \sigma \rangle$, $A$ is true in $\mathfrak {M}''$ if and only if $\mathfrak {M}$ is isomorphically embeddable in $\mathfrak {M}''$.

Let $\sigma$ be a finite signature, let $\mathfrak {M}_{i} = \langle M_{i}; \sigma \rangle$ ($i \in I$) be a system of finite algebraic systems of signature $\sigma$, and suppose there exists $n$ such that $\left|M_{i}\right| \leq n$. Prove that for every ultrafilter $D$ over $I$ there exists $i_{0} \in I$ such that $\prod_{i \in I} \mathfrak {M}_{i} / D \cong \mathfrak {M}_{i_{0}}$.

Let $\mathfrak {M} = \langle M; \sigma \rangle$ be an algebraic system, $A$ a nonempty subset of $M$, and $\mathfrak {M}_{i} = \langle M_{i}; \sigma \rangle$ ($i \in I$) the family of all subsystems of $\mathfrak {M}$ such that $M_{i} \supseteq A$. Prove that $\mathfrak {M}_{0} = \left\langle \bigcap_{i \in I} M_{i}; \sigma \right\rangle$ is the subsystem of $\mathfrak {M}$ generated by the set $A$.

Prove that if $\mathfrak {M}_{1} = \langle M_{1}; \sigma \rangle$ is the subsystem of the system $\mathfrak {M}$ generated by the set $A$, then $M_{1}$ is the set of all values of terms of signature $\sigma$ when the variables take values in the set $A$.

Let $\mathfrak {M} = \langle M; \sigma \rangle$, and let $A$ be a nonempty subset of $M$. Prove that the subsystem $\mathfrak {M}'$ generated by the set $A$ has cardinality at most $\max \left\{ \left|A\right|, \left|\sigma \right|, \aleph_{0}\right\}$.

Prove that every axiomatizable class consists of impoverishments of algebraic systems of some universally axiomatizable class.

Prove that every system of an axiomatizable class $K$ of finite signature contains a finite or countable $K$-subsystem.

Let $K$ be an axiomatizable class whose signature $\sigma$ has cardinality $p$, and let $\mathfrak {M} = \langle M; \sigma \rangle$ be some $K$-system. Prove that every subset $A \subseteq M$ of cardinality $m$ is contained in a suitable $K$-subsystem of the system $\mathfrak {M}$ of cardinality at most $p + m + \aleph_{0}$ (the Lowenheim--Skolem theorem).

Prove that every infinite system $\mathfrak {M} = \langle M; \sigma \rangle$ of an axiomatizable class $K$ admits a $K$-extension of any preassigned cardinality greater than $\left|M\right| + \left|\sigma \right|$.

Construct an example of an axiomatizable class $K$ such that the class $K$ contains finite models with arbitrarily large numbers of elements, while all infinite models of $K$ have cardinality at least the cardinality of the continuum.

Construct an example of an axiomatizable class $K$ such that $K$ has a countable model, while every other model of the class $K$ that is an extension of this model has cardinality at least the cardinality of the continuum.

Prove that if an axiomatizable class $K$ contains a system of cardinality $m \geq \aleph_{0}$, then for every $n \geq 2^{m}$ there exists a $K$-system of cardinality $n$.

Suppose the generalized continuum hypothesis holds: for any cardinal numbers $m, n$ with $m \leq n \leq 2^{m}$, it follows that $m = n$ or $n = 2^{m}$. Prove that then, for every axiomatizable class $K$, exactly one of the following conditions holds:

Prove that if $\varphi : M \to M'$ is an elementary mapping, then $\varphi$ is one-to-one, and for every formula $A(x_{1}, \ldots , x_{n})$ and all $m_{1}, \ldots , m_{n} \in M$ we have

Let $\mathfrak {N} = \langle N; \leq \rangle$, $\mathfrak {M} = \langle M; \leq \rangle$, where $N$ is the set of natural numbers and $M$ the set of positive integers. Show that $\mathfrak {N}$ and $\mathfrak {M}$ are elementarily equivalent, but $\mathfrak {N}$ is not an elementary extension of $\mathfrak {M}$.

Let $M$ be the set of even numbers, $\mathfrak {M} = \langle M; \leq \rangle$, $\mathfrak {N} = \langle N; \leq \rangle$, where $\leq$ is the usual order. Is $\mathfrak {M}$ an elementary submodel of $\mathfrak {N}$?

Let $\mathfrak {R} = \langle \mathbb {R}; +, \cdot \rangle$ be the field of real numbers, and $\mathfrak {C} = \langle \mathbb {C}; +, \cdot \rangle$ the field of complex numbers. Is $\mathfrak {C}$ an elementary extension of $\mathfrak {R}$?

Prove that for every ultrafilter $D$ over $I$ the canonical mapping $\varphi : M \to M^{I} / D$, defined by $\varphi (b) = f / D$, where $f(i) = b$ for all $i \in I$, is an elementary embedding of $M$ into $M^{I} / D$. Prove that if $M$ is a finite system, then $\varphi$ is an isomorphism of $M$ onto $M^{I} / D$.

Let $\mathfrak {M}_{n} = \langle M_{n}; \leq \rangle$ be linearly ordered sets ($n \in \mathbb {N}$); $M_{n}$ contains $2n + 1$ elements.

Let $FD(\mathfrak {M})$ be the complete diagram of the system $\mathfrak {M} = \langle M; \sigma \rangle$ and let $\mathfrak {M}' = \langle M'; \sigma \cup M \rangle$ be a model for $FD(\mathfrak {M})$. Prove that $\mathfrak {M}$ is elementarily embeddable in $\langle M'; \sigma \rangle$.

Prove that for every infinite system $\mathfrak {M} = \langle M; \sigma \rangle$ and every cardinal number $m$, there exists an elementary extension of the system $\mathfrak {M}$ of cardinality greater than $m$.

Let $\mathfrak {M} = \langle M; \sigma \rangle$ be a subsystem of the system $\mathfrak {M}' = \langle M'; \sigma \rangle$. Prove that, for $\mathfrak {M}$ to be an elementary subsystem of $\mathfrak {M}'$, it is necessary and sufficient that, for every formula $A(x_{1}, \ldots , x_{n}, y)$ of signature $\sigma$ and all $m_{1}, \ldots , m_{n} \in M$, $\mathfrak {M}' \vDash \exists y \, A(m_{1}, \ldots , m_{n}, y)$ implies the existence of $m \in M$ such that $\mathfrak {M} \vDash A(m_{1}, \ldots , m_{n}, m)$.

Prove that every infinite system of finite or countable signature $\sigma$ is an elementary extension of a countable system of signature $\sigma$.

Let $\mathfrak {M} = \langle M; \sigma \rangle$ be an infinite system, $X \subseteq M$, and let $m$ be a cardinality such that $\max \left\{ \left|\sigma \right|, \left|X\right|, \aleph_{0}\right\} \leq m \leq \left|M\right|$. Prove that there exists an elementary subsystem $\mathfrak {M}' = \langle M'; \sigma \rangle$ of cardinality $m$ such that $X \subseteq M'$.

Let $\mathfrak {M} = \langle M; \sigma \rangle$ be an infinite system and $m \geq \max \left\{ \left|M\right|, \left|\sigma \right|\right\}$. Prove that $\mathfrak {M}$ has an elementary extension of cardinality $m$.

Let $\mathfrak {M}_{1}, \ldots , \mathfrak {M}_{n}, \ldots$ be a set of systems such that $\mathfrak {M}_{i + 1}$ is an elementary extension of $\mathfrak {M}_{i}$ for every $i$. Prove that $\bigcup_{i} \mathfrak {M}_{i}$ is an elementary extension of every $\mathfrak {M}_{i}$.

Prove that a class $K$ is axiomatizable if and only if $K$ is abstract, closed under ultraproducts, and closed under taking elementary subsystems.

Prove that a class $K$ of systems of signature $\sigma$ is universally axiomatizable if and only if, for every system $\mathfrak {M}$ of signature $\sigma$, the fact that every finite impoverishment of every finite submodel of the system $\mathfrak {M}$ is isomorphically embeddable in some $K$-system implies that $\mathfrak {M}$ belongs to $K$.

Show that a class $K$ is universally axiomatizable if and only if $K$ is closed under ultraproducts, abstract, and hereditary (closed under taking subsystems).

Let the class $K$ be axiomatizable, and let $SK$ be the class of systems isomorphic to subsystems of $K$-systems. Prove that the class $SK$ is universally axiomatizable.

Prove that, for $\mathfrak {M}$ and $\mathfrak {M}_{1}$ to be elementarily equivalent, it is necessary and sufficient that there exist an ultrafilter $D$ over a suitable set $I$ for which there exists an elementary mapping of $\mathfrak {M}$ into $\mathfrak {M}_{1}^{I} / D$.

Prove that if $\mathfrak {M}$ and $\mathfrak {M}_{1}$ are elementarily equivalent and $\mathfrak {M}$ is finite, then $\mathfrak {M}_{1}$ is finite and isomorphic to $\mathfrak {M}$.

Prove that, for a consistent theory $T$ to be complete, it is necessary and sufficient that all of its models be elementarily equivalent.

Show that the class of models of a categorical theory consists (up to isomorphism) of a single finite system. (A theory is called categorical if all of its models are isomorphic.)

Let $T$ be an elementary theory having no finite models, which is $m$-categorical for some infinite cardinality $m$. Prove that $T$ is a complete theory. (A theory is called $m$-categorical if all of its models of cardinality $m$ are isomorphic.)

Prove that the theory of densely ordered sets (see Problem I.5.13 of 5 of Part I) without least or greatest element is complete.

Let $\Gamma$ be a complete set of sentences of signature $\sigma$, and let $\Gamma_{0} \supseteq \Gamma$, $\Gamma_{1} \supseteq \Gamma$ be two consistent sets of sentences such that all object constants of $\Gamma_{0}$ and all function and predicate symbols of $\Gamma_{1}$ belong to $\sigma$. Prove that the set $\Gamma_{0} \cup \Gamma_{1}$ is consistent.

Let $\Gamma$ be a complete set of sentences of signature $\sigma$, $A$ a sentence all of whose object constants belong to $\sigma$, and $\Gamma \cup \left\{ A\right\}$ consistent. Prove that if $\Gamma$ is satisfiable in a system $\mathfrak {M} = \langle M; \sigma \rangle$, then the set $\left\{ A\right\} \cup FD(\mathfrak {M})$ is consistent.

Let $\mathfrak {M} = \langle M; \sigma \rangle$ be an impoverishment of the system $\mathfrak {M}_{1} = \langle M_{1}; \sigma \rangle$, and let $\mathfrak {M}_{2} = \langle M_{2}; \sigma \rangle$ be an elementary extension of $\mathfrak {M}$. Prove that there exists an elementary extension $\mathfrak {M}_{3} = \langle M_{3}; \sigma_{1} \rangle$ of the system $\mathfrak {M}_{1}$ such that $\langle M_{3}; \sigma \rangle$ is an elementary extension of $\mathfrak {M}_{2}$.

Let $\Gamma$ be a complete set of sentences of signature $\sigma$, $A$ a sentence of signature $\sigma_{1} \supseteq \sigma$, $B$ a sentence of signature $\sigma_{2} \supseteq \sigma$, and $\sigma_{1} \cap \sigma_{2} = \sigma$, with all object constants of $A$ and all object constants of $B$ belonging to $\sigma$. Prove that if $\Gamma \cup \left\{ A\right\}$ and $\Gamma \cup \left\{ B\right\}$ are consistent, then $\Gamma \cup \left\{ A, B\right\}$ is consistent.

Let $\Gamma$ be a complete set of sentences of signature $\sigma$, $A$ a sentence of signature $\sigma_{1} \supseteq \sigma$, $B$ a sentence of signature $\sigma_{2} \supseteq \sigma$, and $\sigma_{1} \cap \sigma_{2} = \sigma$. Prove that if $\Gamma \cup \left\{ A\right\}$ and $\Gamma \cup \left\{ B\right\}$ are consistent, then $\Gamma \cup \left\{ A, B\right\}$ is consistent.

Let $A$ be a sentence of signature $\sigma_{1}$, $B$ a sentence of signature $\sigma_{2}$, and $\vdash (A \supset B)$ in PrC, with $\neg A$ and $B$ not derivable in PrC. Prove that $\sigma = \sigma_{1} \cap \sigma_{2}$ is nonempty and there exists a sentence $C$ of signature $\sigma$ such that $\vdash (A \supset C)$ and $\vdash (C \supset B)$ in PrC (the interpolation theorem for PrC).