MATHEMATICS

S. R. KOGALOVSKII

ON ONE GENERAL METHOD FOR OBTAINING STRUCTURAL CHARACTERISTICS OF AXIOMATIZABLE CLASSES

(Presented by Academician A. I. Mal'cev, 10 X 1960)

The structural characteristics of classes from \(UC_\Delta\) (for notation and terminology see \((^1)\)), obtained by A. Tarski \((^1)\) and J. Łoś \((^2)\), were generalized by C. Chang \((^3)\) to classes from \(UEC_\Delta\). Developing Chang’s method, A. D. Taimanov obtained characteristics of classes from \(EC_\Delta\), \(EUC_\Delta\), \(UEUC_\Delta,\ldots\), and \(AC_\Delta\) (see also \((^4)\)). In doing so, Taimanov generalized certain important theorems on axiomatizable classes, in particular the Łoś–Suszko theorem \((^5)\) and Chang’s theorem \((^3)\) on unions of chains of models.

In the present note the method, used by the authors cited above, for obtaining structural characteristics of axiomatizable classes is generalized, which makes it possible to make these characteristics more transparent and to obtain a series of new characteristics.

In § \(1^\circ\) a known set-theoretic scheme is considered; the essence of our method, described in § \(2^\circ\), consists in using this scheme.

\(1^\circ\). Let \(V\) be a nonempty class. An operation assigning to each of its subclasses \(K\) a certain subclass \(\overline K\) is called a closure operation if it satisfies the following conditions: 1) \(K \subset \overline K\), 2) \(\overline{\overline K}=\overline K\); 3) from \(K_1\subset K_2\) it follows that \(\overline{K_1}\subset \overline{K_2}\); 4) all classes \(K\) such that \(K=\overline K\) form a set. The concept of a closure operation is equivalent to the concept of an \(O\)-closure operation defined below.

Let \(O\) be some set of subclasses of \(V\). An element \(a\) of \(V\) is called a point of contact of the class \(K\) with respect to \(O\) if in \(O\) there are no classes containing \(a\) and disjoint from \(K\). A class is called \(O\)-closed if it contains all of its points of contact with respect to \(O\). The \(O\)-closed classes form a set closed under intersections and containing \(V\). Therefore, for every class \(K\subset V\) there exists a least \(O\)-closed class containing it. The latter will be called the \(O\)-closure of \(K\). The operation assigning to each \(K\subset V\) its \(O\)-closure is called the \(O\)-closure operation.

By \(P(a)\), where \(a\in V\) and \(P\) is a set of subclasses of \(V\), we shall denote the set of all classes from \(P\) that contain \(a\). The set \(P\) is called inscribed in \(O\), in notation \(P\preccurlyeq O\), if for every \(a\in V\) the following holds: 1) for every \(K\in O(a)\) there exists an \(L\in P(a)\) such that \(L\subset K\); 2) for every \(L\in P(a)\) there exists a \(K\in O(a)\) such that \(L\subset K\). If \(P\preccurlyeq O\), then every \(O\)-closed class is \(P\)-closed. If \(P\) is a subset of \(O\), then every \(P\)-closed class is \(O\)-closed. Thus, if \(P\preccurlyeq O\) and \(P\subset O\), then the operations of \(O\)-closure and \(P\)-closure coincide.

Remark 1. The last proposition is equivalent to the following: an element \(a\) is a point of contact of the class \(K\) with respect to \(O\) if and only if \(a\) is a point of contact of \(K\) with respect to some set \(R\subset O(a)\) inscribed in \(O(a)\).

Let \(O_W\) be the trace on \(W \subset V\) of the set \(O\). Then the closure operation for subclasses of \(W\), induced by the \(O\)-closure operation, coincides with the \(O_W\)-closure operation. This implies the validity of Remark 2.

Remark 2. If \(P \leq O\) and \(P \subset O\), then the operations of \(O_W\)-closure and \(P_W\)-closure on \(W\) (where \(O_W\) and \(P_W\) are the traces of \(O\) and \(P\) on \(W\)) coincide.

A class \(K\) is called finitely \(O\)-closed if it is \(O'\)-closed, where \(O'\) is some finite subset of \(O\).

Remark 3. Let \(P\) be a subset of \(O\), inscribed in \(O\), such that every finitely \(O\)-closed class is finitely \(P\)-closed. Then finite \(O\)-closedness of a class and finite \(P\)-closedness coincide.

