%% LyX 1.1 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[english]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{amsmath}
\usepackage{babel}
\usepackage{amssymb}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\providecommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\@}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\usepackage{ccfonts}
\usepackage{fullpage}
\usepackage{endnotes}
\renewcommand{\bfseries}{\scshape}
\renewcommand{\footnote}{\endnote}

\makeatother
\begin{document}

\title{CSC165H, Mathematical expression and reasoning for computer science\\
week 6}

\maketitle
Gary Baumgartner and Danny Heap

heap@cs.toronto.edu

SF4306A

416-978-5899

http://www.cs.toronto.edu/\textasciitilde{}heap/165/S2005/index.shtml


\section*{Midterm preparation}

\begin{itemize}
\item The midterm (next Thursday from 6:10--7:00) will be 3 questions, worth
5 points each, lasting 50 minutes, during tutorial.
\item Midterm material is based on Lectures 1--6 (see web page) and Assignments
1 and 2 (see solutions on web page). You should review the lecture
summaries, the assignment solutions, and quiz solutions (to be posted
soon).
\item I aim to have the marked midterms back to you less than 10 days, and
a summary of your term marks thus far in the course will be available
at that time.
\end{itemize}

\section*{More proof structure}

We continue to develop a structured format for presenting proofs in
this course. The intention is to provide you with an example of proof
structure that can guide your future work either (a) writing proofs
of your own, or (b) evaluating proofs written by others. The structure
presented here isn't meant to restrict you to a particular way of
writing and presenting proofs, but rather to provide a framework to
decide whether a given proof has all its working parts intact.


\subsubsection*{negation (contrapositive)}

Last time we described the search for a chain of implications of the
form \( p(x)\Rightarrow r_{1}(x)\Rightarrow r_{2}(x)\Rightarrow \cdots  \),
in order to eventually prove \( \forall x\in D,p(x)\Rightarrow q(x) \).
To help form promising links in this chain, consider whether implications
such as \( \forall x\in D,t(x)\Rightarrow \neg r_{k}(x) \). You recognize
this as the contrapositive of \( \forall x\in D,r_{k}(x)\Rightarrow \neg t(x) \),
so if you have \( r_{k}(x) \) on your list, you can now add \( \neg t(x) \).

Symmetrically, we were looking (from the other end) for a chain of
the form \( s_{n}(x)\Rightarrow \cdots \Rightarrow s_{1}(x)\Rightarrow q(x) \).
It helps to consider implications of the form \( \forall x\in D,\neg s_{k}(x)\Rightarrow t(x) \),
since this is the contrapositive of \( \forall x\in D,\neg t(x)\Rightarrow s_{k}(x) \),
adding another link to the chain.


\subsubsection*{bi-implication}

Even when searching for an implication, adding bi-implication links
is useful. Consider\[
\forall x\in D,r_{k}(x)\Leftrightarrow r_{k+1}(x)\]


This is the conjunction of two implications, so that if \( r_{k}(x)\Rightarrow q(x) \)
then \( r_{k+1}(x)\Rightarrow q(x) \), which means that \( r_{k+1} \)
is a {}``dead end'' if and only if \( r_{k} \) is. This helps trim
down the search tree by leading to fewer dead ends.


\subsubsection*{An odd example revisited}

Last week we considered the implication {}``\( \forall n\in \mathbf{N}, \)
\( n \) odd \( \Rightarrow  \) \( n^{2} \) odd,'' and its converse.
We developed a direct proof of the implication%
\footnote{Let \( n\in \mathbf{N} \), and \( n \) is odd.

\begin{quote}
Then, for some \( j\in \mathbf{N} \), \( n=2j+1 \) (definition of
odd number).
\begin{quote}
So \( n^{2}=4j^{2}+2j+1 \) (definition of squaring a number)

So \( n^{2}=2(2j^{2}+j)+1 \) (distributive law)

So there exists a natural number \( k=2j^{2}+j \) such that \( n^{2}=2k+1 \).
(\( \mathbf{N} \) is closed under addition and multiplication)

So \( n^{2} \) is odd.
\end{quote}
Thus \( \forall n\in \mathbf{N} \), \( n \) odd \( \Rightarrow  \)
\( n^{2} \) odd.\end{quote}
}, and found that the same template could not be applied to prove the
converse (even though the converse is true). This asymmetry shows
that the search through the implication trees from \( p \) to \( q \)
does not necessarily follow the same path as from \( q \) to \( p \),
even when both paths exist and \( p\Leftrightarrow q \).

