Week 5: The Pros and Pitfalls of CSC165 Proofs

Many of my classmates have their first exposure to proofs in CSC165 so this class caters towards them.  I think this is fair but I am sure that at least some of my classmates did proofs in other classes.  I become used to the essay-like proofs of my previous proof-oriented math classes: MAT138 (Intro to Proofs) and MAT240 (Algebra I).  So when the first proofs in CSC165 presented themselves in mainly logical sentences instead of mainly English sentences, I was pleasantly surprised.  Their aesthetic appearance reminds me of programming code.  Why are the proofs in CSC165 presented this way?

The Pros

After thinking about it for a few days, I arrive at two justifications.  Proofs can seem overwhelming to those of us who are new it; this certainly was the case for me.  Presenting the proofs in the style of programming code can make it less intimidating to those us who are comfortable with programming.   In addition, the use of mainly logical sentences instead of mainly English sentences can make it easier to catch logic errors.

The Pitfalls

            However, there is a downside to the CSC165 way of writing the proofs.  Where is the intuition? There is emphasis on annotating the logical sentences correctly but not much focus on the how to prove a claim.  How do we decide between a direct proof or proof by contradiction if we are looking for a sound and efficient way to prove?   Do we memorize the cases for when one proof strategy works better than another?  Experience tells me that this is a bad idea because we will be at a loss if we see a new, unfamiliar claim to prove.

So what is the best way to gain intuition?  My opinion is to try things out.  We should think way about different ways to prove a claim.  We should think how the mathematical structures in a claim make a specific proof strategy efficient or inefficient.  Unfortunately, the focus on annotating the logical sentences correctly and making the aesthetics of a proof comparable to programming code is contrary to the goal of gaining intuition.  If CSC165 can focus more on the strategies for approaching proofs, then we might benefit more from the logical rigour through which the course presents its proofs.

Week 4: Logical Cameleons

Suppose that you walk into the forest today and see a purple chameleon.  Then next week, you walk by into same forest and see an orange chameleon.  The orange chameleon looks similar to the purple chameleon except for its colour.  Surely they are not the same chameleon, right?

A Purple Panther Chameleon

An Orange Panther Chameleon

            In logic, a similar problem occurs.  Consider these two logical sentences.  Let $D $ be a set and $P, Q$ be sentences:

                        (1) $\exists x \in D, P(x) \implies Q(x)$

                        (2)  $( \forall x \in D, P(x)) \implies ( \exists x \in D, Q(x))$

These two sentences look very different.  Surely they are not the same sentence, right? 

            For chameleons, you are out of luck but for logic, we can use logical axioms, which link together logical statements that are equivalent, to determine if two logical sentences are saying the same thing.  Let $S$ be a set and $P, Q, R$ be sentences.  These are our axioms:

Table of Logical Axioms for Dummies

Axiom	Result
Commutativity	$P \vee Q \iff Q \vee P$ $P \wedge Q \iff Q \wedge P$
Associativity	$P \vee (Q \vee R) \iff (P \vee Q) \vee R$ $P \wedge (Q \wedge R) \iff (P \wedge Q) \wedge R$
Distributivity	$P \vee (Q \wedge R) \iff (P \vee Q) \wedge (P \vee Q)$ $P \wedge (Q \vee R) \iff (P \wedge Q) \vee (P \wedge Q)$
Implication	$(P \implies Q) \iff (\neg P \vee Q)$
Bi-implication	$(P \iff Q) \iff ((P \implies Q) \wedge (Q \implies P))$
Identity	$P \wedge (Q \vee \neg Q) \iff P$ $P \vee (Q \wedge \neg Q) \iff P$
Idempotency	$P \wedge P \iff P$ $P \vee P \iff P$
DeMorgan’s Law	$\neg (P \wedge Q) \iff \neg P \vee \neg Q$ $\neg (P \vee Q)  \iff \neg P \wedge \neg Q$
Quantifier Commutativity	$\forall x \in S, \forall y \in S, P(x, y) \iff$ $\forall y \in S, \forall x \in S, P(x, y)$ $\exists x \in S, \exists y \in S, P(x, y) \iff$ $\exists y \in S, \exists x \in S, P(x, y)$
Quantifier Distributivity	$\forall x \in S, P(x) \wedge Q(x) \iff$ $(\forall x \in S, P(x)) \wedge (\forall x \in S, Q(x))$ $\exists x \in S, P(x) \vee Q(x) \iff$ $(\exists x \in S, P(x)) \vee (\exists x \in S, Q(x))$

Our job is determine if (1) and (2) are equivalent with these axioms.  Start with (1):

$\exists x \in D, P(x) \implies Q(x)$

By the implication axiom, then (1) has the same meaning as this sentence:

$\exists x \in D, \neg P(x) \vee Q(x)$

By the quantifier distributivity axiom, then (1) camouflages into this sentence :

$(\exists x \in D, \neg P(x)) \vee (\exists x\in D, Q(x))$

Use the implication axiom again so that (1) looks like this sentence:

$(\forall x \in D, P(x)) \implies (\exists x\in D, Q(x))$

We see that sentences (1) and (2) are equivalent even though they look different.  Appearances are always deceiving!

Week 3: Fancy Translations from English to Logic

