Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
1  
High school students should be taught many-sorted logic with bounded quantifiers. Only logicians pretend that the domain of discourse is amorphous, because it suits them for technical purposes. –  Andrej Bauer Jul 9 '13 at 7:14

3 Answers 3

up vote 3 down vote accepted

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/

share|improve this answer
    
Blech! How embarrassing... –  Todd O'Bryan Oct 14 '12 at 22:02
    
I've just sent your correction to my students along with a mea culpa. I think I started with your suggested answer and decided to move the universal quantifier out front, but dropped the parentheses in the process. At least they'll feel better about the small mistakes they made on the problem set. :-) –  Todd O'Bryan Oct 14 '12 at 22:30

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

share|improve this answer
    
Thanks. We've talked about the element-of notation, so I can mention that. I think they (and I) just got confused between the English-like notation with quantifier symbols and standard first-order predicate logic. I'll emphasize the distinction and try to avoid the mixture of notations. –  Todd O'Bryan Oct 14 '12 at 22:32

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).$$

share|improve this answer
    
Or I can just say that we'll avoid abbreviated notations entirely and stick to nice, standard, first-order predicate logic. Thanks for figuring out what we were trying to notate and giving us the benefit of the doubt. :-) –  Todd O'Bryan Oct 14 '12 at 22:27
    
@Todd O'Bryan: You can avoid the abbreviated notations in the formalizations, but they occur naturally in the English sentences that are to be formalized. People say (as you did) "there is a triangle that is above every square", not "there is a thing such that it is a triangle and, for every other thing, if that second thing is a square then the first things is above it." So your students will still have to come to grips with the correspondence between the abbreviated formulations (in English if not in the formal language) and the unabbreviated formulations. –  Andreas Blass Oct 15 '12 at 1:46
    
Absolutely. I actually have a background in theoretical linguistics, so I make sure they realize just how messy natural languages are. Formal languages, however, should not be. :-) –  Todd O'Bryan Oct 15 '12 at 2:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.