# Are quantifiers redundant by treating free variables as implicitly universally quantified?

I am getting suspicious that there is no need whatsoever for quantifiers in formal first-order logic. Why do we write $$\forall x, P(x)$$, when can simply write $$P(x)$$, assuming that we know that $$x$$ is a variable (as opposed to a constant).

A similar question has been asked here: Is the universal quantifier redundant?, and a commenter states that the order of quantifiers matters. Indeed, the order of mixed quantifiers matters, but all existential quantifiers can be reformulated as universal quantifiers, so in fact the order does not matter.

I'm struggling to think of a case where a quantifier provides essential information for a statement.

• How would you distinguish between $\neg\forall x P(x)$ and $\forall x \neg P(x)$ if you omitted quantifiers? Commented Jul 10, 2022 at 20:32
• @Eric Wofsey Good point. I knew that it was something obvious. Commented Jul 10, 2022 at 20:35
• @ryang I see. This is another good example. The more I think about this question, well let's just say I'm facepalming a little bit... Commented Jul 10, 2022 at 20:41
• @somethingaboutus Actually, that deleted example isn't good for your purpose, since $(∀xB(x) \lor ∀xG(x))$ can be equivalently written as $∀x∀y(B(x) \lor G(y)),$ which $(B(x) \lor G(y))$ is understood as, assuming implicit universally quantification, which is your Question's premise. Anyway, as long as your Question has not received an Answer, you're always free to delete it! Commented Jul 10, 2022 at 20:46
• "Indeed, the order of mixed quantifiers matters, but all existential quantifiers can be reformulated as universal quantifiers, so in fact the order does not matter." How it is possible for the order to matter and not matter at the same time?
– Marc
Commented Jul 11, 2022 at 16:31

The problem with replacing $$\exists$$ with $$\neg\forall\neg$$ to not have to worry about the order of quantifiers becomes apparent if you actually try doing so and omitting the quantifiers. For instance, $$\exists x P(x)$$ becomes $$\neg \forall x \neg P(x)$$ and then you omit the quantifier to get $$\neg\neg P(x)$$. Wait, that's equivalent to just $$P(x)$$, which would mean $$\forall xP(x)$$ under your convention. So $$\exists x P(x)$$ turned into just $$\forall xP(x)$$, which isn't right!

The problem here is that the order of negation and universal quantifiers matters. That is, $$\forall x\neg P(x)$$ is different from $$\neg\forall x P(x)$$ (so $$\neg \forall x \neg P(x)$$ is different from $$\forall x \neg\neg P(x)$$). If you omit universal quantifiers everywhere, you lose this distinction.

Rob Arthan's answer is exactly right; let me supplement it with an observation from computability theory.

Consider the structure $$\mathcal{N}=(\mathbb{N};+,\times)$$. It turns out that the quantifier hierarchy over $$\mathcal{N}$$ is non-collapsing: no fixed number of quantifiers will ever be sufficient for capturing all the definable sets in $$\mathcal{N}$$. This turns out (with a slight tweak re: bounded quantifiers, resulting in the arithmetical hierarchy) to have a computational interpretation, according to which definability with $$n$$ alternations of quantifiers + as many bounded quantifiers as you like corresponds to computability relative to the $$n$$th "iterated Halting Problem."

So in a precise sense, "few-quantifier" expressions are quantitatively less powerful than "many-quantifier" expressions.

Let's consider these two quantified statements: \begin{align*} \forall x\exists y M(x, y) \tag*{(1)}\\ \exists x\forall y M(x, y) \tag*{(2)} \end{align*} and let's take the universe of discourse to be people and interpret $$M(x,y)$$ to mean $$y$$ is the mother of $$x$$. Statement (1) says that everybody has a mother while statement (2) say that there there is a person who has every person as a mother. These statements have very different meanings: quantifiers are not redundant.

We write quantifiers to keep close track of the dependencies in our mathematical problems.

• OP is already aware of this and is asking why you can't get around it by expressing the existential quantifiers in terms of universal quantifiers and then taking free variables to be implicitly universally quantified. Commented Jul 11, 2022 at 1:28
• @Eric Wofsey Yes, but actually you end up just running into the same problem since (1) expands to $\forall x \neg \forall y M$ and (2) expands to $\neg \forall x \forall y M$. Commented Jul 11, 2022 at 2:05