MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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".

share|cite|improve this question

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.

share|cite|improve this answer
I see that you want to consider sentences rather than all well-formed formulas of the logic. In this case, consider $\forall x \forall y x=y$ , which is allowed in $L_{\omega,2}^\omega$, but not in $L_{\omega,\infty}^2$. – Joel David Hamkins May 18 '10 at 19:22
You are absolutely correct, but I think this mostly points to a (serious) defect in how I phrased the question. In light of my error and your very helpful answer to my other question (#25071), let me take a day or two to try to figure out how to rephrase the question to correct this problem. Thank you once again! – Adam May 18 '10 at 20:17
Sure, I'll look for a revised question from you later. I had a feeling that this wasn't the example for which you were searching. – Joel David Hamkins May 18 '10 at 20:39
Okay, I've repaired the question in two ways: first, I've accounted for your clarification on what $\alpha$ actually means (I had it wrong) and secondly I accounted for the fact that ${\mathcal L}^\alpha_{\beta,\gamma}={\mathcal L}^\alpha_{\beta,\lceil\gamma\rceil}$. – Adam May 29 '10 at 21:49

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.