\(2^\circ\). We now explain the essence of our method on the example of classes from \(UEC_\Delta\). It is assumed that the models under consideration have some finite type.

A class of models belongs to \(UEC_\Delta\) if and only if it is \(EUC\)-closed, i.e., if all its contact points with respect to \(EUC\) belong to it. Remark 1 shows that we shall obtain a structural characterization of classes from \(UEC_\Delta\) as soon as we find a subset \(EUC^*\) of the set \(EUC\), inscribed in \(EUC\), such that the conditions for a model to belong to classes from \(EUC^*\) are structurally expressible. To each such subset \(EUC^*\) there will correspond its own characterization of classes from \(UEC_\Delta\). Below several series of such subsets are singled out. Every axiom in prenex form

\[ (\exists x_1)\ldots(\exists x_m)(y_1)\ldots(y_n)[\alpha(x_1,\ldots,y_n)] \]

is equivalent to some axiom

\[ (\exists x_1)\ldots(\exists x_m)(y_1)\ldots(y_n)[D_1(x_1,\ldots,y_n)\vee\ldots \]
\[ \ldots\vee D_p(x_1,\ldots,y_n)], \tag{I} \]

where \(D_i(x_1,\ldots,y_n)\) is the diagram of some model defined on \(\{x_1,\ldots,y_n\}\). Axiom (I) is called \(\mathfrak M\)-complete, where \(\mathfrak M\) is some model, if in \(\mathfrak M\) there exist elements \(x_1^0,\ldots,x_m^0\) such that

\[ (y_1)\ldots(y_n)[D_1(x_1^0,\ldots,x_m^0,y_1,\ldots,y_n)\vee\ldots \]
\[ \ldots\vee D_p(x_1^0,\ldots,y_n)], \tag{II} \]

\[ \{(\exists y_1)\ldots(\exists y_n)[D_i(x_1^0,\ldots,x_m^0,y_1,\ldots,y_n)]\},\quad i=1,\ldots,p. \tag{III} \]

To every tuple \(x_1^0,\ldots,x_m^0\) of elements of \(\mathfrak M\) and to every natural number \(n\) there corresponds some \(\mathfrak M\)-complete axiom (I) such that \(x_1^0,\ldots,x_m^0\) satisfy (II) and (III).

