<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass{article}

\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{changepage}  % For adjustwidth environment
\usepackage{colortbl}  % Provides the  \arrayrulecolor command.
\usepackage{environ}
\usepackage{framed}  % For leftbar environment
\usepackage[hidelinks]{hyperref}  % For \autoref
\usepackage{mathtools}  % For \shortintertext
\usepackage{parskip}  % Don't indent paragraphs; skip instead.
\usepackage{ragged2e}  % FlushLeft environment
\usepackage{varwidth}
\usepackage{url}
\usepackage{xcolor}

% Stuff that should already be on slides.
\NewEnviron{onslide}{{

    \newdimen\slidewidth
    \slidewidth=\linewidth
    % Without this, I get errors beginning "Overfull \hbox (6.79999pt too
    % wide)"
    \advance\slidewidth by -7pt

    \medskip
    
    \fbox{\parbox{\slidewidth}{\BODY}}

    \medskip

  }}

% Stuff I should write or draw during lecture.
\NewEnviron{writelive}{\vspace{1ex}\begin{leftbar}{\BODY}\end{leftbar}}

\newenvironment{indentone}{\begin{adjustwidth}{2em}{0em}}{\end{adjustwidth}}


% Binary and unary all-uppercase text operators. \mathop gives too little space
% around the binary ones; e.g. \(P \op{AND} Q\) needs lots of space between
% those capital letters.
\newcommand\op[1]{{\ \mathrm{#1}\ }}
\newcommand\uop[1]{{\mathrm{#1}}}

\newcommand\AND{{\op{AND}}}
\newcommand\IFF{{\op{IFF}}}
\newcommand\IMPLIES{{\op{IMPLIES}}}
\newcommand\NOT{{\uop{NOT}}}
\newcommand\OR{{\op{OR}}}
\newcommand\XOR{{\op{XOR}}}

\newcommand\FALSE{{\mathrm{F}}}
\newcommand\TRUE{{\mathrm{T}}}

\DeclareMathOperator\concat{+\!\!+}
\DeclareMathOperator\Bkt{Bkt}
\DeclareMathOperator\leftT{left}
\DeclareMathOperator\rightT{right}

\newcommand\stringLit[1]{{\texttt{"#1"}}}

\newcommand\ComplexNums{{\mathbb{C}}}
\newcommand\Ints{{\mathbb{Z}}}
\newcommand\Nats{{\mathbb{N}}}
\newcommand\Reals{{\mathbb{R}}}
\newcommand\Rationals{{\mathbb{Q}}}

\newcommand\lbkt{{\texttt{[}}}
\newcommand\rbkt{{\texttt{]}}}

\newcommand\powerset{{\mathcal{P}}}

\newcommand\optional[1]{\textcolor[rgb]{0.5,0.5,0.3}{#1}}

% Warning: this resets the colour to black using \arrayrulecolor.
\newcommand{\greyline}{\arrayrulecolor{black!20}\hline\arrayrulecolor{black}}

\newcommand\Todo[1]{{\fbox{\begin{varwidth}{\linewidth}TODO: {#1}\end{varwidth}}}}

% Don't put theorem text in italics, because in this document, italics is for
% descriptions of things I should write or have on slides.
\theoremstyle{definition}
\newtheorem{theorem}{Theorem}
\newtheorem*{definition*}{Definition}
\newtheorem*{lemma*}{Lemma}

\begin{document}

These are \emph{rough notes} based on my own notes I prepared for the Week~6
lecture. They go with the annotated lecture slides you can see on the ``More''
page of the course website. Although they are rough, I'm providing them here in
case they help you remember what we did in lecture.

(In case you're curious: I don't follow these notes exactly in lecture. Once
I'm in class, I try not to read them at all if I can avoid it. So why do I
write them? Because writing these notes is like a practice run for the lecture.
I find any presentation I give (like a lecture) goes a lot more smoothly if
I've spent a bit of time thinking about every part of it.)

\section{Legend}

\begin{onslide}
Text that should already be on slides.

\emph{Descriptions of other things that should already be on slides.}
\end{onslide}

\begin{writelive}
Text I should write during lecture.

\emph{Descriptions of other things I should draw or write or do.}
\end{writelive}

\section{Recursively defined functions}

\begin{onslide}
\textbf{Recursively defined functions}

\bigskip

Let \(F\) be the smallest set such that
\begin{itemize}
\item Base case: variables \(A,B,\dotsc,Z\in F\).
\item Constructor cases: If \(e,f\in F\), then \((e\AND f),\NOT\ e\in F\).
\end{itemize}
(\(F =\) propositional formulas with AND and NOT.)

\bigskip

For \(f\in F\), let
\begin{itemize}
\item \(N_v(f)=\) \# occurrences of variables in \(f\)
\item \(N_{op}(f)=\) \# occurrences of operators in \(f\)
\end{itemize}

\bigskip

Give recursive (or ``inductive'') definitions of \(N_v\) and \(N_{op}\).
\end{onslide}

We've talked about recursively defined sets. We can also define functions on
those sets recursively.

\begin{writelive}
Base case: If \(e\in F\), \(N_v(e)=1\) and \(N_{op}(e)=0\).

Constructor cases: If \(e,f\in F\),
\begin{itemize}
\item \(N_v((e\AND f))=N_v(e)+N_v(f)\)
\item \(N_{op}(e\AND f)=1+N_{op}(e)+N_{op}(f)\)
\item \(N_v(\NOT\ e)=N_v(e)\)
\item \(N_{op}(\NOT\ e)=1+N_{op}(e)\)
\end{itemize}
\end{writelive}

\begin{onslide}
Let \(\Bkt\) be the smallest set such that
\begin{itemize}
\item Base case: \(\lambda\in\Bkt\)
\item Constructor cases: If \(s,t\in\Bkt\), then \(s\cdot t,\lbkt s\rbkt\in\Bkt\).
\end{itemize}

\bigskip

Define \(f:\Bkt\to\Nats\) by
\begin{itemize}
\item Base case: \(f(\lambda)=1\).
\item Constructor cases: for \(s,t\in\Bkt\), \(f(s\cdot t)=f(s)+f(t)\) and
\(f(\lbkt s\rbkt)=f(s)\).
\end{itemize}

\bigskip

What is \(f(\lbkt\rbkt)\)?
\end{onslide}

\begin{writelive}
\(\lbkt\rbkt=\lbkt\rbkt\cdot\lambda\), so
\(f(\lbkt\rbkt)=f(\lbkt\rbkt)+f(\lambda)=f(\lbkt\rbkt)+1\).

The definition of \(\Bkt\) is \underline{ambiguous}.
\end{writelive}

\begin{onslide}
\textbf{Unambiguous definition of \(\Bkt\)}

\bigskip

Let \(\Bkt\) be the smallest set such that
\begin{itemize}
\item Base case: \(\lambda\in\Bkt\)
\item Constructor case: If \(s,t\in\Bkt\), then \(\lbkt s\rbkt t\in\Bkt\).
\end{itemize}

\bigskip

(Exercise: prove this is the same set.)

\bigskip

(Exercise: prove no string can be constructed more than one way.)

\bigskip

What are these functions?

\bigskip

Define \(N:\Bkt\to\Nats\) by:
\begin{itemize}
\item Base case: \(N(\lambda)=0\)
\item Constructor case: for \(s,t\in\Bkt\), let \(N(\lbkt s\rbkt t)=2+N(s)+N(t)\)
\end{itemize}

\bigskip

Define \(D:B\to\Nats\) by:
\begin{itemize}
\item Base case: \(D(\lambda)=0\)
\item Constructor case: for \(s,t\in\Bkt\), let
\(D(\lbkt s\rbkt t)=\max\{1+D(s),D(t)\}\).
\end{itemize}
\end{onslide}

\begin{writelive}
\(N(s)=\) \# brackets in \(s\)

\bigskip

\(D(s)=\) max depth of brackets in \(s\)
\end{writelive}

\begin{onslide}
Use structural induction to prove \(\forall s\in\Bkt.\&gt;N(s)\ge2D(s)\).
\end{onslide}

\begin{writelive}
Proof:

For \(s\in\Bkt\), let \(P(s)=\) ``\(N(s)\ge2D(s)\)''.

Base case: \(N(\lambda)=0\), \(2D(\lambda)=0\), so \(N(\lambda)\ge2D(\lambda)\), i.e.\ \(P(\lambda)\).

Induction step:
\begin{indentone}
Let \(s,t\in\Bkt\).

Assume \(P(s)\) and \(P(t)\). (I.H.)

Then
\begin{align*}
  N(\lbkt s\rbkt t)
  =&amp; 2+n(s)+N(t) \\
  \ge&amp; 2+2D(s)+2D(t) \quad \text{by I.H.} \\
  =&amp; 2(1+D(s)+D(t)) \\
  \ge&amp; 2\cdot\max\{1+D(s),D(t)\} \\
  =&amp; 2D(\lbkt s\rbkt t)
\end{align*}
\end{indentone}

By structural induction, \(\forall s\in\Bkt.\&gt;P(s)\). \qed
\end{writelive}

\section{Induction over \(\Nats\times\Nats\)}

\begin{onslide}
Suppose \(P:\Nats\times\Nats\to\{\TRUE,\FALSE\}\) is a predicate, and we want
to prove:
\[\forall x\in\Nats.\&gt;\forall y\in\Nats.\&gt;P(x,y)\]
\end{onslide}

(Ask for suggestions.)

\begin{writelive}
Method 1:

Recursively define \(\Nats\times\Nats\): smallest set s.t:
\begin{itemize}
\item \((0,0)\in\Nats\times\Nats\)
\item If \((x,y)\in\Nats\times\Nats\), then
\((x+1,y),(x,y+1)\in\Nats\times\Nats\).
\end{itemize}

Then use structural induction.

Method 2:

For \(x\in\Nats\) let \(Q(x)=\forall y\in\Nats.\&gt;P(x,y)\). Prove
\(\forall x\in\Nats.\&gt;Q(x)\) using complete induction.

\begin{indentone}
Let \(x\in\Nats\) and assume \(\forall x'\in\Nats.\&gt;(x'&lt;x\IMPLIES Q(x))\).

\ \vdots

\ \vdots

\(Q(x)\)
\end{indentone}
\(\forall x\in\Nats.\&gt;Q(m)\) by complete induction.
\end{writelive}

We prove \(Q(x)\) by induction

\begin{writelive}
\emph{Fill in \vdots\ with:}
\begin{indentone}
Let \(y\in\Nats\). Assume \(\forall y'\in\Nats.\&gt;P(x,y')\).

\ \vdots

\(P(x,y)\)
\end{indentone}
By induction, \(\forall y\in\Nats.\&gt;P(x,y)\). \\
\(Q(x)\) \quad (by definition)
\end{writelive}

(Point to the remaining \vdots.) Okay, so this is going to be where the actual
work of the proof goes. When we're trying to prove \(P(x,y)\), what can we
assume?

(Wait for answers.)

\begin{writelive}
\emph{Fill in a grid, showing we can assume \(P(x',y')\) for all \(x'&lt;x\) and
  all \(y'\), and we can assume \(P(x,y')\) for all \(y'&lt;y\).}
\end{writelive}

\section{Order relations}

\begin{onslide}
\begin{definition*}
A \emph{partial order} on a set \(S\) is a binary predicate (``relation'')
\(R:S\times S\to\{\TRUE,\FALSE\}\) such that for all \(x,y,z\in S\):
\begin{itemize}
\item \(R(x,x)\)
\item \((R(x,y) \AND R(y,x)) \IMPLIES x = y\)
\item \((R(x,y) \AND R(y,z)) \IMPLIES R(x,z)\)
\end{itemize}
\end{definition*}
\bigskip
\begin{tabular}{p{10em}|p{10em}|l}
  \(S\) &amp; \(R(x,y)\) &amp; Partial order? \\
  \hline
  \(\Nats\) &amp; \(x\le y\) &amp; \\
  \greyline
  \(\Reals\) &amp; \(x\le y\) &amp; \\
  \greyline
  \(\ComplexNums\) &amp; \(|x|\le|y|\) &amp; \\
  \greyline
  \(\powerset(\{1,2,3\})\) &amp; \(x\subseteq y\) &amp; \\
  \greyline
  \begin{FlushLeft}
  players in a round-robin tournament
  \end{FlushLeft}
        &amp; \(x\) beat \(y\) &amp; \\
  \greyline
  \begin{FlushLeft}
  commits in a git repository
  \end{FlushLeft}
        &amp; \(x\) is an ancestor of \(y\) \emph{(drawing)}
\end{tabular}
\end{onslide}

\begin{writelive}
\emph{Beside the three items:}
\begin{itemize}
\item (reflexive)
\item (antisymmetric)
\item (transitive)
\end{itemize}

\emph{With help, start filling in the table. Yes beside \(\Nats\), \(\Reals\).}

\emph{Beside \(\ComplexNums\):} not antisymmetric: \(|i|\le|1|\) and
\(|1|\le|i|\).

\emph{Beside \(\powerset(\{1,2,3\})\).} Yes

\emph{Beside chess players:} not transitive

\emph{Beside commits in a git repository}
\end{writelive}

\begin{onslide}
\begin{definition*}
A \emph{total order} on \(S\) is a partial order \(R\) on \(S\) such that
\begin{itemize}
\item \(\forall x\in S.\&gt;\forall y\in S.\&gt;(R(x,y)\OR R(y,x))\)
\end{itemize}
\end{definition*}
\end{onslide}

\begin{writelive}
\emph{(Beside the only item)} (comparability)

E.g. \(\le\) on \(\Ints\), \(\Nats\), \(\Reals\).

\(\subseteq\) on \(\powerset(\{1,2,3\})\)?

No, \(\{1,2\}\) and \(\{2,3\}\) not comparable.
\end{writelive}

\begin{onslide}
\begin{definition*}
A total order on a set \(S\) is a \emph{well-ordering} if every non-empty
subset of \(S\) has a minimum element.
\end{definition*}

\bigskip

Which of these total orders \(R\) are well-orderings?

\bigskip

\begin{tabular}{p{10em}|c|l}
  \(S\) &amp; \(R(x,y)\) &amp; Well-ordering? \\
  \hline
  \(\Ints\) &amp; \(x\le y\) &amp; \\
  \greyline
  \(\Nats\) &amp; \(x\le y\) &amp; \\
  \greyline
  \begin{FlushLeft}
  \(\Rationals^+\) (positive rationals \(\frac12,\frac97,\frac23,\dotsc\))
  \end{FlushLeft}
        &amp; \(x\le y\) &amp;
\end{tabular}
\end{onslide}

\begin{writelive}
\emph{Beside \(\Ints\).} No, take \(S=\Ints\subseteq\Ints\): no minimum element.

\emph{Beside \(\Rationals^+\).} No. Also has no minimum element.

\emph{Beside \(\Nats\).} Yes
\end{writelive}

\begin{onslide}
\(\le\) is not a well-ordering on \(\Ints\) or \(\Rationals^+\). Is it possible
to define any well-ordering on those sets?
\end{onslide}

\begin{writelive}
\(\Ints\): order as \(0, -1, 1, -2, 2, \dotsc\).
\[R(x,y) = (|x| \le |y|) \AND (|x| = |y| \IMPLIES x \le y)\]

\(\Rationals^+\): order by \(\max\{\mathrm{numerator},\mathrm{denominator}\}\)
then numerator, in lowest terms.
\(\frac11, \frac12, \frac21, \frac13, \frac23, \frac32, \dotsc\).
\end{writelive}

\section{Well-ordering proofs}

\begin{onslide}
\textbf{Well-ordering proofs}

\bigskip

\begin{theorem}
Every positive rational number \(m/n\) can be expressed in lowest terms, i.e.\ 
as \(m'/n'\) where \(m'\) and \(n'\) in \(\Ints^+\) have no common factors
other than 1.
\end{theorem}
\end{onslide}

\begin{writelive}
Proof:

Let \(m, n \in \Ints^+\).

\(24/20 \to 12/10 \to 6/5\)

We want the \underline{smallest} denominator \(n'\).

Let \(C = \{ \text{possible denominators for \(m / n\)} \}\).

Given \(n'\), want \(m' / n' = m / n\), so \(m' = (m / n) n'\).

\(C = \{ n' \in \Ints^+ | (m / n) n' \in \Ints^+ \}\).

\(C\) is nonempty because \(n \in C\). Since \(\le\) is a well-ordering of
\(\Ints^+\) and \(C \subseteq \Ints^+\), \(C\) has a smallest element. Call it
\(n'\).

Let \(m' = (m / n) n' \in \Ints^+\). Suppose for a contradiction that \(m'\)
and \(n'\) have a common factor \(k &gt; 1\). Then \(n' / k \in C\). But
\(n' / k &lt; n'\) and \(n'\) is the smallest element of \(C\). Contradiction.

So \(m'\) and \(n'\) have no common factors. \qed
\end{writelive}

\begin{onslide}
\textbf{Any complete induction proof can be turned into a well-ordering proof}

\bigskip

E.g.\ from last week:

\smallskip

\begin{theorem}
Every integer greater than 1 is a product of (one or more) prime numbers.
\end{theorem}
\end{onslide}

(In class, we ran out of time, and I only wrote the definition of \(C\).)

\begin{writelive}
Proof:

Let \(C = \{ x \in \Nats | x &gt; 1 \AND \text{\(x\) is not a product of prime
  numbers} \}\). Enough to prove \(C = \emptyset\).

Suppose for a contradiction that \(C \not= \emptyset\).

Then since \(\le\) is a well-ordering on \(\Nats\), there is a smallest element
\(x^* \in C\).

\(x^*\) is not prime (otherwise: product of just itself) and \(x &gt; 1\), so
\(\exists\) integers \(y &gt; 1, z &gt; 1\) s.t.\ \(x = y z\).

\(y &lt; x^*\) and \(z &lt; x^*\) so \(y, z \not\in C\). So \(y\) and \(z\) can be
written as products of primes, so \(x^*\) can too. So \(x^* \not\in C\).
Contradiction.

So \(C = \emptyset\) (proof by contradiction). \qed
\end{writelive}
\end{document}
</pre></body></html>