# Abstract We investigate the logic L(aa) which allows the second-order quantifier “aa s” meaning “for almost all countable sets s.” We prove Completeness, Compactness, and Omitting Types Theorems and develop a Gentzen-style proof theory for this logic, as well as for the infinitary version L_A(aa). Relations with various sublogics like L(Q) are discussed. # 1. Introduction Recall the notions of [[Club sets and stationary sets#Club and stationary subsets of $P_{ omega_{1}}(X)$|club and stationary]] subsets of $P_{\omega_{1}}(M)$. Basic definitions of [[Stationary logic]]. ## Examples of expressive power: - " $\varphi(\cdot)$ is countable": $\mathtt{aa}s\forall y(\varphi(y) \rightarrow s(y))$. - $E$ is an equivalence relation with countably many classes: $\mathtt{aa}s \forall y \exists z(s(z)\land E(y,z))$ **Remark.** This is Keisler's counterexample for interpolation in $\mathcal{L}(Q_{1})$. - A linear order $\varphi(\cdot, \cdot)$ is $\aleph_1$-like: $\forall x \mathtt{aa} s\forall y(\varphi(y, x) \rightarrow s(y))$. This can also be expressed in $L(Q_{1})$, but the following cannot: - There is a $\sup$-preserving mapping from $\langle \omega_{1},< \rangle$ to $\varphi(\cdot,\cdot)$: $\mathtt{aa}s \exists x \forall y (s(y)\to y<x)$. - If $s$ occures positively in $\varphi(s)$, then $\exists s \varphi\leftrightarrow \mathtt{aa} s \varphi$, so $\mathcal{L}(\mathtt{aa})$ contains $L^{\mathrm{pos}}$ (see [[L-pos]]) - Eklof: Let $T$ be a torsion (abelian) group and let $J$ be torsion free. If $J$ is countable, then Baer's Theorem gives a necessary and sufficient condition that $\operatorname{Ext}(J, T)=0$, a condition that can be expressed in $\mathrm{L}_{\omega_{1}, \omega}$. If we assume $\mathrm{V}=\mathrm{L}$ then Eklof [8] proves that for $|\mathrm{J}| \leq \aleph_1$, $\operatorname{Ext}(J, T)=0$ iff $ \begin{aligned} & \mathtt{aa} s\operatorname{Ext}(s, T)=0, \\ & \mathtt{aa} s \mathtt{aa} s'\left(s' \supseteq s \rightarrow \operatorname{Ext}\left(s^{\prime} / s, T\right)=0\right), \end{aligned} $ so that, for $|J| \leqslant \aleph_1, \operatorname{Ext}(J, T)=0$ is expressible in $\mathrm{L}_{\omega_{1},\omega}(\mathtt{aa})$. On the other hand, Eklof shows, again assuming $\mathrm{V}=\mathrm{L}$, that this is not expressible in $\mathrm{L}_{\infty,\omega_{1}}$. ## Axioms $(A 0) \quad \mathtt{aa}s \varphi(s) \leftrightarrow \mathtt{aa}t \varphi(t)$ $(A 1) \quad \neg \mathtt{aa}s(\perp)$ $(A 2) \quad \mathtt{aa}s(x \in s)$, $\mathtt{aa}t(s \subseteq t)$ $(A 3) \quad(\mathtt{aa}s \varphi \wedge \mathtt{aa}s \psi) \rightarrow \mathtt{aa}s(\varphi \wedge \psi)$ $(A 4) \quad \mathtt{aa}s(\varphi \rightarrow \psi) \rightarrow(\mathtt{aa}s \varphi \rightarrow \mathtt{aa}s \psi)$ $(A 5) \quad \forall x \mathtt{aa}s \varphi(x, s) \rightarrow$ $\mathtt{aa}s \forall x \in s \varphi(x, s)$. Where the rules are Modus Ponens, generalization and $\mathtt{aa}$-generalization: if $T\vdash \varphi\to \psi$ and $s$ is not free in $T\cup \{\varphi\}$ then $T\vdash \varphi\to \mathtt{aa}s\psi$. **1.4. Completeness Theorem for $\mathrm{L}(\mathtt{aa})$.** A set $T$ of sentences of $L(\mathtt{aa})$ is consistent iff $T$ has a standard model. **1.5. Compactness Theorem for $\mathrm{L}(\mathtt{aa})$.** If $T$ is a set of sentences of $\mathrm{L}(\mathtt{aa})$ and every finite subset $T_0 \subseteq T$ has a standard model then $T$ has a standard model. **1.6. Downward Löwenheim-Skolem Theorem for $\mathrm{L}(\mathtt{aa})$.** Any set $T$ of sentences of $\mathrm{L}(\mathtt{aa})$ which has a standard model has one of power at most $\aleph_1$. >[!note] Remark >In the above results the language is countable. ## Infinitary versions >[!info] Definition > A *fragment* $\mathrm{L}_{A}(\mathtt{aa})$ of $\mathrm{L}_{\omega_1 \omega}(\mathtt{aa})$ is defined to be a set of formulas of $\mathrm{L}_{\omega_1, \omega}(\mathtt{aa})$ closed under subformulas, substitutions and the finitary operations $\forall, \wedge, \neg, \mathtt{aa}$, and the following: if $\bigwedge_{i<\omega} \mathtt{aa} s \varphi_i$ is in $\mathrm{L}_A(\mathtt{aa})$ so is $\bigwedge_{i<\omega} \varphi_i$. >[!info] Definition >Let $\mathrm{L}_A(\mathtt{aa})$ be a fragment of $\mathrm{L}_{\omega_{1},\omega}(\mathtt{aa})$ and let $T$ be a set of sentences of $\mathrm{L}_A(\mathtt{aa})$. The *consequences of $T$* form the smallest set of $\mathrm{L}_A(\mathtt{aa})$ formulas containing $T$, all the usual axioms for $\mathrm{L}_{\mathrm{A}}$ (as given in Section III. 4.1 of Barwise [2], e.g.), all $\mathrm{L}_{\mathrm{A}}(\mathtt{aa})$ instances of Axioms $\mathrm{A} 0-\mathrm{A} 5$ above and Axiom $\mathrm{A} 6$ below, and closed under the usual rules of modus ponens, generalization, infinitary conjunction and the rule of aa-generalization given above. > >$(A6)\ \bigwedge_{i<\omega} \operatorname{aas} \varphi_i(s) \rightarrow \operatorname{aa} s \bigwedge_{i<\omega} \varphi_i(s)$. **1.8. Completeness Theorem for $\mathrm{L}_{\omega_{1},\omega}(\mathtt{aa})$.** Let $\mathrm{L}_{A}(\mathtt{aa})$ be a countable fragment of $\mathrm{L}_{\omega_{1},\omega}(\mathtt{aa})$ and $T$ a set of sentences of $\mathrm{L}_{A}(\mathtt{aa})$. Then $T$ is consistent iff $T$ has a standard model. # 2. Some formal consequences of the axioms and rules **2.1. Lemma.** If $\vdash \varphi(s) \rightarrow \psi(s)$ then $\vdash \mathtt{aa} s \varphi(s) \rightarrow \mathtt{aa} s \psi(s)$. **2.2. Lemma.** If $\vdash \varphi(s) \rightarrow \psi(s)$ then $\mathtt{stat} s \varphi(s) \rightarrow \mathtt{stat}s \psi(s)$. **2.3. Lemma.** If $\vdash \varphi(s) \rightarrow \eta$ where $s$ is not free in $\eta$ then $\vdash \mathtt{stat} s \varphi(s) \to \eta$ **2.4. Lemma**. If $s$ is not free in $\varphi$ then $\vdash \varphi \leftrightarrow \mathtt{aa} \varphi$. **2.6. Lemma**. $\mathtt{aa} \varphi \wedge \mathtt{stat} s \psi \rightarrow \mathtt{stat} s(\varphi \wedge \psi)$. **2.7. Lemma.** If $s$ is not free in $\varphi$ then $\vdash \varphi \wedge \mathtt{stat} s \psi \rightarrow \mathtt{stat} s(\varphi \wedge \psi)$. **2.8. Lemma.** $\mathtt{aa}\varphi(s) \rightarrow \mathtt{stat} s \varphi(s)$. **2.9. Lemma.** $\vdash \forall x \mathtt{aa} \varphi(x, s) \leftrightarrow \mathtt{aa} s \forall x \in s \varphi(x, s)$. **2.13. Lemma.** If $s_j$ does not ocur in $\varphi\left(s_i\right)$ then $ \vdash \forall x\left(s_i(x) \leftrightarrow s_j(x)\right) \rightarrow\left(\varphi\left(s_i\right) \leftrightarrow \varphi\left(s_j\right)\right) . $ # 3. Weak models and the Completeness Theorem for $\mathrm{L}(\mathtt{aa})$.