Boy do I ever not like this proof structure stuff.

This is a post I've been meaning to write for, well, more than three weeks now. In a way, it's almost better I put it off, since my opinions have somewhat changed.

When it was first introduced, I thought the rigid structure used to prove statements in this course was just incredibly tedious. It wasn't a huge problem, however, since anything we were asked to prove was pretty simple and direct.

When I got to writing up the assignment though, having to stick to such a rigid structure really bothered me. I've got some math background, so having to break every thought into a sentence that begins with either "Assume", "Let", or "Then" just feels silly, and the impossibility of giving even mildly complicated statements was so frustrating. It sure didn't help that typesetting it in Latex was a pain (for an indication of how dumb my approach was, all proofs were plopped into a flalign* environment, with \quads as indents. It looked great, but boy was it tedious). I was ready to write this right after that, but, of course, I put it off, since I'm too busy to write blog posts for dour TAs and google search crawlers.

Now, after having studied for the midterm, I've started to come around and appreciate the value of the way lines in a proof are linked, at least as an introduction to formal logic. It's not like you can get away with writing decent proofs without at least a tacit understanding of inference rules, and in some sense, being introduced to it explicitly would have saved me some pain in a previous life. 

However, I do still have problems with the way proofs are being taught in this course. The whole formal background isn't discussed--inference rules were given as almost a side note in lecture, and the reasoning behind using statements like "assume" and "let" isn't explained any better than in a more standard introduction to proof. While its formal roots are showing, this course is not an introduction to formal logic. Things like "you don't get to choose x if you're trying to prove a universal" will be permanently burned into everyone's minds, but the fact that you can't choose \(x\) to depend on \(y\) in a statement like $$\exists\,x,\,\, \forall\, y$$ was barely mentioned, despite being less obvious.

At the same time, the rigidity of the structure makes proving things more difficult than it would be otherwise. Implication between lines is not always clear, so a statement like 
$$\text{Since } \lfloor y\rfloor \in \mathbb{Z} \text{ and } \lfloor y \rfloor \leq x \text{, } \lfloor y \rfloor \leq \lfloor x\rfloor $$  
becomes unnecessarily difficult and cumbersome to follow when split into tiny steps (see A2 solutions, for an example). 

It's kind of like asking someone to write an essay but limiting them to use certain keywords and format it in jot notes. It can be illustrative if the content is relatively simple, but as soon as things become difficult or more nuanced, it's more of a hindrance than it is a help. 

I know that an introduction to proofs can be a nightmare, and forcing people to conform to a rigid structure is useful in ensuring everyone understands how to introduce universals, existentials, and impications, but ultimately, learning to write proofs is difficult no matter what. Forcing a rigid structure on all proofs in the course without getting into the background of why such a structure is important really limits the content for little gain; there are countless proofs within grasp of the math prerequisites given for this course, but so far we've been limited to proofs about the floor function and products modulo an integer. One would hope that using in using a more unconventional approach to introducing proofs, it might more readily bring a student to a baseline level of knowledge, but I have some trouble believing that learning in this way generally prepares someone for more advanced topics any more effectively than another approach. As it stands, I feel like the majority of the three or so weeks spent covering proofs can be summarized in a few lines:

1. If proving a Universal -> write "assume x in [domain]", conclude "for all x ..."
2. If proving an Existential -> write "let x = __. Then x in [domain]", conclude "exists x ..."
3. If proving an Implication -> write "assume [antecedent]",conclude "A => C"

There's more to it than that, but the more difficult ideas (like what to do with conjunction and disjunction) have almost been left to the student to figure out--as they always are in an introduction to proof.

Week 4 Miscellany

