\documentclass{article}
\input{preamble.tex}
\usepackage{url}
\title{Day 3}
\date{Wednesday May 23, 2012}
\newcommand{\df}{\textbf}
\def\Display{\@empty}
\newcommand{\Hide}[2]{\ifx \Display\undefined \strut \\ \vspace{#1} \\ \strut \else { \color{darkred} #2} \fi }
\begin{document}
\maketitle
Objectives:
\begin{itemize}
\item Learn the basics of Propositional Logic
\item Learn the basic building blocks of proofs (specifically, direct proofs)
\end{itemize}
\section{Propositional Logic}
Today we introduce the concepts of propositional logic. We do this because a basic understanding of propositional logic is essential to understanding how a mathematical statement is formed and proved.
\subsection{Atoms}
We begin with the discussion of an atom. Note that the etymology of the word atom is Greek, for something that can not be further divided. In physics and chemistry, atomic is the word to describe the basic unit of matter. Keep this in mind for our mathematical discussion.
\begin{dfn}
An \df{atom} is something which is either true of false and whose truth can be checked independently from other statements.
\end{dfn}
Atoms are the basic unit of mathematics. Let's do some examples.
\begin{eg}
The following are some atoms:
\Hide{1in}{
\begin{itemize}
\item The sun is up.
\item $2 < 3$
\item $2 + 2 = 4$
\item The chair is purple.
\end{itemize}
}
\end{eg}
\begin{dfn}
An \df{atomic variable} is a variable which stands in place for an atomic statement. That is, atomic variables are variables which can either be true or false.
\end{dfn}
\begin{dfn}
We also have two special atoms: $\top$ and $\bot$. These stand for \df{true} and \df{false} respectively.
\end{dfn}
\begin{dfn}
A \df{statement} is something which is either true or false. Therefore, all atoms are statements, but statements incldue things which are not atoms.
A \df{connective} is an operation which can join together statements to make a new statement.
\end{dfn}
\subsection{Connectives}
In classical mathematics, there are four connectives.
\subsubsection{And}
\df{And} is a connective which acts on two statements, and is true when both of the statement it joins are true. These statements are also called \df{conjunctions}
\begin{eg}
\mbox{}
\begin{itemize}
\item ``It is sunny outside and it is not raining'' this is a statement which is (hopefully) true right now!
\item ``$(3 > 2)$ and $(10 < 4)$'' this is a statement that is false. Why?
\end{itemize}
\end{eg}
In a formal context, we use the $\oand$ symbol to stand for and.
\begin{eg}
In the above example, we could have written
\[
(3 > 2) \oand (10 < 4)
\]
\end{eg}
\begin{rmk}
A way to remember this is and is because $\oand$ looks like the letter A!
\end{rmk}
\subsubsection{Not}
``Not'' is a connective which acts on only one statement. It is true exactly when the statement it acts on is false. These statements are also called \df{negations}
\begin{eg}
\mbox{}
\begin{itemize}
\item ``It is not raining outside'' this statement is hopefully true, since we want the statement ``It is raining outside'' to be false.
\item ``Not $2 > 3$'' this statement is true, since $2>3$ is a false statement.
\item ``Not( $(2 < 6) \oand (2>3)$ )'' is this statement true or false?
\end{itemize}
\end{eg}
In a formal context we use the $\neg$ symbol to stand for not.
\begin{eg}
In the above example, we could have written
\[
\neg(2 > 3)
\]
\end{eg}
\subsubsection{Or}
``Or'' is a connective which acts on two statements, and is true when either one or both of the statements it joins are true. This statements are also called \df{disjunctions}
\begin{eg}
\mbox{}
\begin{itemize}
\item ``They lights are on in this room or the lights are off in this room.'' This is a true statement, because the lights are on in this room!
\item ``We are having fun or we are doing math.'' This statement is true, because we are both having fun and doing math.
\item ``It is either raining outside or not raining outside.'' This statement is true since it will always be the case that one of these statements is true.
\end{itemize}
\end{eg}
\begin{rmk}
We see the first difficulty in proving ``Or'' statements. The last statement above is a true statement, but despite knowing that one of the two statements is true we have no idea which! Therefore, ``or'' statements are almost exclusively non-constructive in nature; that is, we can know an ``or'' statement is true without being able to construct exactly which of the two things it joins are true.
\end{rmk}
\begin{eg}
Let $x$ be a real number. Then we can see the following statement is true:
\[
(x > 2) \mbox{ or } (x<5)
\]
But, until we know the value of $x$, we don't know which of the two statements are true!
\end{eg}
In a formal context we use the $\oor$ symbol to stand for or.
\begin{eg}
In the above example, we could have written
\[
(x > 2) \oor (x < 5)
\]
\end{eg}
\subsubsection{Implies}
``Implies'' is an interesting connective which acts on two statements. It is true if one can assume that the first statement is true and prove that the second is true. These statements are also called \df{implications}
\begin{rmk}
Implies is very interesting. First off it is the first asymmetric connective. What do you suppose that means?
\Hide{1in}{
Well, it smeans ``A implies B'' is a completely different statement than ``B implies A.''
}
Secondly, it is essentially defined in terms of proofs. We'll see a lot of examples to make this sense and pragmatic, but let's first do some examples to gain some intuition.
\end{rmk}
\begin{itemize}
\item ``If it is raining, then the ground is wet'' or ``It is raining imlies the ground is wet.'' This statement is true. You suppose it was raining, so we live in a unvervise where rain is falling from the sky. In that universe, the ground would be wet!
\item ``If I'm hot then it is sunny.'' This statement is false. How would you show it?
\Hide{1cm}{
Well, you just consider a universe where you are hot but it isn't sunny. Maybe you're standing next to a fire, or wearing too many layers. Or maybe it's just a hot, cloudy summer day.
}
\item ``If $x>0$ then $x>-1$'' Suppose that you lived in a universe where the first statement were true. Then $x$ would be larger than $0$. $0$ itself is larger than $-1$, so $x$ must be larger than $-1$.
\end{itemize}
As you can maybe see, implications are tricky business. But, they're the most useful type of statements in mathematics. In fact, without implications we can't ever state as much stuff as we'd every want.
In a formal context we use the $\to$ symbol to stand for implies.
\begin{eg}
In the above example, we could have written
\[
(x>0) \to (x>-1)
\]
\end{eg}
\begin{dfn}
If $A\to B$ we say that $A$ is \df{sufficent} for $B$, since knowing $A$ suffices to know $B$. Therefore, if you imagine we really wanted to prove $B$, and we knew $A\to B$ it would suffice to prove $A$.
We say that $B$ is \df{neccessary} for $A$, since $A$ being true requires that $B$ is true.
\end{dfn}
\subsection{Proving Statements}
Now that we understand what a statement is, and what components make up a statement, our next logical question should be how do I prove a statement is true?
\subsubsection{Direct versus Indirect}
We've already stated that ``or'' statements maybe be difficult to prove as one may not know which of the two statements it joins is true. This highlights an important distinction between \df{direct proofs} and \df{indirect proofs}. For now, we are only going to be talking about direct proofs. Later, we will talk about indirect proofs.
\subsubsection{Contexts}
Now that we know the connectives. But, how can we prove anywhere without some assumptions? For example, is it true that $x^2 \geq 0$? Well, sort of, but we are assuming $x$ is a real number! We have to have assumptions to prove things.
\begin{dfn}
A \df{hypothesis} is statement which we assume to be true. We often have many hypotheses during a proof.
While writing a proof, the \df{context} is all of the hypotheses that you currently have. We are going to see that your context changes while writing the proof. But at any stage of the proof, there is a context.
Therefore, the goal of a proof can be seen as getting a particular statement into our context! There's a lot of ways to do this.
\end{dfn}
It's difficult to give a specific example without first talking about some particular proofs.
\subsubsection{Proving Implications Directly}
The definition of what an implication is basically told us how to prove them.
To prove an implication $A\to B$, you add $A$ to your current context, and then try to prove $B$.
\begin{thm}
Let $A$ be a statement. Then $A\to A$
\end{thm}
\begin{proof}
\Hide{1in}{
We are trying to prove the statement $A\to A$. Therefore, we add $A$ to our present context (ie. we assume $A$ is true) and we then try to prove $A$.
At this stage, we have $A$ in our context, which means we are assuming $A$ is true. We are trying to prove $A$ is true. Therefore, we're done!
}
\end{proof}
\subsubsection{Proving Conjections Directly}
To prove a conjunction, like $A\oand B$ you must prove $A$ and you must prove $B$.
\subsubsection{Proving Disjunction Directly}
To prove a disjunction, like $A\oor B$ directly you must prove $A$ or you must prove $B$.
\begin{rmk}
Remember, this is often impossible, as in ``It is raining or it is not raining.''
\end{rmk}
\subsubsection{Proving Negations Directly}
In order to prove a negation, like $\neg A$ you add $A$ to your current context, and then prove any statement and its negation (ie. a \df{contradiction})
\begin{rmk}
This is, ostensibly, a tricky thing. But, it makes sense. To prove $\neg A$, you really want to assume $A$ and get a contradiction. This would tell you that there's no possible way to find a unvierse where $A$ is true!
\end{rmk}
\subsubsection{Lots of Examples!}
\begin{itemize}
\item $A \to A$
\begin{proof}
\Hide{.2in}{A direct proof of $A\to A$ relies on first assuming $A$ and then proving $A$. But, if we assume $A$ is true, then we immediately have $A$ is true!}
\end{proof}
\item $A \to (A \oor B)$
\begin{proof}
\Hide{.2in}{As before, we are trying to prove an implication. So, to prove it directly, we assume $A$ and seek to prove $A\oor B$. To prove $A\oor B$ we want to either prove $A$ or $B$. But we know $A$ is true as it is in our current context. Thus, we have $A\oor B$.}
\end{proof}
\item $A \to (B \to (A\oand B))$
\begin{proof}
\Hide{.2in}{We are trying to prove an implication. Thus we add $A$ to our current context, and seek to prove $B\to (A\oand B)$. This is also an implication. So we add $B$ to our context. Thus our context contains $A$ and $B$, and we want to prove $A\oand B$. But, we are assuming $A$ and $B$, thus we have $A\oand B$, which is what we want!}
\end{proof}
\end{itemize}
\subsection{Using Hypotheses}
So far, the only hypotheses that we've been using are atoms. But, how do we use the hypothesis that $A\to B$, or $A\oand B$.
\subsubsection{Using Conjunctions Directly}
The conjunction is the easiest statement to know how to prove, and it's also the easiest to use. Remember that you prove a conjunction by proving each part. So, if $A\oand B$ is in your context, How can you use it?
\Hide{2cm}{
Well, you can add $A$ and $B$ individually to your context! Put another way, if you are assuming $A\oand B$ you might as well individually assume $A$ and $B$.
}
\begin{eg}
\[
(A\oand B) \to B
\]
\begin{proof}
\Hide{.1in}{We assume $A\oand B$ and seek to prove $B$. As we know $A\oand B$, we can conclude $B$, so we are done. }
\end{proof}
\end{eg}
\subsubsection{Using Implications Directly}
Say that in your present context you have $A\to B$. Think about what implications are suppose to mean. How do you think you use it?
\Hide{2cm}{
To use $A\to B$, you would get $A$ and $A\to B$ in your context. Then, you conclude $B$ since $A\to B$ really means that if you knew $A$ is true than you know $B$ is true!
}
\begin{eg}
\[
(A \to B) \to ( (A\oand C) \to (B\oand C) )
\]
\begin{proof}
\Hide{1in}{This is a long formula, so it helps to unravel it one level at a time. Not we are are trying to prove an implication at the outer-most level. So we assume $A\to B$ and seek to prove $(A\oand C) \to (B\oand C)$. This is also an implication, so we assume $A\oand C$ and try to prove $B\oand C$. So, currently in our context is: $(A\to B)$ and $A\oand C$.
We have already said how to use a conjunction. We know $A\oand C$, so we know $A$ and we know $C$. In particular, we know $A\to B$ and we know $A$. Thus, we know $B$. Therefore, we know $B\oand C$, which is what we wanted. }
\end{proof}
\end{eg}
\subsubsection{Using Negations Directly}
If we have $\neg A$ in our context, how can we go about using it?
\Hide{2cm}{
Well, remember, if we have $\neg A$ then we know that $A$ must be false. So, if we could somehow get both $A$ and $\neg A$ in our context, then our world explodes! This is called a contradiction. From a contradiction, we can prove anything we wish.
}
\begin{eg}
\[
\neg A \to ( A \to B )
\]
\begin{proof}
\Hide{.5in}{We assume $\neg A$ and try to prove $A\to B$. To prove $A\to B$, we assume $A$ and prove $B$. Our current context is $\neg A$ and $A$. Because we have $\neg A$ and $A$, we can conclude any sentence we wish. Therefore, we conclude $B$.}
\end{proof}
\end{eg}
\subsubsection{Using Disjunctions Directly}
If you have $A\oor B$ in your context, how could you go about using it?
\Hide{3cm}{
Well, remember, you don't know exactly which one of $A$ and $B$ is true, but you know one of them is. Therefore, you can split your proof into two parts.
In one of the parts, you would have the same context, but also $A$. And in the other part, you'd have the same context but also $B$. This is called a \df{proof by cases}.
}
Example:
\[
(A \oor B) \to ( \neg A \to B )
\]
\begin{proof}
\Hide{2in}{We assume $A \oor B$ and seek to prove $\neg A \to B$. Because we are trying to prove $\neg A \to B$, we can assume $\neg A$ and try to prove $A$. Here, we use $A\oor B$, and do cases.
If we assume $A$, and notice we are assuming both $A$ and $\neg A$. Thus we can conclude anything we wish. In particular, we can conclude $B$. This completes this case.
If we assume $B$, then we have $B$ outright. This completes this case.
Thus, in either case, we have $B$. This completes the proof. }
\end{proof}
\subsection{Summary}
Here's a little table which hopes to summarize how to direct proofs:
\begin{center}
\begin{tabular}{c | p{2in} | p{3in} }
\multicolumn{3}{c}{Summary of Direct Proofs} \\ \hline
Formula & \multicolumn{1}{c | }{To Prove} & \multicolumn{1}{c}{To Use if in context to Prove $C$} \\ \hline
$A\oand B$ & Prove $A$ and Prove $B$ (both) & Add $A$ to context and Prove $C$ \newline or \newline Add $B$ to context and Prove $C$ \newline (you can do either ) \\ \hline
$A\oor B$ & Prove $A$ or Prove $B$ (either) & Do Case on whether $A$ is true or $B$ is true: \newline Add $A$ to context and Prove $C$ \newline and \newline Add $B$ to context and Prove $C$ \\ \hline
$A\to B$ & Add $A$ to context. Prove $B$ & If $A$ is in your context, you may Add $B$ to your context, and prove $C$ \\ \hline
$\neg A$ & Add $A$ to context. Prove $\bot$ & If $A$ is in your context, you made add any formula to your context \\ \hline
\end{tabular}
\end{center}
\begin{rmk}
Remember, it's almost always unrealistic to prove statements like $A\oor B$ directly. We'll talk about methods to do that next time.
Also, it is often unrealistic to prove $A\to B$ directly.
The others are almost always proved directly.
\end{rmk}
\subsection{Lots of Examples}
\begin{eg}
\[
(A \oor B) \to ( (\neg B \oand A) \to C )
\]
\begin{proof}
\Hide{2in}{
We begin by assuming $(A\oor B)$ and then we try to prove $( (\neg B \oand \neg A) \to C )$. This iteself is an implication, so we assume $\neg B \oand \neg A$ and then we try to prove $C$.
Well, our current context is $(A\oor B)$ and $(\neg B \oand \neg A)$. We have not a lot of choice: we need to do cases on $A\oor B$.
Suppose $A$ is true. Then in our current context we have $\neg B\oand \neg A$. Therefore, we can say $\neg B$ and $\neg A$ are both true. So we have $A$ and $\neg A$. This is a contradiction, so we can conclude $C$.
Suppose $B$ is true. Similarly, we can add $\neg B$ to our context. Thus we have $B$ and $\neg B$ in our context, thus we can conclude $C$.
}
\end{proof}
\end{eg}
\begin{eg}
\[
(A \to B) \to ( (B\to C) \to (A \to C) )
\]
\begin{proof}
\Hide{3in}{
Assume $A\to B$. I want to prove $(B\to C) \to (A\to C)$. Well, assume $B\to C$. Now I want to prove $A\to C$. Well, assume $A$.
Now, I am assuming: $A\to B$, $B\to C$, and $A$. Since I have $A\to B$ and $A$, I have $B$,. And since I now have $B$ and I had $B\to C$ I have $C$, which is what I wanted!
}
\end{proof}
\end{eg}
\begin{eg}
\[
(A\to (B\to C)] \to ( [A\to B] \to (A \to C) )
\]
\begin{proof}
\Hide{3in}{
We are trying ot prove an implication. So we add $[A\to (B\to C)]$ to our context and try to prove $[A\to B] \to (A \to C)$. We are still trying to prove an implication, so we add $A\to B$ to our context and try to prove $A\to C$. We are STILL trying to prove an implication, so we add $A$ to our context, and try to prove $C$.
Now, our current context is: $A\to (B \to C)$, $A\to B$ and $A$. Since we have $A\to B$ and $A$ in our context, we can add $B$ to our context. Since we have $A\to (B\to C)$ and $A$ in our context, we can add $B\to C$ in our context.
Therefore, right now we have the following assumptions: $B$ and $B\to C$. Therefore, we have $C$.
}
\end{proof}
\end{eg}
\begin{eg}
\[
(A\oor (B\to A)) \to ( B \to A )
\]
\begin{proof}
\Hide{3in}{
Since we are proving an implication, I assume $A\oor (B\to A)$ and Try to prove $B\to A$. This is an implication, so I assume $B$ and try to prove $A$.
My current context is $A\oor(B\to A)$ and $B$. so I do cases based on the first.
If I have $A$, then I have proved $A$, which is what I wanted.
Otherwise, I have $B\to A$. $B$ is also in my context, so I have $A$, which is what I wanted.
}
\end{proof}
\end{eg}
\subsection{Bi-implication}
\begin{dfn}
A \df{bi-implication} or \df{equivalence} is a statement that stays one statement exacltly when the other one is. If $A$ and $B$ are statements, we write $A\bimp B$ for this.
\end{dfn}
\begin{rmk}
There's nothing special about proving a bi-implication. $A\bimp B$ is short hand for:
\[
(A \to B) \oand (B\to A)
\]
We will do more examples next time of this notion, on why it is useful.
\end{rmk}
\end{document}