\documentclass[twoside,12pt]{article}
\usepackage{light}

%  Commands added so the SAT textbox doesn't end up by itself on a page.

\renewcommand{\floatpagefraction}{0.9}
\renewcommand{\topfraction}{0.9}
\renewcommand{\bottomfraction}{0.9}
\renewcommand{\textfraction}{0.1}

\begin{document}

\lecture{Logic}{February 1, 2005}

\noindent It's really sort of amazing that people manage to
communicate in the English language.  Here are some typical sentences:
%
\begin{enumerate}
\item ``You may have cake or you may have ice cream.''
\item ``If pigs can fly, then you can understand the Chernoff bound.''
\item ``If you can solve any problem we come up with, then you get an
A for the course.''
\item ``Every American has a dream.''
\end{enumerate}
%
What \textit{precisely} do these sentences mean?  Can you have both
cake and ice cream or must you choose just one desert?  If the second
sentence is true, then is the Chernoff bound incomprehensible?  If you
can solve some problems we come up with but not all, then do you get
an A for the course?  And can you still get an A even if you can't
solve any of the problems?  Does the last sentence imply that all
Americans have the same dream or might they each have a different
dream?

Some uncertainty is tolerable in normal conversation.  But when we
need to formulate ideas precisely--- as in mathematics--- the
ambiguities inherent in everyday language become a real problem.  We
can't hope to make an exact argument if we're not sure exactly what
the individual words mean.  (And, not to alarm you, but it is
\textit{possible} that we'll be making an \textit{awful lot} of
exacting mathematical arguments in the weeks ahead.)  So before we
start into mathematics, we need to investigate the problem of how to
talk about mathematics.

To get around the ambiguity of English, mathematicians have devised a
special mini-language for talking about logical relationships.  This
language mostly uses ordinary English words and phrases such as
``or'', ``implies'', and ``for all''.  But mathematicians endow these
words with definitions more precise than those found in an ordinary
dictionary.  Without knowing these definitions, you could sort of read
this language, but you would miss all the subtleties and sometimes
have trouble following along.

Surprisingly, in the midst of learning the language of logic, we'll
come across the most important open problem in computer science--- a
problem whose solution could change the world.

\section{Propositions}

A \term{proposition} is a statement that is either true or false.
This definition is a little vague, but it does exclude sentences such
as, ``What's a surjection, again?'' and ``Learn logarithms!''  Here
are some examples of propositions.
%
\begin{center}
``All Greeks are human.'' \\
``All humans are mortal.'' \\
``All Greeks are mortal.''
\end{center}
%
Archimedes spent a lot of time fussing with such propositions in the
4th century BC while developing an early form of logic.  These are
perfectly good examples, but we'll be more concerned with propositions
of a more mathematical flavor:
%
\begin{center}
``$2 + 3 = 5$''
\end{center}
%
This proposition happens to be true.  Sometimes the truth of a
proposition is more difficult to determine:
%
\begin{center}
``$a^4 + b^4 + c^4 = d^4$ has no solution where $a$, $b$, $c$ are
positive integers.''
\end{center}
%
Euler made this conjecture in 1769.  For 218 years no one knew whether
this proposition was true or false.  Finally, Noam Elkies who works at
the liberal arts school up Mass Ave. found a solution to the equation:
$a = 2682440, b = 15365639, c = 18796760, d = 20615673$.  So the
proposition is false!

There are many famous propositions about primes.  Recall that a
\term{prime} is an integer greater than 1 not divisible by any
positive integer other than 1 and itself.  The first few primes are 2,
3, 5, 7, 11, and 13.  On the other hand, 9 and 77 are not primes,
because 9 is divisible by 3 and 77 is divisible by 7.  The following
proposition is called Goldbach's Conjecture, after Christian Goldbach
who first stated it in 1742.
%
\begin{center}
``Every even integer greater than 2 is the sum of two primes.''
\end{center}
%
Even today, no one knows whether Goldbach's Conjecture is true or
false.  Every even integer ever checked is a sum of two primes, but
just one exception would disprove the claim.

For the next while, we won't be much concerned with the internals of
propositions--- whether they involve mathematics or Greek mortality---
but rather with how propositions are combined and related.  So we'll
frequently use variables such as $P$ and $Q$ in place of specific
propositions such as ``All humans are mortal'' and ``$2 + 3 = 5$''.
The understanding is that these variables, like propositions, can take
on only the values ``true'' and ``false''.  Such true/false variables
are sometimes called \term{Boolean variables} after their inventor,
George something-or-other.

