How do quantifiers limit scope?

Question

I'm teaching a discrete math class at the high school level and realize that I'm fuzzier on a topic than I should be.

In their last problem set, I asked my students to translate "There is a triangle that is above every square." into formal notation.

My answer was $\exists t\forall s(\text{triangle}(t)\wedge\text{square}(s)\rightarrow\text{above}(t, s))$.

Many students made a mistake of replacing the implication with conjunction, but once I explained they were saying that all members of the domain were squares, they understood why they needed the implication.

A few students side-stepped the problem by writing $\exists t\ \text{triangle}(t)(\forall s\ \text{square}(s)(\text{above}(t, s)))$. This was inspired by a quasi-formal notation in the textbook that would have written the sentence as $\exists\ \text{triangle}\ t,\ \forall\ \text{squares}\ s,\ \text{above}(t, s)$.

What I'm not sure about is whether this is okay. Is there some notational convention that $$ \forall xP(x)(Q(x))\equiv\forall x(P(x)\rightarrow Q(x))$$ or am I just making that up?

What confuses this somewhat is that I'm pretty sure that $$\exists xP(x)(Q(x))\equiv\exists x(P(x)\wedge Q(x))$$ under the normal understanding of the notation without any convention, so I'm afraid that I let my students get away with playing fast and loose with the notation when I shouldn't have.

Thanks! Todd

Answer 1

I'm afraid your suggested answer is wrong. Suppose $a$ is in the domain and a non-triangle. Then $$\forall s(\text{triangle}(a)\wedge\text{square}(s)\rightarrow\text{above}(a, s))$$ is vacuously true as it always has a false antecedent (recall $\land$ binds tighter than $\to$). Hence $$\exists t\forall s(\text{triangle}(t)\wedge\text{square}(s)\rightarrow\text{above}(t, s))$$ is true even if no triangle is above a square.

What you need is $$\exists t(\text{triangle}(t)\wedge \forall s(\text{square}(s)\rightarrow\text{above}(t, s)))$$ or equivalently $$\exists t\forall s(\text{triangle}(t)\wedge(\text{square}(s)\rightarrow\text{above}(t, s)))$$ Bracketing matters!

As for $$\forall xP(x)(Q(x))\equiv\forall x(P(x)\rightarrow Q(x))$$ what's on the left is horribly ill-formed by normal standards and so is to be deprecated. But the thought that restricted universals are to be rendered using conditionals, and restricted existentials rendered using conjunctions is of course right. Your students might find the (freely available) chapters on transcription in Paul Teller's Logic Primer very helpful: see the first four chapters of Part 2 at http://tellerprimer.ucdavis.edu/pdf/

Answer 2

Bounded quantifiers of various kinds, like $\forall x<t$ or $\exists y\in\mathbb{N}$, are a commonly used notational convention. The convention for such notations is exactly what you expect: $$\forall x<t\ P(x)\equiv \forall x(x<t\rightarrow P(x))$$ $$\exists x<t\ P(x)\equiv \exists x(x<t\wedge P(x)).$$ The different choice of connective is necessary and appropriate, since it preserves duality: $$\forall x<t\ P(x)\Leftrightarrow \neg\exists x<t\ \neg P(x).$$ Your students are using bounded quantifiers of this kind, with the correct interpretation. However that particular syntax isn't generally used, for the reasons Peter Smith notes. People who want quantifiers bounded by predicates generally introduce some other notation; the one I'm most familiar with is: $$\forall x\in P (Q(x)),$$ but there are other variants (for instance, introducing $\in$ in a high school class would presumably require at least some discussion of sets, which might be undesirable).

There's no canonical set of abbreviations, so you ultimately have to make a call about which syntax is permitted. (Having a textbook that casually uses non-standard abbreviations is a further complication; I know I'd be quite frustrated to be told that formulas had to be built using certain rules when my own textbook couldn't be bothered to follow them.)

Answer 3

You have a right idea, but it might help to refine your notation this way: write $\forall_{x: X} Q(x)$ and $\exists_{x: X} Q(x)$ whenever you mean to interpret your variable $x$ as ranging over elements of a set $X$.

Then, what you are asking about is the relationship between the meanings of the quantifiers $\forall_{x: X}$ and $\forall_{x: A}$ where $A \subseteq X$ is a subset defined by a predicate $P(x)$, i.e., $A = \{x \in X: P(x)\}$. Similarly for the relationship between $\exists_{x: X}$ and $\exists_{x: A}$.

There are various ways of explaining the relationships; I would recommend looking at Paul Taylor's Practical Foundations of Mathematics, particular with regard to guarded quantifiers and also how quantification relates to adjunctions. But of course this is for you, not for your students! For your students, I think you can pitch the translation $\forall_{x: A} Q(x) := \forall_{x: X} P(x) \Rightarrow Q(x)$ either informally (i.e., in terms of 'common sense', that $\forall_{x: A} Q(x)$ means we want $Q(x)$ for all $x$ under the condition $P(x)$), or more formally like this: if you accept that

$$\exists_{x: X} P(x) \wedge Q(x)$$

is the correct translation of $\exists_{x: A} Q(x)$, then

$$\forall_{x: A} Q(x) = \neg \exists_{x: A} \neg Q(x) = \neg \exists_{x: X} P(x) \wedge \neg Q(x) = \forall_{x: X} \neg(P(x) \wedge \neg Q(x)) = \forall_{x: X} P(x) \Rightarrow Q(x).$$