\documentclass[11pt,twoside]{article}
%\input{../handouts/macros-course}
\usepackage{/a/class/6.042/fall00/newlectures/macros-course-lectures}
\usepackage{graphics}

\textwidth=6.5in
%\topmargin=-.15in
%\evensidemargin=0.75in
%\oddsidemargin=0.7pt
%\newcommand {\pindent} {\hspace*{20pt}}
\textheight=9.5in
\parskip=12pt plus 2pt minus 2pt
\pagestyle{empty}
\setlength{\parindent}{0in}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\newcommand{\pagetitle}[1]{\newpage {\bf #1} \hfill 
L5$-$P. \thepage \\ \vspace{-0.5cm} \hrule \vspace{12mm}}
\newcommand{\doublespace}{\addtolength{\baselineskip}{.35\baselineskip}}
%\newcommand{\remove}[1]{}


\begin{document}

\renewcommand{\thepage}{\arabic{page}}


\Huge
\pagetitle{Lecture Overview}

Predicates\\
\\
Predicate reasoning examples\\
\\
(Ordinary) mathematical induction\\
\\
Inductive proof examples


\pagetitle{Predicates}

\noindent
Predicates are similar to propositions\\
but depend on variables\\
$P(x,y,z)$ denotes a predicate on variables $x,y,z$

$P(x)$: $x$ is a prime number.\\
$Q(x)$: $x > 2$.\\
$R(x)$: $x$ is an odd number.


Predicates are {\em not} propositions\\
because they can be true or false\\
depending on the value of the variable $x$.

When the value of $x$ is not specified,\\
we say $x$ is \emph{unbound}.

Predicates are like functions\\
from the domains of the variables to propositions.\\
$P(2)$ is true.\\
$R(2)$ is false.\\
$P(4) \vee R(3)$ is true.\\
$Q(3) \wedge R(4)$ is false.\\
$Q(1) \Rightarrow R(2)$ is true.

\pagetitle{Quantifiers}

Propositions may assert ---\\
something is true for all or some elements\\
of a given domain (e.g., all natural numbers).

When a particular {\bf universe of
discourse} is agreed upon in advance then:

``$\forall$'' means ``for all'',
$\forall x P(x)$ is a statement that is true:
iff $P(x)$ is true for {\em every} $x$ in the universe of
discourse.

``$\exists$'' means ``there exists.'' $\exists x P(x)$ is true
iff $P(x)$ is true for {\em at least one} $x$ in the universe of
discourse.

``$\nexists$'' mean ``there does not exist'' (``there is no'').

``$\exists !$'' means ``there exists {\em exactly} one.''

$\forall x \in S$'' means ``for every $x$ in the set $S$.''

$(\forall x \in S) P(x)$ is equivalent to $\forall x (x \in S \Rightarrow P(x)).$

\pagetitle{Quantifiers turn predicates\\ into propositions}

$\forall x (P(x) \wedge Q(x) \Rightarrow R(x))$

Each occurrence of $x$ is associated with the $\forall$ quantifier.

The quantifier makes the variable to be {\em bound}.

Thus, $\forall x (P(x) \wedge Q(x) \Rightarrow R(x))$
is a predicate.

$P(x)$: $x$ is a prime number.\\
$Q(x)$: $x > 2$.\\
$R(x)$: $x$ is an odd number.

Every prime number greater than 2 is an odd number.

\pagetitle{Quantifiers Cont.}

$\forall x \exists y$ is {\em different} from $\exists y
\forall x$:\\

Suppose $S(x,y)$ means student $x$ falls asleep in class $y$.\\
\\
What is?  $\forall y \exists x S(x,y):$\\
\\
``In every class, some student falls asleep.''
\\
And what is? $\exists x \forall y S(x,y):$\\
\\
``There exists a student who
falls asleep in every class.''

\pagetitle{Deduction rules\\ involving quantifiers}

Deduction rules for arbitrary propositions: e.g.,
Modus ponens: \\
Given that $P$ and $P \Rightarrow Q$ are both true \\
Conclude:  $Q$

Deduction rules for propositions with quantifiers:

$\neg [\forall x S(x)]$ is equivalent to $\exists x \neg S(x)$. \\
Example: $\forall x S(x):$  For all primes $x > 2$, $x$ is odd. \\
$\exists x \neg S(x):$  There is some prime $x > 2$ such that $x$
is not odd.\\
(Domain of discourse:  Primes $>2$)

$\neg [\exists x S(x)]$ is equivalent to $\forall x \neg S(x)$. \\
  Example: $\exists x S(x):$  There is an even prime.\\
  $\forall x \neg S(x):$  All primes are not even.\\
  (Domain of discourse:  Primes)

\pagetitle{Manipulating Quantifiers\\ in Proofs}

We reason about propositions with quentfiers\\
(predicates with quantifiers that bound
variables)\\
Using the following rules:

Universal Generalization UG:
To prove something is true for all $x$ ($\forall x$),
we can show that it works for an arbitrary fixed $x$.

Universal Instantiation UI:
If a statement is true for all $x$ ($\forall x$), then it is true for
any particular $x$ we want to study.

Existential Generalization EG: 
If we have exhibited one $x$ that satisfies some property, we have
proved one exists ($\exists x$).

Existential Instantiation EI:
If we know that some $x$ exists satisfying a property ($\exists x$),
then we can choose one and use it in the proof.

\pagetitle{Predicate reasoning examples}

\begin{tabbing}
xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \kill
Prove: $\forall n \in N (n^2 + n \mbox{ is even})$. \\
1. Fix $n \in N$. \\
2. $n^2 + n$ is even.
\> \> \> \> \> ??? \\
3. QED
\> \> \> \> \> Universal Generalization (UG)
\end{tabbing}

Fix any arbiterary element $n$ and prove for it.

To show step 2, we can use cases:
\begin{tabbing}
xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \kill
Prove: $\forall n \in N (n^2 + n \mbox{ is even})$. \\
1. Fix $n \in N$. \\
2. $n^2 + n$ is even. \\
\> 1. If $n$ is odd then $n^2 + n$ is even.
   \> \> \> \> \> \> \> \> \> \> \>   ??? \\
\> 2. If $n$ is even then $n^2 + n$ is even.
   \> \> \> \> \> \> \> \> \> \> \>   ??? \\
\> 3. QED      
   \> \> \> \> \> \> \> \>Cases \\
3. QED
\end{tabbing}

\pagetitle{Predicate reasoning\\ examples, Cont.}
\begin{tabbing}
xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \kill
\> 2. If $n$ is even then $n^2 + n$ is even.   \\
\> \> 1. Assume $n$ is even. \\
\> \> 2. $n^2 + n$ is even. \\
\> \> \> 1. $\exists x \in N (n = 2x)$\\
\> \> \> \> \> Definition of ``even'' \\
\> \> \> 2. Choose $x \in N$, $n = 2x$\\
\> \> \> \> \> Existential Instantiation (EI) \\
\> \> \> \> \> (If {\em exists\/} one, can {\em choose\/} one.) \\
\> \> \> 3. $n^2 + n = 4x^2 + 2x =$\\
\> \> \> \> \> \> $2(2x^2 + x)$\\
\> \> \> \> \> Algebra \\
\> \> \> 4. $\exists y \in N (n^2 + n = 2y)$\\
\> \> \> \> \> Existential Generalization (EG) \\
\> \> \> \> \> (If you {\em have\/} one, then one {\em exists}.) \\
\> \> \> 5. QED
         \> \> Definition of ``even'' \\
\> \> 3. QED   
      \> \> \> Implication
\end{tabbing}

\pagetitle{Predicate reasoning\\ examples, Cont.}
\begin{tabbing}
xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \kill
\> 1. If $n$ is odd then $n^2 + n$ is even.   \\
\> \> 1. Assume $n$ is odd. \\
\> \> 2. $n^2 + n$ is even. \\
\> \> \> 1. $\exists x \in N (n = 2x + 1)$\\
\> \> \> \> \> Definition of ``odd'' \\
\> \> \> 2. Choose $x \in N$, $n = 2x + 1$\\
\> \> \> \> \> EI \\
\> \> \> 3. $n^2 + n = 4x^2 + 4x + 1 + 2x + 1 =$\\ 
\> \> \> \> \> \>$2(2x^2 + 3x + 1)$ \\
\> \> \> \> \> Algebra \\
\> \> \> 4. $\exists y \in N (n^2 + n = 2y)$\\
\> \> \> \> \> EG \\
\> \> \> 5. QED --- Definition of ``even'' \\
\> \> 3. QED --- Implication\\
\end{tabbing}

\pagetitle{Quentifire reasoning $\sqrt{2}$, Ex.}

\vspace{-1cm}
\begin{tabbing}
xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \= xx \kill
Prove: $\sqrt{2}$ is irrational. \\
1. $\sqrt{2}$ rational $\Rightarrow \ms{false}$ \\
\> 1. Assume $\sqrt{2}$ rational. \\
\> 2. $\ms{false}$ \\
\> \> 1. Choose $a, b \in N^{+}$, $\sqrt{2} = \frac{a}{b}$, lowest terms.\\
\> \> \> \> \> Basic properties of rationals, EI \\
\> \> 2. $2 b^2 = a^2$   --- Algebra \\
\> \> 3. $a^2$ is even. --- EG, definition of ``even'' \\
\> \> 4. $a$ is even.  --- ??? \\
\> \> 5. Choose $c \in N$, $a = 2c$.\\
\> \> \> \> \> Definition of ``even'', EI \\
\> \> 6. $4 c^2 = a^2 = 2b^2$ ---  Algebra \\
\> \> 7. $2 c^2 = b^2$ Algebra \\
\> \> 8. $b^2$ is even --- EG, definition of ``even'' \\
\> \> 9. $b$ is even. --- ??? \\
\> \> 10. $a$, $b$ aren't in lowest terms, 1.2.4, 1.2.9 \\
\> \> 11. QED --- 1.2.1, 1.2.10, propositional logic \\
\> 3.  QED --- Implication \\
2. QED --- Contradiction
\end{tabbing}

\end{document}	
