2
$\begingroup$

I believe that "fewer than $\alpha$ variables" is equivalent to "every subformula has fewer than $\alpha$ free variables." The left-to-right implication is straightforward, and from right to left one can always rename variables. For example, the following trivial (and not very useful) theorem of ZFC has no more than two free variables in any subformula:

$$(\exists x) (\forall y) (y\notin x\ \&\ (\exists z) y\in z))$$

It uses three distinct variables (x, y, and z), but because no subformula contains more than two free variables, we can rewrite it to the equivalent:

$$(\exists x) (\forall y) (y\notin x\ \&\ (\exists x) y\in x))$$

So, are the two formulations of the restriction equivalent? If so, why isn't the latter formulation used more often in papers on bounded-variable logic? It seems to have the advantage that it doesn't impose a restriction on the (irrelevant) choice of which variables one uses, limiting only the number that appear free in any given subformula.

Thanks!

$\endgroup$
2
  • 1
    $\begingroup$ I think the phrases should technically be "fewer than $\alpha$ (free) variables." (-: $\endgroup$ May 18, 2010 at 4:07
  • $\begingroup$ Yes, you're right :) I'll edit to fix that. $\endgroup$
    – Adam
    May 18, 2010 at 4:44

1 Answer 1

2
$\begingroup$

If you are speaking of infinitary logic, which your notation (and your other question) suggests, then the statement is not true. Take the case $\alpha=\omega$. Suppose that $\varphi_n$ is a sentence that uses $n$ variables, and cannot be expressed equivalently with fewer than $n$ variables. But $\varphi_n$ has no free variables. Consider the statement $\bigwedge_n \varphi_n$. This is a sentence, having no free variables, and it uses $\omega$ many variables. However, its subformulas are itself (with no free variables), plus the subformulas of any $\varphi_n$, which each have at most $n$ free variables.

Thus, this assertion has the property that every subformula has fewer than $\omega$ free variables, but the assertion does not use fewer than $\omega$ variables. So it seems to be a negative example to your conjecture.

To take a specific example, let $\varphi_n$ assert "there are at least $n$ distinct objects", which can be expressed in a finite formula using $n$ variables. The conjunction $\bigwedge_n \varphi_n$ asserts that the universe is infinite.

$\endgroup$
2
  • $\begingroup$ Thank you once again! I particularly appreciate the simple and clear example at the end of your answer. Can you perhaps recommend some reading on how the number-of-variables parameter interacts with the conjunction-cardinality and quantification-cardinality parameters of infinitary logic? I've found plenty of reading on how the latter two interact, and a few sources on bounded-variable subsets of first-order logic, but haven't had much luck finding material that covers both of them. $\endgroup$
    – Adam
    May 18, 2010 at 20:06
  • $\begingroup$ Thanks for the kind remark and for accepting my answer. Unfortunately, I don't really know of any references for you, however, but perhaps someone else can post something here... $\endgroup$ May 18, 2010 at 20:13

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.