4

Say I have a sequence of quantifiers like so:

$$ \\ \exists x\ ( \forall y\ F(x, y)) \tag{1} $$

If there was no parentheses this would be $$ \\ \exists x\ \forall y\ F(x, y) \tag{2} $$

Take another expression If there was no parentheses this would be $$ \\ \forall y\ \exists x\ F(x, y) \tag{3} $$

So, is $(1)$ equal to $(2)$ (basically the parentheses don't matter), or is it equal to $(3)$ (the parentheses causes us to look at the inner expression first)?

CSCSCSCSCSCSCSCSCS
  • 127
  • 2
    The order of the quantifiers matters, but I don't see what parentheses have to do with it one way or the other. – Qiaochu Yuan Oct 11 '20 at 01:01
  • 1
    @QiaochuYuan I think the OP is trying to draw an analogy with e.g. "$a\times (b+c)$," where the parentheses indicate that the expression "$b+c$" should be evaluated first. – Noah Schweber Oct 11 '20 at 01:01
  • 2
    But what is the alternative? "$(\forall x \exists y)$" isn't an expression that can be evaluated so the "other possible parenthesization" doesn't mean anything. – Qiaochu Yuan Oct 11 '20 at 01:02
  • Yes, I was basically asking if it is like order of operations. – CSCSCSCSCSCSCSCSCS Oct 11 '20 at 03:45

2 Answers2

5

$(1)$ and $(2)$ are the same, $(3)$ is different.

Quantifiers don't act like arithmetic operations: when we see $\mathsf{Q}x[\mathsf{stuff}]$ for a quantifier $\mathsf{Q}$, this basically means that the inside clause $[\mathsf{stuff}]$ only makes sense within the scope of $\mathsf{Q}x$. If you think of game semantics, we only start considering $[\mathsf{stuff}]$ after the appropriate player has picked a value for $x$. So parentheses used in the above ways actually indicate what to evaluate last: they show that a certain expression is within the scope of a certain quantifier.

Noah Schweber
  • 245,398
1

You can imagine that quantifiers affect the thing to the right of them - for instance, $$F(x,y)$$ asserts some predicate in two free values $x$ and $y$. We can create a new logical statement with a quantifier $$\forall y\,F(x,y)$$ which only has one free variable - $x$ - and we are stating that for this unknown $x$, we have $F(x,y)$ for every $y$. We can then bind the variable $x$ with another quantifier like $$\exists x \forall y\,F(x,y)$$ which has no free variables - simply asserting the existence of some $x$ so that the condition $\forall y \, F(x,y)$ holds.

Note how this proceeds from an expression with two free variables ($F(x,y)$) to one with none ($\exists x\forall y\,F(x,y)$) in steps, where the first step is to somehow apply $\forall y$ to the expression. The view that quantifiers are applied to the expression to their right starting at the innermost quantifier reflects some structure of mathematical organization - for instance, in analysis, one often starts by talking about a metric, then building a notion of a limit by wrapping some statements about that metric in quantifiers. Then maybe you take your idea of a limit and wrap it in another layer of quantifiers to discuss the idea of a convergent sequence - and maybe you wrap that up even more to get the idea of sequential compactness. Note that this process is the same as what is illustrated above, just more complicated: we take a small notion, and build quantifiers up moving "outwards" (to the left in notation) - and often these intermediate expressions analogous to $\forall y\,F(x,y)$ get independent meaning or names even if occurring within the scope of a bigger quantifier.

When you use parenthesis, this is the notion of "looking at the expression first" that is being invoked - and you can notice that this does not translate to writing the quantifier you see in the parenthesis first.

Milo Brandt
  • 60,888