\subsection{Combining Propositions}

In English, we can modify, combine, and relate propositions with words
such as ``not'', ``and'', ``or'', ``implies'', and ``if-then''.
For example, we can combine three propositions into one like this:
%
\begin{center}
\textbf{If} all humans are mortal \textbf{and} all Greeks are human,
\textbf{then} all Greeks are mortal.
\end{center}

\subsubsection{``Not'', ``And'' and ``Or''}

We can precisely define these special words using \term{truth tables}.
For example, if $P$ denotes an arbitrary proposition, then the
validity of the proposition ``not $P$'' is defined by the following
truth table:
%
\[
\begin{array}{c|c}
P & \text{not $P$} \\ \hline
\true & \false \\
\false & \true \\
\end{array}
\]
%
The first row of the table indicates that when proposition $P$ is true
(T), the proposition ``not $P$'' is false (F).  The second line
indicates that when $P$ is false, ``not $P$'' is true.  This is
probably what you would expect.

In general, a truth table indicates the true/false value of a
proposition for each possible setting of the variables.  For example,
the truth table for the proposition ``$P$ and $Q$'' has four lines,
since the two variables can be set in four different ways:
%
\[
\begin{array}{cc|c}
P & Q & \text{$P$ and $Q$} \\ \hline
\true & \true & \true \\
\true & \false & \false \\
\false & \true & \false \\
\false & \false & \false
\end{array}
\]
%
According to this table, the proposition ``$P$ and $Q$'' is true only
when $P$ and $Q$ are both true.  This is probably reflects the way you
think about the word ``and''.

There is a subtlety in the truth table for ``$P$ or $Q$'':
%
\[
\begin{array}{cc|c}
P & Q & \text{$P$ or $Q$} \\ \hline
\true & \true & \true \\
\true & \false & \true \\
\false & \true & \true \\
\false & \false & \false
\end{array}
\]
%
This says that ``$P$ or $Q$'' is true when $P$ is true, $Q$ is true,
or \textit{both} are true.  This isn't always the intended meaning of
``or'' in everyday speech, but this is the standard definition in
mathematical writing.  So if a mathematician says, ``You may have cake
or your may have ice cream'', then you \textit{can} have both.

\subsubsection{``Implies''}

The least intuitive connecting word is ``implies''.  Mathematicians
regard the propositions ``$P$ implies $Q$'' and ``if $P$ then $Q$'' as
synonymous, so both have the same truth table.  (The lines are
numbered so we can refer to the them later.)
%
\[
\begin{array}{rcc|c}
   & P & Q & \parbox[b]{13ex}{$P$ implies $Q$, \\ if $P$ then $Q$} \\ \hline
1. & \true & \true & \true \\
2. & \true & \false & \false \\
3. & \false & \true & \true \\
4. & \false & \false & \true
\end{array}
\]

Let's experiment with this definition.  For example, is the following
proposition true or false?
%
\begin{center}
``If Goldbach's Conjecture is true, then $x^2 \geq 0$ for every real
number $x$.''
\end{center}
%
Now, we told you before that no one knows whether Goldbach's
Conjecture is true or false.  But that doesn't prevent you from
answering the question!  This proposition has the form $P \implies Q$
where $P$ is ``Goldbach's Conjecture is true'' and $Q$ is ``$x^2 \geq
0$ for every real number $x$''.  Since $Q$ is definitely true, we're
on either line 1 or line 3 of the truth table.  Either way, the
proposition as a whole is \textit{true}!

One of our original examples demonstrates an even stranger side of
implications.
%
\begin{center}
``If pigs fly, then you can understand the Chernoff bound.''
\end{center}
%
Don't take this as an insult; we just need to figure out whether this
proposition is true or false.  Curiously, the answer has
\textit{nothing} to do with whether or not you can understand the
Chernoff bound.  Pigs do not fly, so we're on either line 3 or line 4
of the truth table.  In both cases, the proposition is \textit{true}!

