path: root/gust.tex

%!TeX program = lualatex

% gust.tex
%   https://git.benjidial.net/gust
% Copyright 2024 Benji Dial
% Released under CC BY-SA 4.0
%   https://creativecommons.org/licenses/by-sa/4.0/

\documentclass{montgomery}

\DeclareMathOperator{\abs}{abs}

\begin{document}

\thispagestyle{empty}

\phantom{.}

\vfill

\begin{center}

  {\huge Grand Unified Study Guide}

  {\Large (under construction)}

  \phantom{.}

  \hrule

  \vfill

  {\large Copyright 2024 Benji Dial}

  {\large Licensed under \href{https://creativecommons.org/licenses/by-sa/4.0/}{CC BY-SA 4.0}}

  {\large \url{https://git.benjidial.net/gust}}

\end{center}

\vfill

\phantom{.}

\newpage
\thispagestyle{empty}

\frontmatter
\chapter*{Preface}

This is intended to be a study guide for a number of classes I have taken. I attempt to cover all the topics listed for these in the syllabi at the universities where I took them (University of North Carolina Charlotte and University of South Carolina), although they are not necessarily presented in the same way. For example, I present topology before analysis and then cite a lot of facts from topology, even though a first-year course in analysis usually does not require such a long detour.

There are exercises and examples interspersed throughout the text. The solutions to the exercises appear in Appendix \ref{solutions-chapter}. You are encouraged to think about the examples and the exercises, and to read the proofs of the theorems, in order to enhance your understanding of the material. Exercises are freely cited by future theorems and exercises as though they have been proven.

Throughout this text, $\mathbb{N}$ denotes the non-negative integers, and $\mathbb{Z}_+$ denotes the positive integers. $\mathbb{Q}_+$ and $\mathbb{R}_+$ are the positive rationals and reals respectively. $\mathbb{Z}_\pm$, $\mathbb{Q}_\pm$, and $\mathbb{R}_\pm$ are the non-zero integers, rationals, and reals respectively. For any set $S$, we use $\mathcal{P}(S)$ for the power set of $S$.

What follows is a summary of each chapter and its prerequisites. Note that a chapter does not necessarily depend on each previous chapter.

\begin{itemize}

  \item \Cref{logic-chapter}: Logic

    This chapter provides a very formal treatment of first-order logic and natural deduction up to G\"odel's completeness and incompleteness theorems. It is intended to be understandable by anyone who has (successfully) taken some proof-based course in mathematics.

  \item \Cref{set-theory-chapter}: Set Theory

    Here we develop the von Neumann--Bernays--G\"odel ($NBG$) set theory. For those already versed in set theory, this is a theory where every object is a class and sets are defined as those classes which are an element of some other class. The language of $NBG$ is a superset of the language of $ZFC$, and the statements which can be written in the language of $ZFC$ are true in $NBG$ if and only if they are true in $ZFC$. This chapter requires only \Cref{logic-chapter} as a prerequisite.

  \item \Cref{algebra-chapter}: Algebra

    This covers some amount of group theory, ring theory, and linear algebra. The topics covered are intended to align with those a student would see in their first year of graduate school. Some of the statements from \Cref{set-theory-chapter} (in particular Zorn's lemma) are used here, but if you believe the statements you do not need to read \Cref{set-theory-chapter} or \Cref{logic-chapter} in detail. If you are content to believe the statements from \Cref{set-theory-chapter} that are used here, the prerequisites for this are the same as those for \Cref{logic-chapter}.

  \item \Cref{topology-chapter}: Topology

    This covers the parts of topology that I find interesting and don't require too much set theory. Topics discussed include the separation and countability axioms, metrizability, and compactness. The prerequisites for this section are the same as those for \Cref{logic-chapter}, plus the parts of \Cref{set-theory-chapter} about orders, ordinals, and cardinality.

  \item \Cref{analysis-chapter}: Analysis, Part I

    We begin by developing the real numbers in $NBG$. \Cref{encoding-of-the-real-numbers-section} requires \Cref{set-theory-chapter} and \Cref{algebra-chapter}. If one is content to believe that the real numbers are a complete ordered field and is not interested in the details, then that section can be skipped. Only \Cref{topology-chapter} is required for the remaining sections, which discuss compactness, continuity, and differentiation specifically in $\mathbb{R}$ and $\mathbb{R}^n$.

\end{itemize}

\tableofcontents

\mainmatter

\chapter{Logic}
\label{logic-chapter}

\section{Propositional logic}

We begin this chapter with a discussion of propositional logic, also known as zeroth-order logic. I think the topics in this section will be familiar to those who have seen Boolean logic in an undergraduate computer science context.

We will first define the set of propositional formulae. There is an infinite set of propositional variables $\mathcal{L}_0 = \{P_1, P_2, P_3, \dots\}$, and a set of binary connectives $\mathcal{C} = \{{\land}, {\lor}, {\rightarrow}, {\leftrightarrow}\}$, which will not vary throughout this section. For now, propositional formula should be considered as nothing more than formal strings over the alphabet $\mathcal{L}_0 \cup \mathcal{C} \cup \{{\lnot}, {(}, {)}\}$.

\begin{definition}
  For any integer $n > 0$, we let \[
    \mathcal{L}_n = \mathcal{L}_{n - 1} \cup \{(\lnot \phi) : \phi \in \mathcal{L}_{n - 1}\} \cup \{(\phi \diamond \chi) : \phi, \chi \in \mathcal{L}_{n - 1}, {\diamond} \in \mathcal{C}\}.
  \]
  We define the set of all \textit{propositional formulae} by \[
    \mathcal{L} = \bigcup_{n \in \mathbb{N}} \mathcal{L}_n.
  \]
\end{definition}

\begin{example}
  The following are formulae:
  \begin{itemize}
    \item $(P_1 \land P_2)$
    \item $((P_1 \land P_2) \lor (P_1 \land P_3))$
    \item $(P_1 \rightarrow (P_2 \lor P_3))$
    \item $(\lnot (P_1 \rightarrow (\lnot P_2)))$
  \end{itemize}
\end{example}

When one wants to prove something is true for all formulae, one often uses the following pattern:

\begin{theorem}
  \label{formula-induction}
  Let $\Gamma \subseteq \mathcal{L}$. Suppose that the following are true:
  \begin{itemize}
    \item $\mathcal{L}_0 \subseteq \Gamma$.
    \item If $\phi \in \Gamma$, then $(\lnot \phi) \in \Gamma$.
    \item If $\phi, \chi \in \Gamma$ and $\diamond \in \mathcal{C}$, then $(\phi \diamond \chi) \in \Gamma$.
  \end{itemize}
  Then, $\Gamma = \mathcal{L}$.
  \begin{proof}
    We need to show that $\mathcal{L} \subseteq \Gamma$. We will show that $\mathcal{L}_n \subseteq \Gamma$ for all $n$ by inducting on $n$.

    Our base case is $\mathcal{L}_0 \subseteq \Gamma$, which we already assumed.

    For the inductive step, let $n > 0$ and suppose that we have $\mathcal{L}_m \subseteq \Gamma$ for all $m < n$. Let $\phi \in \mathcal{L}_n$. There are three cases:
    \begin{itemize}
      \item $\phi \in \mathcal{L}_{n - 1}$. By the induction hypothesis, we have $\phi \in \Gamma$.
      \item $\phi = (\lnot \chi)$ for some $\chi \in \mathcal{L}_{n - 1}$. By the induction hypothesis, we have $\chi \in \Gamma$, and then by one of our assumptions, $(\lnot \chi) \in \Gamma$.
      \item $\phi = (\chi \diamond \psi)$ for some $\chi, \psi \in \mathcal{L}_{n - 1}$ and $\diamond \in \mathcal{C}$. By the induction hypothesis, we have $\chi, \psi \in \Gamma$, and then by one of our assumptions, $(\chi \diamond \psi) \in \Gamma$.
    \end{itemize}
    In any case, $\phi \in \Gamma$, so $\mathcal{L}_n \subseteq \Gamma$.
  \end{proof}
\end{theorem}

\begin{example}
  Every formula has an equal number of $($ and $)$.
  \begin{proof}
    Let $f : \mathcal{L} \to \mathbb{N}$ map a formula $\phi$ to the number of $($ in $\phi$. Let $g : \mathcal{L} \to \mathbb{N}$ map a formula $\phi$ to the number of $)$ in $\phi$. Let $\Gamma = \{\phi \in \mathcal{L} : f(\phi) = g(\phi)\}$.

    For every $\phi \in \mathcal{L}_0$, we have $f(\phi) = 0 = g(\phi)$, so $\phi \in \Gamma$.

    For every $\phi \in \Gamma$, we have $f((\lnot \phi)) = 1 + f(\phi) = g(\phi) + 1 = g((\lnot \phi))$, so $(\lnot \phi) \in \Gamma$.

    For every $\phi, \chi \in \Gamma$ and $\diamond \in \mathcal{C}$, we have $f((\phi \diamond \chi)) = 1 + f(\phi) + f(\chi) = g(\phi) + g(\chi) + 1 = g((\phi \diamond \chi))$, so $(\phi \diamond \chi) \in \Gamma$.

    Then, the theorem gives us $\Gamma = \mathcal{L}$.
  \end{proof}
  In the future, we will not explicitly define a set $\Gamma$ of formulae with the property. We will just show that every formula in $\mathcal{L}_0$ has the property, if $\phi$ is a formula with the property then $(\lnot \phi)$ has the property, and if $\phi, \chi$ are formulae with the property and $\diamond \in \mathcal{C}$ then $(\phi \diamond \chi)$ has the property.
\end{example}

In particular, that example shows us that every formula has a finite length.

\begin{exercise}
  \label{start-and-end}
  Show that, for every $\phi \in \mathcal{L}$, the first symbol in $\phi$ that is not a $($ is in $\mathcal{L}_0 \cup \{{\lnot}\}$, and the last symbol in $\phi$ that is not a $)$ is in $\mathcal{L}_0$.
  \begin{solution}
    Let $\phi \in \mathcal{L}_0$. Then, $\phi$ starts and ends with a symbol from $\mathcal{L}_0$ (namely $\phi$).

    Let $\phi = (\lnot \chi)$, where $\chi \in \mathcal{L}$, and suppose the exercise is true for $\chi$. The first symbol in $\phi$ that isn't a $($ is $\lnot$, and the last symbol in $\phi$ that isn't a $)$ is the same as that of $\chi$.

    Let $\phi = (\chi \diamond \psi)$, where $\chi, \psi \in \mathcal{L}$ and $\diamond \in \mathcal{C}$, and suppose the exercise is true for $\chi$ and $\psi$. The first symbol in $\phi$ that isn't a $($ the same as that of $\chi$, and the last symbol in $\phi$ that isn't a $)$ is the same as that of $\psi$.
  \end{solution}
\end{exercise}

\begin{exercise}
  \label{proper-more-open}
  Show that, for every formula $\phi$, every nonempty proper initial substring of $\phi$ has more $($ than $)$.
  \begin{solution}
    If $\phi \in \mathcal{L}_0$, then $\phi$ has no nonempty proper substrings.

    Let $\phi = (\lnot \chi)$, where $\chi \in \mathcal{L}$, and suppose the exercise is true for $\chi$. A nonempty proper initial substring of $\phi$ is one of:
    \begin{itemize}
      \item $($
      \item $(\lnot$
      \item $(\lnot$ followed by a nonempty proper initial substring of $\chi$
      \item $(\lnot \chi$
    \end{itemize}
    In each case we have more $($ than $)$.

    Let $\phi = (\chi \diamond \psi)$, where $\chi, \psi \in \mathcal{L}$ and $\diamond \in \mathcal{C}$, and suppose the exercise is true for $\chi$ and $\psi$. A nonempty proper initial substring of $\phi$ is one of:
    \begin{itemize}
      \item $($
      \item $($ followed by a nonempty proper initial substring of $\chi$
      \item $(\chi$
      \item $(\chi \diamond {}$
      \item $(\chi \diamond {}$ followed by a nonempty proper initial substring of $\psi$
      \item $(\chi \diamond \psi$
    \end{itemize}
    In each case we have more $($ than $)$.
  \end{solution}
\end{exercise}

We will use a similar pattern when providing a definition that is parameterized by a formula. Implicit in this is that you can't get to the same formula in two different ways by applying those operations repeatedly. We prove that with the following theorem.

\begin{theorem}
  Let $\phi \in \mathcal{L}$. Then, exactly one of the following is true:
  \begin{itemize}
    \item $\phi \in \mathcal{L}_0$.
    \item There is a $\chi \in \mathcal{L}$ with $\phi = (\lnot \chi)$.
    \item There are $\chi, \psi \in \mathcal{L}$ and $\diamond \in \mathcal{C}$ with $\phi = (\chi \diamond \psi)$.
  \end{itemize}
  Furthermore:
  \begin{itemize}
    \item In the second case, there is a unique $\chi$ that works.
    \item In the third case, there is a unique combination of $\chi, \psi, \diamond$ that works.
  \end{itemize}
  \begin{proof}
    We will show this for $\phi \in \mathcal{L}_n$ for each $n$ by induction on $n$.

    For the base case, let $\phi \in \mathcal{L}_0$. The first case is true, and since $\phi$ does not start with a $($, the second and third cases are not true.

    Now let $n > 0$ and $\phi \in \mathcal{L}_n$. There are three ways to be in $\mathcal{L}_n$:
    \begin{itemize}
      \item $\phi \in \mathcal{L}_{n - 1}$: apply the inductive hypothesis.
      \item $\phi = (\lnot \chi)$ with $\chi \in \mathcal{L}_{n - 1}$: we are in the second case. We are not in the first case since $\phi$ is not a single symbol, and we are not in the third case since the $\chi$ of the third case would have to start with $\lnot$, which no formula does. Uniqueness of $\chi$ is immediate: if there are $\chi_1, \chi_2 \in \mathcal{L}$ with $(\lnot \chi_1)$ and $(\lnot \chi_2)$ the same string, then $\chi_1$ and $\chi_2$ are the same string.
      \item $\phi = (\chi \diamond \psi)$ with $\chi, \psi \in \mathcal{L}_{n - 1}$ and $\diamond \in \mathcal{C}$: we are in the third case. We are not in the first case for same reason as before, and we are not in the second case since again $\chi$ would have to start with $\lnot$. For uniqueness, suppose we had $\chi_1, \chi_2, \psi_1, \psi_2 \in \mathcal{L}$ and $\diamond_1, \diamond_2 \in \mathcal{C}$ with $(\chi_1 \diamond_1 \psi_1)$ and $(\chi_2 \diamond_2 \psi_2)$ the same string. Then, one of $\chi_1$ and $\chi_2$ is an initial substring of the other. It cannot be a proper initial substring, because then \cref{proper-more-open} and the example after \cref{formula-induction} would contradict. Thus, $\chi_1 = \chi_2$. Then, $(\chi_1$ and $(\chi_2$ are the same string, and so ${} \diamond_1 \psi_1)$ and ${} \diamond_2 \psi_2)$ are the same string. Since $\diamond_1$ and $\diamond_2$ are both the first symbol of the same string, they are the same symbol. Then, $\psi_1)$ and $\psi_2)$ are the same string, so $\psi_1 = \psi_2$. \qedhere
    \end{itemize}
  \end{proof}
\end{theorem}

That theorem allows us to recurse on formulae with no worries about well-definedness. By applying that theorem repeatedly, we uniquely decompose a formula into a tree. That tree must be finite, since at each non-terminal step the length strictly decreases and the length of a formula is finite.

\begin{definition}
  An \textit{assignment of truth values} is a function from $\mathcal{L}_0$ to $\{0, 1\}$. Given an assignment $\tau : \mathcal{L}_0 \to \{0, 1\}$, we extend $\tau$ to a $\hat{\tau} : \mathcal{L} \to \{0, 1\}$ by recursion:
  \begin{itemize}
    \item If $\phi \in \mathcal{L}_0$, then $\hat{\tau}(\phi) = \tau(\phi)$.
    \item If $\chi \in \mathcal{L}$ and $\hat{\tau}(\chi)$ has already been defined, then $\hat{\tau}((\lnot \chi)) = 1 - \hat{\tau}(\chi)$.
    \item If $\chi, \psi \in \mathcal{L}$ and $\hat{\tau}(\chi)$ and $\hat{\tau}(\psi)$ have already been defined, then:
      \begin{itemize}
        \item $\hat{\tau}((\chi \land \psi)) = \min(\hat{\tau}(\chi), \hat{\tau}(\psi))$.
        \item $\hat{\tau}((\chi \lor \psi)) = \max(\hat{\tau}(\chi), \hat{\tau}(\psi))$.
        \item $\hat{\tau}((\chi \rightarrow \psi)) = \max(1 - \hat{\tau}(\chi), \hat{\tau}(\psi))$.
        \item $\hat{\tau}((\chi \leftrightarrow \psi)) = 1 - \abs(\hat{\tau}(\chi) - \hat{\tau}(\psi))$.
      \end{itemize}
  \end{itemize}
\end{definition}

\begin{example}
  The following table shows evaluations of $\hat{\tau}$ for different $\tau$'s:
  \begin{center}
    \begin{tabular}{ccc|ccc}
      $\tau(P_1)$ & $\tau(P_2)$ & $\tau(P_3)$ & $\hat{\tau}((P_1 \land P_2))$ & $\hat{\tau}((\lnot P_3))$ & $\hat{\tau}(((P_1 \land P_2) \rightarrow (\lnot P_3)))$\\
      \hline
      0 & 0 & 0 & 0 & 1 & 1\\
      0 & 0 & 1 & 0 & 0 & 1\\
      0 & 1 & 0 & 0 & 1 & 1\\
      0 & 1 & 1 & 0 & 0 & 1\\
      1 & 0 & 0 & 0 & 1 & 1\\
      1 & 0 & 1 & 0 & 0 & 1\\
      1 & 1 & 0 & 1 & 1 & 1\\
      1 & 1 & 1 & 1 & 0 & 0
    \end{tabular}
  \end{center}
\end{example}

\begin{exercise}
  For each of the eight rows above, find the values of:
  \begin{enumerate}
    \item $\hat{\tau}(((P_1 \land P_2) \lor (P_1 \land P_3)))$
    \item $\hat{\tau}((P_1 \rightarrow (P_2 \lor P_3)))$
    \item $\hat{\tau}((P_1 \rightarrow (P_2 \rightarrow P_1)))$
    \item $\hat{\tau}((P_1 \rightarrow (P_2 \rightarrow (P_1 \land P_2))))$
  \end{enumerate}
  \begin{solution}
    \begin{center}
      \begin{tabular}{ccc|cccc}
        $\tau(P_1)$ & $\tau(P_2)$ & $\tau(P_3)$ & (a) & (b) & (c) & (d)\\
        \hline
        0 & 0 & 0 & 0 & 1 & 1 & 1\\
        0 & 0 & 1 & 0 & 1 & 1 & 1\\
        0 & 1 & 0 & 0 & 1 & 1 & 1\\
        0 & 1 & 1 & 0 & 1 & 1 & 1\\
        1 & 0 & 0 & 0 & 0 & 1 & 1\\
        1 & 0 & 1 & 1 & 1 & 1 & 1\\
        1 & 1 & 0 & 1 & 1 & 1 & 1\\
        1 & 1 & 1 & 1 & 1 & 1 & 1
      \end{tabular}
    \end{center}
  \end{solution}
\end{exercise}

\begin{definition}
  We say a formula $\phi \in \mathcal{L}$ is \textit{satisfied} by an assignment $\tau : \mathcal{L}_0 \to \{0, 1\}$ if $\hat{\tau}(\phi) = 1$. We say a formula $\phi \in \mathcal{L}$ is a \textit{tautology} if it is satisfied by every $\tau : \mathcal{L}_0 \to \{0, 1\}$, and a \textit{antilogy} if it is not satisfied by any $\tau : \mathcal{L}_0 \to \{0, 1\}$.
\end{definition}

\chapter{Set Theory}
\label{set-theory-chapter}

\chapter{Algebra}
\label{algebra-chapter}

\chapter{Topology}
\label{topology-chapter}

\chapter{Analysis, Part I}
\label{analysis-chapter}

\section{Encoding of the real numbers}
\label{encoding-of-the-real-numbers-section}

\appendix

\chapter{Links to Qualifying Exam Problems}

\chapter{Solutions to Exercises}
\label{solutions-chapter}

\solutions


\end{document}