However, it seems aesthetically disturbing that when \( p\Leftrightarrow q \)
we don't find a doubly-linked list of implications connecting them.
One of your classmates came up with an approach that allows this symmetry
(I've modified it slightly)

\begin{description}
\item [Claim:]\( \forall n\in \mathbf{N} \), \( n \) odd \( \Leftrightarrow  \)
\( n^{2} \) odd.
\item [Proof:]~
\end{description}
\begin{quote}
Let \( n\in \mathbf{N} \).
\begin{quote}
Then

\( n^{2} \) is odd

is equivalent to

\( \exists k\in \mathbf{N} \) such that \( n^{2}=2k+1 \) (definition
of odd natural numbers);

is equivalent to

\( n^{2}-1=2k \) is even (definition of even integer),

is equivalent to

\( (n-1)(n+1) \) is even (complete the square);

is equivalent to

\( (n-1) \) is even or \( (n+1) \) is even (\( \Rightarrow  \)
if prime number 2 divides a product, it divides some factor) (\( \Leftarrow  \)
definition of even);

is equivalent to

\( (n-1) \) is even or \( (n+1)-2=(n-1) \) is even (integer \( i \)
is even if and only if \( i-2 \) is even);

is equivalent to

\( (n-1) \) is even (idempotent law);

is equivalent to

\( n-1=2j \) for some integer \( j \) (definition of even)

is equivalent to

\( n=2j+1 \) for some integer \( j \);

is equivalent to

\( n \) is odd 
\end{quote}
Thus \( n^{2} \) is odd \( \Leftrightarrow  \) \( n \) is odd.

Since \( n \) is an arbitrary natural number,

\( \forall n\in \mathbf{N}, \) \( n^{2} \) odd \( \Leftrightarrow  \)
\( n \) odd.
\end{quote}

\subsubsection*{Direct proof structure of the universal}

Our general form of a direct proof of the implication \( \forall x\in D,\, \, p(x)\Rightarrow q(x) \)
is:

\begin{quote}
Let \( x\in D \). (introduce variable \( x \) with scope indicated
by indentation).
\begin{quote}
Suppose \( p(x) \) (indentation indicates where \( p(x) \) is assumed
true)
\begin{quote}
(fill in the proof of \( q(x) \))
\end{quote}
Hence \( p(x)\Rightarrow q(x) \).
\end{quote}
Since \( x \) is an arbitrary element of \( D \), \( \forall x\in D,p(x)\Rightarrow q(x) \).
\end{quote}
Here's an example.

\begin{quote}
Let \( \mathbf{R} \) be the set of real numbers. \( \forall x\in \mathbf{R},x>0\Rightarrow 1/(x+2)<3 \).
\end{quote}
Structure the proof as above:

\begin{quote}
Let \( x\in \mathbf{R} \).
\begin{quote}
Suppose \( x>0 \)
\begin{quote}
(prove \( 1/(x+2)<3 \))

Therefore \( 1/(x+2)<3 \).
\end{quote}
Hence \( x>0 \) \( \Rightarrow  \) \( 1/(x+2)<3 \).
\end{quote}
Since \( x \) is an arbitrary element of \( \mathbf{R} \), \( \forall x\in \mathbf{R},x>0\Rightarrow 1/(x+2)<3 \).
\end{quote}
Of course, you should unwrap the sub-proof that \( 1/(x+2)<3 \).

\begin{quote}
Let \( x\in \mathbf{R} \).
\begin{quote}
Suppose \( x>0 \)
\begin{quote}
so \( x+2>2 \) (since \( x>0 \))

so \( 1/(x+2)<1/2 \) (since \( x+2>2 \) and \( 2>0 \))

so \( 1/(x+2)<3 \) (since \( 1/(x+2)<1/2 \) and \( 1/2<3 \))

Therefore \( 1/(x+2)<3 \).
\end{quote}
Hence \( x>0 \) \( \Rightarrow  \) \( 1/(x+2)<3 \).
\end{quote}
Since \( x \) is an arbitrary element of \( \mathbf{R} \), \( \forall x\in \mathbf{R},x>0\Rightarrow 1/(x+2)<3 \).
\end{quote}
Is the converse true (what is the converse)?%
\footnote{\( \forall x\in \mathbf{R},\, \, 1/(x+2)<3\Rightarrow x>0 \). False,
for example let \( x=-4 \) (Alex's suggestion), then \( 1/(-4+2)=-1/2<3 \)
but \( -4\not >0 \). Indeed, every \( x<-2 \) is a counter-example.
}

When no implication is stated, then we don't assume (suppose) anything
about \( x \) other than membership in the domain. For example, \( \forall x\in D,p(x) \)
has this proof structure:

\begin{quote}
Let \( x\in D \)
\begin{quote}
(prove \( q(x) \))

Hence \( q(x) \).
\end{quote}
Since \( x \) is an arbitrary element of \( D \), \( \forall x\in D,q(x) \).
\end{quote}

\subsubsection*{Direct proof structure of the existential}

Consider the example \( \exists x\in \mathbf{R},x^{3}+2x^{2}+3x+4=2 \).
Since this is the existential, we need only find a single example,
and structure the proof as follows:

\begin{quote}
Let \( x=-1 \).
\begin{quote}
Then \( x\in \mathbf{R} \).

Also, \( x^{3}+2x^{2}+3x+4 \) \( = \) \( (-1)^{3}+2(-1)^{2}+3(-1)+4 \)
\( = \) \( -1+2-3+4 \) \( = \) \( 2 \).
\end{quote}
Since \( x\in \mathbf{R} \), \( \exists x\in \mathbf{R},\, \, x^{3}+2x^{2}+3x+4=2 \).
\end{quote}
The general form for a direct proof of \( \exists x\in D,p(x) \)
is:

\begin{quote}
Let \( x= \) {[}pick a specific value, unlike the universal{]}
\begin{quote}
Then \( x\in D \) {[}this may be obvious from choice of \( x \){]}.

prove \( p(x) \).

Hence \( p(x) \)
\end{quote}
Since \( x\in D \), \( \exists x\in D,p(x) \).
\end{quote}

\subsubsection*{Multiple quantifiers}

Multiple quantifiers cause multiple nesting. Consider \( \forall x\in D,\exists y\in D,p(x,y) \).
The corresponding proof structure is:

\begin{quote}
Let \( x\in D \)
\begin{quote}
Let \( y_{x}= \)(select something that helps prove \( p(x,y)) \)
\begin{quote}
Then \( y_{x}\in D \).

Also \( p(x,y_{x}) \)
\end{quote}
Since \( y_{x}\in D \), \( \exists y,p(x,y) \)
\end{quote}
Since \( x \) is an arbitrary element of \( D \), \( \forall x\in D,\exists y\in D,p(x,y) \).
\end{quote}
\newpage

\begingroup

\setlength{\parindent}{0pt}

\setlength{\parskip}{2ex}

\renewcommand{\enotesize}{\normalsize}

\theendnotes\endgroup
\end{document}