In contrast, here's an example of a false implication:
%
\begin{center}
``If the moon is white, then the moon is made of white cheddar.''
\end{center}
%
Yes, the moon is white.  But, no, the moon is not made of white
cheddar cheese.  So we're on line 2 of the truth table, and the
proposition is false.

The truth table for implications can be summarized in words as
follows:
%
\begin{center}
\textit{An implication is true when the if-part is false or the
then-part is true.}
\end{center}
%
This sentence is worth remembering; a large fraction of all
mathematical statements are of the if-then form!

\subsubsection{``If and Only If''}

Mathematicians commonly join propositions in one additional way that
doesn't arise in ordinary speech.  The proposition ``$P$ if and only
if $Q$'' asserts that $P$ and $Q$ are logically equivalent; that is,
either both are true or both are false.
%
\[
\begin{array}{cc|c}
P & Q & P \text{ if and only if } Q \\ \hline
\true & \true & \true \\
\true & \false & \false \\
\false & \true & \false \\
\false & \false & \true
\end{array}
\]
%
The following if-and-only-if statement is true for every real number
$x$:
%
\begin{center}
``$x^2 - 4 \geq 0$ if and only if $|x| \geq 2$''
\end{center}
%
For some values of $x$, \textit{both} inequalities are true.  For
other values of $x$, \textit{neither} inequality is true .  In every
case, however, the proposition as a whole is true.

The phrase ``if and only if'' comes up so often that it is often
abbreviated ``iff''.

\subsection{Propositional Logic in Computer Programs}

Propositions and logical connectives arise all the time in computer
programs.  For example, consider the following snippet, which could be
either C, C++, or Java:
%
\begin{tabbing}
\hspace{1in} \= \quad\quad \= \quad\quad \= \quad\quad \= \kill
\> \texttt{if ( x > 0 || (x <= 0 \&\& y > 100) )} \\
\> \> \textit{(further instructions)}
\end{tabbing}
%
The symbol \texttt{||} denotes ``or'', and the symbol \texttt{\&\&}
denotes ``and''.  The \textit{further instructions} are carried out
only if the proposition following the word \texttt{if} is true.  On
closer inspection, this big expression is built from two simpler
propositions.  Let $A$ be the proposition that \texttt{x > 0}, and let
$B$ be the proposition that \texttt{y > 100}.  Then we can rewrite the
condition this way:
%
\[
A \text{ or } ((\text{not } A) \text{ and } B)
\]
%
A truth table reveals that this complicated expression is logically
equivalent to ``$A \text{ or } B$''.
%
\[
\begin{array}{cc|c|c}
A & B &
    A \text{ or } ((\text{not } A) \text{ and } B) &
    A \text{ or } B \\ \hline
\true & \true & \true & \true \\
\true & \false & \true & \true \\
\false & \true & \true & \true \\
\false & \false & \false & \false
\end{array}
\]
%
This means that we can simplify the code snippet without changing the
program's behavior:
%
\begin{tabbing}
\hspace{1in} \= \quad\quad \= \quad\quad \= \quad\quad \= \kill
\> \texttt{if ( x > 0 || y > 100 )} \\
\> \> \textit{(further instructions)}
\end{tabbing}

Rewriting a logical expression involving many variables in the
simplest form is both difficult and important.  Simplifying
expressions in software might slightly increase the speed of your
program.  But, more significantly, chip designers face essentially the
same challenge.  However, instead of minimizing \texttt{\&\&} and
\texttt{||} symbols in a program, their job is to minimize the number
of analogous physcial devices on a chip.  The payoff is potentially
enormous: a chip with fewer devices is smaller, consumes less power,
has a lower defect rate, and is cheaper to manufacture.

\subsection{A Cryptic Notation}

Programming languages use symbols like $\&\&$ and $!$ in place of
words like ``and'' and ``not''.  Mathematicians have devised their own
cryptic symbols to represent these words, which are summarized in the
table below.
%
\begin{center}
\begin{tabular}{cc}
\textbf{English} & \textbf{Cryptic Notation} \\[1ex]
``not $P$'' & $\neg P$ or $\overline{P}$ \\
``$P$ and $Q$'' & $P \wedge Q$ \\
``$P$ or $Q$'' & $P \vee Q$ \\
``$P$ implies $Q$'' or ``if $P$ then $Q$'' & $P \implies Q$ \\
``$P$ if and only if $Q$'' & $P \iff Q$
\end{tabular}
\end{center}
%
For example, using this notation, ``If $P$ and not $Q$, then $R$''
would be written:
%
\[
(P \wedge \neg Q) \implies R
\]

