UDC 51.01.164

MATHEMATICS

S. R. KOGALOVSKII

SOME REDUCTION THEOREMS FOR LOGIC OF HIGHER LEVELS

(Presented by Academician P. S. Novikov, 2 VI 1969)

In this note we present some reduction theorems concerning pure logic of the $\omega$-th level. We base ourselves on the set theory $ZF$ and define cardinals as initial ordinals, while every ordinal is identified with the set of all smaller ordinals.

Let us introduce the necessary concepts. The least of the sets of words in the alphabet $\{0,(,)\}$ that contains $0$ and contains together with any words $\tau_1,\ldots,\tau_n$ the word $(\tau_1\ldots\tau_n)$ will be denoted by $J$. The elements of $J$ will be called types. For every type $\tau$, by $F_\tau$ we shall denote the mapping of $J$ into itself such that $F_\tau 0=\tau$ and $F_\tau(\tau_1\ldots\tau_n)=(F_\tau\tau_1\ldots F_\tau\tau_n)$. By $\operatorname{St}$ we shall denote the mapping of $J$ into $\omega$ such that $\operatorname{St}0=0$ and $\operatorname{St}(\tau_1\ldots\tau_n)=1+\max\{\operatorname{St}\tau_1,\ldots,\operatorname{St}\tau_n\}$. For every type $\tau$ the number $\operatorname{St}\tau$ will be called the level of the type $\tau$. It is easy to see that $\operatorname{St}F_\tau\tau_1=\operatorname{St}\tau+\operatorname{St}\tau_1$ for any types $\tau$ and $\tau_1$.

Let $A$ be a nonempty set. A family $(A^\tau)_{\tau\in J}$ such that $A^0=A$ and $A^{(\tau_1\ldots\tau_n)}=P(A^{\tau_1}\times\ldots\times A^{\tau_n})$, where $P(B)$ denotes the set of all subsets of $B$, will be called the type scale of sets over $A$ and denoted by $J(A)$. The elements of $A^\tau$ $(\tau\in J)$ will be denoted by small initial Latin letters with superscript $\tau$.

The language of the $\omega$-th level contains, for each $\tau\in J$, a sequence $x_0^\tau,x_1^\tau,\ldots$ of variables of type $\tau$, the symbols of logical operators: $/$ — the Sheffer stroke, $\exists$ — the existential quantifier, and $=$ — equality. By means of these operators the operators $\neg,\wedge,\vee,\to,\leftrightarrow$ and $\forall$ are defined in the natural way. Expressions of the forms $x_m^\tau=x_n^\tau$ and $x_p^{(\tau_1\ldots\tau_r)}x_{q_1}^{\tau_1}\ldots x_{q_r}^{\tau_r}$ are called atomic formulas. Starting from the concept of an atomic formula, the concepts of a formula and of a sentence are defined in the usual way.

Let $\sigma$ be an arbitrary formula, and let $x_{i_0}^{\tau_0},\ldots,x_{i_n}^{\tau_n}$ be the list of variables occurring in it; let $A$ be some set, and let $a=\langle a_{i_0}^{\tau_0}\ldots a_{i_n}^{\tau_n}\rangle$ be a tuple of elements of the sets from $J(A)$. We say that $a$ satisfies $\sigma$ in $A$ if one of the following four cases holds:

1. $\sigma$ is the atomic formula $x_{i_k}^{\tau_k}=x_{i_l}^{\tau_l}$ $(\tau_k=\tau_l)$ and $a_{i_k}^{\tau_k}=a_{i_l}^{\tau_l}$.

2. $\sigma$ is the atomic formula $x_{i_k}^{\tau_k}x_{i_l}^{\tau_l}\ldots x_{i_m}^{\tau_m}$ $(\tau_k=(\tau_l\ldots\tau_m))$ and $\langle a_{i_l}^{\tau_l}\ldots a_{i_m}^{\tau_m}\rangle\in a_{i_k}^{\tau_k}$.

3. $\sigma$ is the formula $\pi/\rho$ and $a$ does not satisfy $\pi$ or $a$ does not satisfy $\rho$.

