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.

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

Today Demi assigns this homework:

Prove: ∃n:nat· n^{3} > 3^{n}

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

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!”

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!”