This symbolic language is helpful for writing complicated logical
expressions compactly.  But in most contexts ordinary words such as
``or'' and ``implies'' are much easier to understand than symbols such
as $\vee$ and $\implies$.  So we'll use this symbolic language
sparingly, and we advise you to do the same.

\subsection{Logically Equivalent Implications}

Are these two sentences saying the same thing?
%
\begin{center}
If I am hungry, then I am grumpy. \\
If I am not grumpy, then I am not hungry.
\end{center}
%
We can settle the issue by recasting both sentences in terms of
propositional logic.  Let $P$ be the proposition ``I am hungry'', and
let $Q$ be ``I am grumpy''.  The first sentence says ``$P$ implies
$Q$'' and the second says ``(not $Q$) implies (not $P$)''.  We can
compare these two statements in a truth table:
%
\[
\begin{array}{c|c|c|c}
P & Q &
    \text{$P$ implies $Q$} &
    \text{(not $Q$) implies (not $P$)} \\ \hline
\true & \true & \true & \true \\
\true & \false & \false & \false \\
\false & \true & \true & \true \\
\false & \false & \true & \true
\end{array}
\]
%
Sure enough, the two statements are precisely equivalent.  In general,
``(not $Q$) implies (not $P$)'' is called the \term{contrapositive} of
``$P$ implies $Q$''.  And, as we've just shown, the two are just
different ways of saying the same thing.  This equivalence is mildly
useful in programming, mathematical arguments, and even everyday
speech, because you can always pick whichever of the two is easier to
say or write.

In contrast, the \term{converse} of ``$P$ implies $Q$'' is the
statement ``$Q$ implies $P$''.  In terms of our example, the converse
is:
%
\begin{center}
If I am grumpy, then I am hungry.
\end{center}
%
This sounds like a rather different contention, and a truth table
confirms this suspicion:
%
\[
\begin{array}{c|c|c|c}
P & Q &
    \text{$P$ implies $Q$} &
    \text{$Q$ implies $P$} \\ \hline
\true & \true & \true & \true \\
\true & \false & \false & \true \\
\false & \true & \true & \false \\
\false & \false & \true & \true
\end{array}
\]
%
Thus, an implication \textit{is} logically equivalent to its
contrapositive, but is \textit{not} equivalent to its converse.

One final relationship: an implication and its converse together are
equivalent to an if and only if statement.  Specifically, these two
statements together:
%
\begin{center}
If I am grumpy, then I am hungry. \\
If I am hungry, then I am grumpy.
\end{center}
%
are equivalent to the single statement:
%
\begin{center}
I am grumpy if and only if I am hungry.
\end{center}
%
Once again, we can verify this with a truth table:
%
\[
\begin{array}{c|c|c|c}
P & Q &
    \text{($P$ implies $Q$) and ($Q$ implies $P$)} &
    \text{$Q$ if and only if $P$} \\ \hline
\true & \true & \true & \true \\
\true & \false & \false & \false \\
\false & \true & \false & \false \\
\false & \false & \true & \true
\end{array}
\]

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

\floatingtextbox{
\textboxtitle{SAT}

A proposition is \textbf{satisfiable} if some setting of the variables
makes the proposition true.  For example, $P \wedge \neg Q$ is
satisfiable because the expression is true when $P$ is true and $Q$ is
false.  On the other hand, $P \wedge \neg P$ is not satisfiable
because the expression as a whole is false for both settings of $P$.
But determining whether or not a more complicated proposition is
satisfiable is not so easy.  How about this one?
%
\[
(P \vee Q \vee R) \wedge (\neg P \vee \neg Q)
                  \wedge (\neg P \vee \neg R)
                  \wedge (\neg R \vee \neg Q)
\]

The general problem of deciding whether a proposition is satisfiable
is called \term{SAT}.  One approach to SAT is to construct a truth
table and check whether or not a $\true$ ever appears.  But this
approach is not very efficient; a proposition with $n$ variables has a
truth table with $2^n$ lines.  For a proposition with just 30
variables, that's already over a billion!

Is there an \textit{efficient} solution to SAT?  Is there some
ingenious procedure that \textit{quickly} determines whether any given
proposition is satifiable or not?  No one knows.  And an awful lot
hangs on the answer.  An efficient solution to SAT would immediately
imply efficient solutions to many, many other important problems
involving packing, scheduling, routing, and circuit verification.
This sounds fantastic, but there would also be worldwide chaos.
Decrypting coded messages would also become an easy task (for most
codes).  Online financial transactions would be insecure and secret
communications could be read by everyone.

At present, though, researchers are completely stuck.  No one has a
good idea how to either solve SAT more efficiently or to prove that no
efficient solution exists.  This is the outstanding unanswered
question in computer science.}

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

