\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{axiom}{Axiom}
\title{Examples for Proof Techniques I}
\author{Gabi RĂ¶ger}
\date{}
\begin{document}
\maketitle
\section{Basic Definitions}
We will use sets to illustrate some proof techniques. For this purpose, we start with a few basic definitions.
\begin{definition}
A \emph{set} is an unordered collection of distinct objects.
\smallskip
The objects in a set are called the \emph{elements} of the set. A set is said
to \emph{contain} its elements.\smallskip
We write $x\in S$ to indicate that $x$ is an element of set $S$, and $x\notin
S$ to indicate that $S$ does not contain $x$.
\smallskip
The set that does not contain any elements is the \emph{empty set} $\emptyset$.
\end{definition}
We can express sets in terms of other sets:
\begin{definition}
For sets $A$ and $B$,
\begin{itemize}
\item the \emph{union} $A\cup B$ is the smallest set that contains all
elements of $A$\\and all elements of $B$;
\item the \emph{intersection} $A\cap B$ is the smallest set that contains all
elements of $A$ that are elements of $B$;
\item the \emph{set difference} $A\setminus B$ is the smallest set that
contains all elements of $A$ that are \emph{not} elements of $B$.
\end{itemize}
\end{definition}
We also can compare sets. Two interesting properties are equality and the subset relation:
\begin{definition}
Two sets $A$ and $B$ are \emph{equal} (written $A = B$) if they contain exactly
the same elements.
\medskip
We say that set $A$ is a \emph{subset} of set $B$ (written $A\subseteq B$) if
every element of $A$ is an element of $B$.
\end{definition}
\clearpage
\section{Example: Direct Proof}
We will use a direct proof to establish the following theorem:
\begin{theorem}
For all sets $A$, $B$ and $C$ it holds that
\[A\cap(B\cup C) = (A\cap B) \cup (A\cap C).\]
\end{theorem}
\bigskip
\begin{proof}
Let $A$, $B$ and $C$ be arbitrary sets. We will show separately that
\begin{itemize}
\item $x\in A\cap (B\cup C)$ implies $x\in (A\cap B)\cup(A\cap C)$ and
that
\item $x\in (A\cap B) \cup (A\cap C)$ implies $x\in A\cap(B\cup C)$.
\end{itemize}
We first show that $x\in A\cap (B\cup C)$ implies $x\in (A\cap B)\cup(A\cap
C)$:
\smallskip
Consider any $x\in A\cap(B\cup C)$. By the definition of $\cap$ it holds that
$x\in A$ and that $x\in (B\cup C)$. We make a case distinction between $x\in B$
and $x\notin B$:
\begin{description}
\item [Case 1 ($x\in B$):] As $x\in A$ is true, it holds in this case that
$x\in(A\cap B)$.
\item [Case 2 ($x\notin B)$:] From $x\in (B\cup C)$ it follows for this
case that $x\in C$. This implies together with $x\in A$ that $x\in (A\cap C)$.
\end{description}
In both cases it holds that $x\in A\cap B$ or $x\in A\cap C$, and we conclude
that $x\in(A\cap B) \cup (A\cap C)$.
\smallskip
As $x$ was chosen arbitrarily from $A\cap(B\cup C)$ we have shown that every
element of $A\cap (B\cup C)$ is an element of $(A\cap B)\cup (A\cap C)$.
\bigskip
We will now show that every element of $(A\cap B) \cup (A\cap C)$ is an element
of $A\cap (B\cup C)$.
\bigskip
$\dots$ \textbf{[Homework assignment] $\dots$}
\bigskip
Overall we have shown for arbitrary sets $A,B$ and $C$ that $x \in A\cap(B\cup
C)$ if and only if $x\in (A\cap B)\cup (A\cap C)$, which concludes the proof of
the theorem.
\end{proof}
\section{Example: Proof by Contradiction}
We will use a proof by contradiction to establish the following theorem:
\begin{theorem}
For any sets $A$ and $B$: If $A\setminus B = \emptyset$ then $A\subseteq B$.
\end{theorem}
\bigskip
\begin{proof}
Assume that there are sets $A$ and $B$ with $A\setminus B = \emptyset$ and
$A\not\subseteq B$.
Let $A$ and $B$ be such sets. Since $A\not\subseteq B$ there is some $x\in A$
such that $x\not\in B$. For this $x$ it holds that $x\in A\setminus B$. This is
a contradiction to $A\setminus B=\emptyset$.
\end{proof}
\pagebreak
\section{Example: Proof by Contraposition}
We will prove the following theorem by contraposition:
\begin{theorem}
For any sets $A$ and $B$: If $A\subseteq B$ then $A\setminus B = \emptyset$.
\end{theorem}
\bigskip
\begin{proof}
We prove the theorem by contraposition, showing for any sets $A$ and $B$ that
if $A\setminus B\neq \emptyset$ then $A\not\subseteq B$.
Let $A$ and $B$ be arbitrary sets with $A\setminus B\neq \emptyset$. As the set
difference is not empty, there is at least one $x$ with $x\in A\setminus B$. By
the definition of the set difference ($\setminus$), it holds that $x\in A$ and
$x\notin B$. Hence, not all elements of $A$ are elements of $B$, so it does not
hold that $A\subseteq B$.
\end{proof}
\end{document}