Question

The notation ${\mathcal L}^\alpha_{\beta,\gamma}$ refers to the set of sentences of predicate calculus with less than $\alpha$ variables, conjunctions of size less than $\beta$, and quantification over families of less than $\gamma$ variables. Formally, the following are formulas of ${\mathcal L}^\alpha_{\beta,\gamma}$ in addition to the atomic formulas:

• $\neg\phi$ if $\phi\in {\mathcal L}^\alpha_{\beta,\gamma}$
• $\underset{i\in I}\bigvee \Phi_i$ if $|I|<\beta$ and $(\forall i\in I)\Phi_i\in {\mathcal L}^\alpha_{\beta,\gamma}$ and $NV(\underset{i\in I}\bigvee \Phi_i)<\alpha$
• $(\exists \{x_i\}_{i\in I})\phi$ if $|I|<\gamma$ and $\phi\in {\mathcal L}^\alpha_{\beta,\gamma}$

Where $NV(\phi)$ is the number of variables (free or bound) used anywhere in $\phi$.

Let $\lceil\gamma\rceil$ be the least limit ordinal greater than or equal to $\gamma$. Observe that ${\mathcal L}^\alpha_{\beta,\gamma}={\mathcal L}^\alpha_{\beta,\lceil\gamma\rceil}$.

So, my question is: why $\gamma$? More specifically, when is

$$ {\mathcal L}^\alpha_{\beta,\gamma}\neq {\mathcal L}^{min(\alpha,\lceil\gamma\rceil)}_{\beta,\infty} $$

I think they are the same, but if that is the case I can't see why the notation hasn't been reduced to simply ${\mathcal L}^\alpha_\beta$.

Note that there are various notions of what a "proof in ${\mathcal L}^\alpha_{\beta,\gamma}$" might mean, but I'm only interested in knowing if the notational distinction matters for contexts in which $\vdash$ means "true in all models".

Answer 1

In your terminology, ordinary first order logic would be $L_{\omega,\omega}^\omega$.

Consider the case of $L_{\omega,2}^\omega$. Here, we close the atomic formulas under finite conjunctions, negation and quantifiers over one variable. (By induction, this also gives rise to all of the assertions of first order logic, since any finite block of quantifiers can be thought of as happening one at a time.) In particular, any finite quantifier-free expression of first order logic is in this logic.

The logic $L_{\omega,\infty}^2$, in contrast, does not include any quantifier-free formulas with more than one variable.

So they are not the same.