\section{Sets and Sequences}

Propositions of the sort we've considered so far are good for
reasoning about individual statements, but not so good for reasoning
about a collection of objects.  Let's first review a couple
mathematical tools for grouping objects and then extend our logical
language to cope with such collections.

A \term{set} is a collection of distinct objects, which are called
\term{elements}.  The elements of a set can be just about anything:
numbers, points in space, or even other sets.  The conventional way to
write down a set is to list the elements inside curly-braces.  For
example, here are some sets:
%
\[
\begin{array}{rcll}
\mathbb{N} & = & \set{0, 1, 2, 3, \ldots} & \text{the natural numbers} \\
C & = & \set{\text{red}, \text{blue}, \text{yellow}} & \text{primary colors} \\
D & = & \set{\text{Nifty}, \text{Friend}, \text{Horatio}, \text{Pretty-Pretty}} & \text{dead pets} \\
P & = & \set{ \set{a, b}, \set{a, c}, \set{b, c}} & \text{a set of sets}
\end{array}
\]
%
The elements of a set are required to be distinct; a set can not
contain multiple copies of the same element.  The order of elements is
not significant, so $\set{x, y}$ and $\set{y, x}$ are the same set
written two different ways.  The expression $e \in S$ asserts that $e$
is an element of set $S$.  For example, $7 \in \mathbb{N}$ and
$\text{blue} \in C$, but $\text{Wilbur} \not\in D$ yet.

Sets are simple, flexible, and everywhere.  You'll find at least one
set mentioned on almost every page in these notes.

\subsection{Some Popular Sets}

Mathematicians have devised special symbols to represent some common
sets.

\begin{center}
\begin{tabular}{ccc}
\textbf{symbol} & \textbf{set} & \textbf{elements} \\
$\emptyset$ & the empty set & \text{none}\\
$\mathbb{N}$ & natural numbers & $\set{0, 1, 2, 3, \ldots}$ \\
$\mathbb{Z}$ & integers & $\set{\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots}$ \\
$\mathbb{Q}$ & rational numbers & $\frac{1}{2},\ -\frac{5}{3},\ 16,\ \text{etc.}$ \\
$\mathbb{R}$ & real numbers & $\pi,\ e,\ -9,\ \text{etc.}$ \\
$\mathbb{C}$ & complex numbers & $i,\ \frac{19}{2},\ \sqrt{2} - 2i,\ \text{etc.}$
\end{tabular}
\end{center}
%
A superscript $+$ restricts a set to its positive elements; for
example, $\mathbb{R}^+$ is the set of positive real numbers.

\subsection{Comparing and Combing Sets}

The expression $S \subseteq T$ indicates that set $S$ is a
\term{subset} of set $T$, which means that every element of $S$ is
also an element of $T$.  For example, $\mathbb{N} \subseteq
\mathbb{Z}$ (every natural number is an integer) and $\mathbb{Q}
\subseteq \mathbb{R}$ (every rational number is a real number), but
$\mathbb{C} \not\subseteq \mathbb{Z}$ (not every complex number is an
integer).

As a memory trick, notice that the $\subseteq$ points to the smaller
set, just like a $\leq$ sign points to the smaller number.  Actually,
this connection goes a little further: there is a symbol $\subset$
analogous to $<$.  Thus, $S \subset T$ means that $S$ is a subset of
$T$, but the two are not equal.  So for every set $A$, $A \subseteq
A$, but $A \not\subset A$.

There are several ways to combine sets.  Let's define a couple for use
in examples:
%
\begin{align*}
X & = \set{1, 2, 3} \\
Y & = \set{2, 3, 4}
\end{align*}
%
\begin{itemize}