4. $\sigma$ is the formula $(\exists x_{i_k}^{\tau_k})(\pi)$ and there exists $b^{\tau_k}\in A^{\tau_k}$ such that $a(a_{i_k}^{\tau_k}/b^{\tau_k})$ satisfies $\pi$ in $A$ (where $a(a_{i_k}^{\tau_k}/b^{\tau_k})$ is the tuple obtained from $a$ by replacing $a_{i_k}^{\tau_k}$ by $b^{\tau_k}$).

If every $a$ satisfies $\sigma$ in $A$, then we say that $\sigma$ is true in $A$, or that $A$ satisfies $\sigma$.

Formulas are called equivalent if they are true on the same sets, and $\infty$-equivalent if they are true on the same infinite sets.

For every formula \(\sigma\), by \(C(\sigma)\) we shall denote the class of all cardinals satisfying \(\sigma\). This class is called the spectrum of \(\sigma\).

Let \(\tau\) be some type. By \(F_\tau\sigma\) we shall denote the formula obtained from \(\sigma\) by replacing each variable \(x_n^\tau\) by \(x_n^{F\tau}\). The following is easily proved.

Lemma. Let \(A\) be an infinite set. Then, for every formula \(\sigma\), the truth of \(F_{(0)}\sigma\) on \(A\) is equivalent to the truth of \(\sigma\) on \(P(A)\). And, in general, for every \(\tau\), the truth of \(F_\tau\sigma\) on \(A\) is equivalent to the truth of \(\sigma\) on \(P^{\operatorname{St}\tau}(A)\), where \(P^1(A)=P(A)\) and \(P^{n+1}(A)=P(P^n(A))\).

The degree of a formula will mean the highest of the degrees of the types of the variables occurring in it, increased by one.

A formula in prenex form will be called regular if it contains no quantifier over a variable of higher degree following a quantifier over a variable of lower degree. By \(\bigvee_n^i\) (\(\bigwedge_n^i\)) we shall denote the set of all regular formulas of degree \((i+1)\) beginning with an existential (universal) quantifier and having \(n-1\) alternations of quantifiers.

No. 1. We shall say that a class of cardinals \(C\) is defined by a formula \(\sigma\) if \(C=C(\sigma)\). If, moreover, \(\sigma\in\bigvee_n^i\) (\(\sigma\in\bigwedge_n^i\)), then \(C\) will be called a \(\bigvee_n^i\)-class (a \(\bigwedge_n^i\)-class). \(C\) is called a \(\Delta_n^i\)-class if \(C\) is simultaneously a \(\bigvee_n^i\)- and a \(\bigwedge_n^i\)-class. \(C\) is called a definable class if \(C=C(\sigma)\) for some formula \(\sigma\).

We shall say that a cardinal \(\mathfrak n\) is defined by a formula \(\sigma\) if \(\{\mathfrak n\}=C(\sigma)\). The notions of a \(\bigvee_n^i\)-, \(\bigwedge_n^i\)-, and \(\Delta_n^i\)-cardinal and the notion of a definable cardinal are defined analogously. By \(\mathfrak C(\bigvee_n^i)\) we shall denote the set of all \(\bigvee_n^i\)-cardinals. The symbols \(\mathfrak C(\bigwedge_n^i)\) and \(\mathfrak C(\Delta_n^i)\) will have the analogous meaning.

It follows from the lemma that \(C\) is a class of cardinals definable by a formula of degree \((n+1)\) if and only if \(\{2^{\mathfrak n}:\mathfrak n\in C\}\) is a class definable by a formula of degree \(n\) (\(n\ge 2\)). Hence it is clear that the study of definable classes reduces to the study of classes definable by formulas of degree 2. As is known, \(\mathfrak C(\bigvee_1^1)=\mathfrak C(\bigwedge_1^1)=\omega\). From Zykov’s results \((^1)\) it follows that, for every class \(C\) definable by a formula of degree 2, the class \(\{2^{\mathfrak n}:\mathfrak n\in C\}\) is a \(\bigvee_2^1\)-class. Hence it follows (see \((^2)\), p. 97) that \(\mathfrak C(\bigvee_2^1)\) is cofinal in the set \(D\) of all definable cardinals. This circumstance motivates interest in the study of \(\mathfrak C(\bigwedge_2^1)\) and \(\mathfrak C(\Delta_2^1)\). Some results in this direction were announced by Garland \((^3)\), who conjectured that in \(ZF\) the cofinality of \(\mathfrak C(\Delta_2^1)\) and \(D\) is unprovable.