The person next to me in tutorial asked if associativity worked between conjunction and disjunction. For example:
\[ P \wedge (Q \vee R) \overset{?}{\Leftrightarrow} (P \wedge Q) \vee R \]At first, I said "sure, why not?" not really thinking about it, but really, the two expressions mean different things.
\[ P \wedge (Q \vee R) \Leftrightarrow (P \wedge Q) \vee (P \wedge R) \\

(P \wedge Q) \vee R \Leftrightarrow (P \vee R) \wedge (Q \vee R)\]Namely, the second one is true whenever \(R\) is true. As a truth table,
\[\begin{array}{c c c | c | c}
P & Q & R & P \wedge (Q \vee R) & (P \wedge Q) \vee R \\ \hline
T & T & T & T & T \\
T & T & F & T & T \\
T & F & T & T & T \\
T & F & F & F & F \\
F & T & T & F & T \\
F & T & F & F & F \\
F & F & T & F & T \\
F & F & F & F & F \\
\end{array}\]Good to know.

Week 3

This past week focussed on conjunction, disjunction, negation, and implication. 

While I find conjunction and disjunction pretty straightforward, implication, in this context, doesn't come as readily. I learn best by writing things out and working through them, so that's what I'm going to do for implication.

The truth table for the implication \( P \Rightarrow Q \) is:
\[
\begin{array}{ r  r | c }

P & Q & P \Rightarrow Q \\ \hline

T & T & T \\

T & F & F \\

F & T & T \\

F & F & T \\
\end{array}\] As given in class, we also have \[ P \Rightarrow Q \;\Leftrightarrow\; \neg P \vee  Q\]
With the above we can check that the contrapositive is the same as the regular implication:
\[\begin{align*}

\neg Q \Rightarrow \neg P &\;\Leftrightarrow\; \neg \neg Q \vee \neg P \\
&\;\Leftrightarrow\; Q \vee \neg P \\
&\;\Leftrightarrow\; \neg P \vee Q
\end{align*}\]
Next, let's translate an equivalence into conjunction and disjunction, starting by splitting the bi-implication into two implications:
\[\begin{align*}

P \Leftrightarrow Q &\;\Leftrightarrow\; ( P \Rightarrow Q ) \wedge (Q \Rightarrow P \\

&\;\Leftrightarrow\; (\neg P \vee Q) \wedge (\neg Q \vee P)\\

&\;\Leftrightarrow\; (\neg P \wedge \neg Q) \vee (\neg P \wedge P) \vee (Q \wedge \neg Q) \vee (Q \wedge P)\\

&\;\Leftrightarrow\; (\neg P \wedge \neg Q) \vee (P \wedge Q)


\end{align*}\]What about the transitive property?
\[\begin{align*}
((P \Rightarrow Q) \wedge (Q \Rightarrow R)) &\;\Rightarrow\; (P\Rightarrow R)\\

(\neg P \vee Q) \wedge (\neg Q \vee R) &\;\Rightarrow\; (\neg P \vee R)\\

\neg ((\neg P\vee Q) \wedge (\neg Q \vee R) &\;\,\vee\; (\neg P \vee R)\\

\neg(\neg P\vee Q) \vee \neg(\neg Q \vee R) &\;\,\vee\; (\neg P \vee R)\\

(P \wedge \neg Q) \vee (Q \wedge \neg R) &\;\,\vee\; (\neg P \vee R)\\

\end{align*}\]
as a truth table:
\[\begin{array}{c c c | c c c | c }
P & Q & R & (P \wedge \neg Q) & (Q \wedge \neg R) & (\neg P \vee R) & (P \wedge \neg Q) \vee (Q \wedge \neg R) \vee (\neg P \vee R)\\\hline
T & T & T & F & F & T & T \\
T & T & F & F & T & F & T \\
T & F & T & T & F & T & T \\
T & F & F & T & F & F & T \\
F & T & T & F & F & T & T \\
F & T & F & F & T & T & T \\
F & F & T & F & F & T & T \\
F & F & F & F & F & T & T \\

\end{array}\]So it's a tautology. Great. (It would have been easier to just go straight to a truth table, but let's call it "good practice").

Finally, how does it look for \( P\Rightarrow (Q\Rightarrow R)\)?
\[\begin{align*}
P\Rightarrow (Q\Rightarrow R) &\;\Leftrightarrow\; \neg P \vee (\neg Q \vee R) \\

&\;\Leftrightarrow\; (\neg P \vee \neg Q) \vee R \\

&\;\Leftrightarrow\; \neg (P \wedge Q) \vee R \\
&\;\Leftrightarrow\; (P \wedge Q) \Rightarrow R\\

\end{align*}
\]
That's all I can really think of right now. A lot of this stuff is easier to show by just writing up a truth table, but I learn better if I can think about things multiple ways. Also, a truth table would show that \[ P \Rightarrow (Q \Rightarrow R)) \;\Leftrightarrow\; (P\Rightarrow R) \vee (Q\Rightarrow R)\] but I haven't figured out how to get there by manipulating terms.

Let's be precise.

We're now a week into the course, and we've been talking a lot about sets and statements about sets. A lot of this has revolved around English language or Python statements about sets, such as 

     not all({x in S2 for x in S1})

And

      Some male employee earns over 42,000.


While discussing sets in a way any English speaker might understand is useful, it helps me, personally, to put such statements into the cold, precise language of math.

Towards this goal, we'll start off by introducing some terminology. Then we'll move to applying the terminology to statements encountered in class. Finally we'll end with a brief discussion of why this sort of thing is useful.

Terminology

We'll use the standard \(\cup\) and \(\cap\) to denote set union and intersection, respectively. In other words: 
$$ \begin{align*} x \in A \cup B & \; \Leftrightarrow \; x \in A \text{ or } x \in B\ \\ x \in A \cap B & \; \Leftrightarrow \; x \in A \text{ and } x \in B \end{align*} $$
We'll also use \(\overline{X}\) to denote the complement of \(X\) (that is, not \(X\)), and \(\varnothing\) to denote the empty set.

The Meat

With this terminology, it's not too hard to translate statements used in the course. We'll be talking about two sets, \(S_1\) and \(S_2\).
$$\begin{align*} \text{''all } S_1 \text{ in } S_2 \text{''} & \;\Leftrightarrow\; S_1 \cap S_2 = S_1 \\ \text{''some/any } S_1 \text{ in } S_2 \text{''}  &\; \Leftrightarrow\; S_1 \cap S_2 \neq \varnothing  \\ \text{''no/none } S_1 \text{ in } S_2 \text{''} &\;\Leftrightarrow\; S_1 \cap S_2 = \varnothing \end{align*}$$ Negating these is easy—switch \( = \) to \(\neq\) and vice versa:
$$\begin{align*} \text{''not all } S_1 \text{ in } S_2 \text{''} & \;\Leftrightarrow\; S_1 \cap S_2 \neq S_1 \\ \text{''not some/any } S_1 \text{ in } S_2 \text{''}  &\;\Leftrightarrow\; S_1 \cap S_2 = \varnothing  \\ \text{''not no/none } S_1 \text{ in } S_2 \text{''} &\;\Leftrightarrow\; S_1 \cap S_2 \neq \varnothing \end{align*}$$ 
Applied to the statement at the beginning, "Some male employee earns over $42,000", we have, with \(M\) as the set of male employees and \(O\) as the set of employees earning over $42,000, 
$$ M \cap O \neq \varnothing$$
This also allows us to evaluate nonsense like "Not some not male employees earn not more than $42,000":
$$ \overline{M} \cap \overline{O} = \varnothing \; \Leftrightarrow \; F \cap L = \varnothing$$
where we have used (keeping in mind that the complement means "not", in a sense) \(F\) as the set of female employees (assuming all non-male employees are female) and \(L\) as the set of employees earning less than $42,000. In plain language, we have the statement "No female employees earn less than $42,000". 

Finally, an added bonus is that this way of thinking makes Venn diagrams damn easy.

It's a lot easier to translate a statement like "some male employees earn more than $42,000" onto the diagram now. Let the set of male employees be \(S_1\) and the set of high earners be \(S_2\). Then we have \(S_1 \cap S_2 \neq \varnothing\). In other words, the middle region must be occupied.

If you have any questions/thoughts or see any errors, leave me a comment.