\documentclass{beamer}
\usepackage[english]{babel}
\usetheme{CambridgeUS} %% \usepackage{beamerthemesplit}%% Activate for custom appearance
 \usepackage{amsmath}
 \usepackage{amssymb}
 \usepackage{amsthm}
\usepackage{verbatim}
\usepackage{booktabs}
%\usepackage{fancybox}
\title{Introduction to Sets \& Quantifiers}
%\author{T. Reinhardt}
\date{Fall 2013}
\usepackage[cmtip,all]{xy}
%% some definitions
%\newtheorem{exercise}{Do in class}
\newcommand{\inclass}[1]{\huge \centerline{ \textcolor{red}{ \fcolorbox{red}{yellow}{#1} } } }
\newcommand{\question}[1]{ \textcolor{red}{#1} }
\newtheorem{exercise}{Classroom Exercise}
%\newtheorem{example}{Example}
\begin{document}
\setlength{\fboxrule}{2pt}
\frame{\titlepage}
%
%\section[Outline]{}
%\frame{\tableofcontents}

\section{Introduction}
\subsection{Learning Outcomes for this Presentation}
\frame
{
  \frametitle{Learning Outcomes \dots}
At the conclusion of this session, we will
 \begin{itemize}
	\item Define mathematical sets; explore sets that are particularly relevant to this class.
	\item Define logical quantifiers
	\item Translate between English and quantified statements.
	\item Negate some quantified statements and characterize their truth sets.
	\item Employ both existential and universal quantifiers in various orders.
	\item Prove a validity (and show that its converse does not necessarily follow.)
  \end{itemize}
}

\frame{
\frametitle{Important definition(s)}
\begin{definition}
A \emph{set} is a collection of distinct objects called its \emph{elements}.
\end{definition}
\centering{One important property of a set is its ``size:''}
\begin{definition}
The \emph{cardinality} or size of a set is the number of elements it contains.
\end{definition}

\begin{itemize}
 \item A set may be empty, i.e., contain no elements: we will write $\emptyset$ or $\{\}$.
  (Or, a set may contain an infinite number of elements.)
 \item We will use the$\lvert S \rvert$ or the $\#(S)$ symbols to name the function (to be defined shortly) that
takes a set to its cardinality.
\end{itemize}

}

\frame{
\frametitle{Some other properties of sets}
In addition to its cardinality (size), sets are also characterized as:
\begin{description}
 \item[Empty or Non-Empty] Non empty sets exhibit different properties than empty sets.
 \item[Finite or Infinite] Popular ``number systems,'' such as the integers and reals are infinite, while
 most sets that interest computer science are finite.
 \item[Countable or Uncountable] Sets containing discrete objects are ``countable,'' whereas sets comprised
 of continuous objects are not---we will explore these differences later in this course.
\item[Ordered or Unordered] Self-explanatory---even ordered sets, however, have different kinds of orderings. 
\end{description}
}

\frame{
 \frametitle{Some important set properties, cont'd.}
 Unless told otherwise, assume that we are working with \emph{abstract} sets.
 \begin{itemize}
 \item<1->Elements in a set are assumed to be \emph{unique}.
For example:
\begin{align*}
\{a,b,c\} &\equiv \{a,b,a,b,c\}\\
\{1\} & \equiv \{1,1,1,1,1\}\\
\end{align*}
\item<2->Unless other specified, sets are \emph{unordered}:
\[
\{b,c,a,d\} \equiv \{a,b,c,d\} \equiv \{a,c,d,b\} \cdots .
\]
\end{itemize}

}

\frame{
\frametitle{Ways of writing sets \dots }
\begin{itemize}
\item<1-> Small sets may sometimes be specified \emph{explicitly}, such as in 
 \[
 S = \{a,b,c,d\},
 \]
 where each element is explicitly given, or
 \item<2-> By \emph{set-builder} notation,
 \[
 T = \{ a\; \vert \; \text{a is an even positive integer} \}.
 \]
 \item<3-> More compactly, replace the text between the braces with a function whose value
 is true/false, such as ``is an even integer.'' Such functions are called \emph{predicates}. Let $E(x)$ be
 the predicate that returns true if $x$ is an even positive integer; now 
 \[
 T = \{ a\; \vert \; E(a) \}.
 \]
\end{itemize}
}

\frame{
\frametitle{Sets that are interesting to us \dots}
We will frequently reference the following sets:
 $\mathbb{Z}, \mathbb{N}, \mathbb{Q},$ and $\mathbb{R}$, along with several common ``superscripts.''
 \bigskip
 
 \inclass{{Define these now.}}
}

\frame{
\frametitle{Functions \& and Sets}
We will spend lots of time with formal definitions and proofs regarding functions later, but
 for now we need a working understanding\dots
\begin{definition}[Function]
A \emph{function} is a \emph{unitary mapping} between one set called the \emph{domain} to another
set called the \emph{codomain}. A unitary mapping associates each point in one set (the domain) to 
exactly one point in another set (the codomain).
\end{definition}
Notation: $f\colon A \longrightarrow B$ or $\xymatrix@1{A\ar[r]^{f} &B}$, denotes the function $f$ with $\mathrm{dom}(f)=A$ and
$\mathrm{cod}(f)=B$.\\
\begin{center}
Functions reveal the underlying structure of their domains and codomains.
\end{center}
}



\frame{
\frametitle{Functions that tell us about elements of a set}

\begin{definition}
The $\in$ function takes any object and a set and returns true if the object is an element of the set, false otherwise.
Symbolically:
\[
\in\colon \mathtt{Object} \times Set \longrightarrow \{\mathtt{true}, \mathtt{false}\}.
\]
Note, a ``stroke'' is sometimes used to name the dual function:
\[
\not\in\colon \mathtt{Object} \times Set \longrightarrow \{\mathtt{false}, \mathtt{true}\}.
\]
\end{definition}

\begin{example}
Let $S= \{a,b,c\}$, then $a \in S$, but $d \not\in S$. \\
In Java, the \texttt{contains(T ele)} method on the \texttt{Set}  interface serves a similar purpose!
\end{example}
}

\frame{
 \frametitle{Operations that relate sets to sets}
 \begin{definition}
 A set $T$ is a \emph{subset of} another set $S$, if the elements of $T$ are contained within $S$.
 Symbolically: $T \subset S$.\\
 Likewise, a ``stroke'' denotes that a set is \emph{not} a subset of another:
 \[
 \{a,b\} \not \subset \{1,2,3\}.
 \]
 \end{definition}
 For completeness, a complementary operation, the superset, is sometimes used:
 \[
 \{a,b,c\} \supset \{a,b\}
 \]
 And, $\subseteq$ and $\supseteq$ relations are also available, with the expected meanings.
%\begin{example}}
% \[
% S=\{a,b\}\text{ and } T = \{a,b,c,d\}\quad\text{so } S \subseteq T\text{ and } T \supseteq S.
% \] and, given another set
% \[
% U=\{1,2,3\} \text{, and we see that } U \not \subseteq T.
% \]
% \end{example}
}
%\frame{
% \frametitle{Commonly used number systems \dots}
% \begin{itemize}
%  \item The natural numbers are 
% \end{itemize}
%}
%\frame{
%\frametitle{Set relations between number systems}
%Equipped with these operators, see if you can describe the relationships between
%the number systems just defined:
%\begin{itemize}
%\item<1-> Is $\mathbb{N}$ related to $\mathbb{Z}$? If so, how?
%\item<2-> Perhaps $\mathbb{N} \subseteq \mathbb{Z}$? If you're feeling uneasy with this, we'll revisit these
%kinds of questions later in this course!
%\item<3-> What about the relationship between $\mathbb{Z}$ and $\mathbb{Q}$?
%\item<4-> Does $\mathbb{Z}^{+}$ differ from $\mathbb{N}$?
%\item<5-> That might depend upon how we defined $\mathbb{N}$?
%\item<6-> What about the role of the real numbers, $\mathbb{R}$?
%\end{itemize}
%\inclass{Explore these in class.}
%}

\frame{
\frametitle{Quantifiers extend logic to sets \dots}
Quantifiers are operators that extend the laws of logic to sets: they only make sense
in the context of sets.
\begin{definition}
The existential quantifier, written $\exists$, is read ``there exists,'' or ``some'' or
``at least one.''
\end{definition}
For example: $\exists \; n \in \mathbb{Z}$, reads ``There exists an integer $n$ \dots.
\begin{definition}
The \emph{universal} quantifier, written $\forall$, is read ``for all,'' or ``for any.''
\end{definition}
For example: $\forall\; n\in \mathbb{Z}$, reads ``For every integer $n$ \dots''.
}

\frame{
\frametitle{Defining quantifiers \ldots logically}
$\exists \; x \in S \colon P(x) $ says that for at least one $x_{i} \in S$, $P(x_{i})$ holds:
\[
P(x_{0}) \vee P(x_{1}) \vee \cdots \vee P(x_{n}).
\]
\medskip
 $\forall \; x \in S\colon P(x)$ says that for every $x_{i} \in S$, $P(x_{i})$ holds:
\[
P(x_{0}) \wedge P(x_{1}) \wedge \cdots \wedge P(x_{n}).
\]
}
%\frame{
%\frametitle{Expressing properties as quantified statements}
%For the following, assume that the domain is the integers $\mathbb{Z}$, and
%that the equal sign has its common meaning.
%\begin{example}
%Produce quantified statements for the following:
%\begin{itemize}
%\item<1->The associative property of addition.
%\item<2-> The commutative property of addition.
%\item<3-> That $0$ is the identity for addition.
%\end{itemize}
%\end{example}
%
%\inclass{Do in class}
%}
\frame{
  \frametitle{Using quantifiers in English statements}
  Let $P$ be the set of all people, and define some predicates:
  \begin{description}
  \item[$B(x)$] Returns true if $x \in P$ is ``wearing a blue hat.'' And,
  \item[$S(x)$] Returns true if $x \in P$ is a ``student in this class.''
  \item[$G(x)$] Returns true if $x \in P$ is ``a good student.''
  \end{description}

Translate the following:
 \begin{itemize}
 \item<1-> A student in this class is wearing a blue hat.
 \item<2-> $(\exists \; x \in P)[B(x) \wedge S(x)]$.
 \item<3-> All good students are in this class.
 \item<4-> $(\forall \; x \in P)[G(x) \implies C(x)]$.
 \item<5-> Does the last statement mean that \emph{only} good students are in this class?
 \end{itemize}
 }
 \frame{
  \frametitle{Truth and falsity in quantified statements}
  \begin{itemize}
  \item<1-> To show that an \emph{existential} statement is true, find an example that satisfies the predicate(s):
  \item<1-> Look around you and determine if $(\exists x \in P)[B(x) \wedge S(x)]$ is true.
  \item<2-> What about that second statement: $(\forall x \in P)[G(x) \implies C(x)]$?
  \item<3-> This one might not be so straightforward!
  \item<4-> Is every person in this class a good student? Maybe. What if $G(x)$ returned false for some
  student in this class?
  \end{itemize}
}
 
%\frame{
%\frametitle{Some Domains for Quantified Statements}
%\begin{itemize}
%\item The truth or falsity of a quantified statement is \emph{formally decidable}. Hence, its
%structure is first and foremost. But, that structure is lifeless without a domain of objects over which
%it may be applied.
%\end{itemize}
%\begin{exercise}
%Consider two existential statements:
%\[
%\exists x \in \mathbb{Z}\colon x^{2}=x\quad\text{and}\quad
%\exists x \in \{2,3,4,5,7\}\colon x^{2}=x.
%\]
%Are these equivalent statements? Could you show that one was true where the other false?
%\end{exercise}
%}

\frame{
\frametitle{Negating Universal statements}
\begin{itemize}
\item<1-> The negation of a universal statement is an existential statement
and vice versa. Let's try the first example:
\[
\neg(\exists x \in P)[B(x) \wedge S(x)].
\]
\item<2-> First: perform the formal operation(s):
\begin{align*}
\neg(\exists x \in P)& [B(x) \wedge S(x)]\\
(\forall x \in P) & \neg[B(x) \wedge S(x)]\\
(\forall x \in P) & [\neg B(x) \vee \neg S(x) ].
\end{align*}
\item<3-> Now, translate that last statement in formalized English.
\item<4-> Consider now $\neg(\forall x \in P)[G(x) \implies C(x)]$.
\end{itemize}
\inclass{Do in class.}
}

%\frame{
%\frametitle{Negating universals, cont'd.}
%\alert{Clearly, $\exists x \in P, \neg P(x)$ cannot be true when $P$ is empty.}
%
%\begin{itemize}
%\item<1-> The only way for a statement to be false is for its negation to be true.
%\item<2-> Because the negation of the last statement is not true, the original
%statement is true \textbf{by default}, or it is \textbf{vacuously true}.
%\item<3-> In general: $\forall x \in D, P(x) \Rightarrow Q(x)$ is \emph{true by default},
%iff $P(x)$ is false for every $x \in D$.
%\end{itemize}
%}

\subsection{Going negative on me \dots}
\frame{
\frametitle{Negating quantified statements}
Recall that the negation of an existential statement is a universal and vice versa. Try these:
\begin{itemize}
\item<1-> $\exists x \in \mathbb{R}\colon x>3 \implies x^{2} > 9$.
\item<2-> Formalize the following, then negate it: ``The sum of any two irrational numbers
is irrational.''
\item<3->\alert{The sum of at least two irrational numbers is rational.} ---Which shows that this
is harder than you might think!
\item<4-> For all integers $n$, if $n^{2}$ is even, then $n$ is even.
\item<5->\alert{There is at least one integer $n$ such that $n^{2}$ is even and $n$ is odd.}
\end{itemize}
}


\subsection{Variations within Universal statements}
\frame{
\frametitle{Variations within Universal Statements}
Consider statements of the form: 
\[
\forall x \in D, P(x) \implies Q(x).
\]
Given: ``If $f(x)=f(y)$, for any real numbers $x$ and $y$,  then $x=y$.'' 
\begin{itemize}
\item<1-> Recast it as a universal;
\item<2-> Rewrite it, showing its contrapositive, converse, and inverse forms.
\end{itemize}
}
\section{Combining quantifiers}
\subsection{Sometimes order matters \dots}

\frame{
\frametitle{A matter of order \dots or order matters}
\alert{By convention \dots  Assume that the actions
suggested by the quantifiers  are performed in the order
in which they appear.
}

Given domains $A$ and $B$, and a predicate defined over them, $\mathbf{P}$:
\begin{itemize}
\item<1-> $\exists x \in A\colon \forall y \in B, \mathbf{P}(x,y)$: I can find a \emph{particular} $x\in A$ such
that no matter which $y\in B$ is chosen, $\mathbf{P}(x,y) holds$.
\item<2->$\forall x \in A\colon \exists y \in B\colon \mathbf{P}(x,y)$: Choose \emph{any} $x\in A$,
and I will find a $y\in B$ such that $\mathbf{P}(x,y)$ holds.
\end{itemize}
}

\frame{
 \frametitle{Some examples of how order matters}
 For the following, assume that $a,b \in \mathbb{N}$:
 
 \begin{enumerate}
 \item<1-> $(\forall a\; \exists b)[a < b]$?
 \item<2-> True. Why? Well, for any chosen $a$, let $b=a+1$.
 \item<3-> $(\exists b\; \forall a)[a < b]$?
 \item<4-> False. Why? $\mathbb{N}$ contains no \emph{maximal} element.
 \item<5-> $(\exists  a\; \forall b)[ a < b]$?
 \item<6-> False. Choose $b=0$, no $a\in \mathbb{N}$ is smaller than $0$.
 \end{enumerate}
 
 \inclass{Do these in class.}
 }
 
 \frame{
 \frametitle{A good rule of thumb \dots }
 When working with nested quantifiers:
 \begin{itemize}
 \item Work from the outer to the inner; or, said another way, work from left to 
 the right, assuming that the leftmost is done before the next.
 \item Interpret universals as saying ``allow me to choose \emph{any}'' from \dots 
 \item Interpret existentials as saying ``choose a particular one of these'' from \dots.
 \end{itemize}
 }
 
 \frame{
 \frametitle{Applying the rule to a mathematical example}
 
 \begin{itemize}
 \item To show that an existential statement is true, find an example:
 \item To show that a universal statement is \emph{false}, find a counter-example:
 \end{itemize}
 
 Let $x,y,z \in \mathbb{N}$, and prove or disprove, by counter-example:
 \begin{itemize}
 \item<1-> $(\exists x\; \exists y\; \exists z)[x = y^{2} + z^{2}]$.
 \item<2->$(\exists x\; \forall y\; \forall z)[x \not= y^{2} + z^{2}]$.
 \item<3->$(\forall x\; \exists y\; \exists z)[ Even(y) \wedge Even(z) \wedge x = y + z]$.
 \end{itemize}

 \inclass{Do in class.}
 }
 
\frame{
\frametitle{An example by way of a proposition and its proof}
 The importance of quantified statements, however, is how they are used to 
 construct  definitions, axioms, theorems and proofs.
 
Certain quantified statements are true
for \emph{any} domain. Here's an example from the intro course a few years ago at MIT:
\begin{theorem}
Let $P(a,b)$ be any predicate defined for all $a\in A$ and $b\in B$. Then,
\[
( \exists a\in A, \forall b \in B, P(a,b)) \implies (\forall b\in B, \exists a \in A, P(a,b)).
\]
\end{theorem}
}
\frame{\frametitle{Simplifying our proof by defining a few things}
\alert{Stay calm: begin by defining a few things \dots}
\begin{enumerate}
 \item Let $A=\{\text{Students in CMSC250}\}$, and 
  \item Let $B=\{\text{CMSC Lectures}\}$.
 \item Interpret $P(a,b):=\text{student }a\text{ falls asleep in lecture }b.$
\end{enumerate}
Now, you construct the English sentences for the hypothesis and the conclusion:
\begin{itemize}
 \item $\exists a\in A, \forall b\in B, P(a,b)$.
 \item $\forall b \in B, \exists a \in A, P(a,b)$.
\end{itemize}

}
\frame{
\frametitle{Proving a quantified implication}
Recall the truth table for implications: essentially we have two cases to consider:
\begin{proof}
The proof is by cases.
\begin{itemize}
\item Case 1: Suppose that $(\exists a\in A, \forall b\in B, P(a,b))$ is false, then the entire implication is true
by default.
\item Case 2: Suppose that $(\exists a\in A, \forall b\in B, P(a,b))$ is true. Choose a student $a_{i}\in A$
such that $P(a_{i},b)$ is true $\forall b \in B$. Now, for all $b \in B$ there exists a particular $a$, namely
$a_{i}\in A$ such that $P(a,b)$ is true; therefore the implication is true.
\end{itemize}
\end{proof}
}
\frame{
\frametitle{Easy does it, but only one way}
We've just proved a \emph{validity}, which is a quantified tautology. Its converse,
\[
(\forall b \in B, \exists a\in A, P(a,b)) \implies (\exists a \in A, \forall b \in B, P(a,b)),
\]
does not necessarily follow!
\inclass{Show this in class.}
}

\frame{
 \frametitle{Quantified statements in programming contexts}
 \begin{definition}
 An \emph{invariant} is a property of a computational object that remains unchanged throughout the
 lifespan of the object.
 \end{definition}
 
 \begin{itemize}
 \item<1->Invariants are used to reason about ``loops:'' For example: showing that if a loop terminates then certain values
 are possible or impossible.
 \item<2->Invariants are used to reason about ``objects'' of a particular class: for example, ensuring that the constructors
 and accessor methods for a particular class restrict access to and values of certain properties.
 \end{itemize}
 \medskip
 \inclass{Construct examples, time-permitting.}
 }
 
\frame{
\frametitle{Summary \& Next Steps \dots}
\begin{itemize}
\item Quantifiers are used to apply logic to \emph{sets} of objects.
\item Existential quantifiers posit the existence of a particular object with certain properties described
by its predicate: $(\exists x \in S)[P(x)]$, which says that there exists at least one $x \in S$ such that $P(x)$ holds.
\item Universal quantifiers posit the truth of a predicate across all objects in a set: $(\forall x \in S)[P(x)]$, which 
means that $P(x)$ is true for all $x \in S$.
\item Quantifiers can be negated: the negation of an existential is a universal and vice versa:
\begin{align*}
(\neg \exists x \in S)[P(x)] &=  (\forall x \in S)[\neg P(x)]\\
(\neg \forall x \in S)[P(x)] &= (\exists x \in S)[\neg P(x)].
\end{align*}
\end{itemize}
}
\frame{
\frametitle{Summary, continued \dots}
\begin{itemize}
 \item Nested quantifiers are treated from the outer to inner, from left to right.
 \[
 (\forall x \in S)(\exists y \in S)[P(x,y)] \not\equiv (\exists y \in S)(\forall x \in S)[P(x,y)].
 \]
 \item We explored one common tautology:
 \[
 (\exists x \in D)(\forall y \in D)[P(x,y)] \implies (\forall y \in D)(\exists x \in D)[P(x,y)],
 \]
 whose converse is not true.
\end{itemize}
}
\end{document}