\documentclass[10pt,twoside]{article}
\usepackage{amssymb}
\usepackage{epsf}
\input epsf
\def\ste{\enspace\enspace\enspace\enspace}
\def\pltw#1#2#3{\noindent#1.$\,\,\,$\hbox to 5cm{#2\hfill}$\qquad$instead
of #3} 
\def\pltwnd#1#2#3{\noindent#1$\,\,\,$\hbox to 5cm{#2\hfill}$\qquad$instead
of $\quad$ #3} 
\font\largebold = cmbx10 scaled \magstep1
\def\hugeee{\Huge}
\def\largerbold{\Large\bf}
\newcount{\quesco}
\newcommand{\sepa}{\medbreak
\begin{center}$\,$\hbox to5cm{\hrulefill}$\,$\end{center}
\medbreak}
\def\pline#1{\noindent #1}
\def\eqj#1#2#3{\hbox to 12cm{
\noindent\hbox to 3cm{\hfill $#1$}$\,\,=\,\,$\hbox to 6.5cm{$#2$\hfill}\hfill\fbox{\hbox to 1.3cm{\hfill\phantom{A}#3\phantom{A}\hfill}}}}
\def\eqpend{\hbox to 12cm{\hfill\pend\hbox to 1.3cm{\hfill}}}
\def\eqjn#1#2#3{\hbox to 12cm{
\noindent\hbox to 2cm{\hfill $#1$}$\,\,\phantom{=}\,\,$\hbox to 7.5cm{$#2$\hfill}\hfill\fbox{\hbox to 1.3cm{\hfill\phantom{A}#3\phantom{A}\hfill}}}}
\def\imply{\longrightarrow}
\def\bimply{\longleftrightarrow}
\def\lto{\longrightarrow}
\def\quesno{\the\quesco\global\advance\quesco by 1}
\def\wmo{{\large{\bf\em WMO}}}
\def\nin{\noindent}
\def\mnin{\medbreak\noindent}
\def\bnin{\bigbreak\noindent}
\newcounter{boxcount}
\setcounter{boxcount}{0}
\quesco=1
\newcommand{\boxon}[1]{\refstepcounter{boxcount}
\medbreak
\begin{center}
{\bf BOX NO. \theboxcount$\,$:\ \ #1.}
\end{center}
\medbreak}
\newcommand{\boxonnop}[1]{\refstepcounter{boxcount}
\medbreak
\begin{center}
{\bf BOX NO. \theboxcount$\,$:\ \ #1}
\end{center}
\medbreak}
\newcommand{\Ft}[1]{\footnote{\mynine\baselineskip 8pt #1}}
\def\vup{\vspace{-1mm}}
\def\imply{\longrightarrow}
\def\zz{\mathbb{Z}}
\def\kk{\mathbb{K}}
\def\qq{\mathbb{Q}}
\def\cc{\mathbb{C}}
\def\rr{\mathbb{R}}
\def\nn{\mathbb{N}} 
\def\itobf{\subsubsection}
\def\unde#1{\underbar{#1}}
\def\tto{\mbox{$\kern4pt\rightarrow\kern-14.3pt\mapsto\kern5pt$}}
\def\vepsi{V^{\beps,\eps,\delta}}
\def\vepsim{V^{\beps(m),\eps(m),\delta(m)}}
\def\kepsi{K^{\beps,\eps}}
\def\pepsi{P^{\beps,\eps}}
\def\phixeps{\Phi_x^{\beps}}
\newcommand{\bprn}{\begin{proof}}
\newcommand{\eprn}{\end{proof}}
\newenvironment{proof}{\noindent {\em Proof}.\ }{\medskip}
\def\So{{\rm So}}
\def\Ta{{\rm Ta}}
\def\Gr{{\rm Gr}}
\def\Do{{\rm Dom}}
\def\Im{{\rm Im}}
\def\acabx{AC([a,b],X)}
\def\cabx{C^0([a,b],X)}
\def\acomabx{AC_{\Omega}([a,b],X)}
\def\comabx{C_{\Omega}^0([a,b],X)}
\newcommand{\myput}{\input}
\newcommand{\authorsar}{\cite{antocell,bressancolombo,cellina,cellinaornelas,colomboetal,fry,ornelas}}
\newcommand{\dato}{\vskip 3cm
{\bf THIS IS A DRAFT.\\
\vskip 0.2cm
DO NOT QUOTE WITHOUT PERMISSION.\\
\vskip 0.2cm
Date of this draft: \today.}}
\renewcommand{\theequation}{\arabic{section}.\arabic{subsection}.\arabic{equation}}
\newcommand{\idx}{\index}
\renewcommand{\contentsname}{\hfil {%\small
{\bf Contents}}}
%\topmargin -1.5cm
\newcommand{\hjsdraft}{\hfill{\rm Math 300 -- 01 -- Fall 2002}}
\newcommand{\mpdraft}{{\rm Instructor's Notes, No. 1, 
September 5, 2002} \hfill }
\begin{document}
\markboth{\hjsdraft}{\mpdraft}\parskip 0pt
\def\lefquo{``} %``for home use
\newcommand{\tgt}{{T}^{2,\ge}}
\newcommand{\bi}{\begin{itemize}}
\newcommand{\comment}[1]{}
\newcommand{\ei}{\end{itemize}}
\def\beps{\bar\varepsilon}
\def\co{{\rm co}}
\def\cco{\overline{{\rm co}}}
\def\belo{\,\epsilon\,}
\def\lowsub#1{\lower 2pt\hbox{${_{#1}}$}}
\def\adj{{\rm Adj\,}}
\def\traj{{\rm Traj\,}}
\def\ctraj{{\rm CTraj\,}}
\def\arc{{\rm Arc\,}}
\def\carc{{\rm CArc\,}}
\def\bloi{{\cal BL}(\Omega,I)}
\def\blon{{\cal BL}(\rr^n,\rr)}
\def\bor{{\rm Bor}}
\def\leb{{\rm Leb}}
\def\blons{{\cal BL}(\rr^n,\rr;S)}
\def\mbloiy{{\cal M}_e(\bloi,Y)}
\def\blxr{{\cal BL}(X,\rr)}
\def\bbxr{{\cal B}(X\times\rr)}
\def\mblxr{{\cal M}(\blxr,Y)}
\def\cvf{TVVF}
\def\cvfadomi{TVVF_{AD}(\Om,I)}
\def\ndc{{\bf W}}
\def\togr{{\buildrel \rm igr \over \to}}
\newcommand{\halmos}{\rule{1ex}{1.4ex}}
\newcommand{\edo}{\end{document}}
%\newcommand{\indexentry}[2]{\smalltype #1,$\,$#2}
%\newcommand{\indexentry}[2]{#1,$\,$#2}
\newcommand{\eprnoen}{\hspace*{\fill}$\halmos$\medskip}
\newtheorem{ittheorem}{Theorem}
\newtheorem{itdef}{Definition} 
\newtheorem{itlem}{Lemma} 
\newtheorem{itprop}{Proposition}
\newtheorem{itcor}{Corollary}
\newtheorem{itrem}{Remark}
\newcounter{itfac}
\newcounter{itexam}
\newtheorem{myfact}[itfac]{Fact}
\newtheorem{myexample}[itexam]{Example}
\newtheorem{mytheorem}[ittheorem]{Theorem}
\newtheorem{mydefinition}[itdef]{Definition}
\newtheorem{mylemma}[itlem]{Lemma}
\newtheorem{myproposition}[itprop]{Proposition}
\newtheorem{mycorollary}[itcor]{Corollary}
\newtheorem{myremark}[itrem]{Remark}
\newcommand{\subssection}[1]{\subsection{#1}
   \setcounter{equation}{0}}
\newenvironment{theorem}{\begin{mytheorem}$\!\!\!{\bf .}$}{\end{mytheorem}}
\newenvironment{definition}{\begin{mydefinition}$\!\!\!{\bf .}$\rm}{\end{mydefinition}} %no-italics
\newenvironment{lemma}{\begin{mylemma}$\!\!\!{\bf .}$}{\end{mylemma}}
\newenvironment{corollary}{\begin{mycorollary}$\!\!\!{\bf .}$}{\end{mycorollary}}
\newenvironment{proposition}{\begin{myproposition}$\!\!\!{\bf .}$}{\end{myproposition}}
\newenvironment{remark}{\begin{myremark}$\!\!\!{\bf .}$\rm}{\end{myremark}} %no-italics
\newenvironment{fact}{\begin{myfact}$\!\!\!{\bf .}$}{\end{myfact}}
\newenvironment{example}{\begin{myexample}$\!\!\!{\bf .}$\rm}{\end{myexample}} %no-italics
\def\proofend{\hfill$\diamondsuit\,$}
\def\pend{$\quad${\bf THE END}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\beqn}{\begin{eqnarray}}
\newcommand{\eeqn}{\end{eqnarray}}
\newcommand{\beqno}{\begin{eqnarray*}}
\newcommand{\eeqno}{\end{eqnarray*}}
\newcommand{\bequot}{\begin{quotation}}
\newcommand{\equot}{\end{quotation}}
\newcommand{\rf}[1]{[\ref{#1}]} %bibliographical references
\newcommand{\text}[1]{\hbox{\rm \ #1\ \/}}
\newcommand{\beql}[1]{\begin{equation}\label{#1}}
\newcommand{\bt}{\begin{theorem}}
\newcommand{\bl}{\begin{lemma}}
\newcommand{\br}{\begin{remark}}
\newcommand{\bc}{\begin{corollary}}
\newcommand{\bp}{\begin{proposition}}
\newcommand{\bd}{\begin{definition}}
\newcommand{\bfact}{\begin{fact}}
\newcommand{\bex}{\begin{example}}
\newcommand{\ber}[1]{\begin{exercise}\label{#1}}
\newcommand{\bem}[1]{\begin{example}\label{#1}}  %Yes, 2 different ones...
\newcommand{\ec}{\end{corollary}}
\newcommand{\el}{\end{lemma}}
\newcommand{\er}{\end{remark}}
\newcommand{\et}{\end{theorem}}
\newcommand{\ed}{\end{definition}}
\newcommand{\ednoen}{\end{definition}}
\newcommand{\eprop}{\end{proposition}}
\newcommand{\epr}{\end{proof}}
\newcommand{\bpr}{\begin{proof}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  These are just for statements, no "qed" box is put in.
%%  (Also for when I have to finish something after a displayed equation
%%        or itemized.)
\newcommand{\ecs}{\end{corollary}}
\newcommand{\eers}{\end{exercise}}
\newcommand{\eexs}{\end{example}}
\newcommand{\eems}{\end{example}}
\newcommand{\els}{\end{lemma}}
\newcommand{\eles}{\end{lemmaex}}
\newcommand{\ers}{\end{remark}}
\newcommand{\ets}{\end{theorem}}
\newcommand{\eds}{\end{definition}}
\newcommand{\eps}{\end{proposition}}
\newcommand{\efact}{\end{fact}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\mybox}{\hfill \mbox{$\Box$}} %put at right margin (white square)
\newcommand{\qed}{\mybox} %put qed at right margin


\def\bptl{\pmb{\partial}}
\def\bptld{\pmb{\partial}^{{\cal D}}}
\def\nball{\bmath^n}  
\def\idnpball{{\rm id}_{\partial\bmath_n}}
\def\idrn{{\rm id}_{\rr^n}}
\def\id{{\rm id}}
\def\nno{\nn\cup\{0\}}
\def\dom{{\rm Dom}}
\def\msr{{\rm meas}}
\def\mitem{\medbreak\item}
\def\uitem{\vspace{-3mm}\item}
\def\oitem{\vspace{-1.2mm}\item}
\def\bigparo{\parindent=23pt}
\def\miitem{\medbreak\itemitem}
\def\medno{\medbreak\noindent}
\def\smalltype{\baselineskip=8pt}
\def\normaltype{\baselineskip=11pt}
\def\dekkertype{\baselineskip=0.54true cm}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%% Set up for Black Board Bold (\Bbb) font
% N.B. \Bbb works only in math mode
%\def\aabx{{\cal A}([a,b],X)}
\def\convav#1{{\onarr{{\rm av}#1}}}
\def\convtr{{\onarr{{\rm T}}}}
\def\Om{\Omega}
\def\mtraj{{\rm MTraj\,}}
\def\indi{\raise 1.5pt\hbox{$\chi$}}
\def\lowsub#1{\lower 2pt\hbox{${_{#1}}$}}
\def\pfo#1{{\cal P}_{#1}^{\rightarrow}}
\def\pba#1{{\cal P}_{#1}^{\leftarrow}}  
\def\aabx{{\cal A}(a,b,X)}
\def\icone{IC\kern0.1pt$^1$}
\def\iconeit{IC\kern0.5pt$^1$}
\def\mdno{\medbreak\noindent}
\def\inn{\int_{0}^{\tau}}
\def\bel{\beta}
\def\al{\alpha}
\def\eps{\varepsilon}
\def\bes{\bar\varepsilon}
\def\bdel{\bar\delta}\def\ffi{\varphi}
\def\al{\alpha}
%\font\twelvemsy=msym10 scaled\magstep1
%\font\tenmsy=msym10
%\font\sevenmsy=msym7
%\font\tinyfont=cmr6 
%\newfam\msyfam
%\textfont\msyfam=\twelvemsy
%\scriptfont\msyfam=\tenmsy
%\scriptscriptfont\msyfam=\sevenmsy
%\def\Bbb{\fam\msyfam}
%\def\nn{\Bbb{N}}
\def\nninf{\bar{\Bbb{N}}}
%\def\pmb#1{\setbox0=\hbox{$#1$}%
%  \kern-.025em\copy0\kern-\wd0
%  \kern.05em\copy0\kern-\wd0
%  \kern-.025em\raise.0433em\box0 }
\def\pmb#1{\setbox0=\hbox{$#1$}%
  \kern-.025em\copy0\kern-\wd0
  \kern.05em\copy0\kern-\wd0
  \kern-.025em\raise.0144em\box0 
  \kern-.025em\raise.0288em\box0 
  \kern-.025em\raise.0433em\box0 }
\def\pmbsus{\pmb}
\def\equaldef{\,{\buildrel \rm def \over =}\,}
\def\steero{$\sim$\kern -0.1cm$\sim$\kern -0.1cm$\sim$\kern-0.2cm$>$\kern-0.28cm$>$\kern-0.28cm$>$\kern-0.28cm$>$\kern-0.28cm$>$\kern-0.28cm$>$\kern-0.28cm$>$\kern0.1cm}
\def\PPhi{\pmb{\Phi}}
\def\steer#1#2{$#1$\steero$#2$}
\def\steert#1#2#3{\hbox{$#1$\hbox{\lower0.4ex\hbox{\steero}}\kern-0.59cm\raise0.53ex\hbox{$#2$}}\kern0.35cm$#3$}
%BLACKBOARD BOLD
\def\vbar{\mathchoice{\vrule height6.3ptdepth-.5ptwidth.8pt\kern-.8pt}
   {\vrule height6.3ptdepth-.5ptwidth.8pt\kern-.8pt}
   {\vrule height4.1ptdepth-.35ptwidth.6pt\kern-.6pt}
   {\vrule height3.1ptdepth-.25ptwidth.5pt\kern-.5pt}}
\def\fudge{\mathchoice{}{}{\mkern.5mu}{\mkern.8mu}}
\def\bbc#1#2{{\rm \mkern#2mu\vbar\mkern-#2mu#1}}
\def\bbb#1{{\rm I\mkern-3.5mu #1}}
\def\bba#1#2{{\rm #1\mkern-#2mu\fudge #1}}
\def\bb#1{{\count4=`#1 \advance\count4by-64 \ifcase\count4\or\bba A{11.5}\or
   \bbb B\or\bbc C{5}\or\bbb D\or\bbb E\or\bbb F \or\bbc G{5}\or\bbb H\or
   \bbb I\or\bbc J{3}\or\bbb K\or\bbb L \or\bbb M\or\bbb N\or\bbc O{5} \or
   \bbb P\or\bbc Q{5}\or\bbb R\or\bbc S{4.2}\or\bba T{10.5}\or\bbc U{5}\or
   \bba V{12}\or\bba W{16.5}\or\bba X{11}\or\bba Y{11.7}\or\bba Z{7.5}\fi}}
\def\eps{\varepsilon}
\def\pmath{{\rm I}\kern-.2em{\rm P}}
\def\emath{{\rm I}\kern-.2em{\rm E}}
\def\bmath{{\rm I}\kern-.2em{\rm B}}
\def\rarr{\rightarrow}
\font\mymagfivebf=cmbx10 scaled\magstep 5
\font\mymagfiverm=cmr10 scaled\magstep 5
\font\mymagfourbf=cmbx10 scaled\magstep 4
\font\mymagfourrm=cmr10 scaled\magstep 4
\font\mymagthreebf=cmbx10 scaled\magstep 3
\font\mymagthreerm=cmr10 scaled\magstep 3
\font\mymagtwobf=cmbx10 scaled\magstep 2
\font\mymagtworm=cmr10 scaled\magstep 2
\font\mymagonebf=cmbx10 scaled\magstep 1
\font\mymagonerm=cmr10 scaled\magstep 1
\font\mymagzerobf=cmbx10 scaled\magstep 0
\font\mymagzerorm=cmr10 scaled\magstep 0
\font\mymagfivesl=cmsl10 scaled\magstep 5
\font\mymagfiveit=cmti10 scaled\magstep 5
\font\mymagfoursl=cmsl10 scaled\magstep 4
\font\mymagfourit=cmti10 scaled\magstep 4
\font\mymagthreesl=cmsl10 scaled\magstep 3
\font\mymagthreeit=cmti10 scaled\magstep 3
\font\mymagtwosl=cmsl10 scaled\magstep 2
\font\mymagtwoit=cmti10 scaled\magstep 2
\font\mymagonesl=cmsl10 scaled\magstep 1
\font\mymagoneit=cmti10 scaled\magstep 1
\font\mymagzerosl=cmsl10 scaled\magstep 0
\font\mymagzeroit=cmti10 scaled\magstep 0
\font\mynine=cmr9
\font\myninebf=cmbx9
\font\mysmall=cmr7
\font\mysmallit=cmti7
\font\myverysmall=cmr5
\def\figcap#1#2{\medbreak
\centerline{ Figure {#1}:\ #2}
\vbox to 0.3true in{\vfill}}
\def\mybigbreak{\vskip 0.3true in}
\def\mynotsobigbreak{\vskip 0.2true in}
%THE FOLLOWING MACROS WERE USED FOR THE 1987 CDC PAPER
\def\lip{{\rm Lip}}
\def\lipomy{{\rm Lip}(\Omega,Y)}
\def\rarr{\rightarrow}
\def\rint{\enspace\rightarrow\!\!\!\!\!\!\int}
\def\lint{\enspace\leftarrow\!\!\!\!\!\int}
\def\pvarieta{{\cal  P}({\bf P},\eta)}
\def\pvdata{{\bf P}=(m,{\bf t},{\bf r},{\bf E})}
\def\sre{S_{\rho}(\eta)}
\def\vari{E=\{\eta_{\varepsilon}:\varepsilon\in C\}}
\def\varii{E_{i}=\{\eta_{i,\varepsilon_{i}}:\varepsilon_{i}\in C_{i}\}}
\def\tou{trajectory of uniqueness}
\def\uzsig{{\cal U}_{0}(\Sigma)}
\def\uosig{{\cal U}_{1}(\Sigma)}
\def\uksig{{\cal U}_{k}(\Sigma)}
\def\sigisz{$\Sigma$ is a $C^{0}$ system}
\def\sigiso{$\Sigma$ is a $C^{1}$ system}
\def\sigisk{$\Sigma$ is a $C^{k}$ system}
\def\czad{$C^{0}$-admissible}
\def\coad{$C^{1}$-admissible}
\def\ckad{$C^{k}$-admissible}
\def\mysys{\Sigma=(M,U,f)}
\def\vk{(V,\kappa)}
\def\vkk{(V,\kappa,K)}
\def\chm{{\cal CH}(M)}
\def\km{{\cal K}(M)}
\def\kz{{\cal K}_{0}}
%\def\kk{\kappa(K)}
\def\kv{\kappa(V)}
\def\rr{{\rm I}\kern-.2em{\rm R}}
\def\rrinf{\overline{\rr}}
\def\nn{{\rm I}\kern-.2em{\rm N}}
\def\nninf{\overline{\nn}}
\def\rrsmall{{\mysmall I}\kern-.2em{\mysmall R}}
\def\R{{\rm I}\kern-.2em{\rm R}}
\def\emath{{\rm I}\kern-.2em{\rm E}}
\def\pmath{{\rm I}\kern-.2em{\rm P}}
\def\lmath{{\rm I}\kern-.2em{\rm L}}
\def\ro{{\rr}}
\def\rn{{\rr}^{n}}
\def\rnn{{\rr}^{n\times n}}
\def\rnlow{{\rr}_{n}}
\def\vkinchm{(V,\kappa)\in {\cal CH}(M)}
\def\vkkinkm{(V,\kappa,K)\in {\cal K}(M)}
\def\vvkkinkm{{\cal V}=(V,\kappa,K)\in {\cal K}(M)}
\def\vvkkinkz{{\cal V}=(V,\kappa,K)\in {\cal K}_{0}}
\def\vinkm{{\cal V}\in {\cal K}(M)}
\def\vinkz{{\cal V}\in {\cal K}_{0}}
\def\xinkv{x\in\kappa(V)}
\def\xinkk{x\in\kappa(K)}
\def\fk{f^{\kappa}}
\def\fke{f_{\eta}^{\kappa}}
\def\fkeo{f_{\eta_{1}}^{\kappa}}
\def\fket{f_{\eta_{2}}^{\kappa}}
\def\fkei{f_{\eta_{i}}^{\kappa}}
\def\szve{\sigma_{{\cal V},\eta}^{0}}
\def\sove{\sigma_{{\cal V},\eta}^{1}}
\def\skve{\sigma_{{\cal V},\eta}^{k}}
\def\rzveoet{\rho_{{\cal V},\eta_{1},\eta_{2}}^{0}}
\def\roveoet{\rho_{{\cal V},\eta_{1},\eta_{2}}^{1}}
\def\rtildeoveoet{\tilde \rho_{{\cal V},\eta_{1},\eta_{2}}^{1}}
\def\rkveoet{\rho_{{\cal V},\eta_{1},\eta_{2}}^{k}}
\def\delzveoet{\delta_{\cal V}^{0}(\eta_{1},\eta_{2})}
\def\deloveoet{\delta_{\cal V}^{1}(\eta_{1},\eta_{2})}
\def\delkveoet{\delta_{\cal V}^{k}(\eta_{1},\eta_{2})}
\def\delkvee{\delta_{\cal V}^{k}(\eta,\eta)}
\def\delkv{\delta_{\cal V}^{k}}
\def\delkvj{\delta_{{\cal V}_{j}}^{k}}
\def\dome{{\rm Dom}(\eta)}
\def\domei{{\rm Dom}(\eta_{i})}
\def\domej{{\rm Dom}(\eta_{j})}
\def\domeo{{\rm Dom}(\eta_{1})}
\def\domet{{\rm Dom}(\eta_{2})}
\def\arrint{\rightarrow\kern -7.5pt\int}
\def\expint#1#2#3{e^{\arrint_{#1}^{#2}#3}}
\def\compo{\hbox{$\,${\myverysmall o}$\,$}}
\def\plplus{(+\kern-0.02in\compo\kern -0.02in\oplus)}
\def\Om{\Omega}
\def\om{\omega}
\def\restr{\lceil}
\def\ffi{\varphi}
\def\ep{\varepsilon}
\def\dki{{\partial\,\,\,\over\partial\kappa^i}}
\def\dkia{\partial_i^\kappa}
\def\dkonea{\partial_1^\kappa}
\def\dkna{\partial_n^\kappa}
\def\pdto{\,\rightarrow\kern -12pt ^{pd}\,}
\def\tvto{\,\rightarrow\kern -12pt ^{tv}\,}
\def\opdto{\,\longrightarrow\kern -18pt ^{opd}\,}
\def\pdtvto{\,\hbox to 1.1true cm{\rightarrowfill}\kern -20pt ^{pdtv}\,\,\,}
\def\tpdtvto{\,\hbox to 1.1true cm{\rightarrowfill}\kern -23pt ^{tpdtv}\,\,\,}
\def\adjo#1{{\rm Adj}(#1)}
\def\adjonul#1{{\rm Adj}^{\nu,L}(#1)}
\def\cch{\overline{co}}


%\voffset=-0.28true in
%\hsize=16true cm
%\vsize=9.45true in
%\parindent 0.25true in
\raggedbottom
%\def\onarr#1{\,\hbox to 0.4in{\rightarrowfill}\kern-0.25 in
%\raise 5pt\hbox{$#1$}\kern 0.2 in}
\def\onarr#1{\,\hbox to 0.37in{\rightarrowfill}\kern-0.37in
\raise 7pt\hbox to 0.37in{\hfill$#1$\hfill}\kern 0.04 in}
\def\nextarr#1{\,\,\,\,\,\,|\kern-3.8pt\lower 9.3pt
\hbox{$\downarrow$}\lower 3pt\hbox{$#1$}\,\,}
\def\pmbeta{{\pmb{\eta}\kern 0.02in}}
\def\pmbetas{{\pmbsus{\eta}\kern 0.02in}}

\setcounter{page}{1}
%\pagestyle{empty}

\begin{center}
\fbox{\begin{minipage}{12cm}
\begin{center}
{\bf MODUS PONENS (a.k.a. Rule $\imply$-out)}
\end{center}

\medbreak\noindent\hbox to 7cm{\hfill $P\imply Q$}

\noindent\hbox to 7cm{\hfill $P$}

\noindent\hbox to 7cm{\hbox to 5cm{\hfill}\hrulefill}\hbox to 4cm{\hfill}

\noindent\hbox to 7cm{\hfill $Q$}
\end{minipage}}\end{center}

\begin{center}
\fbox{\begin{minipage}{12cm}
\begin{center}
{\bf THE CONDITIONAL PROOF RULE (a.k.a. Rule $\imply$-in)}
\end{center}

\medbreak{\em Rule $\imply$-in} says that {\bf if, assuming $P$,
you prove $Q$, then you can go to $P\imply Q$.}

In other words, 

\medbreak
\pline{\ste\ste\ste Assume $P$\hfill}

\pline{\ste\ste\ste\ste $\vdots$\hfill}

\pline{\ste\ste\ste $Q$\hfill}

\pline{\ste\ste\hbox to 2cm{\hrulefill}\hfill}

\pline{\ste $P\imply Q$\hfill}

\medbreak
(The change in indentation is explained below.)

\end{minipage}}\end{center}

\medbreak\noindent  COMMENT. To apply Rule $\imply$-in, we proceed as follows:
suppose $p$ and $q$ are propositions, and we want to prove $p\imply q$;
we start a ``subproof'' (i.e., a ``proof within a proof'', see below)
by saying ``assume $p$'', and we proceed to proving $q$. Then we exit
the subproof and assert $p\imply q$ in our main proof. 

Notice that to apply this rule {\bf we can introduce any assumptions we want}.
It does not matter at all whether the assumptions we introduce are true
or false. On the other hand, any time we introduce an assumption $p$,
and we prove something---say a proposition $q$---using that assumption, then
we will not have {\em proved $q$}.  We will only have 
{\em proved $q$ under the assumption $p$}. Rule $\imply$-out 
tells us that, if we do that, then we can ``get out from working 
under the assumption $p$'' and assert the implication $p\imply q$. 
But {\em this does not tell us that $q$ is true}. If we want to conclude 
that $q$ is true, we need to prove $p$. (If we can do that,
then we can use the Modus Ponens rule to conclude 
$q$ from $p$ and $p\imply q$.)

\medbreak\noindent EXAMPLE. If you want to understand how Hamlet must
have felt, you could try to imagine that you are Hamlet. That is, you
would place yourself under the assumption that you are Hamlet (e.g. by
saying to yourself ``suppose I was Hamlet'') and follow your thoughts.
Under that assumption, you might reach the conclusion that you hate
your uncle very much and want to punish him for having killed your
father and taking his place as king. All these facts (that your uncle
killed your father, that you hate him, that you want to punish him)
are not true facts in the real world, but are true {\em in the
imaginary world that you entered when you made the assumption that you
were Hamlet}.  If you want to, you can come out of that imaginary
world and, in the real world, draw the conclusion that ``if I was
Hamlet I would hate my uncle.''  Your argument would have the following
form:

\medbreak\noindent\hbox to 3cm{\hfill} $\qquad$ Assume I am Hamlet

\medbreak\noindent\hbox to 3cm{\hfill} $\qquad$ $\qquad$ $\vdots$

\medbreak\noindent\hbox to 3cm{\hfill} $\qquad$ {\it think, think, think}

\medbreak\noindent\hbox to 3cm{\hfill} $\qquad$ $\qquad$ $\vdots$

\medbreak\noindent\hbox to 3cm{\hfill} $\qquad$ I hate my uncle.

\medbreak\noindent\hbox to 3cm{\hfill} If I was Hamlet I would hate my uncle.

\medbreak\noindent This is of the form described in the previous box:

\medbreak\noindent\hbox to 3cm{\hfill} $\qquad$ Assume $P$

\medbreak\noindent\hbox to 3cm{\hfill} $\qquad$ $\vdots$

\medbreak\noindent\hbox to 3cm{\hfill} $\qquad$ $Q$

\medbreak\noindent\hbox to 3cm{\hfill} $P\imply Q$




\begin{center}
\fbox{\begin{minipage}{12cm}
\begin{center}
{\bf Rule} $\wedge${\bf-in}
\end{center}

\medbreak\noindent\hbox to 7cm{\hfill $P$}

\noindent\hbox to 7cm{\hfill $Q$}

\noindent\hbox to 7cm{\hbox to 5cm{\hfill}\hrulefill}\hbox to 4cm{\hfill}

\noindent\hbox to 7cm{\hfill $P\wedge Q$}

\end{minipage}}\end{center}




\begin{center}
\fbox{\begin{minipage}{12cm}
\begin{center}
{\bf Rule} $\wedge${\bf-out}
\end{center}

\medbreak{\em Rule $\wedge$-out} is actually a pair of rules, namely,
the propositional inference forms

\medbreak\noindent\hbox to 7cm{\hfill $P\wedge Q$}

\noindent\hbox to 7cm{\hbox to 5cm{\hfill}\hrulefill}\hbox to 4cm{\hfill
(called``Rule $\wedge$-out-a'')}

\noindent\hbox to 7cm{\hfill $P$}

and

\medbreak\noindent\hbox to 7cm{\hfill $P\wedge Q$}

\noindent\hbox to 7cm{\hbox to 5cm{\hfill}\hrulefill}\hbox to 4cm{\hfill
(called``Rule $\wedge$-out-b'')}

\noindent\hbox to 7cm{\hfill $Q$}
\end{minipage}}\end{center}

\begin{center}
\fbox{\begin{minipage}{12cm}
\begin{center}
{\bf Rule} $\vee${\bf-in}
\end{center}

\medbreak{\em Rule $\vee$-in} is actually a pair of rules, namely,
the propositional inference forms

\medbreak\noindent\hbox to 7cm{\hfill $(\neg\,P)\imply Q$}

\noindent\hbox to 7cm{\hbox to 5cm{\hfill}\hrulefill}\hbox to 4cm{\hfill
(called``Rule $\vee$-in-a'')}

\noindent\hbox to 7cm{\hfill $P\vee Q$}

and

\medbreak\noindent\hbox to 7cm{\hfill $(\neg\,Q)\imply P$}

\noindent\hbox to 7cm{\hbox to 5cm{\hfill}\hrulefill}\hbox to 4cm{\hfill
(called``Rule $\vee$-in-b'')}

\noindent\hbox to 7cm{\hfill $P\vee Q$}
\end{minipage}}\end{center}

\medbreak\noindent  COMMENT. Rule $\vee$-in captures the common sense
principle that ``if you want to show that one of two things is true,
it suffices to suppose that one of them is not true and prove the other one.''
For example:

\bi
\item[a.] To prove that today must be Monday or Thursday, we prove 
that if today isn't Monday then it has to be Thursday.
\item[b.] To tell your travel agent that you want an aisle seat or a window 
seat, you could say ``if you cannot get me a window seat 
get me an aisle seat.''
\ei

\medbreak\noindent  COMMENT. In view of Rule $\imply$-in, to apply
Rule $\vee$-in we can use the following format:

\pline{\ste\ste\ste Assume $\neg\,P$\hfill}

\pline{\ste\ste\ste\ste $\vdots$ \hfill}

\pline{\ste\ste\ste $Q$\hfill}

\pline{\ste\ste $P\vee Q$\hfill}

\medbreak\noindent  COMMENT. As special cases of Rule $\vee$-in, 
we have the following valid propositional inference rules:

\medbreak\noindent\hbox to 7cm{\hfill $P$}

\noindent\hbox to 7cm{\hbox to 5cm{\hfill}\hrulefill}\hbox to 4cm{\hfill}

\noindent\hbox to 7cm{\hfill $P\vee Q$}

and

\medbreak\noindent\hbox to 7cm{\hfill $Q$}

\noindent\hbox to 7cm{\hbox to 5cm{\hfill}\hrulefill}\hbox to 4cm{\hfill}

\noindent\hbox to 7cm{\hfill $P\vee Q$}

\medbreak
\begin{center}
\fbox{\begin{minipage}{12cm}
\begin{center}
{\bf PROOF BY CASES (a.k.a Rule} $\vee${\bf-out)}
\end{center}

\medbreak\noindent\hbox to 7cm{\hfill $P\vee Q$}

\medbreak\noindent\hbox to 7cm{\hfill $P\imply R$}

\medbreak\noindent\hbox to 7cm{\hfill $Q\imply R$}

\noindent\hbox to 7cm{\hbox to 5cm{\hfill}\hrulefill}\hbox to 4cm{\hfill}

\noindent\hbox to 7cm{\hfill $R$}
\end{minipage}}\end{center}

\begin{center}
\fbox{\begin{minipage}{12cm}
\begin{center}
{\bf PROOF BY CONTRADICTION (a.k.a. Rule} $\neg${\bf-in-out)}
\end{center}

\medbreak\noindent\hbox to 7cm{\hfill $P\imply Q$}

\noindent\hbox to 7cm{\hfill $\neg Q$}

\noindent\hbox to 7cm{\hbox to 5cm{\hfill}\hrulefill}\hbox to 4cm{\hfill}

\noindent\hbox to 7cm{\hfill $\neg P$}
\end{minipage}}\end{center}

\medbreak\noindent COMMENT. We labeled Rule $\neg$-in-out 
both an ``in'' rule and an ``out'' rule because one can think 
of this rule as a way to {\em use} a negation (if you 
have $\neg\,Q$ you can use this, in conjunction with 
$P\imply Q$, to prove something) or as a way to {\em prove}
a negation (since it gives us a way to prove $\neg\,P$.

\medbreak\noindent COMMENT. A very common use of Rule $\neg$-in-out 
is to do {\bf proofs by contradiction}. Suppose you want to 
prove that something (say a proposition $p$) is not true. Then you 
prove that this proposition implies something impossible, i.e., that 
``if $p$ then $q$'', where $q$ is something that you can prove 
is not true. This shows that $p$ cannot be true.  Using Rule $\imply$-in
(see below) we can carry out our proof y contradiction according to the
following format:

\bigbreak\noindent\hbox to 4cm{\hfill} $\vdots$

\noindent\hbox to 4cm{\hfill} $\neg\,q$

\noindent\hbox to 4cm{\hfill} $\quad$ Assume $p$

\noindent\hbox to 4cm{\hfill} $\qquad$ $\vdots$

\noindent\hbox to 4cm{\hfill} $\quad$ $q$

\noindent\hbox to 4cm{\hfill} $p\imply q$

\noindent\hbox to 4cm{\hfill} $\neg\,p$

\medbreak\noindent or

\noindent\hbox to 4cm{\hfill} $\quad$ Assume $p$

\noindent\hbox to 4cm{\hfill} $\qquad$ $\vdots$

\noindent\hbox to 4cm{\hfill} $\quad$ $q$

\noindent\hbox to 4cm{\hfill} $p\imply q$

\bigbreak\noindent\hbox to 4cm{\hfill} $\vdots$

\noindent\hbox to 4cm{\hfill} $\neg\,q$

\noindent\hbox to 4cm{\hfill} $\neg\,p$

\medbreak\noindent That is, we make sure that $q$ is impossible,
by proving $\neg\,q$, and then we say ``assume $p$'' and go on 
to prove $q$; we then conclude the argument by saying
``but $q$ is not true, so we have reached a contradiction,
and this establishes that $p$ is false.'' 


\medbreak\noindent{\bf EXAMPLES OF PROOFS BY CONTRADICTION:}

\noindent THEOREM: {\sl The number $30$ cannot be expressed as 
the difference of the squares of two integers.}

\medbreak\noindent PROOF: Suppose $30$ can be expressed as the
difference of the squares of two integers. ({\em Comment: this is a
typical proof by contradiction.  We want to prove Sthat something isn't
true. To do so, we imagine it is true, that is, we explore what things
would be like in an imaginary world where it is true. We then set out
to show that this imaginary world is impossible, because in it
something impossible would have to be true.})  Pick two integers $n$
and $m$ such that $n^2-m^2=30$. Then $(n-m)(n+m)=30$. Now
$n+m=(n-m)+2m$. Therefore $n-m$ and $n+m$ are either both odd or both
even.  If $n-m$ and $n+m$ are both odd then their product, i.e., the
number $30$, would have to be odd. If $n-m$ and $n+m$ are both even
then their product, i.e., the number $30$, would have to be divisible
by $4$.  So $30$ is either odd or divisible by $4$. But this is false,
because $30$ is neither odd nor divisible by $4$. So the assumption that
$30$ can be expressed as the difference of the squares of two integers
leads to an impossible conclusion. Therefore
$30$ cannot be expressed as the difference of the squares of two integers.
\proofend

\medbreak\noindent THEOREM: {\sl The number $2$ is not the square
of a rational number.}
(That is, ``$\sqrt{2}$ is irrational.'')

\medbreak\noindent PROOF: Suppose $2$ is the square of a rational number.
This means that $2$ can be expressed as the
quotient of the square of an integer divided by the square of
a nonzero integer. 
Pick two integers $n$
and $m$ such that $2=\frac{n^2}{m^2}$ and $m\neq 0$. Then, after 
cancelling all common factors $>1$, we may assume that 
$n$ and $m$ have no common factors $>1$. In particular, 
$n$ and $m$ are not both even, for if they were both
even then they would have the factor $2$ in common. 
Now, the equality $2=\frac{n^2}{m^2}$ implies 
$2m^2=n^2$. So $n^2$ is even. But then $n$ is even, because
if $n$ was odd then $n^2$ would be odd. So $n=2k$ for some integer $k$.
But then $2m^2=n^2=(2k)^2=4k^2$. So $m^2=2k^2$. So $m^2$ is even.
Then $m$ is even, because
if $m$ was odd then $m^2$ would be odd. 
Therefore $n$ and $m$ are both even, and at the same time
$n$ and $m$ are not both even. These two assertions together
add up to an impossible conclusion. Therefore
$2$ is not the square of a rational number.
\proofend

\bigbreak

\begin{center}
\fbox{\begin{minipage}{12cm}
\begin{center}
{\bf Rule} $\bimply${\bf-in}
\end{center}

\medbreak\noindent\hbox to 7cm{\hfill $P\imply Q$}

\medbreak\noindent\hbox to 7cm{\hfill $Q\imply P$}

\noindent\hbox to 7cm{\hbox to 5cm{\hfill}\hrulefill}\hbox to 4cm{\hfill}

\noindent\hbox to 7cm{\hfill $P\bimply Q$}
\end{minipage}}\end{center}

\medbreak\noindent COMMENT. Often, one uses Rule $\bimply$-in
as follows. Suppose we want to prove $p\bimply q$. Then we 
prove $q$ assuming $p$, and $p$ assuming $q$. For this, 
we use the following format:

\vbox{
\noindent\hbox to 4cm{\hfill} $\vdots$

\noindent\hbox to 4cm{\hfill} $\quad$ Assume $p$

\noindent\hbox to 4cm{\hfill} $\qquad$ $\vdots$

\noindent\hbox to 4cm{\hfill} $\quad$ $q$

\noindent\hbox to 4cm{\hfill} $p\imply q$

\noindent\hbox to 4cm{\hfill} $\quad$ Assume $q$

\noindent\hbox to 4cm{\hfill} $\qquad$ $\vdots$

\noindent\hbox to 4cm{\hfill} $\quad$ $p$

\noindent\hbox to 4cm{\hfill} $q\imply p$

\noindent\hbox to 4cm{\hfill} $p\bimply q$
}

\medbreak

\begin{center}
\fbox{\begin{minipage}{12cm}
\begin{center}
{\bf Rule} $\bimply${\bf-out}
\end{center}

\medbreak{\em Rule $\bimply$-out} is actually a pair of rules, namely,
the propositional inference forms

\medbreak\noindent\hbox to 7cm{\hfill $P\bimply Q$}

\medbreak\noindent\hbox to 7cm{\hfill $P$}

\noindent\hbox to 7cm{\hbox to 5cm{\hfill}\hrulefill}\hbox to 5cm{\hfill
(called``Rule $\bimply$-out-a'')}

\noindent\hbox to 7cm{\hfill $Q$}

and

\medbreak\noindent\hbox to 7cm{\hfill $Q\bimply P$}

\medbreak\noindent\hbox to 7cm{\hfill $Q$}

\noindent\hbox to 7cm{\hbox to 5cm{\hfill}\hrulefill}\hbox to 5cm{\hfill
(called``Rule $\bimply$-out-a'')}

\noindent\hbox to 7cm{\hfill $P$}
\end{minipage}}\end{center}

\begin{center}
\fbox{\begin{minipage}{12cm}
\begin{center}
{\bf THE TAUTOLOGY PROOF RULE(S)}
\end{center}

\medbreak This ``rule'' really consists of lots of propositional
inference rules, one for each tautology. What these rules say is 
that if $T$ is a tautology, then 

\noindent\hbox to 7cm{\hbox to 5cm{\hfill}\hrulefill}\hbox to 5cm{\hfill}

\noindent\hbox to 7cm{\hfill $T$}

\medbreak\noindent is a valid propositional inference form.
\end{minipage}}\end{center}

\medbreak\noindent COMMENT: Notice that in this rule there are no
premisses.  So what the rule really amounts to is that {\bf you can
bring in an instance of a tautology at any point in your proof.}


\newpage

\begin{center}
{\mymagtwobf PROOFS WITHIN PROOFS.}
\end{center}

\begin{center}
\fbox{\fbox{\begin{minipage}{11cm}
{\large{\em Whenever you want, you can start a
``subproof,'' or ``proof within a proof,'' in which you can make {\bf
any assumption you want}.  However, when you do that then all the
things you prove are proved {\bf under that assumption}.}}
\end{minipage}}}\end{center}

\medbreak\noindent 
For example, suppose we are reading a mystery novel, and I am trying to
prove to you that it was Bob that murdered Bill.  Suppose we got to a point
where I have established that the murderer must have been Bob or John.  Now
I want to convince you that it's not John, so it must have been Bob.

Here is one thing I could say: ``Suppose John murdered Bill.  We know that
Bill's body was found in his house, so the killing must have taken place in
the house itself, or nearby, because even if the body had been moved it
still couldn't have been moved very far. So John must have been in or near
Bill's house at the time of the murder. But Bill was killed on September 8
between 9 and 10 p.m.  EST.  So John must have been in or near Bill's house
on September 8 between 9 and 10 p.m.  EST.  On the other hand, we know that
John gave a public lecture in San Diego on September 8, starting at 6
p.m. Pacific time, i.e.  at 9 p.m. EST. So he must have traveled from New
York to San Diego in one hour or less, which is impossible. So John did not
murder Bill.''

Notice that what we did here is construct, within our main proof that Bob
is the murderer, a ``subproof,'' or ``proof within a proof,'' whose goal is
to prove that John is not the murderer.  We did this by {\sl introducing a
new hypothesis}, namely, by assuming that John is the murderer.  In other
words, {\sl we created and set out to explore an imaginary world}, in which
John did indeed kill Bill, in order to find out what are the consequences
and ramifications of the new hypothesis.  In this imaginary world, we
proved a number of things, such as, for example, that ``John traveled from
New York to San Diego in one hour or less.''  But we proved these things
{\sl under the hypothesis that John killed Bill}.  In order words, we did
not really prove that ``John traveled from New York to San Diego in one
hour or less,'' but only that this must have been so {\sl if John killed
Bill.}

The ultimate consequence of our ``proof within a proof'' is that 
this world we have imagined, in which John killed Bill, is impossible,
because in this world something impossible happened.   So we get out of
this ``proof within a proof'' the conclusion that {\sl John did not kill
Bill}. And {\sl this conclusion no longer depends on the new hypothesis
that ``John killed Bill.''}   The final conclusion, that 
{\sl John did not kill Bill}, is valid {\sl without any extra hypotheses},
so it is part of our main proof.    

In our mathematical formalism, we are allowed to start a ``proof within
a proof'' any time we want, by assuming anything we want.  However,
anything we prove will only be part of this ``proof within a proof.''
There will be rules telling us how to get out of the ``proof within a proof'' 
and go back to the main proof.  The most important one is the following: 

\medbreak\noindent{{\bf RULE $\lto$-in.}}\ \ (The 
``conditional proof rule,'' also  called ``Rule
$\lto$-in,'' or ``rule for proving an implication.'')
{\sl If assuming $p$ you get to $q$
then you can go, without assuming $p$, to 
$p\imply q$.}

\medbreak For example, suppose that the action takes place 
some time before the November 2000 presidential election.
Suppose that, in some argument you are writing,
you have established that 

\medbreak
\pline{(3591)\ste If Gore wins Florida then Gore will become president.
\hfill($\ldots\ldots\ldots\ldots$)}

\medbreak\noindent and, later, that

\medbreak
\pline{(4507)\ste If Gore becomes president then the next Attorney 
General will not}
\pline{\phantom{(4507)}\ste be a 
conservative.\hfill($\ldots\ldots\ldots\ldots\ldots\ldots\ldots$)}

\medbreak\noindent That means that, if we use the letters 
$\mathcal{A}$, $\mathcal{B}$, $\mathcal{C}$ to represent
the sentences ``Gore wins Florida,'' ``Gore becomes president,'' 
and ``the next Attorney General will not be a
conservative,'' then we already got

\medbreak
\pline{(3591)\ste $\mathcal{A}\imply\mathcal{B}$\,.
\hfill($\ldots\ldots\ldots\ldots\ldots\ldots\ldots$)}

\pline{(4507)\ste $\mathcal{B}\imply\mathcal{C}$\,.
\hfill($\ldots\ldots\ldots\ldots\ldots\ldots\ldots$)}

\medbreak\noindent Suppose you just finished writing 
Step 6812, and now you want to prove
$\mathcal{A}\imply\mathcal{C}$.
Here is one thing you could do:

\medbreak
\pline{(6813)\ste\ste\ste\ste  Assume $\mathcal{A}$.\hfill  
(Preparation to apply Rule $\lto$-in)} 

\pline{(6814)\ste\ste\ste\ste  $\mathcal{B}$.\hfill(Modus Ponens from 
(3591) and  (6813))}

\pline{(6815)\ste\ste\ste\ste  $\mathcal{C}$.\hfill  (Modus Ponens from 
(4507) and (6814))}

\pline{(6816)\ste $\mathcal{A}\imply\mathcal{C}$.\hfill  (Rule $\lto$-in, 
from (6813) and (6815))}

\medbreak\noindent Steps 6813, 6814, 6815 constitute a ``proof
within a proof,'' in which you \mbox{introduce} the new assumption 
$\mathcal{A}$, and under
this assumption you prove first $\mathcal{B}$ and then $\mathcal{C}$. 
Then in Step 6816 you go back to the main proof, using Rule 4.P.  

Notice that we have used extra indentation to indicate that we are writing
a proof within a proof.   The way we have organized our proof makes it
clear that {\sl at no point are we proving $\mathcal{B}$ or 
$\mathcal{C}$}. We are proving $\mathcal{B}$ and $\mathcal{C}$ 
{\em under the assumption $\mathcal{A}$}, from which we can 
conclude that $\mathcal{A}\lto\mathcal{C}$, 
as we do in Step 6816.   For all we know, 
{\em $\mathcal{B}$ and $\mathcal{C}$ could perfectly well be false}, 
and nothing in what we wrote says otherwise.   (Actually,
$\mathcal{B}$ and $\mathcal{C}$ {\em are} false.)
All our ``proof within a proof'' says is that 
{\em if you assume that $\mathcal{A}$ is true, then
$\mathcal{C}$ must be true.}

The ``proof within a proof'' tells us nothing about what happens if
$\mathcal{A}$ is false. And our final conclusion, that 
$\mathcal{A}\rightarrow\mathcal{C}$, is of course valid if 
$\mathcal{A}$ is false, because {\bf an implication such as
$\mathcal{A}\rightarrow\mathcal{C}$ is true when 
$\mathcal{A}$ is false.}



\bigbreak\noindent{\bf INTRODUCING ASSUMPTIONS.} Let us look at what 
we have just said from a slightly different angle.


\begin{center}
\fbox{\fbox{
\begin{minipage}{12cm}

\boxon{HYPOTHESES (A.K.A. ASSUMPTIONS)\label{pigs-box}}

\noindent{\bf Hypotheses}, or {\bf assumptions},
are statements that we {\bf assume} to be true in a particular
situation.

When we discuss proofs later on, we will see that 
that there are certain statements that you are free to bring in any time you want,
because you know them to be true.  (Such statements are called
``axioms,'' or ``postulates.'') In additions, {\em definitions}
function exactly like axioms, the only difference being 
that an axiom is something you {\em accept} as true (say, because 
you are convinced it is true but you do not know how to prove it)
whereas a definition (say, for example, $2=1+1$) is something
that you {\em declare}, or {\em decide} to be true.
{\bf Within a particular proof, hypotheses/assumptions
function exactly like 
axioms and definitions: they are statements that you can bring
in any time.} 

There is, however, a big difference. Axioms and definitions
are things that we take to be
true forever, because we believe they are true. Hypotheses/assumptions
are taken to be
true not because we believe they are true, but {\bf because we want to know
the consequences of their being true.}  

For example: suppose we want to find out what the world would be like
if pigs had wings.  To do this, we first
make the assumption ``pigs have wings,'' by saying

\medbreak\noindent($\ldots$) $\qquad$ Assume that pigs have wings. 

\medbreak Then we would set out to explore the consequences of this 
assumption.
That is, if you prefer, we would set out to study an {\bf imaginary world}
in which pigs have wings, and try to understand what that world would
have to be like. We might then be able to ``prove'' all kind of ``theorems,''
such as

\medbreak THEOREM 1: {\it Pigs can fly}.

\medbreak THEOREM 2: {\it If a pigsty does not have a roof, then the 
pigs will fly away}. 

\medbreak (Proving these theorems might not be easy. For example,
it is not true that ``every animal that has wings can fly,'' since, for example,
ostriches, penguins and dodos do not fly. But you might notice that
all the exceptions to the general rule seem to be birds, so perhaps
you could make a convincing case that 
``every animal that has wings and is not a bird can fly.'' If you manage 
to do that, then you might go on to argue that pigs can fly, since pigs 
clearly are not birds.) 

All these theorems would be proved {\bf under the hypothesis}
that pigs have wings.  That is, we would never be saying that we have
proved that pigs can fly.  All we would be saying is that {\bf IF} pigs
had wings {\bf THEN} pigs could fly.  In other words, all the facts
we would ``prove'' about pigs under the ``pigs have wings'' hypothesis would
be valid {\bf in the imaginary world of pigs with wings}, which, in principle,
is not our real world.
\end{minipage}}}\end{center}

\medbreak

\begin{center}
\fbox{\fbox{
\begin{minipage}{11cm}
\boxon{ENTERING AND LEAVING IMAGINARY WORLDS}

\noindent As we explained in Box \ref{pigs-box}, when you assume something
you are setting 
out to explore an {\bf imaginary world}, namely, a world in which that thing
you are assuming is true. When can you leave that world and go back to the
real world, taking with you the things you have discovered in your
imaginary world? The answer is simple: if the thing you assumed is actually
true in the real world, then everything you proved {\bf under that
assumption} is true, because in that case the imaginary world really 
is the real world.  

Our rules of inference capture this very obvious idea as follows: 

\bi
\item{} You are always allowed to introduce anything you want as an
assumption, any time you want. 

\item{} When you do that, whatever you have proved will have been proved 
{\bf under your assumption}.

\item{} If, assuming a statement $\mathcal{A}$, you prove some other 
statement $\mathcal{B}$, then you will
be allowed to go back to ``the real world'' and assert there that 
$\mathcal{A}\imply\mathcal{B}$.  

\item{} If, in addition, you can prove $\mathcal{A}$, then the Modus 
Ponens rule allows you to go to $\mathcal{B}$.
\ei

In simpler terms: whatever you prove under the assumption
$\mathcal{A}$ will be valid unrestrictedly (that is, without having to
assume that you are under the assumption $\mathcal{A}$) if you can
also prove $\mathcal{A}$.

\medbreak\noindent EXAMPLE: If you prove that ``pigs can fly''
under the assumption that ``pigs have wings,'' then the conclusion
that ``pigs have wings'' will have been established in a world
where pigs have wings. You can also go back from such an imaginary 
world to the real world by stating that ``if pigs have wings
then pigs can fly.''  This, however, is not enough 
to be able to conclude that in the real world 
pigs can fly, because in the real world you do not know
that pigs have wings, and {\bf if you do not know
that pigs have wings then you cannot go from 
``if pigs have wings then pigs can fly'' to 
``pigs can fly.''}
\end{minipage}}}
\end{center}






\begin{center}
\fbox{\fbox{
\begin{minipage}{11cm}
\vspace{1mm}
\begin{center}
{\bf HOW COME WE ASSUME THINGS THAT AREN'T KNOWN TO BE TRUE?}
\end{center}
A question students frequently ask is:

\begin{center}
\begin{minipage}{8cm}
{\large{\bf How can I assume something if I don't know
that it is is true?}}
\end{minipage}\end{center} 

The answer is very simple: 

\begin{center}
\begin{minipage}{8cm}
{\large{\bf you assume something that you
don't know to be true because you want to find out what would happen
if it was true.  And often {\em you assume it precisely in order to
prove it is not true.}}}
\end{minipage}\end{center} 

Often, you prove that something is not true by assuming it is true and
exploring the consequences of this assumption until you get to
something impossible. This is called ``proof by contradiction.'' We
have just seen an example: to prove by contradiction that $30$ cannot
be expressed as the difference of the squares of two integers, we
assumed that $30$ could be expressed as the difference of the squares
of two integers, and ended up with something false, namely, that $30$
is either odd or divisible by $4$.  That is, {\bf we set out to
explore an imaginary world in which $30$ can be expressed as the
difference of the squares of two integers, until we saw that in this
world impossible things would haver to happen, and then we concluded
that such a world could not exist, so $30$ cannot be expressed as the
difference of the squares of two integers.}

\vspace{1mm}
\end{minipage}
}}
\end{center}

The following four rules are the ``in'' and ``out'' rules for each
of the two quantifiers.  They deal with the following situation:

\begin{itemize}
\item[S1.] $x$ is a variable and $\mathcal{A}(x)$ is a formula where there 
is no $x$-quantifier, 
\item[S2.] $a$ is a constant and $\mathcal{A}(a)$ is what you get from 
$\mathcal{A}(x)$ 
by substituting $a$ for $x$ in {\bf all} the occurrences of $x$ in
$\mathcal{A}(x)$.
\end{itemize}

\medbreak\noindent EXAMPLE: $\mathcal{A}(x)$ could be the formula
$x>a\imply(\neg\,x=a)$, in which case $\mathcal{A}(a)$ would be the
formula $a>a\imply(\neg\,a=a)$.\proofend

\begin{center}
\fbox{
\begin{minipage}{11cm}
\vspace{1mm}
\begin{center}
{\bf THE SPECIALIZATION RULE\\
(a.k.a. Rule $\forall$-out)}
\end{center}

Suppose S1, S2 are true. Then, 

\pline{\ste\ste\ste $\forall x,\mathcal{A}(x)$\hfill}

\pline{\ste\ste \hbox to 2cm{\hrulefill}\hfill}

\pline{\ste\ste\ste $\mathcal{A}(a)$ \hfill}.
\end{minipage}}\end{center}

\medbreak\noindent EXAMPLE: Suppose $\mathcal{A}(x)$ is the formula
$x>a\imply(\neg\,x=a)$. Then, as explained before,
$\mathcal{A}(a)$ is the formula $a>a\imply(\neg\,a=a)$.  

If, in a proof,  you got to $\forall x,(x>a\imply(\neg\,x=a))$, then
Rule $\forall$-out enables you to conclude that 
$a>a\imply(\neg\,a=a)$.  

\begin{center}
\fbox{
\begin{minipage}{11cm}
\vspace{1mm}
\begin{center}
{\bf THE UNIVERSAL GENERALIZATION RULE\\
(a.k.a. Rule $\forall$-in)}
\end{center}

Suppose that S1 and S2 are true. 
Suppose you are in a proof $P$ (which may be itself
be a subproof of some other proof) and you have started a subproof $P'$ of $P$
by saying ``Let $a$ be arbitrary,'' and that until that point
$a$ had never appeared in $P$.  Suppose that in $P'$
you got to $\mathcal{A}(a)$. Suppose that $\mathcal{A}(x)$ does
not contain $a$. Then you can get
out of $P'$ and go to $\forall x,\mathcal{A}(x)$ in the proof $P$.
\end{minipage}}\end{center}

\medbreak\noindent EXAMPLE: Suppose $\mathcal{A}(x)$ is the formula
$x\in A\imply x\in B$, and $\mathcal{B}(x)$ is the formula 
$x\in B\imply x\in C$, where $A$, $B$, $C$ are constants
that stand for sets, 
and we have, as previous steps in our proof (say 
in steps 231 and 486), the statements
``$A\subseteq B$''  and ``$B\subseteq C$''. Then we can prove 
$A\subseteq C$ as follows (starting, say,  at step 895):

\medbreak

\pline{\phantom{(231)}\ste $\vdots$\hfill}

\pline{(231)\ste $A\subseteq B$\hfill}

\pline{\phantom{(231)}\ste $\vdots$\hfill}

\pline{(486)\ste $B\subseteq C$\hfill}

\pline{\phantom{(231)}\ste $\vdots$\hfill}

\pline{(895) \ste\ste Let $a$ be arbitrary.\hfill}

\pline{(896) \ste\ste $A\subseteq B\bimply \forall x,(x\in A\imply
x\in B)$\hfill  (Definition of $\subseteq$)}

\pline{(897) \ste\ste $\forall x,(x\in A\imply
x\in B)$\hfill  (From (231) and (896) by $\bimply$-out)}

\pline{(898) \ste\ste $B\subseteq C\bimply \forall x,(x\in B\imply
x\in C)$\hfill  (Definition of $\subseteq$)}

\pline{(899) \ste\ste $\forall x,(x\in B\imply
x\in C)$\hfill  (From (486) and (898) by $\bimply$-out)}

\pline{(900) \ste\ste $a\in A\imply a\in B$\hfill  (From (897) by 
$\forall$-out)}

\pline{(901) \ste\ste $a\in B\imply a\in C$\hfill  (From (899) by 
$\forall$-out)}

\pline{(902) \ste\ste\ste Assume $a\in A\,$.\hfill}

\pline{(903) \ste\ste\ste $a\in B\,$\hfill(From (900) and (902) by
$\imply$-out)}

\pline{(904) \ste\ste\ste $a\in C\,$\hfill(From (903) and (901) by
$\imply$-out)}

\pline{(905) \ste\ste $a\in A\imply a\in C\,$\hfill(From (902) and (904) by
$\imply$-in)}

\pline{(906) \ste $\forall x,(x\in A\imply x\in C)\,$\hfill(From (895) 
and (905) by $\forall$-in)}

\pline{(907) \ste $A\subseteq C\bimply \forall x,(x\in A\imply
x\in C)$\hfill  (Definition of $\subseteq$)}

\pline{(908) \ste $A\subseteq C$\hfill(From (906) and (907) by
$\bimply$-out)}

\medbreak\noindent REMARK. You could make the above proof one step shorter
by making a clever use of the tautology rule:

\medbreak

\vbox{
\pline{\phantom{(231)}\ste $\vdots$\hfill}

\pline{(231)\ste $A\subseteq B$\hfill}

\pline{\phantom{(231)}\ste $\vdots$\hfill}

\pline{(486)\ste $B\subseteq C$\hfill}

\pline{\phantom{(231)}\ste $\vdots$\hfill}

\pline{(895) \ste\ste Let $a$ be arbitrary.\hfill}

\pline{(896) \ste\ste $A\subseteq B\bimply \forall x,(x\in A\imply
x\in B)$\hfill  (Definition of $\subseteq$)}

\pline{(897) \ste\ste $\forall x,(x\in A\imply
x\in B)$\hfill  (From (231) and (896) by $\bimply$-out)}

\pline{(898) \ste\ste $B\subseteq C\bimply \forall x,(x\in B\imply
x\in C)$\hfill  (Definition of $\subseteq$)}

\pline{(899) \ste\ste $\forall x,(x\in B\imply
x\in C)$\hfill  (From (486) and (898) by $\bimply$-out)}

\pline{(900) \ste\ste $a\in A\imply a\in B$\hfill  (From (897) by 
$\forall$-out)}

\pline{(901) \ste\ste $a\in B\imply a\in C$\hfill  (From (899) by 
$\forall$-out)}

\pline{(902) \ste\ste $(a\in A\to a\in B)\to((
a\in B\to a\in C)\to(a\in A\to a\in C))$\hfill}

\pline{\hfill  (Instance
of the tautology $(P\to Q)\to((Q\to R)\to (P\to R))$)}

\pline{(903) \ste\ste $(a\in B\to a\in C)\to(a\in A\to a\in C)$\hfill}

\pline{\hfill (From (900) and (902) by $\imply$-out)}

\pline{(904) \ste\ste $a\in A\imply a\in C\,$\hfill(From (901) and (903) by
$\imply$-out)}

\pline{(905) \ste $\forall x,(x\in A\imply x\in C)\,$\hfill(From (895) 
and (904) by $\forall$-in)}

\pline{(906) \ste $A\subseteq C\bimply \forall x,(x\in A\imply
x\in C)$\hfill  (Definition of $\subseteq$)}

\pline{(907) \ste $A\subseteq C$\hfill(From (905) and (906) by
$\bimply$-out)}

}

\bigbreak
\begin{center}
\fbox{
\begin{minipage}{11cm}
\vspace{1mm}
\begin{center}
{\bf THE EXISTENTIAL GENERALIZATION RULE\\
(a.k.a. ``the witness rule,'' or ``Rule $\exists$-in'')}
\end{center}

Suppose S1, S2 are true.
Suppose you got $\mathcal{A}(a)$ in a previous 
step. Then you can go to $\exists x,\mathcal{A}(x)$.  
\end{minipage}}\end{center}

\medbreak\noindent COMMENT: This rule says that to prove that ``there 
exists $x$ such that something about $x$ is true'' what you can do is
exhibit an object $a$ for which the thing is true. Such an $a$ is called
a {\em witness} for $\mathcal{A}(x)$. So, to prove that 
$\exists x,\mathcal{A}(x)$, you find a witness.

\medbreak\noindent EXAMPLE. {\em Prove that 
$\exists x,(x\in\zz\wedge x+5=12)$.}

\medbreak\noindent PROOF. 

\pline{\ste $7\in\zz\wedge 7+5=12$\hfill}

\pline{\ste $\exists x,(x\in\zz\wedge x+5=12)$\hfill}

\bigbreak
\begin{center}
\fbox{
\begin{minipage}{11cm}
\vspace{1mm}
\begin{center}
{\bf THE EXISTENTIAL SPECIALIZATION RULE\\
(a.k.a. ``Rule $\exists$-out'')}
\end{center}

Suppose S1, S2 are true.  Suppose you have $\exists x,\mathcal{A}(x)$
in a proof $P$ (which could itself be a subproof of another proof).
Then you can start a subsubproof $P'$ within $P$ by saying ``Pick $a$
such that $\mathcal{A}(a)$,'' provided that until that point $a$ had
never appeared in $P$.  Suppose that in $P'$ you get 
$\mathcal{B}$, where $\mathcal{B}$ is a sentence that does not contain
the constant $a$. Then you can get
out of $P'$ and go to $\mathcal{B}$ in $P$.

In other words:

\pline{\ste $\exists x,\mathcal{A}(x)$\hfill}

\pline{\ste\ste\ste Pick $a$ such that $\mathcal{A}(a)$\hfill} 

\pline{\ste\ste\ste $\vdots$\hfill} 

\pline{\ste\ste\ste $\mathcal{B}$\hfill}

\pline{\ste\hbox to 2cm{\hrulefill}\hfill}

\pline{\ste $\mathcal{B}$\hfill}

\medbreak provided that $a$ has not appeared before the ``PIck $a$''
step, and $\mathcal{B}$ does not contain $a$.
\end{minipage}}\end{center}

\medbreak\noindent EXAMPLE. Suppose $m,n$ are integers, $n|m$, 
$n>0$, $m>0$, and $n$ is composite. Prove that $m$ is composite.

\medbreak\noindent PROOF. Since $n$ is composite, $n>1$ and 
$\exists x,(x|n\wedge 1<x\wedge x<n)$. Pick one such $x$ and call
it $a$. Then $a>1$, $a<n$, and $a|n$. Since $a|n$, 
$\exists x,n=a.x$. Pick one such $x$ and call it $b$. Then
$n=a.b$. Since $n|m$, $\exists x,m=n.x$. Pick one such $x$ and call 
it $c$. Then $m=n.c$. So $m=(a.b).c=a.(b.c)$. Therefore 
$\exists x,m=a.x$. So $a|m$. Furthermore, $n\le m$, because
$n>0$, $m>0$, and $n|m$. Since $a<n$, it follows that $a<m$. So
$a>1\wedge a<m\wedge a|m$. Therefore
$\exists x,(x>1\wedge x<m\wedge x|m)$. So $m$ is composite.\proofend

\bigbreak\noindent{\large The following example shows that if you do not
apply Rule $\exists$-out correctly you can ``prove'' things that are false.}

\begin{center}
\fbox{
\begin{minipage}{12cm}
\vspace{1mm}
\begin{center}
{\bf THE PEANO PARADOX}
\end{center}

\medbreak
THEOREM: $1$ is the largest natural number. 

\medbreak
PROOF: Let $n$ be the largest natural number. Then $n^2$ is a natural 
number too.  Since $n$ was the largest natural number, $n^2\le n$. 
On the other hand, $n\ge 1$, so $n^2=n.n\ge n.1=n$. So $n^2\le n$ and 
$n^2\ge n$. Therefore $n^2=n$. The only solutions $x$ of $x^2=x$ are 
$x=1$ and $x=0$.  So $n=1$ or $n=0$. But $0$ is not a natural number, so
$n$ cannot be $0$. Therefore $n$ has to be equal to $1$. {\bf QED}

\end{minipage}
}
\end{center} 




\end{document}