\item The \textbf{union} of sets $X$ and $Y$ (denoted $X \cup Y$)
contains all elements appearing in $X$ or $Y$ or both.  Thus, $X \cup
Y = \set{1, 2, 3, 4}$.

\item The \textbf{intersection} of $X$ and $Y$ (denoted $X \cap Y$)
consists of all elements that appear in \textit{both} $X$ and $Y$.  So
$X \cap Y = \set{2, 3}$.

\item The \textbf{difference} of $X$ and $Y$ (denoted $X - Y$)
consists of all elements that are in $X$, but not in $Y$.  Therefore,
$X - Y = \set{1}$ and $Y - X = \set{4}$.

\end{itemize}

Sometimes one is exclusively concerned with subsets of a certain large
set.  For example, we might be focused on subsets of a the real
numbers.  In this case, we can talk about the \textbf{complement} of a
set $Z$, which consists of all elements \textit{not} in $Z$ and is
denoted $\overline{Z}$.  For example, when we're working with the real
numbers $\mathbb{R}$, the complement of the positive real numbers is
the set of negative real numbers together with zero.

\subsection{Sequences}

Sets provide one way to group a collection of objects.  Another way is
in a \term{sequence}, which is a list of objects called \term{terms}
or \term{components}.  Short sequences are commonly described by
listing the elements between parentheses; for example, $(a, b, c)$ is
a sequence with three terms.

While both sets and sequences perform a gathering role, there are
several differences.
%
\begin{itemize}

\item The elements of a set are required to be distinct, but terms in
a sequence can be the same.  Thus, $(a, b, a)$ is a valid sequence,
but $\set{a, b, a}$ is not a valid set.

\item The terms in a sequence have a specified order, but the elements
of a set do not.  For example, $(a, b, c)$ and $(a, c, b)$ are
different sequences, but $\set{a, b, c}$ and $\set{a, c, b}$ are the
same set.

\item The empty set is usually denoted $\emptyset$, and the empty
sequence is typically $\lambda$.

\end{itemize}

The product operation is one link between sets and sequences.  A
\term{product} of sets, $S_1 \times S_2 \times \ldots \times S_n$, is
a new set consisting of all sequences where the first component is
drawn from $S_1$, the second from $S_2$, and so forth.  For example,
$\mathbb{N} \times \mathbb{N}$ is the set of all pairs of natural
numbers:
%
\[
\mathbb{N} \times \mathbb{N}
    = \set{(0,0), (0,1), (1,0), (0,2), (1,1), (2, 0), \ldots}
\]
%
A product of $n$ copies of a set $S$ is denoted $S^n$.  For example,
$\set{0, 1}^3$ is the set of all $3$-bit sequences:
%
\[
\set{0, 1}^3 = \set{ (0,0,0), (0,0,1), (0,1,0), (0,1,1),
                     (1,0,0), (1,0,1), (1,1,0), (1,1,1) }
\]

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

\section{Predicates}

A \term{predicate} is a proposition whose truth depends on the value
of one or more variables.  For example,
%
\begin{center}
``$n$ is a perfect square''
\end{center}
%
is a predicate whose truth depends on the value of $n$.  The predicate
is true for $n = 4$ since $4$ is a prefect square, but false for $n =
5$ since 5 is not a perfect square.

Like other propositions, predicates are often named with a letter.
Furthermore, a function-like notation is used to denote a predicate
supplied with specific variable values.  For example, we might name
our earlier predicate $P$:
%
\[
P(n) = \text{``$n$ is a perfect square''}
\]
%
Now $P(4)$ is true, and $P(5)$ is false.

This notation for predicates is confusingly similar to ordinary
function notation.  If $P$ is a predicate, then $P(n)$ is either
\textit{true} or \textit{false}, depending on the value of $n$.  On
the other hand, if $P$ is an ordinary function, like $n^2 + 1$, then
$P(n)$ is a \textit{numerical quantity}.  Students frequently confuse
these two, but that's what thumbscrews are for.

\subsection{Quantifying a Predicate}

There are a couple kinds of assertion one commonly makes about a
predicate: that it is \textit{sometimes} true and that it is
\textit{always} true.  For example, the predicate
%
\[
\text{``$x^2 \geq 0$''}
\]
%
is always true when $x$ is a real number.  On the other hand, the
predicate
%
\[
\text{``$5x^2 - 7 = 0$''}
\]
%
is only sometimes true; specifically, when $x = \pm \sqrt{7/5}$.