In \((^3)\) the following questions were posed:

1. Does \(\aleph_\alpha\in\mathfrak C(\Delta_2^1)\) follow from \(\aleph_{\alpha+1}\in\mathfrak C(\Delta_2^1)\)?
2. Is it true that \(2^{\aleph_0}\in\mathfrak C(\Delta_2^1)\) is unprovable in \(ZF\)?

From the following theorem (reported by the author at the Ninth All-Union Algebraic Colloquium) it is not difficult to derive that the answers to both questions are negative and that \(\mathfrak C(\Delta_2^1)\) (and hence also \(\mathfrak C(\bigwedge_2^1)\)) is cofinal in \(D\).

Theorem 1. For every formula \(\sigma\) of degree 2 one can effectively construct a formula \(\sigma^*\) from \(\bigwedge_2^1\) such that, for every infinite set \(A\), the truth of \(\sigma\) on \(A\) is equivalent to the truth of \(\sigma^*\) on \(P(A)\).

Hence, and from Zykov’s theorem \((^1)\), it follows:

Theorem 2. For every class of cardinals \(C\) definable by a formula of degree 2, \(\{2^{\mathfrak n}:\mathfrak n\in C\wedge \mathfrak n\ge\omega\}\) is a \(\Delta_2^1\)-class.

No. 2. Let \(J_0\) be the smallest of the subsets \(J\) containing \(0\) and containing, together with every type \(\tau\), also the type \((\tau)\). Types from \(J_0\) will be called monadic types. A formula will be called monadic if the types of the variables occurring in it are monadic. Using the fact that, for every set \(A\), the mapping of the set

\[ \underbrace{A\times\cdots\times A}_{n} \]

into \(P(P(A))\) such that

\[ f(\langle a_1a_2\ldots a_n\rangle)=\{\{a_1\},\{a_1,a_2\},\ldots,\{a_1,a_2,\ldots,a_n\}\}, \]

is one-to-one—

but it is not hard to establish that every formula of the 2nd order is equivalent to a suitable monadic formula of the 4th order, and, in general, every formula of the \(m\)-th order is equivalent to a monadic formula of the \((m+2)\)-nd order. In \((4)\) the following result was announced: for every formula of the 2nd order such that the types of the variables occurring in it belong to \(\{0,(00)\}\), one can effectively construct an equivalent monadic formula of the 3rd order. This result is generalized as follows: for every formula from \(\bigvee n^1(\bigwedge n^1)\) one can effectively construct an equivalent monadic formula from \(\bigvee n^2(\bigwedge n^2)\). Using this result and the lemma, it is easy to prove the following theorem.

Theorem 3. For every formula from \(\bigvee n^i(\bigwedge n^i)\) one can effectively construct an equivalent monadic formula from \(\bigvee n^{i+1}(\bigwedge n^{i+1})\). \((n,i<\omega)\).

From Behmann’s results \((5)\) it follows that not for every formula is there an equivalent monadic formula of the same order. At the same time, for every formula \(\sigma\) of the 3rd order one can effectively construct an \(\infty\)-equivalent monadic formula of the 3rd order. Indeed, let \(A\) be an arbitrary infinite set. One can effectively construct a formula \(\sigma^*\) of the 2nd order such that: 1) the types of the variables occurring in it belong to \(\{0,(00)\}\), and 2) the truth of \(\sigma\) on \(A\) is equivalent to the truth of \(\sigma^*\) on \(P(A)\). The formula \(F_{(0)}\sigma^*\) of the 3rd order is equivalent to \(\sigma\). We shall show that \(F_{(0)}\sigma^*\) is equivalent on \(A\) to a suitable monadic formula of the 3rd order.

Let \(E\) be the class of elementary structures \(\langle M,\varepsilon\rangle\), where \(\varepsilon\) is a binary relation defined by the conditions:

\[ \begin{aligned} E_1:\quad &(\forall x^0)(\forall y^0)((\forall z^0)(\varepsilon z^0x^0\leftrightarrow \varepsilon z^0y^0)\to x^0=y^0);\\ E_2:\quad &(\forall x^0)(\forall y^0)(\exists z^0)(\forall u^0)(\varepsilon u^0z^0\leftrightarrow u^0=x^0\vee u^0=y^0);\\ E_3:\quad &(\exists x^0)(\exists y^0)(\neg x^0=y^0);\\ E_4:\quad &(\exists x^0)(\varphi(x^0)), \end{aligned} \]

where \(\varphi(x^0)\) is the formula
\[ \varepsilon x^0x^0\wedge(\forall y^0)(\varepsilon y^0y^0\to y^0=x^0). \]
The unique \(x^0\) in an \(E\)-structure for which \(\varphi(x^0)\) is true will be denoted by \(0\).

By definition, \(z^0=\{x^0,y^0\}\) is equivalent to
\[ (\forall u^0)(\varepsilon u^0z^0\leftrightarrow u^0=x^0\vee u^0=y^0), \]
\[ \{x^0\}=\{x^0,x^0\}, \]
\[ \langle x^0y^0\rangle=\{\{x^0\},\{x^0,y^0\}\}, \]
\[ \langle x_1^0x_2^0\ldots x_n^0\rangle=\langle x_1^0\langle x_2^0\ldots x_n^0\rangle\rangle. \]

It is not hard to verify that
\[ \langle x_1^0\ldots x_n^0\rangle=\langle y_1^0\ldots y_n^0\rangle \leftrightarrow x_1^0=y_1^0\wedge\cdots\wedge x_n^0=y_n^0. \tag{*} \]

Hence it follows that every structure in \(E\) is equipotent to each of its finite Cartesian powers, and since, by virtue of \(E_3\), it has more than one element, it is infinite. It is obvious that \(E\) is a nonempty class. Consequently, by the Löwenheim—Skolem theorem and the compactness theorem, on every infinite set one can define a structure from \(E\). Let \(\mathfrak A=\langle A,\varepsilon\rangle\) be some \(E\)-structure defined on \(A\). From \(E_4\) and the noted properties of the class \(E\) it follows that the mapping \(\langle ab\rangle\to\langle\!\langle ab\rangle\!\rangle\) of the Cartesian square of the set \(B=A\setminus\{0\}\) into \(B\) is one-to-one. Denote by \(F\) the mapping \(B^{((0)(0))}\) into \(A^{(((00)))}\), defined as follows:

\[ F(\langle a^{(0)}b^{(0)}\rangle)= \begin{cases} a^{(0)}\times b^{(0)}, & \text{if } a^{(0)} \text{ and } b^{(0)} \text{ are nonempty},\\ \{0\}\times b^{(0)}, & \text{if } a^{(0)} \text{ is empty and } b^{(0)} \text{ is nonempty},\\ a^0\times \{0\}, & \text{if } a^{(0)} \text{ is nonempty and } b^{(0)} \text{ is empty},\\ \{0\}\times\{0\}, & \text{if } a^{(0)} \text{ and } b^{(0)} \text{ are empty}. \end{cases} \]

$F$ is one-to-one and $a^{(00)} \in A^{(00)}$ is then, and only then, the $F$-image of some element of the set $B^{((0)(0))}$, when the following conditions are satisfied:

1. $a^{(00)}x^{0}y^{0} \land a^{(00)}z^{0}u^{0} \to a^{(00)}x^{0}u^{0} \land a^{(00)}z^{0}y^{0}$.
2. $a^{(00)}0u^{0} \land a^{(00)}x^{0}y^{0} \to x^{0}=0$.
3. $a^{(00)}x^{0}0 \land a^{(00)}x^{0}y^{0} \to y^{0}=0$.

We denote the conjunction of these conditions by $\chi(a^{(00)})$.

Let us denote by $\bar{\sigma}$ the formula formed from $F_{(0)}\sigma^{*}$ as follows:

1) each variable of type $((0)(0))$ is replaced (one-to-one) by a variable of type $((00))$; 2) each atomic formula
$x^{(0)(0)}x_{1}^{(0)}x_{2}^{(0)}$
is replaced by
\[ (\forall x^{(00)})\bigl(\psi(x^{(00)},x_{1}^{(0)},x_{2}^{(0)}) \to x^{((00))}x^{(00)}\bigr), \]
where $x^{((00))}$ is the variable by which, in accordance with item 1, $x^{((0)(0))}$ is replaced, and $\psi$ is the conjunction of the formulas:

1. $\chi(x^{(00)})$.
2. $x^{(00)}0x^{0} \to (\forall x^{0})(\neg x_{1}^{(0)}x^{0})$.
3. $x^{(00)}x^{0}0 \to (\forall x^{0})(\neg x_{2}^{(0)}x^{0})$.
4. $(\exists x^{0})(x_{1}^{(0)}x^{0}) \land x^{(00)}x^{0}y^{0} \to x_{1}^{(0)}x^{0}$.
5. $(\exists y^{0})(x_{2}^{(0)}y^{0}) \land x^{(00)}x^{0}y^{0} \to x_{2}^{(0)}y^{0}$.

These formulas express that $x^{(00)}$ is the Cartesian product of the sets $y_{1}^{(0)}$ and $y_{2}^{(0)}$ such that $y_{i}^{(0)}=x_{i}^{(0)}$ if $x_{i}^{(0)}$ is nonempty, and $y_{i}^{(0)}=\{0\}$ otherwise $(i=1,2)$. In other words, $\psi(x^{(00)},x_{1}^{(0)},x_{2}^{(0)})$ expresses that
\[ x^{(00)}=F(\langle x_{1}^{(0)}x_{2}^{(0)}\rangle). \]

By induction on the number of logical operators it is easily proved that $\bar{\sigma}$ is equivalent to $F_{(0)}\sigma^{*}$, and hence also $\sigma$, on $\mathfrak A$. Thus, every formula of the 3rd level is equivalent relative to the class $E$ to a formula $\bar{\sigma}$ of the 3rd level such that the types of the variables entering it belong to the set
\[ \{0,(0),(00),((00))\}. \]
Using property $(*)$ of the class $E$, the formula $\bar{\sigma}$ can be transformed into a formula of the 3rd level equivalent to it relative to $E$ such that the types of the variables entering it are monadic. Hence it follows that $\sigma$ is $\infty$-equivalent relative to $E$ to a formula of the 3rd level of the language corresponding to $E$ such that the types of the variables entering it belong to the set
\[ \{0,(0),(00),((0))\}. \]

Using the linear-order relation on $A$, every predicate, and in particular a binary one, can be reduced to a suitable $a^{((0))}$. Since the linear-order relation is mutually definable with the set of initial segments, it follows easily from this that the obtained formula is reducible to a monadic one. From the proof of the lemma given (in outline) one can derive

Theorem 4. For every formula from $\bigvee_{n}^{i}(\bigwedge_{n}^{i})$, where $i>1$, one can effectively construct an $\infty$-equivalent monadic formula from $\bigvee_{n}^{i}(\bigwedge_{n}^{i})$ such that the types of the variables entering it belong to
\[ \{\tau,(\tau),((\tau))\}, \]
where $\tau$ is a monadic type of the $(i-2)$-nd level.

Let $0,\tau_{1},\ldots,\tau_{n+1}$ be a sequence of types of levels respectively $0,1,\ldots,n+1$. It is called premonadic if $\tau_{k+1}=(\tau_{k})$ for every $k<n+1$. A formula is called premonadic if the types of the variables entering it form a premonadic sequence. The following theorem is proved without the axiom of choice.

Theorem 5. For every formula from $\bigvee_{n}^{i}(\bigwedge_{n}^{i})$ one can effectively construct an equivalent premonadic formula from $\bigvee_{n}^{i}(\bigwedge_{n}^{i})$ $(n,i<\omega)$.

Ivanovo Textile Institute
named after M. V. Frunze

Received
29 V 1969

References

1. A. A. Zykov, Izv. AN SSSR, ser. matem., 17, No. 1, 63 (1953).
2. S. R. Kogalovskii, Izv. vyssh. uchebn. zaved., Matematika, No. 1 (50), 89 (1966).
3. St. I. Garland, J. Symbolic Logic, 32, No. 4, 437 (1967).
4. D. Kaplan, R. Montague, Logic, Methodology and Philosophy of Science, Amsterdam, 1965, p. 101—111.
5. H. Behman, Math. Ann., 86, 163 (1922).