Last week, we saw that a sentence in a natural language can be represented in the formal language of logic through predicates, implications and quantifiers.  Yet we can be a little fancier with our representations by introducing two new members to our zoo of logical symbols. 

Suppose that we want to represent these English statements in logic:

(1) Some student that is in CSC165 is both cool and likes math.

(2) All students that are CSC165 are either cool or like math.

Let $U$ be the set of all students.  Let $C(x)$ mean $x$ is in CSC165, $K(x)$ mean $x$ is cool and $M(x)$ mean $x$ likes math.  The conjunction symbol, which represents the English word “and”, and the disjunction symbol, which represents the word English “or”, allows the translation of statements (1) and (2) into logic:

                        (1) $\exists x \in U, C(x) \implies (K(x) \wedge M(x))$.

                        (2) $\forall x \in U, C(c) \implies (K(x) \vee M(x))$.

Now let us play a game of I-Spy.   See these statements:

                        (3) $\exists x \in U, C(x) \implies (K(x) \implies M(x))$.

                        (4) $\forall x \in U, C(x) \implies (K(x) \implies M(x))$.

I spy a nuance between statements (3) and (1) and statements (4) and (2).   What is this nuance?  It is the relation between predicates $K(x)$ and $M(x)$.  Replacing either the conjunction or disjunction symbol in a statement with an implication symbol changes the meaning of that statement.  Let us illustrate the difference between statements (1) and (3) and statements (2) and (4) with a CSC165 student named Bobby.

Bobby wants to take up the burden of satisfying statement (1).  Then he needs be cool and he has to like math.  Later Bobby decides that this is too much of a burden for him so he decides to satisfy statement (3) instead.  From last week`s post about implications, we know that he has a choice of either being uncool or keeping his fondness for math.  Hence, the implication is much more flexible than the conjunction.

Now Bobby wants to take up the burden of satisfying statement (2).  He campaigns to convince all his CSC165 classmates to either be cool or like math.  His classmates rebel and decide to neither be cool nor like math.  Yet Bobby is enterprising.  He decides to satisfy statement (4) instead.  Then he needs to get all his classmates to either be uncool or like math.  However, his CSC165 classmates are just as adept at defying Bobby and they decide to be both cool and dislike math.  Poor Bobby!  Hence, the implication and disjunction are different in how they are satisfied but they are the same in their flexibility.

Week 2: Introducing... the Logical Zoo

The English Language

            Currently the most commonly used language in the developed world, the English language has a diverse vocabulary, a sophisticated grammar system and a rich history that dates back to the end of the Roman Empire.  Like all natural languages, English allows for ambiguity of expression.  Take a look at this sentence:

           

Panda mating fails: veterinarian takes over.

Either one of two things is being said:

(1) The veterinarian will investigate the pandas.

(2) The pandas will have to mate with the veterinarian.

Common sense is enough here to determine what the sentence-writer meant.  Yet there are occasions in which both interpretations are plausible.  What if you have a weird friend who said this to you:

"People are fashionably hungry unless they eat Satsumas"

Your friend means either one of two things:

(1) People that are fashionably hungry do not eat Satsumas.

(2) People that do not eat Satsumas are fashionably hungry.

Neither common sense nor the semantics of the English language tells us beyond doubt what your friend meant.  We need some other tool.

The Language of Logic

            Logic can solve the riddle of what your friend said.  The language of logic uses symbols to represent meaning just like English uses the alphabet the represent words.  Yet unlike English, logic communicates everything in terms of whether something is true or false.  The following table introduces common logical symbols:

Table of Logical Symbols for Dummies

Symbol	Meaning	Comments
$x, y, z, …$	Variable	A variable represents some real-world object.  It can be a person, word, number or any object you like.
$S, T, U, …$	Set	A set is an ordered collection of unique objects.  It can be a set of people, numbers, cars or any object you like.
$P(x), Q(x), R(x), …$	Predicate	A predicate is a function that maps some variable to the value “true” or the value “false”.  Think of it as telling the reader whether or not some real-world object has some attribute.
$\exists$	There Exists	A quantifier that conveys that at least one member of some set has some attribute.
$\forall$	For All	A quantifier that conveys that all members of some set have some characteristic.
$\implies$	If... then...	A composition of two sentences.  The first is an assumption, which is called the antecedent.  The second is a conclusion, called the consequent.  Its structure is as follows: if antecedent is true, then the consequent is true.
$\neg$	Negation	A negation is an operation that can be applied to a sentence.  A negated sentence is false if the original sentence is true and vice-versa.

These are all the symbols that we need to translate what your weird friend said from English to logic.  There is two mores hoops to jump however.  The English word “unless” is translated to logic as an implication that has a negated antecedent.  Additionally, since "unless" is in the middle of the sentence, then the overall sentence is in the form of "then... if...".  Now, we can translate the sentence:

Let $P$ be a set of all people and $H(x), S(x)$ be predicates with the following definitions:

$H(x): x$ is fashionably hungry

$S(x): x$ eats Satsumas

Then the sentence “People are fashionably hungry unless they eat Satsumas” is translated to logic as:

$\forall x \in P, \neg S(x) \implies H(x)$

The meaning of this logical statement in English is “People that do not eat Satsumas are fashionably hungry" so therefore, your weird friend meant (2).