3
$\begingroup$

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

$\endgroup$
0

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$ May 18, 2010 at 19:22
  • $\begingroup$ 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! $\endgroup$
    – Adam
    May 18, 2010 at 20:17
  • $\begingroup$ 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. $\endgroup$ May 18, 2010 at 20:39
  • $\begingroup$ 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}$. $\endgroup$
    – Adam
    May 29, 2010 at 21:49
0
$\begingroup$

They are not the same when $\beta$ exceeds the cofinality of $\gamma$. In that case, we can form in $\mathcal{L}^{\infty}_{\beta,\gamma}$ a disjunction of existentials each of which binds fewer than $\gamma$ variables, but which together use $\gamma$ or more variables, even up to alpha-renaming.

For example, the sentence $$ (\exists x_0. \mathrm{true}) \vee (\exists x_0 x_1. \mathrm{true}) \vee (\exists x_0 x_1 x_2. \mathrm{true}) \vee \cdots $$ belongs to $\mathcal{L}^{\infty}_{\omega_1, \omega}$ but not to $\mathcal{L}^{\omega}_{\omega_1, \omega}$. Similar examples can be constructed for arbitrary (let's say regular) cardinals $\gamma$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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