There are several ways to express the notions of ``always true'' and
``sometimes true'' in English.  The table below gives some general
formats on the left and specific examples using those formats on the
right.  You can expect to see such phrases hundreds of times in
mathematical writing!
%
\begin{center}
\begin{tabular}{cc}
\multicolumn{2}{c}{\textbf{Always True}} \\[1ex]
``For all $n$, $P(n)$ is true.'' & ``For all $x$, $x^2 \geq 0$. \\
``$P(n)$ is true for every $n$.'' & ``$x^2 \geq 0$ for every $x$.'' \\[2ex]
\multicolumn{2}{c}{\textbf{Sometimes True}} \\[1ex]
``There exists an $n$ such that $P(n)$ is true.'' & ``There exists an $x$ such that $5x^2 - 7 = 0$''.\\
``$P(n)$ is true for some $n$.'' & ``$5x^2 - 7 = 0$ for some $x$.''\\
``$P(n)$ is true for at least one $n$.'' & ``$5x^2-7=0$ for at least one $x$.''
\end{tabular}
\end{center}

All these sentences quantify how often the predicate is true.
Specifically, an assertion that a predicate is always true is called a
\term{universal} quantification, and an assertion that a predicate is
sometimes true is an \term{existential} quantification.  Sometimes the
English sentences are unclear with respect to quantification:
%
\begin{center}
``If you can solve any problem we come up with, then you get an A for
the course.''
\end{center}
%
The phrase ``you can solve any problem we can come up with'' could
reasonably be interpreted as either a universal or existential
quantification:
%
\begin{center}
``you can solve \textit{every} problem we come up with'' \\
``you can solve \textit{at least one} problem we come up with''
\end{center}
%
In any case, notice that this quantified phrase appears inside a
larger if-then statement.  This is quite normal; quantified statements
are themselves propositions and can be combined with and, or, implies,
etc. just like any other proposition.

\subsection{More Cryptic Notation}

There are symbols to represent universal and existential
quantification, just as there are symbols for ``and'' ($\wedge$),
``implies'' ($\implies$), and so forth.  In particular, to say that a
predicate $P(n)$ is true for all values of $n$ in some set $S$, one
writes:
%
\[
\forall n \in S\ P(n)
\]
%
The symbol $\forall$ is read ``for all'', so this whole expression is
read ``for all $n$ in $S$, $P(n)$ is true''.  To say that a predicate
$P(n)$ is true for at least one value of $n$ in $S$, one writes:
%
\[
\exists n \in S\ P(n)
\]
%
The backward-E is read ``there exists''.  So this expression would be
read, ``There exists an $n$ in $S$ such that $P(n)$ is true.  The
symbols $\forall$ and $\exists$ are always followed by a variable and
then a predicate, as in the two examples above.

As an example, let $P$ be the set of problems we come up with, $S(x)$
be the predicate ``You can solve problem $x$'', and $A$ be the
proposition, ``You get an A for the course.''  Then the two
different interpretations of
%
\begin{center}
``If you can solve any problem we come up with, \\
then you get an A for the course.''
\end{center}
%
can be written as follows:
%
\[
(\forall x \in P\ S(x)) \implies A \hspace{1in}
(\exists x \in P\ S(x)) \implies A
\]

\subsection{Mixing Quantifiers}

Many mathematical statements involve several quantifiers.  For
example, Goldbach's Conjecture states:
%
\begin{center}
``Every even integer greater than 2 is the sum of two primes.''
\end{center}
%
Let's write this more verbosely to make the use of quantification more
clear:
%
\begin{center}
``For every even integer $n$ greater than 2, \\
there exist primes $p$ and $q$ such that $n = p + q$.''
\end{center}
%
Let $E$ be the set of even integers greater than 2, and let $P$ be the
set of primes.  Then we can write Goldbach's Conjecture in logic
notation as follows:
%
\[
\underbrace{\forall n \in E}_{\substack
    {\text{for every even} \\
     \text{integer $n \geq 2$}}}
\ 
\underbrace{\exists p \in P\ \exists q \in P}_{\substack
    {\text{there exist primes} \\
     \text{$p$ and $q$ such that}}}
\ 
n = p + q
\]

