# Abstract The chief purpose of this paper is to discuss some questions about the sentences of a language with a generalized quantifier which are true in well-ordered sets. These questions were raised by L. D. Lipner in his thesis [6]. It turns out that an investigation I had earlier made of the sentences of a first order language true in all well-ordered sets can be extended in a straightforward way to cover generalized quantifiers, and so this paper begins with a discussion of the first order case. The main technique used is the game theoretic method of Ehrenfeucht [[Wihuri Application form|2]] and its extension to languages with generalized quantifiers by Lipner [6], and, independently, by Vinner [13]. The chief results are these. Let $T_\alpha$ be the set of sentences of the language with the show that $T_1$ is recursive. Then, making use of an observation of Vinner's, we show that if $\alpha, \beta>0$, then $T_\alpha=T_\beta$, and hence for all $\alpha>0, T_\alpha$ is recursive. # 1. First order axioms for well-ordered sets >[!note] Notation >$Th(On)$ is the set of all sentences true in all well-ordered sets. $\lambda,\mu,\kappa\dots$ are order types >[!info] Definition - limit point of type $n$ of $\lambda$ > - *A limit point of type 1 of $\lambda$* is a point of $\lambda$ with no immediate predecessor. > Defined by the formula $l_1(v)$ $ > (\forall u)[u<v \rightarrow(\exists t)(u<t<v)] > $ > - *A limit point of type $n+1$ of $\lambda$* is a limit point of type $n$ which is a limit point of type 1 in the ordering restricted to the limit points of type $n$. > Defined by the formula $l_{n+1}(v)$ which is the relativization of $l_1(v)$ to the formula $l_n(v)$, i.e. $ > (\forall u)[(l_{n}(u)\land u<v) \rightarrow(\exists t)(l_{n}(t)\land u<t<v)] > $ > - We let $l_n(\lambda)$ be the set of limit points of type $n$ of $\lambda$. Thus > $ > l_{n+1}(\lambda)=l_1\left(\lambda \cap l_n(\lambda)\right) . > $ >[!note] Notation > Let $\sigma^*$ be the sentence of $L$ which characterises linear orderings with a least element. That is, $\sigma^*$ is the sentence > $ > \begin{aligned} > & (\forall v) \neg(v<v) \&(\forall u)(\forall v)(u<v \vee u=v \vee v<u) \& \\ > & \quad(\forall u)(\forall v)(\forall w)(u<v \& v<w \rightarrow u<w) \&(\exists u)(\forall v) \neg(v<u) . > \end{aligned} > $ > > Let $\sigma_0$ be the conjunction of the two sentences > (i) $(\forall u)[(\exists v)(u<v) \rightarrow(\exists v)(u<v \& \neg(\exists t)(u<t<v))]$ > "every element with a successor has an immediate successor", and > (ii) $(\forall v)(\exists u)\left[u \leqq v \& l_1(u) \& \neg(\exists t)\left(u<t<v \& l_1(t)\right)\right]$ > "every element has a largest limit point of type 1 less than or equal to it". > We let $\sigma_n$ be the relativization of $\sigma_0$ to the formula $l_n(v)$, and we let $\Sigma=\left\{\sigma^*\right\} \cup\left\{\sigma_n\right.$ : $n \in \omega\}$. We show in the next section that $T h(O n)$ is precisely the set of sentences of $L$ deducible from $\Sigma$. # 2. Ehrenfeucht's game Let $\mathfrak{A,B}$ be two relational structures. >[!note] Notation >$G_{n}(\mathfrak{A,B})$ is Ehrenfeucht's $n$-move game, see [[Ehrenfeucht - An application of games to the completeness problem for formalized theories]]. >$\mathfrak{A}\sim_{n}\mathfrak{B}$ if the second player has a winning strategy in this game. >$\mathfrak{A} \equiv_n \mathfrak{B}$ if $\mathfrak{A,B}$ agree on sentences with at most $n$ variables ($\sigma\in F_n$). **Theorem 2.1. (Ehrenfeucht [2], Fraisse [3])** (i) If $\mathfrak{A} \sim_n \mathfrak{B}$ then $\mathfrak{A} \equiv_n \mathfrak{B}$. (ii) If $\mathfrak{A} \equiv \mathfrak{B}$ then for each $n, \mathfrak{A} \sim{ }_n \mathfrak{B}$ (provided that $\mathfrak{A}$ and $\mathfrak{B}$ are structures with only a finite number of relations, which is the case considered here). >[!note] Notation >If $\xi, \xi^{\prime}$ are ordinals we write *$\xi=\xi^{\prime}\left(\bmod \omega^k\right)$* if either $\xi=\xi^{\prime}$ or for some ordinals $\zeta, \zeta^{\prime}$ and $\eta$, with $\zeta, \zeta^{\prime} \neq 0, \xi=\omega^k \cdot \zeta+\eta$ and $\xi^{\prime}=\omega^k \cdot \zeta^{\prime}+\eta$. > If $\langle A,<\rangle$ is a totally ordered set by a *segment of $A$* is meant a subset $X$ of $A$ such that if $x, y \in X$ and $x<z<y$ then $z \in X$. > For all $x, y \in A$, we let > $ > [x, y)=\{a \in A: x \leqq a<y\},[x, \infty)=\{a \in A: x \leqq a\} \text { and }[0, x)=\{a \in A: a<x\} \text {. } > $ The following well-known results are easily proved using Ehrenfeucht's game (i. e. Theorem 2.1). **Theorem 2.2.** (i) $\omega+\left(\omega^*+\omega\right) \lambda \equiv \omega$, (ii) $\omega+\left(\omega^*+\omega\right) \lambda+\omega^* \sim_k n$ provided $n \geqq 2^k-1$, (iii) if for $i \in I, \lambda_i \sim_k \mu_i$ then $\sum \lambda_i \sim_k \sum \mu_i$, (iv) if $\lambda \sim_k \mu$ then $\nu \cdot \lambda \sim_k \nu \cdot \mu$, (v) if $\xi, \zeta$ are ordinals such that $\xi \equiv \zeta\left(\bmod \omega^k\right)$, then $\xi \sim_k \zeta$. **Theorem 2.6.** If $n \geqq 1$ and $\lambda \models \sigma^* \& \sigma_0 \& \ldots \& \sigma_n$, then for some ordinal $\xi<\omega^{n+1}$, $\lambda \sim{ }_{2 n} \xi$. **Corollary 2.7.** If the sentence $\sigma$ has a well ordered model then for some ordinal $\xi<\omega^\omega, \xi \models \sigma$. **Theorem 2.8.** $\sigma \in T h(O n)$ iff $\left\{\sigma_n: n \in \omega\right\} \cup\left\{\sigma^*\right\} \models \sigma$. **Theorem 2.9. (Mostowski and Tarski [8], Rabin [9])** $Th(On)$ is recursive. # 3. Generalized Quantifiers >[!note] Notation >For each ordinal $\alpha$ we let $L_\alpha$ be the language obtained from $L$ by adding the quantifier symbol $Q_\alpha$. $Q_\alpha$ is interpreted as saying "there exist at least $\aleph_\alpha$ ". >[!info] Definition (Lipner,Vinner) >Suppose $\mathfrak{A}$ and $\mathfrak{B}$ are similar structures (i.e., of the same type), $n<\omega$. We describe $G_{n}^{\alpha}(\mathfrak{A},\mathfrak{B})$ - a game consisting of $n$ turns. > In each turn Player I chooses a structure and then chooses between two types of moves. We describe the moves in case $\mathfrak{A}$ was chosen: > **$\exists$ move**: Player I chooses an element from $A$ denoted $a_{i}$. Player II then responds with an element from from $B$, $b_{i}$. > **$Q$-move**: Player I chooses a set $X\subseteq A$ of size at least $\aleph_{\alpha}$. Plays II responds with $Y\subseteq B$ of size at least $\aleph_{\alpha}$. > Then Player I chooses $b_{i}\in Y$. Player II responds with $a_{i}\in X$. > Player II wins if after $n$ turns the respectively chosen elements form a partial isomorphism. > Denote $\mathfrak{A}\sim_{n}^{\alpha}\mathfrak{B}$ if Player II has a winning strategy in this game. **Theorem 3.1.** (Lipner [6].) 1. If $\mathfrak{A} \sim{ }_n^\alpha \mathfrak{B}$ then $\mathfrak{A} \equiv{ }_n^\alpha \mathfrak{B}$. 2. If $\mathfrak{A} \equiv{ }^\alpha \mathfrak{B}$ then for each $n, \mathfrak{A} \sim_n^\alpha \mathfrak{B}$. **Theorem 3.2.** Suppose $\aleph_{\alpha}$ is regular then 1. if for $i \in I, \lambda_i \sim{ }_n^\alpha \mu_i$ then $\sum \lambda_i \sim{ }_n^\alpha \sum \mu_i$, 2. if $\lambda \sim{ }_n^\alpha \mu$ then $\nu \cdot \lambda \sim{ }_n^\alpha \nu \cdot \mu$. **Theorem 3.3.** For any $\aleph_{\alpha}$ 1. If $\lambda \sim{ }_n^\alpha \mu$ and $\lambda^{\prime} \sim{ }_n^\alpha \mu^{\prime}$ then $\lambda+\lambda^{\prime} \sim{ }_n^\alpha \mu+\mu^{\prime}$. 2. If $card(\lambda),card(\mu)<\aleph_\alpha$ , $\lambda \sim_n \mu$ and $\lambda^{\prime} \sim_n^\alpha \mu^{\prime}$ then $\lambda+\lambda^{\prime} \sim_n^\alpha \mu+\mu^{\prime}$ and $\lambda^{\prime}+\lambda \sim{ }_n^\alpha \mu^{\prime}+\mu$. >[!info] Definition (Vinner) >The game $G_n^{\alpha, \beta}(\lambda, \mu)$ is similar to $G_n^\alpha(\lambda, \mu)$ except that for $Q$-moves, when a player chooses from $\lambda$ he has to pick a set of at least $\aleph_\alpha$-elements while when he chooses from $\mu$ he has to pick a set of at least $\aleph_\beta$ elements. > We write $\lambda^\alpha \sim{ }_n^\beta \mu$ if the second player has a winning strategy in this game. >[!note] Notation >Let $T h_\alpha^n(\lambda)$ be the set of sentences of $L_\alpha$, with at most $n$ variables, true of $\lambda$. >We write $T h_\alpha^n(\lambda) \equiv T h_\beta^n(\mu)$ if $T h_\beta^n(\mu)$ can be obtained from $T h_\alpha^n(\lambda)$ by replacing each occurrence of the quantifier $Q_\alpha$ by an occurrence of $Q_\beta$. >We write $\lambda^\alpha \equiv{ }_n^\beta \mu$ if $T h_{\alpha}^n(\lambda) \equiv Th_{\beta}^n(\mu)$ and we write $\lambda^\alpha \equiv{ }^\beta \mu$ if $\lambda^\alpha \equiv{ }_n^\beta \mu$ for each $n$. **Theorem 3.4 (Vinner [13]).** 1. If $\lambda^\alpha \sim{ }_n^\beta \mu$ than $\lambda^\alpha \equiv{ }_n^\beta \mu$. 2. If $\lambda^\alpha \equiv{ }^\beta \mu$ then for each $n, \lambda^\alpha \sim{ }_n^\beta \mu$. # $\aleph_{\alpha}$-like sets >[!info] Definition >A linearly ordered set is *$\aleph_{\alpha}$-like* if it is of cardinality $\aleph_{\alpha}$ but all its initial segments are of cardinality lt;\aleph_{\alpha}$. >[!note] Notation >Let $\varrho_0$ be the sentence $\left(Q_\alpha x\right)(x=x) \&(\forall x) \neg\left(Q_\alpha y\right)(y<x)$ and for $n>0$, let $\varrho_n$ be the sentence $\left(Q_\alpha x\right) l_n(x) \&(\forall x) \neg\left(Q_\alpha y\right)(y<x)$. > $\varrho_0$ characterizeslt;\aleph_{\alpha}$-like sets and, clearly, for $n>0$, if $\lambda \models \varrho_n$, then $l_n(\lambda)$ is $\aleph_{\alpha}$-like. **Theorem 4.2.** If $\alpha>0$ and $\lambda$ is a model of $\Sigma \cup\left\{\varrho_k\right\}$ then $\lambda \sim{ }_{k+1}^\alpha \omega_\alpha$. *Proof idea.* Induction on $k$. In the step $k+1$, show how to win the first move so that we get elements $x\in\lambda,\xi\in\omega_{\alpha}$ satisfying 1. $[0,x)\sim_{k}[0,\xi)$ 2. $[x,\infty)\vDash \Sigma\cup\{\rho_{k}\}$ 3. $[\xi,\infty)\cong\omega_{\alpha}$ and then use the induction hypothesis to deduce 4. $[x,\infty)\sim_{k}^{\alpha}[\xi,\infty)$ And from 1+4 get a strategy for the rest of the game. **Corollary 4.3.** If $\alpha>0, \lambda \equiv^\alpha \omega_\alpha$ iff $\lambda$ is a model of $\Sigma \cup\left\{\varrho_n: n \in \omega\right\}$. >[!note] Notation >For any set of sentences, $\Gamma$, we let > $ > \Gamma^*=\{\sigma: \text { for all } \mathfrak{A} \text {, if } \mathfrak{A} \models \Gamma \text { then } \mathfrak{A} \models \sigma\} \text {. } > $ **Corollary 4.4.** If $\alpha>0, T h_\alpha\left(\omega_\alpha\right)=\left(\Sigma \cup\left\{\varrho_n: n \in \omega\right\}\right)^*$. **Corollary 4.5.** If $\lambda \models \Sigma \cup\left\{\varrho_k\right\}$ then $\lambda^\alpha \sim{ }_{k+1}^\beta \omega_\beta$ for $\alpha, \beta>0$. **Corollary 4.6.** For all $\alpha, \beta>0, T h_\alpha\left(\omega_\alpha\right) \equiv T h_\beta\left(\omega_\beta\right)$. **Lemma 5.2.** If $\alpha>0$ and there is a nice winning strategy for the second player in the game $G_k^\alpha(\lambda, \mu)$ then there is a winning strategy for the second player in the game $G_{k+1}^\alpha\left(\omega_\alpha \cdot \lambda, \omega_\alpha \cdot \mu\right)$ **Lemma 5.4.** If $\alpha, \beta>0$ and $\omega+\lambda^\alpha \sim{ }_k^\beta \omega+\mu$ then $\omega_\alpha(\omega+\lambda)^\alpha \sim{ }_{k+1}^\beta \omega_\beta(\omega+\mu)$. **Corollary 5.5.** For $\alpha, \beta>0$ and each $k \in \omega, \omega_\alpha^k \equiv{ }^\beta \omega_\beta^k$.