Skip to main content
edited title; edited title
Link
Harry Gindi
  • 19.6k
  • 16
  • 123
  • 215

${\mathcal L}^α_ L^α_{β,γ}$: do we need both $α$α and $β$β for model theory?

x
Source Link
Adam
  • 3.3k
  • 1
  • 23
  • 30

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 (and assuming I was not mistaken), 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 $|FV(\underset{i\in I}\bigvee \Phi_i)|<\alpha$$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}$

So, my questionWhere $NV(\phi)$ is: why the number of variables $\gamma$? More specifically, if(free or bound) used anywhere in $\phi$.

Let $\lceil\gamma\rceil$ isbe 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, thenmy 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$. My reasoning goes like this:

  • The $\gamma=0$ case is obvious; you get no quantifiers.
  • All values $0<\gamma\leq\omega$ yield the same set of formulas because the set of formulas is closed under arbitrary composition (so if $\gamma=2$ you can simulate $\gamma=4$ by using nestings twice as deep)
  • If $\alpha < \gamma$ no quantifier can actually quantify over $\alpha$ or more variables (unless some don't appear, in which case you can just delete them), since any formula which did so would involve a subformula with $\alpha$ or more free variables, which would be ill-formed..
  • If $0 < \gamma < \alpha \leq \omega$ you can just nest finitely many $<\gamma$-variable quantifiers to achieve $<\alpha$-variable quantification, so increasing $\gamma$ to be equal to $\alpha$ will admit additional well-formed formulas, but each of them will be equivalent to some formula which had already been admitted.
  • If $\gamma < \alpha$ and $\omega < \alpha < \omega\cdot{2}$ then a formula with $\gamma$ or more free variables can never appear as a subformula of a closed formula (sentence) because no cardinal $<\gamma$ multiplied by a finite cardinal (nesting depth) is ever equal to a greater cardinal. So reducing $\alpha$ to equal $\gamma$ would not change the set of well-formed sentences (although I guess it might affect the set of formulas, but the sentences are what really matter, right?)

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

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 (and assuming I was not mistaken) 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 $|FV(\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}$

So, my question is: why $\gamma$? More specifically, if $\lceil\gamma\rceil$ is the least limit ordinal greater than or equal to $\gamma$, then 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$. My reasoning goes like this:

  • The $\gamma=0$ case is obvious; you get no quantifiers.
  • All values $0<\gamma\leq\omega$ yield the same set of formulas because the set of formulas is closed under arbitrary composition (so if $\gamma=2$ you can simulate $\gamma=4$ by using nestings twice as deep)
  • If $\alpha < \gamma$ no quantifier can actually quantify over $\alpha$ or more variables (unless some don't appear, in which case you can just delete them), since any formula which did so would involve a subformula with $\alpha$ or more free variables, which would be ill-formed..
  • If $0 < \gamma < \alpha \leq \omega$ you can just nest finitely many $<\gamma$-variable quantifiers to achieve $<\alpha$-variable quantification, so increasing $\gamma$ to be equal to $\alpha$ will admit additional well-formed formulas, but each of them will be equivalent to some formula which had already been admitted.
  • If $\gamma < \alpha$ and $\omega < \alpha < \omega\cdot{2}$ then a formula with $\gamma$ or more free variables can never appear as a subformula of a closed formula (sentence) because no cardinal $<\gamma$ multiplied by a finite cardinal (nesting depth) is ever equal to a greater cardinal. So reducing $\alpha$ to equal $\gamma$ would not change the set of well-formed sentences (although I guess it might affect the set of formulas, but the sentences are what really matter, right?)

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

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

even more tweaks
Source Link
Adam
  • 3.3k
  • 1
  • 23
  • 30

$L^α_ ${\mathcal L}^α_{β,γ}$: do we need both $α$ and $β$ for model theory?

The notation $L^\alpha_{\beta,\gamma}$${\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 (and assuming I was not mistaken) the following are formulas of $L^\alpha_{\beta,\gamma}$${\mathcal L}^\alpha_{\beta,\gamma}$ in addition to the atomic formulas:

  • $\neg\phi$ if $\phi\in L^\alpha_{\beta,\gamma}$$\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 L^\alpha_{\beta,\gamma}$$(\forall i\in I)\Phi_i\in {\mathcal L}^\alpha_{\beta,\gamma}$ and $|FV(\underset{i\in I}\bigvee \Phi_i)|<\alpha$
  • $(\exists \{x_i\}_{i\in I})\phi$ if $|I|<\gamma$ and $\phi\in L^\alpha_{\beta,\gamma}$$\phi\in {\mathcal L}^\alpha_{\beta,\gamma}$

So, my question is: why $\gamma$? More specifically, if $\lceil\gamma\rceil$ is the least limit ordinal greater than or equal to $\gamma$, then when is

$$ L^\alpha_{\beta,\gamma}\neq \begin{cases} L^0_{\beta,\infty} & \text{\ if\ } 0=\gamma \\ L^{min(\alpha,\omega)}_{\beta,\infty} & \text{\ if\ } 0<\gamma\leq\omega \\ L^{min(\alpha,\gamma)}_{\beta,\infty} & \text{\ if\ } \omega<\gamma \\ \end{cases} $$$$ {\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 $L^\alpha_\beta$${\mathcal L}^\alpha_\beta$. My reasoning goes like this:

  • The $\gamma=0$ case is obvious; you get no quantifiers.
  • All values $0<\gamma\leq\omega$ yield the same set of formulas because the set of formulas is closed under arbitrary composition (so if $\gamma=2$ you can simulate $\gamma=4$ by using nestings twice as deep)
  • If $\alpha < \gamma$ no quantifier can actually quantify over $\alpha$ or more variables (unless some don't appear, in which case you can just delete them), since any formula which did so would involve a subformula with $\alpha$ or more free variables, which would be ill-formed..
  • If $0 < \gamma < \alpha \leq \omega$ you can just nest finitely many $<\gamma$-variable quantifiers to achieve $<\alpha$-variable quantification, so increasing $\gamma$ to be equal to $\alpha$ will admit additional well-formed formulas, but each of them will be equivalent to some formula which had already been admitted.
  • If $\gamma < \alpha$ and $\omega < \alpha$$\omega < \alpha < \omega\cdot{2}$ then a formula with $\gamma$ or more free variables can never appear as a subformula of a closed formula (sentence) because no cardinal $<\gamma$ multiplied by a finite cardinal (nesting depth) is ever equal to a greater cardinal. So reducing $\alpha$ to equal $\gamma$ would not change the set of well-formed sentences (although I guess it might affect the set of formulas, but the sentences are what really matter, right?)

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

$L^α_{β,γ}$: do we need both $α$ and $β$?

The notation $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 (and assuming I was not mistaken) the following are formulas of $L^\alpha_{\beta,\gamma}$ in addition to the atomic formulas:

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

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

$$ L^\alpha_{\beta,\gamma}\neq \begin{cases} L^0_{\beta,\infty} & \text{\ if\ } 0=\gamma \\ L^{min(\alpha,\omega)}_{\beta,\infty} & \text{\ if\ } 0<\gamma\leq\omega \\ L^{min(\alpha,\gamma)}_{\beta,\infty} & \text{\ if\ } \omega<\gamma \\ \end{cases} $$

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 $L^\alpha_\beta$. My reasoning goes like this:

  • The $\gamma=0$ case is obvious; you get no quantifiers.
  • All values $0<\gamma\leq\omega$ yield the same set of formulas because the set of formulas is closed under arbitrary composition (so if $\gamma=2$ you can simulate $\gamma=4$ by using nestings twice as deep)
  • If $\alpha < \gamma$ no quantifier can actually quantify over $\alpha$ or more variables (unless some don't appear, in which case you can just delete them), since any formula which did so would involve a subformula with $\alpha$ or more free variables, which would be ill-formed..
  • If $0 < \gamma < \alpha \leq \omega$ you can just nest finitely many $<\gamma$-variable quantifiers to achieve $<\alpha$-variable quantification, so increasing $\gamma$ to be equal to $\alpha$ will admit additional well-formed formulas, but each of them will be equivalent to some formula which had already been admitted.
  • If $\gamma < \alpha$ and $\omega < \alpha$ then a formula with $\gamma$ or more free variables can never appear as a subformula of a closed formula (sentence) because no cardinal $<\gamma$ multiplied by a finite cardinal (nesting depth) is ever equal to a greater cardinal. So reducing $\alpha$ to equal $\gamma$ would not change the set of well-formed sentences (although I guess it might affect the set of formulas, but the sentences are what really matter, right?)

${\mathcal L}^α_{β,γ}$: do we need both $α$ and $β$ for model theory?

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 (and assuming I was not mistaken) 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 $|FV(\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}$

So, my question is: why $\gamma$? More specifically, if $\lceil\gamma\rceil$ is the least limit ordinal greater than or equal to $\gamma$, then 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$. My reasoning goes like this:

  • The $\gamma=0$ case is obvious; you get no quantifiers.
  • All values $0<\gamma\leq\omega$ yield the same set of formulas because the set of formulas is closed under arbitrary composition (so if $\gamma=2$ you can simulate $\gamma=4$ by using nestings twice as deep)
  • If $\alpha < \gamma$ no quantifier can actually quantify over $\alpha$ or more variables (unless some don't appear, in which case you can just delete them), since any formula which did so would involve a subformula with $\alpha$ or more free variables, which would be ill-formed..
  • If $0 < \gamma < \alpha \leq \omega$ you can just nest finitely many $<\gamma$-variable quantifiers to achieve $<\alpha$-variable quantification, so increasing $\gamma$ to be equal to $\alpha$ will admit additional well-formed formulas, but each of them will be equivalent to some formula which had already been admitted.
  • If $\gamma < \alpha$ and $\omega < \alpha < \omega\cdot{2}$ then a formula with $\gamma$ or more free variables can never appear as a subformula of a closed formula (sentence) because no cardinal $<\gamma$ multiplied by a finite cardinal (nesting depth) is ever equal to a greater cardinal. So reducing $\alpha$ to equal $\gamma$ would not change the set of well-formed sentences (although I guess it might affect the set of formulas, but the sentences are what really matter, right?)

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

Revised to cover case where $0<\gamma<\omega$
Source Link
Adam
  • 3.3k
  • 1
  • 23
  • 30
Loading
edited title for homepage readability; added 2 characters in body
Source Link
Anton Geraschenko
  • 24k
  • 17
  • 127
  • 180
Loading
Add model-theory tag
Link
Adam
  • 3.3k
  • 1
  • 23
  • 30
Loading
Source Link
Adam
  • 3.3k
  • 1
  • 23
  • 30
Loading