Following Chang \((^3)\), we shall call a model \(\mathfrak N\) an \(n\)-covering of \(\mathfrak M\) relative to the submodel \(\mathfrak M'\), if there is an isomorphism \(f\) of \(\mathfrak M'\) into \(\mathfrak N\) such that every submodel \(\mathfrak N'\) of the model \(\mathfrak N\) containing \(f(\mathfrak M')\) and such that \(\mathfrak N'\setminus f(\mathfrak M')\) has at most \(n\) elements is embeddable in \(\mathfrak M\) by an isomorphism that coincides with \(f^{-1}\) on \(f(\mathfrak M')\). If, moreover, every submodel \(\mathfrak M''\) of the model \(\mathfrak M\) containing \(\mathfrak M'\) and such that \(\mathfrak M''\setminus\mathfrak M'\) has at most \(n\) elements is embeddable in \(\mathfrak N\) by an isomorphism that coincides with \(f\) on \(\mathfrak M'\), then \(\mathfrak N\) will be called a strong \(n\)-covering of \(\mathfrak M\) relative to \(\mathfrak M'\).

A model \(\mathfrak N\) satisfies an \(\mathfrak M\)-complete axiom (I) if and only if it is an \(n\)-covering of \(\mathfrak M\) relative to the submodel with elements \(x_1^0,\ldots,x_m^0\) satisfying (II) and (III).

Since the set \(EUC'(\mathfrak M)\) of classes defined by \(\mathfrak M\)-complete axioms is an inscribed subset of \(EUC(\mathfrak M)\), it follows, according to Remark 1, that \(\mathfrak M\) is a contact point of the class \(K\) with respect to \(EUC\) if

$\mathfrak M$ is a point of contact of $K$ with respect to $EUC'(\mathfrak M)$. The latter is equivalent to the fact that for every finite submodel $\mathfrak M'$ of the model $\mathfrak M$ and every natural $n$ there exists in $K$ an $n$-covering of $\mathfrak M$ relative to $\mathfrak M'$.

Hence it follows:

Theorem 1 (see (3)). $K \in UEC_\Delta$ is equivalent to the following: if for every natural $n$ and every finite submodel $\mathfrak M'$ of the model $\mathfrak M$ there exists in $K$ an $n$-covering of $\mathfrak M$ relative to $\mathfrak M'$, then $\mathfrak M \in K$.

To every tuple $x^0_1,\ldots,x^0_m$ of elements of the model $\mathfrak M$ and every natural $n$ there corresponds some axiom of the form

\[ (\exists x_1)\ldots(\exists x_m)\{(y_1)\ldots(y_n)[D_1(x_1,\ldots,y_n)\vee\ldots\vee D_p(x'_1,\ldots,y_n)]\wedge \]
\[ \wedge(\exists z_1)\ldots(\exists z_n)[D_1(x_1,\ldots,x_m,z_1,\ldots,z_n)]\wedge\ldots \]
\[ \ldots\wedge(\exists u_1)\ldots(\exists u_n)[D_p(x_1,\ldots,u_n)]\}, \tag{IV} \]

which is satisfied in $\mathfrak M$ when $x^0_1$ is substituted for $x_1,\ldots,x^0_m$ for $x_m$. It is not hard to see that, if the models $\mathfrak M$ and $\mathfrak N$ satisfy the axiom (IV), then $\mathfrak N$ is a strong $n$-covering of $\mathfrak M$ relative to some $m$-element submodel.

Since the set $EUC''$ of classes defined by axioms of the form (IV) is an inscribed subset of $EUC$, the model $\mathfrak M$ is a point of contact of the class $K$ with respect to $EUC$, if it is a point of contact of $K$ with respect to $EUC''(\mathfrak M)$. The latter is equivalent to the fact that for every finite submodel $\mathfrak M'$ of the model $\mathfrak M$ and for every natural $n$ there exists in $K$ a strong $n$-covering of $\mathfrak M$ relative to $\mathfrak M'$. Thus, the following holds:

Theorem 2. $K \in UEC_\Delta$ is equivalent to the following: if for every natural $n$ and every finite submodel $\mathfrak M'$ of the model $\mathfrak M$ there exists in $K$ a strong $n$-covering of $\mathfrak M$ relative to $\mathfrak M'$, then $\mathfrak M \in K$.

Axiom (I) is called strongly $\mathfrak M$-complete if, for every tuple $x^0_1,\ldots,x^0_m$ of elements of $\mathfrak M$ satisfying (II), (III) is satisfied.

We shall say that a submodel $\mathfrak M''$ of the model $\mathfrak M$ is an $n$-dense submodel of $\mathfrak M'$ if every $n$-covering of $\mathfrak M$ relative to $\mathfrak M''$ is an $n$-covering of $\mathfrak M$ relative to $\mathfrak M'$. We shall call $\mathfrak M''$ an $n$-kernel of $\mathfrak M$ if $\mathfrak M''$ is $n$-dense in every submodel that is $n$-dense in $\mathfrak M''$. If a tuple $x^0_1,\ldots,x^0_m$ of elements of $\mathfrak M$ satisfies (II), where (I) is a strongly $\mathfrak M$-complete axiom, then the submodel with support set $\{x^0_1,\ldots,x^0_m\}$ is an $n$-kernel of $\mathfrak M$.

From the preceding arguments and from the fact that the set $EUC'''(\mathfrak M)$ of classes defined by strongly $\mathfrak M$-complete axioms is inscribed in $EUC(\mathfrak M)$ and is a subset of the latter, it follows:

Theorem 3. $K \in UEC_\Delta$ is equivalent to the following: if for every natural $n$ and every finite $n$-kernel $\mathfrak M'$ of the model $\mathfrak M$ there exists in $K$ an $n$-covering of $\mathfrak M$ relative to $\mathfrak M'$, then $\mathfrak M \in K$.

Let $EUC^{IV}(\mathfrak M)$ be the set of all possible classes, each of which is defined by some axiom of the form (IV), where

\[ (\exists x_1)\ldots(\exists x_m)(y_1)\ldots(y_n)[D_1(x_1,\ldots,y_n)\vee\ldots\vee D_p(x_1,\ldots,y_n)] \]

is a strongly $\mathfrak M$-complete axiom. From the preceding arguments and from the fact that $EUC^{IV}(\mathfrak M)$ is an inscribed subset of $EUC(\mathfrak M)$, it follows:

Theorem 4. $K \in UEC_\Delta$ is equivalent to the following: if for every natural $n$ and every finite $n$-kernel $\mathfrak M'$ of the model $\mathfrak M$ there exists in $K$ a strong $n$-covering of $\mathfrak M$ relative to $\mathfrak M'$, then $\mathfrak M \in K$.

The series of similar characteristics can be continued. In passing from $UEC_\Delta$ to $UEUC_\Delta$, $EUEC_\Delta,\ldots$, the notions of an $\mathfrak M$-complete axiom and a strongly $\mathfrak M$-complete axiom ramify more and more, and this makes possible the obtaining, for classes from these sets, by the uniform method described above, of ever larger series of structural characteristics, and for classes from $AC_\Delta$, an infinite series.

From Theorem 1 and Remark 2 it follows immediately:

Theorem 5. Let \(L \subset K\). Then \(L \in UEC_{\Delta}(K)\) is equivalent to the following: if for every natural number \(n\) and every finite submodel \(\mathfrak M'\) of a model \(\mathfrak M \in K\) there exists an \(n\)-covering of \(\mathfrak M\) relative to \(\mathfrak M'\) in \(L\), then \(\mathfrak M \in L\).

Using Theorems 2, 3, and 4, one can obtain other characterizations of classes in \(UEC_{\Delta}(K)\).

From the fact that \(EUC^{I}\) is an inscribed subset of \(EUC\), it follows easily that every finitely \(EUC\)-closed class is finitely \(EUC^{I}\)-closed. The finite \(EUC^{I}\)-closedness of a class \(K\) is equivalent to the existence of such natural numbers \(m\) and \(n\) that, if for every \(p \le n\) and every model \(\mathfrak M' \in S_m(\mathfrak M)\) in \(K\) there exists a \(p\)-covering of \(\mathfrak M\) relative to \(\mathfrak M'\), then \(\mathfrak M \in K\).* Using the sets \(EUC^{II}\), \(EUC^{III}\), and \(EUC^{IV}\), one can obtain other characterizations of classes in \(UEC\). In particular, the following holds:

Theorem 6. \(K \in UEC\) is equivalent to the following: there exist natural numbers \(m\) and \(n\) such that, if for every \(p \le n\) and every \(p\)-kernel \(\mathfrak M'\) of a model \(\mathfrak M\) belonging to \(S_m(\mathfrak M)\) in \(K\), there exists a strong \(p\)-covering of \(\mathfrak M\) relative to \(\mathfrak M'\), then \(\mathfrak M \in K\).

By \(\mathfrak M_R\) we shall denote a model that is an \(R\)-reduction of the model \(\mathfrak M\) (in the sense of (1)). By \(K_R\) we shall denote the class of \(R\)-reductions of the models of the class \(K\).

Theorem 7 (cf. (1)). Let \(K\) be a class of models of arbitrary type. \(K \in UEC_{\Delta}\) is equivalent to the following: if for every finite set \(R\) of basic predicates, every natural number \(n\), and every finite submodel \(\mathfrak M'\) of a model \(\mathfrak M\) in \(K_R\) there is an \(n\)-covering of \(\mathfrak M_R\) relative to \(\mathfrak M'_R\), then \(\mathfrak M \in K\).

Using the sets \(EUC^{II}\), \(EUC^{III}\), and \(EUC^{IV}\), one can obtain other characterizations of classes in \(UEC_{\Delta}\).

Saratov Automobile and Highway Institute

Received
1 X 1960

REFERENCES

\(^{1}\) A. Tarski, Proc. Koninkl. Nederl. Acad. Wetensch., A57, No. 5 (1954).
\(^{2}\) J. Łoś, Fund. Math., 42, No. 1 (1955).
\(^{3}\) C. C. Chang, Proc. Am. Math. Soc., 10, No. 1 (1959).
\(^{4}\) J. Mycielski, J. Bull. Acad. Polon. Sci., Cl. 3, 5, No. 11 (1957).
\(^{5}\) J. Łoś, R. Suszko, Fund. Math., 44, No. 1 (1957).

* This result was obtained by A. D. Taimanov.