\subsection{Order of Quantifiers}

Swapping the order of different kinds of quantifiers (existential or
universal) changes the meaning of a proposition.  For another example,
let's return to one of our initial, confusing statements:
%
\begin{center}
``Every American has a dream.''
\end{center}
%
This sentence is ambiguous because the order of quantifiers is
unclear.  Let $A$ be the set of Americans, let $D$ be the set of
dreams, and define the predicate $H(a, d)$ to be ``American $a$ has
dream $d$.''.  Now the sentence could mean there is a single dream
that every American shares:
%
\[
\exists d \in D\ \forall a \in A\ H(a, d)
\]
%
Or it could mean that every American has an individual dream:
%
\[
\forall a \in A\ \exists d \in D\ H(a, d)
\]
%
Swapping quantifiers in Goldbach's Conjecture creates a patently false
statement:
%
\[
\underbrace{\exists p \in P\ \exists q \in P}_{\substack
    {\text{there exist primes} \\
     \text{$p$ and $q$ such that}}}
\ 
\underbrace{\forall n \in E}_{\substack
    {\text{for every even} \\
     \text{integer $n \geq 2$}}}
\
n = p + q
\]


\subsection{Negating Quantifiers}

There is a duality between the two kinds of quantifiers.  The
following two sentences mean the same thing:
%
\begin{center}
``It is not the case that everyone likes to snowboard.'' \\
``There exists someone who does not like to snowboard.''
\end{center}
%
In terms of logic notation, this follows from a general equivalence:
%
\[
\neg \forall x\ P(x)
\hspace{0.5in} \iff \hspace{0.5in}
\exists x\ \neg P(x)
\]
%
Similarly, these sentences mean the same thing:
%
\begin{center}
``There does not exist anyone who likes skiing over magma.'' \\
``Everyone dislikes skiing over magma.''
\end{center}
%
We can express the equivalence in logic notation this way:
%
\[
\neg \exists x\ Q(x)
\hspace{0.5in} \iff \hspace{0.5in}
\forall x\ \neg Q(x)
\]
%
The general principle is that \textit{moving a ``not'' across a
quantifier changes the kind of quantifier.}

\subsection{Set Builder Notation}

One specialized, but important use of predicates is in \term{set
builder notation}.  We'll often want to talk about sets that can not
be described very well by listing the elements explicitly or by taking
unions, intersections, etc. of easily-described sets.  Set builder
notation often comes to the rescue.  The idea is to define a
\textit{set} using a \textit{predicate}; in particular, the set
consists of all values that make the predicate true.  Here are some
examples of set builder notation:
%
\begin{align*}
A & = \set{n \in \mathbb{N} \mid \text{$n$ is a prime and $n = 4k+1$ for some integer $k$}} \\
B & = \set{x \in \mathbb{R} \mid x^3 - 3 x + 1 > 0} \\
C & = \set{a + b i \in \mathbb{C} \mid a^2 + 2 b^2 \leq 1}
\end{align*}
%
The set $A$ consists of all natural numbers $n$ for which the
predicate
%
\begin{center}
``$n$ is a prime and $n = 4k+1$ for some integer $k$''
\end{center}
%
is true.  Thus, the smallest elements of $A$ are:
%
\[
5, 13, 17, 29, 37, 41, 53, 57, 61, 73, \ldots
\]
%
Trying to indicate the set $A$ by listing these first few elements
wouldn't work very well; even after ten terms, the pattern is not
obvious!  Similarly, the set $B$ consists of all real numbers $x$ for
which the predicate
%
\[
x^3 - 3x + 1 > 0
\]
%
is true.  In this case, an explicit description of the set $B$ in
terms of intervals would require solving a cubic equation.  Finally,
set $C$ consists of all complex numbers $a + b i$ such that:
%
\[
a^2 + 2 b^2 \leq 1
\]
%
This is an oval-shaped region around the origin in the complex plane.
\end{document}

\iffalse
Logicians have worked very hard to define strict rules for the use of
logic notation so that ideas can be expressed with absolute rigor.
It's all quite charming and clever.  However, the sad irony is that
applied mathematicans usually use their beloved notation as a crude
shorthand, breaking the rules and abusing the notation willy-nilly---
sort of like pounding nails with fine china.
\fi
