Any, For All, Exists

Albert Y. C. Lai, trebla [at] vex [dot] net
February 5, 2010

(I wrote this note a long time ago inspired by the rather liberal use of the word “any” in mathematics textbooks (nevermind daily use). Sometimes it means “for all”, sometimes it means “there exists”, and sometimes it gets more interesting than either.)

Demi teaches logic at highschool (yeah dream on). Ange is a student in the class.

0. For All

Today Demi assigns this homework:

Prove: ∀n:nat· n×(n+1)/2 = (Σi:1..n· i)

Ange asks, “so n is a natural number?”

“Yes, n can be any natural number.”

“So I can pick any natural number?”

“No. While n can be any natural number, it is not up to you. If you like, you can imagine that I do the picking. Since you don't know up front what I'll pick, you'd better write a proof that works for all natural numbers, so that I have no way to pick on your proof.”

1. Exists

Today Demi assigns this homework:

Prove: ∃n:nat· n3 > 3n

Ange asks, "so n is a natural number?"

“Yes, n can be any natural number.”

“So you will pick any natural number?”

“No. This time it is up to you, not me, to do the picking. While this time you have this freedom, you also have the duty to satisfy the rest of the sentence. So, make sure you pick someone that works.”

2. Any

Today Demi discusses formalization. “Formalize this: If there is some natural number n in D, then the size of D is at least 1.”

“(∃n:nat· n:D) ⇒ |D|≥1”

“Note that it is equivalent to: (∀n:nat· n:D ⇒ |D|≥1)”

“Woah, how do you pronounce that in English? I know I can always say: for all natural numbers n, if n is in D, then the size of D is at least 1. But it sounds cumbersome.”

“Well, some people say: If any natural number is in D, then the size of D is at least 1.”

“But I learned in the last two lessons that ‘∀’ and ‘∃’ can be both ‘any’, except there is still the difference of who does the picking. Now you just say ‘any’, so is this one ‘∀’ or ‘∃’?”

“It depends on where you put the parentheses!”

3. Every

Today Demi and Ange take a field trip. (Yeah! There are field trips for logic too!) The field is a pub. (Feynman's secret of success!)

Demi: “Smullyan stated this paradox — but I would just think of it as a funny theorem — in a non-empty pub, there is a person p such that if p drinks then everyone (in the bar) drinks:

(∃p:Pub· p drinks ⇒ (∀q:Pub· q drinks))”

Ange: “Yeah, I can see from this pub that it makes sense. I am under-age and not drinking, so I can pick myself to be the person p in question, and the statement is vacuously true. On the other hand, if everyone drank, the statement would be trivially true. So either way it's a theorem.”

Demi: “Yes, that's one way to prove it, but there is a shorter way, avoiding an explicit case analysis. Remember the equivalence of yesterday? Its dual is applicable today.”

Ange: “Oh!

(∃p:Pub· p drinks ⇒ (∀q:Pub· q drinks))
=(∀p:Pub· p drinks) ⇒ (∀q:Pub· q drinks)

If everyone drinks, then everyone drinks! Duh!”

Go to Blog of Albert Y. C. Lai