\documentclass[%
version=last,%
a5paper,
12pt,%
headings=small,%
bibliography=totoc,%
index=totoc,%
%abstract=true,%
titlepage=no,%
twoside,%
reqno,%
cleardoublepage=empty,%
open=any,%
%parskip=half,%
titlepage=false,%
%draft=false,%
draft=true,%
%DIV=classic,%
DIV=12,%
headinclude=false,%
pagesize]%
{scrbook}
%{scrreprt}
%{scrartcl}

%\usepackage{layout}
%\usepackage[notref,notcite]{showkeys}

\usepackage{scrpage2}
\pagestyle{scrheadings}
\clearscrheadings
\refoot{The Cantor Set}
\lofoot{\leftmark}
\ofoot{\pagemark}
%\ifoot{\headmark}

\usepackage{moredefs,lips}
%\makeindex
%\usepackage{makeidx}

\usepackage[perpage,symbol]{footmisc}
%\renewcommand{\captionformat}{. }

%\usepackage{chngcntr}
%\counterwithout{figure}{chapter}
%\counterwithout{table}{chapter}

\usepackage{graphicx} % allows \rotatebox
\usepackage{verbatim}

\usepackage{relsize} % Here \smaller scales by 1/1.2; \relscale{X} scales by X


%\begin{comment}

\renewenvironment{quote}{\begin{list}{}
{\relscale{.90}\setlength{\leftmargin}{0.05\textwidth}
\setlength{\rightmargin}{\leftmargin}}
\item\relax}
{\end{list}}

\renewenvironment{quotation}{\begin{list}{}%
{\relscale{.90}\setlength{\leftmargin}{0.05\textwidth}
\setlength{\rightmargin}{\leftmargin}
\setlength{\listparindent}{1em}
\setlength{\itemindent}{\listparindent}
\setlength{\parsep}{\parskip}}
\item\relax}
{\end{list}}

%\end{comment}

%\usepackage{verse}

%\usepackage{multicol}
\usepackage{pstricks,pst-node,pst-plot,pst-math}

\usepackage{amsmath,amsthm,amssymb,bm,upgreek,mathrsfs}

\newcommand{\universe}{\mathbf V}
\newcommand{\pow}[1]{\mathscr P(#1)}
\newcommand{\powo}{\pow{\upomega}}
\newcommand{\powf}[1]{\mathscr P_{\upomega}(#1)}
\newcommand{\symdiff}{\mathbin{\triangle}}
\renewcommand{\models}{\vDash}
\newcommand{\nmodels}{\nvDash}
\DeclareMathOperator{\Model}{Mod}
\newcommand{\Mod}[1]{\Model(#1)}
\newcommand{\comp}{^{\mathrm c}}
\newcommand{\modsim}{/\mathord{\sim}}
\DeclareMathOperator{\Theory}{Th}
\newcommand{\Th}[1]{\Theory(#1)}
\newcommand{\Stone}[1]{\mathrm S(#1)}  % Stone space of #1

\DeclareMathOperator{\characteristic}{char}
\newcommand{\Char}[1]{\characteristic(#1)}
\DeclareMathOperator{\lcm}{lcm}

\swapnumbers
\newtheorem{theorem}{Theorem}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{lemma}[theorem]{Lemma}

%\allowdisplaybreaks

\DeclareMathOperator{\identity}{id} % gives weird spacing
\newcommand{\id}[1][V]{\identity_{#1}}
%\newcommand{\id}[1][V]{\mathsf{id}_{#1}}
\newcommand{\inv}{^{-1}}
\renewcommand{\phi}{\varphi}
\newcommand{\divides}{\mid}
\newcommand{\ndivides}{\nmid}
\newcommand{\gpgen}[1]{\langle#1\rangle}
\newcommand{\included}{\subseteq}
\newcommand{\includes}{\supseteq}
\newcommand{\pincluded}{\subset}
\renewcommand{\vec}[1]{\bm{#1}}

\newcommand{\C}{\mathbb C}
\newcommand{\R}{\mathbb R}
\newcommand{\Q}{\mathbb Q}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\F}[1][p]{\mathbb F_{#1}}
\newcommand{\units}[1]{#1{}^{\times}}
\DeclareMathOperator{\dee}{d}
\renewcommand{\setminus}{\smallsetminus}
\DeclareMathOperator{\automorphisms}{Aut}
\newcommand{\Aut}[1][\Zmod,+]{\automorphisms(#1)}
\DeclareMathOperator{\genlin}{GL}
\newcommand{\GL}[1][n]{\genlin_{#1}(\Z)}
\DeclareMathOperator{\diagonal}{diag}
\newcommand{\diag}[1]{\diagonal(#1)}
\newcommand{\alg}[1]{#1{}^{\mathrm{alg}}}
\DeclareMathOperator{\matrices}{M}
\newcommand{\Mat}[1][K]{\matrices_n(#1)}
\DeclareMathOperator{\Identity}{I}
\newcommand{\Id}[1][n]{\Identity_{#1}}
\DeclareMathOperator{\adjoint}{adj}
\newcommand{\adj}[1][B]{\adjoint(#1)}
\DeclareMathOperator{\Span}{span}
\DeclareMathOperator{\symmetric}{Sym}
\newcommand{\Sym}[1][n]{\symmetric(#1)}
\DeclareMathOperator{\signum}{sgn}
\newcommand{\sgn}[1][\sigma]{\signum(#1)}

\newcommand{\mi}{\,\mathrm i\,}
%\newcommand{\me}{\mathrm e}
%\newcommand{\T}{\mathbb T}
%\newcommand{\pru}[1][n]{\upomega_{#1}{}}
\newcommand{\Zmod}[1][n]{\Z_{#1}}
%\DeclareMathOperator{\Li}{Li}
%\newcommand{\conj}[1]{\overline{#1}}
%\newcommand{\doubtful}{\textsuperscript?}
%\newcounter{xnum}
%\newcommand{\xnum}{\refstepcounter{xnum}[\arabic{xnum}]}

\newcommand{\Exists}[1]{\exists#1\;}
\newcommand{\Forall}[1]{\forall#1\;}
%\newcommand{\The}[1]{\text{\rotatebox[origin=c]{180}{$\iota$}}#1\;}


%\newcommand{\Ham}{\mathbb H}
%\DeclareMathOperator{\cont}{C}
\newcommand{\lto}{\Rightarrow}
\newcommand{\liff}{\Leftrightarrow}
\renewcommand{\geq}{\geqslant}
\renewcommand{\leq}{\leqslant}
\renewcommand{\emptyset}{\varnothing}
\renewcommand{\epsilon}{\varepsilon}
%\newcommand{\gid}{\mathrm e}

\usepackage[all]{xy}
%\renewcommand{\theequation}{\fnsymbol{equation}}

%\usepackage[utf8]{inputenc}
%\usepackage[turkish,english]{babel}

%\usepackage{gfsneohellenic}
%\newcommand{\gr}[1]{\foreignlanguage{polutonikogreek}{%
%\relscale{0.9}\textneohellenic{#1}}}

\usepackage[polutonikogreek,english]{babel}
\newcommand{\gr}[1]{\foreignlanguage{polutonikogreek}{#1}}
%\usepackage{gfsporson} % this conflicts with bm, not allowing a boldface digit 0
%\usepackage{gfsneohellenic} % so does this, more so, since it changes the digits anyway
%\newcommand{\gr}[1]{\foreignlanguage{polutonikogreek}{%
%\relscale{0.9}
%\textporson{#1}}}

\newcommand{\enquote}[1]{``#1''}

%\newcommand{\grm}[1]{\ensuremath{\text{\foreignlanguage{polutonikogreek}{#1}}}}
%\newcommand{\grm}[1]{\ensuremath{\text{\gr{#1}}}}
%\newcommand{\myXi}{X}

\newcommand{\abs}[1]{\left\lvert#1\right\rvert}
\newcommand{\size}[1]{\abs{#1}}
\newcommand{\bigsize}[1]{\bigl\lvert#1\bigr\rvert}
%\newcommand{\ord}[1]{\abs{#1}}


\usepackage{hfoldsty}
\usepackage[neverdecrease]{paralist}
\usepackage{url}

\begin{document}

\subtitle{A course at the Nesin Matematik K\"oy\"u}
\title{The Cantor Set}
\author{David Pierce}
\date{January 23--9, 2017\\Last edited, \today}
\publishers{Matematik B\"ol\"um\"u\\
Mimar Sinan G\"uzel Sanatlar \"Universitesi\\
\.Istanbul\\
\url{mat.msgsu.edu.tr/~dpierce/}\\
\url{dpierce@msgsu.edu.tr}}

\maketitle
\thispagestyle{empty}
%\tableofcontents
%\setcounter{chapter}{-1}
\chapter*{Preface}

The present typeset document is based on my course
``The Cantor Set,''
%at the Nesin Mathematics Village \c Sirince, Sel\c cuk, \.Izmir,
January 23--9 (Monday--Sunday), 2017,
11:00--13:00.
The fundamental idea is the existence of a bijection
from the power set of the natural numbers, with the Tychonoff topology,
to the Cantor Ternary Set,
with the Euclidean topology inherited from the real numbers.
Named theorems proved include the following.
\begin{compactdesc}
\item[Cantor's Theorem.]
The power set of a set is strictly larger than the set itself
	(Theorem \ref{thm:Cantor}, page \pageref{thm:Cantor}).
\item[The Heine--Borel Theorem]
  (for $\R$ only; Theorem \ref{thm:HB}, page \pageref{thm:HB}).
\item[The Compactness Theorem] (for propositional logic;
  Theorem \ref{thm:comp}, page \pageref{thm:comp}:
  effectively,
  the simplest nontrivial case of the Tychonoff Theorem for infinite products).
\item[The Stone Representation Theorem.]
  Every Boolean algebra embeds in a power set
	(Theorem \ref{thm:Stone}, page \pageref{thm:Stone}).
\end{compactdesc}
I spoke mostly in Turkish, while writing in English.
Twenty-five students registered,
but attendence dropped below ten by the fourth day.
On the last day, there were four students,
and I was sick with the flu virus
that had been going around;
I spoke for only an hour.

I started typesetting this document
after the first lecture.
Sources include
\begin{inparaenum}[(1)]
\item
my handwritten notes, prepared before the lectures,
\item
my memory of what happened in the lectures,
\item
my typeset notes for a previous course in \c Sirince in 2014
on ultraproducts, and sometimes
\item
my wish for improvement.
\end{inparaenum}


\tableofcontents
%\listoffigures

\chapter{Monday, January 23, 2017}

If there is a bijection from a set $A$ to a set $B$,
we shall write
\begin{equation*}
A\approx B.
\end{equation*}
The relation $\approx$ is an \textbf{equivalence relation,} since
\begin{gather*}
	A\approx A,\\
	A\approx B\implies B\approx A,\\
	A\approx B\And B\approx C\implies A\approx C.
\end{gather*}
In case $A\approx B$, we may say $A$ and $B$ are \textbf{equipollent.}
We may also write
\begin{equation*}
\size A=\size B;
\end{equation*}
but what does $\size A$ itself mean?

If $A$ is a finite set, 
we normally let $\size A$ denote its size.
Thus, defining
\begin{equation*}
\N=\{1,2,3,\dots\}=\{x\in\Z\colon x>0\},
\end{equation*}
the set of \textbf{counting numbers,}
we have
\begin{equation*}
\{x\in\N\colon x\divides 12\}=\{1,2,3,4,6,12\},
\end{equation*}
so
\begin{equation*}
\bigsize{\{x\in\N\colon x\divides 12\}}=6.
\end{equation*}
But in this case, what is $6$?
For our convenience, we shall define
\begin{equation*}
6=\{0,1,2,3,4,5\},
\end{equation*}
a $6$-element set.

What is $\size A$ if $A$ is infinite?  We define
\begin{equation*}
\upomega=\{0\}\cup\N=\{x\in\Z\colon x\geq0\},
\end{equation*}
the set of \textbf{natural numbers.}
Then $\N\approx\upomega$ because of the bijection
$x\mapsto x-1$.  We therefore define
\begin{equation*}
\size{\N}=\upomega.
\end{equation*}
A set is called \textbf{countable}
if it is finite or equipollent with $\upomega$.
But we shall see presently that there are uncountable sets.

Because equipollence is an equivalence relation,
we may consider defining $\size A$ as the corresponding equivalence class,
\begin{equation*}
\{X\colon X\approx A\}.
\end{equation*}
A problem with this is that the term 
\emph{class} is actually appropriate here!
if $A\neq\emptyset$, then $\{X\colon X\approx A\}$
is a \textbf{proper class,}
namely a class that is not a set.

\begin{sloppypar}
Every set is a class, but not every class is a set.
Sets are collections that satisfy certain axioms:
for us, the \textbf{Zermelo--Fraenkel axioms,} called \textbf{ZF,}
along with the \textbf{Axiom of Choice,} called \textbf{AC.}
Together, these axioms are denoted by \textbf{ZFC.}
One of the axioms of ZF is
\end{sloppypar}

\begin{axiom}[Extension]
Sets that have the same elements that are sets are equal:
\begin{equation*}
\Forall x\Forall y\bigl(\Forall z(z\in x\liff z\in y)\lto x=y\bigr).
\end{equation*}
\end{axiom}
All variables, here and in other formal expressions of set theory, 
refer to sets.
In particular, sets $A$ and $B$ can be equal,
even if $A$ has an element that is not a set and that is not in $B$.
In this case though, our logic will still not distinguish between $A$ and $B$.
Briefly, we may assume that \emph{all elements of sets are sets.}

This is a convenience for set theory.
Elsewhere in mathematics,
we do not usually consider elements of sets as sets.
For example, in \emph{point set topology,}
which we shall look at later,
the elements of sets are generally treated merely as points,
which are not required to be sets themselves.
However, in any particular application,
these points can presumably be understood as certain sets.

Once we have sets, as governed by ZFC,
then we can define collections of them
by means of \emph{formulas} that have single free variables.
Such collections are \textbf{classes.}
If $\phi(x)$ is a singulary formula in the language of set theory,
it defines the class denoted by
\begin{equation*}
\{x\colon\phi(x)\}.
\end{equation*}
For example, we can form the class
\begin{equation*}
\Bigl\{x\colon\Forall y\bigl(\Forall z(z\in x\liff z\in y)\lto x=y\bigr)\Bigr\}.
\end{equation*}
By the Extension Axiom, this class is the \textbf{universal class,} 
called $\universe$.
Thus
\begin{equation*}
\universe=\{x\colon x=x\}.
\end{equation*}
Every set $A$ is (or is equal to) the class $\{x\colon x\in A\}$.
However, not every set is a class:

\begin{theorem}[Russell Paradox]
The class $\{x\colon x\notin x\}$ is not a set.
\end{theorem}

\begin{proof}
Suppose if possible that the class is the set $A$.  Then
\begin{align*}
	A\in A&\implies A\notin A,&
	A\notin A&\implies A\in A,
\end{align*}
which is absurd.
\end{proof}

The proof requires $A$ to be a set,
since the variable $x$ used in the definition of $\{x\colon x\notin x\}$
can be replaced only by sets.

It follows from the theorem that $\universe$ itself is not a class,
because of the following.

\begin{axiom}[Separation]
Every subclass of a set is a set, that is,
for every singulary formula $\phi(x)$,
\begin{equation*}
\Forall y\Exists z\Forall x\bigl(x\in z\liff x\in y\land\phi(x)\bigr).
\end{equation*}
\end{axiom}

The subset $\{x\colon x\in A\land\phi(x)\}$ of $A$ 
is usually written as
\begin{equation*}
\{x\in A\colon\phi(x)\}.
\end{equation*}
We shall denote classes by boldface letters.
These will be constants, not variables.
If $\bm C$ is a class, then by definition
\begin{align*}
\pow{\bm C}&=\bigl\{x\colon\Forall y(y\in x\lto x\in\bm C)\bigr\}\\
&=\{x\colon x\included\bm C\}.
\end{align*}
This is the \textbf{power class} of $\bm C$.
Here $\bm C$ may be a proper class;
but in this case it does not belong to $\pow{\bm C}$,
because the elements of this class (as of every class)
are sets.
A proper class is never an element of a class
(much less a set).

\begin{axiom}[Power Set]
The power class of a set is a set,
which we shall call the \textbf{power set} of the set:
\begin{equation*}
\Forall x\Exists y\Forall z(z\in y\liff z\included x).
\end{equation*}
\end{axiom}

Note that
\begin{equation*}
\universe=\pow{\universe}.
\end{equation*}
Thus $\universe\approx\pow{\universe}$,
except that, strictly speaking we did not define the relation $\approx$
to exist between proper classes.

\begin{theorem}[Cantor]\label{thm:Cantor}
For all sets $A$,
\begin{equation*}
A\not\approx\pow A.
\end{equation*}
\end{theorem}

\begin{proof}
We use the idea of the proof of the Russell Paradox.
Supposing $f$ to be an injection from $A$ to $\pow A$, we define
\begin{equation*}
B=\{x\in A\colon x\notin f(x)\},
\end{equation*}
a subset of $A$.
Then for all $c$ in $A$,
\begin{align*}
	c\in B&\implies c\notin f(c),&
	c\notin B&\implies c\in f(c).
\end{align*}
In either case, $B\neq f(c)$,
because the two sets have different elements.
Indeed, it is usually a logical axiom
that equal things have all of the same properties,
and in particular the converse of the Extension Axiom,
\begin{equation}\label{eqn:Ext-conv}
\Forall y\Forall z\bigl(y=z\lto\Forall x(x\in y\liff x\in z)\bigr),
\end{equation}
 is true,
and more generally, for all binary formulas $\phi(x,y)$,
\begin{equation}\label{eqn:=}
\Forall y\Forall z\Bigl(y=z\lto\Forall x\bigl(\phi(x,y)\liff\phi(x,z)\bigr)\Bigr).
\end{equation}
However, in an early paper, Abraham Robinson
(called then Robinsohn) showed that one could \emph{define}
equality of sets by what we have called the Extension Axiom.
This means one also has \eqref{eqn:Ext-conv} by definition;
and then, in order to obtain the generalization \eqref{eqn:=},
one can use, as an axiom, the special case
\begin{equation*}
\Forall y\Forall z\bigl(y=z\lto\Forall x(y\in x\liff z\in x)\bigr).
\end{equation*}
In any case,
at present we have $B\notin f[A]$, where by definition
\begin{equation*}
f[A]=\{f(x)\colon x\in A\}.
\end{equation*}
so $f$ is not surjective.
\end{proof}

The term \emph{power set} can be understood as follows.
First of all,
for any sets $A$ and $B$, we define $B^A$ as the set of functions from $A$ to $B$.
By the ZF axioms, this is really a set.  For,
a function is a class of ordered pairs with certain properties,
and an ordered pair can be defined as a certain set;
if the domain of the function is a set,
then the function itself is a set.%%%%%
\footnote{To be precise,
$(a,b)$ can be defined as the set $\bigl\{\{a\},\{a,b\}\bigr\}$;
and a function whose domain is a set is a set by the
\textbf{Replacement Axiom.}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

For each $n$ in $\upomega$, we understand
\begin{equation*}
n=\{0,\dots,n-1\}=\{x\in\upomega\colon x<n\}.
\end{equation*}
Then
\begin{align*}
	0&=\emptyset,&1&=\{0\},&2&=\{0,1\},
\end{align*}
and also
\begin{equation*}
n+1=n\cup\{n\}.
\end{equation*}
Then by definition $2^A=\bigl\{\text{functions from $A$ to $\{0,1\}$}\bigr\}$,
and so
\begin{equation*}
2^A\approx\pow A,
\end{equation*}
because the function that assigns,
to every $f$ in $2^A$,
the subset $\{x\in A\colon f(x)=1\}$ of $A$
is a bijection with $\pow{A}$.

We are going to show $\powo\approx\R$.
First we shall define an injection from $\powo$ to $\R$.
As a first attempt, if $A\included\upomega$, we define
\begin{equation}\label{eqn:f}
f(A)=\sum_{k\in A}\frac1{2^{k+1}}.
\end{equation}
Then $f(\emptyset)=0$ and $f(\upomega)=1$, and in general
\begin{equation*}
f(A)\in[0,1].
\end{equation*}
We have
\begin{align*}
	f(\{2x\colon x\in\upomega\})&=\frac23,&
	f(\{2x+1\colon x\in\upomega\})&=\frac13.
\end{align*}
However,
the equation $f(X)=1/2$ has two solutions,
$\{0\}$ and $\upomega\setminus\{0\}$;
so $f$ is not injective.
We now define
\begin{equation}\label{eqn:g}
g(A)=\sum_{k\in A}\frac2{3^{k+1}}.
\end{equation}
By definition, $g[\powo]$ is the \textbf{Cantor set.}
We shall show tomorrow that $g$ is injective.

\chapter{Tuesday, January 24, 2017}

Suppose $A$ and $B$ are distinct subsets of $\upomega$.
Defining
\begin{equation*}
A\symdiff B=(A\setminus B)\cup(B\setminus A),
\end{equation*}
the \textbf{symmetric difference} of $A$ and $B$,
we let
\begin{equation*}
m=\min(A\symdiff B).
\end{equation*}
We may assume $m\in B\setminus A$.  Then
\begin{align*}
	A&\included\{x\in A\colon x<m\}\cup\{x\in\upomega\colon x>m\},\\
	B&\includes\{x\in A\colon x<m\}\cup\{m\}.
\end{align*}
With $g$ as in \eqref{eqn:g},
and letting $c=g\bigl(\{x\in A\colon x<m\}\bigr)$, we have
\begin{equation*}
	g(A)\leq c+\frac1{3^{m+1}}
<c+\frac2{3^{m+1}}\leq g(B).
\end{equation*}
Thus $g$ is injective.

Whenever an injective function exists from an arbitrary set $A$
to an arbitary set $B$, we write
\begin{equation*}
A\preccurlyeq B.
\end{equation*}
With $g$, we have shown $\powo\preccurlyeq\R$,
in fact $\powo\preccurlyeq[0,1]$.
We now show
\begin{equation*}
[0,1)\preccurlyeq\powo
\end{equation*}
by defining an injective function $h$ from $[0,1)$ to $\powo$.
If $f$ is as defined on $\powo$ by \eqref{eqn:f},
then $f$ is surjective onto $[0,1]$.
In this case, we can let $h$ be a right inverse of $f$, so that
\begin{equation*}
f\bigl(h(y)\bigr)=y
\end{equation*}
for all $y$ in $[0,1)$.
This means that, for any such $y$, 
for some $X$ in $\powo$,
\begin{align*}
	f(X)&=y,&h(y)&=X.
\end{align*}
Since there are infinitely many values of $y$ 
for which $X$ is not uniquely determined,
we have appealed to the \textbf{Axiom of Choice,} strictly speaking.
This is needed when one has to make infinitely many choices, all at once.
However, in the present case,
we can make an explicit definition of $h$ once for all,
without needing AC.
If $a\in[0,1)$, we define
\begin{equation*}
h(a)=\{k\in\upomega\colon a_k=1\},
\end{equation*}
where the $a_k$ are defined recursively by
\begin{equation*}
a_k=\begin{cases}
	0,&\text{ if }a<\sum_{i<k}a_i/2^{i+1}+1/2^{k+1},\\
	1,&\text{ if }a\geq\sum_{i<k}a_i/2^{i+1}+1/2^{k+1}.
\end{cases}
\end{equation*}
This ensures that, as desired,
\begin{equation*}
a=\sum_{k=0}^{\infty}\frac{a_k}{2^{k+1}}=f\bigl(h(a)\bigr).
\end{equation*}
We have defined the $a_n$ so that,
for all $k$ in $\upomega$,
for some $n$ in $\upomega$, we have $k\leq n$ and $a_n=0$.

We now have
\begin{equation*}
[0,1)\preccurlyeq\powo\preccurlyeq[0,1]\preccurlyeq\R.
\end{equation*}
Moreover, $\R\approx(0,1)$ because the function
\begin{equation*}
x\mapsto\frac{x-1/2}{x\cdot(1-x)}
\end{equation*}
is a bijection from $(0,1)$ to $\R$;
its inverse can be computed as
\begin{equation*}
y\mapsto\begin{cases}
	\displaystyle\frac12+\frac12\cdot\frac{\sqrt{1+y^2}-1}y,&\text{ if }y\neq0,\\
	\displaystyle\frac12,&\text{ if }y=0.
\end{cases}
\end{equation*}
Since $(0,1)\preccurlyeq[0,1)$,
we obtain $\powo\approx\R$ from the following.

\begin{theorem}[Cantor--Schr\"oder--Bernstein]
If $A\preccurlyeq B$ and $B\preccurlyeq A$, then
\begin{equation*}
A\approx B.
\end{equation*}
\end{theorem}

\begin{proof}
Suppose $f$ is an injection from $A$ to $B$;
and $g$, from $B$ to $A$.
By recursion, we define
\begin{align*}
	A_0&=A\setminus g[B],&B_0&=B\setminus f[A],\\
	A_{n+1}&=g[B_n],&B_{n+1}&=f[A_n].
\end{align*}
By induction,
for all $n$ in $\N$,
whenever $i<j\leq n$,
\begin{align*}
A_i\cap A_j&=\emptyset,&B_i\cap B_j&=\emptyset.
\end{align*}
Then also, by induction,
\begin{equation*}
A_{2n}\cup A_{2n+1}\approx B_{2n}\cup B_{2n+1}.
\end{equation*}
Thus
\begin{equation*}
\bigcup_{n\in\upomega}A_n
\approx\bigcup_{n\in\upomega}B_n.
\end{equation*}
Finally,
\begin{equation*}
A\setminus\bigcup_{n\in\upomega}A_n
\approx B\setminus\bigcup_{n\in\upomega}B_n,
\end{equation*}
since
\begin{align*}
	f\left[A\setminus\bigcup_{n\in\upomega}A_n\right]
	&=\bigcap_{n\in\upomega}f\left[A\setminus\bigcup_{k<n}A_k\right]\\
	&=\bigcap_{n\in\upomega}\left(B\setminus\bigcup_{k\leq n}B_k\right)
	=B\setminus\bigcup_{n\in\upomega}B_n.\qedhere
\end{align*}
\end{proof}

Thus $\R$ is uncountable.
Letting $C$ be the Cantor set,
namely the image of $\powo$ under $g$ as defined in \eqref{eqn:g},
we have also
\begin{equation*}
C\approx\R.
\end{equation*}
In particular, $C$ is uncountable
(though we already knew this, because $C\approx\powo$).

\chapter{Wednesday, January 25, 2017}

The Cantor set (strictly the \textbf{Cantor ternary set}) 
$C$ consists of the numbers in $[0,1]$ whose \textbf{ternary expansions}
can be written without the digit $1$.  If $a\in[0,1]$, the ternary expansion of $a$ is
\begin{equation*}
0.a_0a_1a_2\cdots
\end{equation*}
where
\begin{align*}
	a_k&\in\{0,1,2\},&
	\sum_{k\in\upomega}\frac{a_k}{3^{k+1}}=a.
\end{align*}
Note that
\begin{equation*}
0.a_0\cdots a_{n-1}1=0.a_0\cdots a_{n-1}0\overline2,
\end{equation*}
so this is in $C$ if $\{a_0,\dots,a_{n-1}\}\included\{0,2\}$;
but if
\begin{equation*}
0.a_0\cdots a_{n-1}1<x<0.a_0\cdots a_{n-1}2,
\end{equation*}
then $x\notin C$.  
Some elements of $C$ are shown in Figure \ref{fig:Cantor}.
\begin{figure}
\centering
\psset{xunit=1cm,yunit=15cm}
\begin{pspicture}(2,1)
\uput[l](0,0.5){$X$}
\uput[r](2,0.5){$\displaystyle\sum_{k\in X}\frac2{3^{k+1}}$}
\psdots(1,0)
(1,1)
(! 1 1 3 div)(! 1 2 3 div)
(! 1 1 9 div)(! 1 2 9 div)(! 1 7 9 div)(! 1 8 9 div)
(! 1 1 27 div)(! 1 2 27 div)(! 1 7 27 div)(! 1 8 27 div)(! 1 19 27 div)(! 1 20 27 div)(! 1 25 27 div)(! 1 26 27 div)
(! 1 1 81 div)(! 1 2 81 div)(! 1 7 81 div)(! 1 8 81 div)(! 1 19 81 div)(! 1 20 81 div)(! 1 25 81 div)(! 1 26 81 div)
(! 1 55 81 div)(! 1 56 81 div)(! 1 61 81 div)(! 1 62 81 div)(! 1 73 81 div)(! 1 74 81 div)(! 1 79 81 div)(! 1 80 81 div)
%(! 1 1 243 div)(! 1 2 243 div)(! 1 7 243 div)(! 1 8 243 div)(! 1 19 243 div)(! 1 20 243 div)(! 1 25 243 div)(! 1 26 243 div)
%(! 1 55 243 div)(! 1 56 243 div)(! 1 61 243 div)(! 1 62 243 div)(! 1 73 243 div)(! 1 74 243 div)(! 1 79 243 div)(! 1 80 243 div)
{%\relscale{1.1}
\uput[l](0,0){$\emptyset$}
\uput[r](2,0){$0$}
\uput[l](0,1){$\upomega$}
\uput[r](2,1){$1$}
}
\uput[l](! 0 1 3 div){$\upomega\setminus\{0\}$}
\uput[r](! 2 1 3 div){$0.1$}
\uput[l](! 0 2 3 div){$\{0\}$}
\uput[r](! 2 2 3 div){$0.2$}
{%\relscale{0.9}
\uput[l](! 0 1 9 div){$\upomega\setminus\{0,1\}$}
\uput[r](! 2 1 9 div){$0.01$}
\uput[l](! 0 2 9 div){$\{1\}$}
\uput[r](! 2 2 9 div){$0.02$}
\uput[l](! 0 7 9 div){$\upomega\setminus\{1\}$}
\uput[r](! 2 7 9 div){$0.21$}
\uput[l](! 0 8 9 div){$\{0,1\}$}
\uput[r](! 2 8 9 div){$0.22$}
}
{%\relscale{0.8}
\uput[l](! 0 1 27 div){$\upomega\setminus\{0,1,2\}$}
\uput[r](! 2 1 27 div){$0.001$}
\uput[l](! 0 2 27 div){$\{2\}$}
\uput[r](! 2 2 27 div){$0.002$}
\uput[l](! 0 7 27 div){$\upomega\setminus\{0,2\}$}
\uput[r](! 2 7 27 div){$0.021$}
\uput[l](! 0 8 27 div){$\{1,2\}$}
\uput[r](! 2 8 27 div){$0.022$}
\uput[l](! 0 19 27 div){$\upomega\setminus\{1,2\}$}
\uput[r](! 2 19 27 div){$0.201$}
\uput[l](! 0 20 27 div){$\{0,2\}$}
\uput[r](! 2 20 27 div){$0.202$}
\uput[l](! 0 25 27 div){$\upomega\setminus\{2\}$}
\uput[r](! 2 25 27 div){$0.221$}
\uput[l](! 0 26 27 div){$\{0,1,2\}$}
\uput[r](! 2 26 27 div){$0.222$}
}
\end{pspicture}
\caption{The Cantor set}\label{fig:Cantor}
\end{figure}
We have
\begin{equation*}
C=\bigcap_{k\in\upomega}F_k,
\end{equation*}
where
\begin{align*}
	F_0&=[0,1]\setminus(1/3,2/3),\\
	F_{n+1}&=F_n\setminus
	\bigcup\bigl\{(0.x_0\cdots x_n1,0.x_0\cdots x_n2)\colon
	x_k\in\{0,2\}\bigr\}.
\end{align*}
Each set $F_k$ is the union of finitely many closed intervals.
Every intersection of a family of finite unions of closed intervals
is called a \textbf{closed} subset of $\R$.
Thus $C$ is a closed subset of $\R$.
The complement of a closed set is called \textbf{open.}
The only subsets of $\R$ that are both closed and open
are $\emptyset$ and $\R$.

The intersection of an open subset of $\R$
with $C$ is called open in $C$;
it might not be open in $\R$
(in fact it will not be).
The intersection of a closed subset of $\R$
with $C$ is called closed in $C$,
but it is still closed in $\R$ anyway.
However, $C$ will have many subsets
that are both open and closed in $C$.

A collection of subsets of $\R$
whose every finite subcollection has nonempty intersection
is said to have the \textbf{finite intersection property}
or \textbf{FIP.}
In topological terms,
the following theorem is that every closed bounded subset of $\R$ is \textbf{compact.}
In fact the same is true in $\R^n$, though we shall not prove this (or use it).

\begin{theorem}[Heine--Borel]\label{thm:HB}
Every collection of bounded closed subsets of $\R$ with the finite intersection property
has nonempty intersection.
\end{theorem}

\begin{proof}
Let $\mathscr F$ be as in the hypothesis.
We may assume that all elements of $\mathscr F$ are subsets of $[0,1]$.
One of the collections $\mathscr F\cup\{[0,1/2]\}$ and $\mathscr F\cup\{[1/2,1]\}$
must have the FIP.  For, suppose the first does not.
Then for some finite subset $\mathscr F_0$ of $\mathscr F$,
every element of $\bigcap\mathscr F_0$ must belong to $[1/2,1]$.
Let $\mathscr F_1$ be any finite subset of $\mathscr F$.
Then $\bigcap\mathscr F_0\cap\bigcap\mathscr F_1$
is nonempty, and its every element belongs to $[1/2,1]$.
Thus $\mathscr F\cup\{[1/2,1]\}$
has the FIP.

By recursion and induction, 
we obtain a sequence $(I_k\colon k\in\upomega)$
of closed intervals such that $\mathscr F\cup\{I_k\colon k<n\}$
always has the FIP, and 
\begin{equation*}
I_0\includes I_1\includes I_2\includes\cdots,
\end{equation*}
and the length of $I_k$ is $1/2^k$.
If we let
\begin{align*}
a_k&=\sup(I_k),&
b&=\inf\{a_k\colon k\in\upomega\},	
\end{align*}
then
\begin{equation*}
\bigcap_{k\in\upomega}I_k=\{b\}
\end{equation*}
(this is an exercise,
but the proof will involve an observation
to be made on Saturday:
closed sets contain their \emph{limit points}).  
Then $b\in\bigcap\mathscr F$.
For, let $\epsilon>0$.
For some $n$, we have $1/2^n<\epsilon$,
so
\begin{equation*}
I_k\included(b-\epsilon,b+\epsilon).
\end{equation*}
For every $F$ in $\mathscr F$,
since $F\cap I_k\neq\emptyset$,
the set $F$ has an element in $(b-\epsilon,b+\epsilon)$.
This being so for all positive $\epsilon$,
and $F$ being closed, we have $b\in F$
(again because closed sets contain their limit points).
\end{proof}

In particular, $C$ is compact.
Using the bijection $g$ from $\powo$ to $C$,
we can define the closed subsets of $\powo$
as $g\inv[X]$, where $X$ is a closed subset of $C$.
However, we shall first give an independent definition of the closed subsets of $\powo$
and prove a theorem analogous to Heine--Borel.

\chapter{Thursday, January 26, 2017}

Starting with a collection $\{P_k\colon k\in\upomega\}$
of \textbf{(propositional) variable,}
we define \textbf{(propositional) formulas} recursively:
\begin{enumerate}
\item
Each variable is a formula,
namely an \textbf{atomic} formula.
\item
If $F$ is a formula, then so is $\lnot G$,
the \textbf{negation} of $F$.
\item
If $F$ and $G$ are formulas, then so is $(F\land G)$,
the \textbf{conjunction} of $F$ and $G$.
\end{enumerate}

\begin{theorem}
Every formula is \textbf{uniquely readable:}
\begin{enumerate}
\item
No atomic formula is also a negation or a conjunction.
\item
No negation is also a conjunction.
\item
Every conjunction is uniquely so.
\end{enumerate}
\end{theorem}

\begin{proof}
Only the last claim is not entirely clear.
By induction, we show that for all formulas $F$,
\begin{compactenum}[(a)]
\item
no proper initial segment of $F$ is a formula, and
\item
$F$ is not a proper initial segment of any formula.
\end{compactenum}
\begin{asparaenum}
\item
The claim is clearly true when $F$ is atomic.
\item
Suppose the claim is true when $F$ is a formula $G$.
Then the claim must be true when $F$ is $\lnot G$.
For if $H$ is a proper initial segment of $\lnot G$,
then $H$ is of the form $\lnot K$ for some $K$,
which is a proper initial segment of $G$,
so, by hypothesis, $K$ cannot be a formula,
and therefore $H$ cannot be a formula.
There is a similar argument if $\lnot G$ is a proper initial segment of $H$.
\item
Similarly,
if the claim is true when $F$ is $G$ or $H$,
then it must be true when $F$ is $(G\land H)$.
\end{asparaenum}

By induction, which is made possible by the recursive definition of formulas, 
the claim holds for all formulas $F$.
\end{proof}

The foregoing theorem allows us to make recursive definitions 
of functions on the set of all formulas.
For example, for all subsets $A$ of $\upomega$,
we recursively define which formulas are \textbf{true} in $A$.
We shall express that a formula $F$ is true in $A$ by writing
\begin{equation*}
A\models F.
\end{equation*}
Then by definition
\begin{enumerate}[(1)]
\item
$A\models P_k\iff k\in A$;
\item
$A\models\lnot F\iff A\nmodels F$;
\item
$A\models(F\land G)\iff A\models F\And A\models G$.
\end{enumerate}
Note that the expressions $\iff$ and $\And$ here
are just abbreviations of ordinary language.
Without recursion, we define
\begin{equation*}
\Mod F=\{X\included\upomega\colon X\models F\}.
\end{equation*}
If $\Gamma$ is a set of formulas,
we define
\begin{equation*}
\Mod{\Gamma}=\bigcap\{\Mod F\colon F\in\Gamma\};
\end{equation*}
this is the set of \textbf{models} of $\Gamma$.
If every finite subset of $\Gamma$ has a model,
we shall say that $\Gamma$ is \textbf{consistent.}
We shall show that every consistent set of formulas has a model.
To do this, we make one more recursive definition.
\begin{enumerate}[(1)]
\item
$V(P_k)=\{k\}$.
\item
$V(\lnot F)=V(F)$.
\item
$V\bigl((F\land G)\bigr)=V(F)\cup V(G)$.
\end{enumerate}
We do not really need recursion here:
we can just say
\begin{equation*}
V(F)=\{k\in\upomega\colon\text{$P_k$ occurs in $F$}\}.
\end{equation*}

\begin{theorem}
For all formulas $F$, for all subsets $A$ and $B$ of $\upomega$,
if
\begin{equation*}
V(F)\cap A=V(F)\cap B,
\end{equation*}
%, for all $k$ in $V(F)$,
%\begin{equation*}
%k\in A\iff k\in B,
%\end{equation*}
then
\begin{equation*}
A\models F\iff B\models F.
\end{equation*}
\end{theorem}

\begin{proof}
Induction.
\end{proof}

\begin{theorem}[Compactness for propositional logic]\label{thm:comp}
Every consistent set of propositional formulas has a model.
\end{theorem}

\begin{proof}
Let $\Gamma$ be a consistent set of formulas.
Just as in the proof of the Heine--Borel Theorem,
one of $\Gamma\cup\{P_0\}$ and $\Gamma\cup\{\lnot P_0\}$
must be consistent.
In this way, by recursion,
we obtain a sequence $(G_k\colon k\in\upomega)$,
where each $G_k$ is either $P_k$ or $\lnot P_k$,
and each collection $\Gamma\cup\{G_k\colon k<n\}$ is consistent.
Let
\begin{equation*}
A=\{k\in\upomega\colon\text{$G_k$ is $P_k$}\}.
\end{equation*}
For all $F$ in $\Gamma$,
the collection
\begin{equation*}
\{F\}\cup\{G_k\colon k\in V(F)\}
\end{equation*}
has a model $B$.
Then for all $k$ in $V(F)$, we have $B\models G_k$,
and so
\begin{equation*}
k\in B\iff k\in A.
\end{equation*}
By the foregoing theorem,
since $B\models F$, also $A\models F$.
Thus $A\in\Mod{\Gamma}$.
\end{proof}

\chapter{Friday, January 27, 2017}

If $\{F_i\colon i\in I\}$ is a family of subsets of $\R$,
each being a finite union $I_0\cup\dots\cup I_{n-1}$ of closed intervals,
then again, by definition, 
$\bigcap_{i\in I}F_i$ is a \textbf{closed subset} of $\R$.
For any set $\Omega$, since its collection of finite subsets is
\begin{equation*}
\bigl\{X\in\pow{\Omega}\colon\size X<\upomega\bigr\},
\end{equation*}
we shall denote this collection by
\begin{equation*}
\powf{\Omega}.
\end{equation*}

\begin{theorem}
If $\mathscr F$ is the family of closed subsets of $\R$,
then
\begin{enumerate}[(1)]
\item
$\mathscr X\in\pow{\mathscr F}\implies\bigcap\mathscr X\in\mathscr F$;
\item
$\mathscr Y\in\powf{\mathscr F}\implies\bigcup\mathscr X\in\mathscr F$.
\end{enumerate}
\end{theorem}

\begin{proof}
\begin{asparaenum}
\item
Since closed sets are already intersections, the first claim is clear.
\item
We shall show by induction that, for all $n$ in $\upomega$,
for all $n$-element subsets $\mathscr A$ of $\mathscr F$,
$\bigcup\mathscr A\in\mathscr F$.
When $n=0$, then $\bigcup\mathscr A=\bigcup\emptyset=\emptyset$,
which belongs to $\mathscr F$ since, above, we can take one of the $F_i$
to be the empty union.
Suppose the claim holds when $n=m$,
but now $\mathscr A=\{A_k\colon k\leq m\}$.
By hypothesis, $\bigcup_{k<m}A_k\in\mathscr F$,
so it is an intersection $\bigcap_{i\in I}F_i$
of finite unions of closed intervals.
But $A_m$ is a similar intersection $\bigcap_{j\in J}G_j$.
We now have
\begin{align*}
	\bigcup\mathscr A
	=\bigcup_{k<m}A_k\cup A_m
	&=\bigcap_{i\in I}F_i\cup\bigcap_{j\in J}G_j\\
	&=\bigcap_{i\in I}\left(F_i\cup\bigcap_{j\in J}G_j\right)\\
	&=\bigcap_{i\in I}\bigcap_{j\in J}(F_i\cup G_j),
\end{align*}
which is in $\mathscr F$.\qedhere
\end{asparaenum}
\end{proof}

Again,
the complement of a closed set is called \textbf{open.}
If $\tau$ is the family of open subsets of $\R$, then,
with $\mathscr F$ as in the theorem,
\begin{equation*}
\tau=\{\R\setminus X\colon X\in\mathscr F\}=\{X\comp\colon X\in\mathscr F\},
\end{equation*}
and so
\begin{enumerate}[(1)]
\item
$\mathscr X\in\pow{\tau}\implies\bigcup\mathscr X\in\tau$;
\item
$\mathscr Y\in\powf{\tau}\implies\bigcap\mathscr X\in\tau$;
and this is equivalent to
\begin{enumerate}[(a)]
	\item 
	$\R\in\tau$, and
	\item
	$Y,Z\in\tau\implies Y\cap Z\in\tau$.
\end{enumerate}
\end{enumerate}
Precisely because $\tau$ meets these conditions,
$\tau$ is called a \textbf{topology} on $\R$.

Let us denote by
\begin{equation*}
L
\end{equation*}
the set of propositional formulas with variables from the set
$\{P_k\colon k\in\upomega\}$.
Then the family $\{\Mod{\Gamma}\colon\Gamma\included L\}$
satisfies the conditions to be closed.
In particular
\begin{enumerate}[(a)]
	\item 
	$\emptyset=\Mod{P_0\land\lnot P_0}$, and
	\item
$\Mod F\cup\Mod G=\Mod{F\lor G}$,
\end{enumerate}
where $F\lor G$ means $\lnot(\lnot F\land\lnot G)$.

If $(A,\tau)$ and $(B,\sigma)$ are two topological spaces,
$f\colon A\to B$,
and
\begin{equation*}
X\in\sigma\implies f\inv[X]\in\tau,
\end{equation*}
then $f$ is called \textbf{continuous;}
if also $f$ is a bijection,
and $f\inv$ is continuous,
then $f$ is called a \textbf{homeomorphism.}
If $C\included A$,
it is easy to show that $\{C\cap X\colon X\in\tau\}$
is a topology on $C$,
called the \textbf{subspace topology.}
We give the Cantor set this topology from $\R$.

\begin{theorem}
The function $g$ in \eqref{eqn:g}
%$X\mapsto\sum_{k\in X}2/3^{k+1}$
is a homeomorphism from $\powo$
to the Cantor set.
\end{theorem}

\begin{proof}
Given $n$ in $\N$ and a subset $A$ of $n$,
let us define the formula $F_{n,A}$ as
\begin{equation*}
E_0\land\dots\land E_{n-1},
\end{equation*}
where
\begin{equation*}
E_k\text{ is }
\begin{cases}
	P_k,&\text{ if }k\in A,\\
	\lnot P_k,&\text{ if }k\in n\setminus A.
\end{cases}
\end{equation*}
Then
\begin{equation*}
\Mod{F_{n,A}}=\{X\included\upomega\colon X\cap n=A\}.
\end{equation*}
For any $F$ in $L$,
there is $n$ in $\N$ such that $V(F)\included n$.
Now let
\begin{equation*}
I=\{X\included n\colon X\models F\}.
\end{equation*}
Then
\begin{equation*}
\Mod F=\bigcup_{X\in I}\{Y\included\upomega\colon Y\cap n=X\}
=\bigcup_{X\in I}\Mod{F_{n,X}}.
\end{equation*}
Since
\begin{equation*}
\Mod F\comp=\Mod{\lnot F},
\end{equation*}
we can conclude that the open subsets of $L$
are just the unions of sets $\Mod{F_{n,A}}$.

For all $X$ in $\powo$,
\begin{equation*}
X\models F_{n,A}\iff	A\included X\included A\cup\{x\in\upomega\colon x\geq n\}.
\end{equation*}
Thus
\begin{align*}
g[\Mod{F_{n,A}}]
&=C\cap\left[g(A),g(A)+\frac1{3^n}\right]\\
&=C\cap\left(g(A)-\frac1{3^n},g(A)+\frac2{3^n}\right).
\end{align*}
This being open in $C$,
$g\inv$ is continuous.

For the continuity of $g$,
we observe that the interval $(g(A)-1/3^n,g(A)+2/3^n)$
has length $1/3^{n-1}$.
Let $O$ be an open subset of $\R$
and $a\in C\cap O$.
For some positive $\epsilon_a$ we have
\begin{equation*}
(a-\epsilon_a,a+\epsilon_a)\included O.
\end{equation*}
Now let $n_a$ be large enough that $1/3^{n_a-1}<\epsilon_a$.
For some subset $A_a$ of $n_a$, we have
\begin{equation*}
a\in\left(g(A_a)-\frac1{3^{n_a}},g(A_a)+\frac2{3^{n_a}}\right),
\end{equation*}
but then also
\begin{equation*}
\left(g(A_a)-\frac1{3^{n_a}},g(A_a)+\frac2{3^{n_a}}\right)\included(a-\epsilon_a,a+\epsilon_a).
\end{equation*}
Thus
\begin{equation*}
C\cap O=\bigcup_{x\in C\cap O}g[\Mod{F_{n_x,A_x}}],
\end{equation*}
so $g\inv[C\cap O]=\bigcup_{x\in C\cap O}\Mod{F_{n_x,A_x}}$,
and open set.
\end{proof}

\chapter{Saturday, January 28, 2017}

If $A$ is a subset of a topological space,
and $p\in A$, there are two possibilities.
\begin{enumerate}
\item
If, for some open set $O$,
we have $p\in O$ and $O\included A$,
then $A$ is called a \textbf{neighborhood} of $p$,
and $p$ is an \textbf{interior point} of $A$.
\item
If, for all open sets $O$ that contain $p$,
we have $O\cap A\comp\neq\emptyset$,
then $p$ is a \textbf{limit point} of $A\comp$.
In this case $p$ is also a limit point of $A\comp\cup\{p\}$.
\end{enumerate}
To prove the Heine--Borel Theorem (Theorem \ref{thm:HB}, page \pageref{thm:HB}),
we used the easy observation that 
every open set is a neighborhood of all of its points,
so that every closed set must contain all of its limit points.
The converse takes a little more work:

\begin{theorem}
In a topological space,
every set that is a neighborhood of all of its points is open,
and every set that contains all of its limit points is closed.
\end{theorem}

\begin{proof}
Exercise.
\end{proof}

A topological space $(\Omega,\tau)$ is \textbf{compact}
if any of the following equivalent conditions is satisfied:
\begin{enumerate}
	\item 
Every family of closed sets 
whose every finite subfamily has nonempty intersection 
has nonempty intersection.
\item
For every family of closed sets with empty intersection,
there is a finite subfamily $\{F_i\colon i<n\}$ such that
\begin{equation*}
F_0\cap\dots\cap F_{n-1}=\emptyset.
\end{equation*}
\item
For every family $\mathscr O$
of open sets whose union is all of $\Omega$,
there is a finite subfamily $\{O_i\colon i<n\}$ such that
\begin{equation*}
O_0\cup\dots\cup O_{n-1}=\Omega.
\end{equation*}
Here $\mathcal O$ is called an \textbf{open covering} of $\Omega$,
and then $\{O_i\colon i<n\}$ may be referred to as a
\textbf{finite sub-covering} of $\mathcal O$.
\end{enumerate}

The Heine--Borel Theorem
(our Theorem \ref{thm:HB})
is that every closed, bounded subset of $\R$ is compact.
(Actually it is true for each $\R^n$.)
With the Compactness Theorem for propositional logic
(Theorem \ref{thm:comp}),
we showed that $\powo$ is compact in the topology
whose closed sets are just the sets $\Mod{\Gamma}$,
where $\Gamma\included L$,
$L$ being the set of propositional formulas in the variables $P_k$,
where $k\in\upomega$.
Here, for each $F$ in $L$,
\begin{equation*}
\Mod F\comp=\Mod{\lnot F},
\end{equation*}
so that $\Mod F$ is \textbf{clopen:} both closed and open.

\begin{theorem}\label{thm:clopen}
In $\powo$,
the clopen sets are precisely the sets $\Mod F$, where $F\in L$.
\end{theorem}

\begin{proof}
Suppose $\Mod{\Gamma}$ is open (as well as closed)
for some subset $\Gamma$ of $L$.
Then $\Mod{\Gamma}\comp$ is closed,
so it is compact
(as is every closed subset of a compact space, easily).
But
\begin{equation*}
\Mod{\Gamma}\comp=\bigcup_{F\in\Gamma}\Mod{\lnot F}.
\end{equation*}
By Compactness, there is a finite subset $\{F_k\colon k<n\}$ of $\Gamma$
such that
\begin{gather*}
	\Mod{\Gamma}\comp=\Mod{\lnot F_0}\cup\dots\cup\Mod{\lnot F_{n-1}},\\
	\Mod{\Gamma}=\Mod{F_0\land\dots\land F_{n-1}}.\qedhere
\end{gather*}
\end{proof}

The relation $\sim$ of \textbf{logical equivalence} on $L$ is given by
\begin{equation*}
F\sim G\iff\Mod F=\Mod G.
\end{equation*}
We can now define
\begin{gather*}
	[F]=\{X\in L\colon X\sim F\},\\
	L\modsim=\{[X]\colon X\in L\}.
\end{gather*}
The definitions ensure that there is a well-defined injection $X\mapsto\Mod X$
from $L\modsim$ to $\powo$.
By the last theorem,
the map is also surjective onto the collection $\mathscr B$ of clopen subsets of $\upomega$.
Here $\mathscr B$ is closed under
\begin{enumerate}[(1)]
	\item 
the binary operations $\cap$ and $\cup$,
\item
the singulary operation ${}\comp$, and
\item
the nullary operations $\emptyset$ and $\upomega$
(that is, $\mathscr B$ contains these sets).
\end{enumerate}
This makes $\mathscr B$ a \emph{Boolean subalgebra} of $\powo$.
Since
\begin{gather*}
	\Mod{F\land G}=\Mod F\cap\Mod G,\\
	\Mod{F\lor G}=\Mod F\cup\Mod G,\\
	\Mod{\lnot F}=\Mod F\comp,\\
	\Mod{P_0\land\lnot P_0}=\emptyset,\\
	\Mod{P_0\lor\lnot P_0}=\omega,
\end{gather*}
$L\modsim$ is a Boolean algebra
with respect to the (well-defined) operations given by
\begin{gather*}
	[F]\land[G]=[F\land G],\\
	[F]\lor[G]=[F\lor G],\\
	\lnot[F]=[\lnot F],\\
	\bot=[P_0\land\lnot P_0],\\
	\top=[P_0\lor\lnot P_0].
\end{gather*}
In general, an abstract \textbf{Boolean algebra}
(like $L\modsim$)
is a set $B$ with operations $\land$, $\lor$, $\lnot$,
$\bot$, and $\top$ with the following properties.
\begin{compactenum}
\item
The binary operations $\lor$ and $\land$ are \textbf{commutative:}
\begin{align*}
  x\lor y&=y\lor x,&x\land y&=y\land x.
\end{align*}
\item
The elements $\bot$ and $\top$ 
are \textbf{identities} for $\lor$ and $\land$ respectively:
\begin{align*}
x\lor\bot&=x,&x\land\top&=x.  
\end{align*}
\item
$\lor$ and $\land$ are mutually \textbf{distributive:}
  \begin{align*}
    x\lor(y\land z)&=(x\lor y)\land(x\lor z),\\
    x\land(y\lor z)&=(x\land y)\lor(x\land z).
  \end{align*}
\item
The element $\lnot x$ is a \textbf{complement} of $x$:
\begin{align*}
  x\lor\lnot x&=\top,&x\land\lnot x&=\bot.
\end{align*}
\end{compactenum}
Additional properties like associativity of $\land$ and $\lor$
follow from the given identities:

\begin{theorem}[E. Huntington, 1904]
  In any Boolean algebra:
  \begin{gather*}%\label{eqn:idemp}
    x\lor x=x,\qquad x\land x=x,\\%\label{eqn:zero-el}
x\lor\top=\top,\qquad x\land\bot=\bot,\\%\label{eqn:absorb}
x\lor(x\land y)=x,\qquad x\land(x\lor y)=x,\\%\label{eqn:double-neg}
\lnot\lnot x=x,\\%\label{eqn:De-M}
\lnot(x\lor y)=\lnot x\land\lnot y,\qquad
\lnot(x\land y)=\lnot x\lor\lnot y,\\%\label{eqn:assoc}
(x\lor y)\lor z=x\lor(y\lor z),\qquad(x\land y)\land z=x\land(y\land z).
  \end{gather*}
\end{theorem}

\begin{proof}
We give only an example:
\begin{gather*}
	x\lor(x\land y)=(x\land\top)\lor(x\land y)
	=x\land(\top\lor y)
	=x\land\top=x.\qedhere
\end{gather*}
\end{proof}

We shall investigate how $\powo$,
or more precisely a space homeomorphic with it,
can be obtained from the Boolean algebra $L\modsim$.
The same construction will work for any Boolean algebra,
and then the algebra can be recovered 
as being isomorphic to the algebra of clopen subsets of the space.
(This is the Stone Representation Theorem.)

We shall need that, on any Boolean algebra,
there is a partial ordering $\vdash$ given by
\begin{equation*}
x\vdash y\iff x\land y=x.
\end{equation*}
Note that
\begin{equation*}
x\land y=x\iff x\lor y=y.
\end{equation*}

We may henceforth blur the distinction between formulas in $L$
and their equivalence classes in $L\modsim$.
If $A\included\upomega$, we define
\begin{equation*}
\Th A=\{X\in L\colon A\models X\}.
\end{equation*}
This is the \textbf{theory} of $A$,
and it has the following properties.
\begin{enumerate}
	\item 
	If $F$ and $G$ are in $\Th A$, then $(F\land G)\in\Th A$.
	\item
	If $F\in\Th A$ and $F\vdash G$, then $G\in\Th A$.
	\item
	$F\notin\Th A$ if and only if $\lnot F\in\Th A$.
\end{enumerate}
By the first two properties,
$\Th A$ is a \textbf{filter} of the algebra $L\modsim$;
then the third property makes $\Th A$ an \textbf{ultrafilter,}
that is, a maximal filter
(the whole algebra not being counted as a filter;
any larger filter than $\Th A$ would contain some $F$ not in $\Th A$;
but then $\Th A$ contains $\lnot F$, 
so the larger filter contains $F\land\lnot F$,
which is equivalent to $\bot$,
and $\bot\vdash G$ for all $G$ in $L$).
The converse also holds:

\begin{theorem}\label{thm:ultra}
Every ultrafilter of $L\modsim$
is the theory of some element of $\powo$.
\end{theorem}

\begin{proof}
Given an ultrafilter $\Phi$ of $L\modsim$,
we may let
\begin{equation*}
A=\{k\in\upomega\colon P_k\in\Phi\}.
\end{equation*}
By induction $U=\Th A$, that is, for all $F$ in $L$,
\begin{equation*}
F\in U\iff A\models F.\qedhere
\end{equation*}
\end{proof}

For any Boolean algebra $B$,
we shall denote the set of ultrafilters of $B$ by
\begin{equation*}
\Stone B;
\end{equation*}
this is the \textbf{Stone space} of $B$,
because it will have a topology.
In our case,
we have a bijection $X\mapsto\Th X$
from $\powo$ to $\Stone{L\modsim}$,
and this will be a homeomorphism.

\chapter{Sunday, January 29, 2017}

We have been working with the relation $\models$ from $\powo$ to $L$.
We have used it to define 
	$X\mapsto\Mod X$ from $L$ to $\pow{\powo}$, where
	\begin{equation*}
	\Mod F=\{Y\in\powo\colon Y\models F\}.
	\end{equation*}
	Here
	\begin{gather*}
	\Mod{F\land G}=\Mod F\cap\Mod G,\\
	\Mod{\lnot F}=\Mod F\comp,
	\end{gather*}
	so that, when we define
	\begin{equation*}
	F\sim G\iff\Mod F=\Mod G,
	\end{equation*}
	the map $X\mapsto\Mod X$ induces a
	Boolean-algebra embedding of $L\modsim$ in $\pow{\powo}$.
	As we have shown (Theorem \ref{thm:clopen}, page \pageref{thm:clopen}),
the embedding is an isomorphism with the algebra of clopen subsets of $\powo$.

We have also defined a ``dual'' map, $Y\mapsto\Th Y$,
from $\powo$ to $\pow{L\modsim}$,
where
\begin{equation*}
\Th A=\{X\in L\colon A\models X\};
\end{equation*}
by Theorem \ref{thm:ultra} (page \pageref{thm:ultra}),
the map is a bijection
onto $\Stone{L\modsim}$,
the set of ultrafilters of $L\modsim$.

We have already defined
\begin{equation*}
\Mod{\Gamma}=\bigcap_{X\in\Gamma}\Mod X
\end{equation*}
when $\Gamma\included L$;
likewise we can define
\begin{equation*}
\Th{\mathscr A}=\bigcap_{Y\in\mathscr A}\Th Y
\end{equation*}
when $\mathscr A\included\powo$.  Then
\begin{gather*}
	\Gamma\included\Delta\implies\Mod{\Gamma}\includes\Mod{\Delta},\\
	\mathscr A\included\mathscr B\implies\Th{\mathscr A}\includes\Th{\mathscr B}.
\end{gather*}
Simply on this basis,
\begin{gather*}
	\Model\circ\Theory\circ\Model=\Model,\\
	\Theory\circ\Model\circ\Theory=\Theory,
\end{gather*}
so that there is a one-to-one correspondence,
called a \textbf{Galois correspondence,}
between the sets $\Mod{\Gamma}$
and the sets $\Th{\mathscr A}$.
In the original Galois theory,
the correspondence is between subfields of a field $K$ 
and subgroups of the group of automorphisms of $K$;
one obtains this by using, in place of our $\models$, 
the relation $R$ from the field to the automorphism group
given by
\begin{equation*}
x\mathrel R\sigma\iff x^{\sigma}=x.
\end{equation*}
In our case, the sets $\Th{\mathscr A}$ are filters of $L\modsim$,
while the sets $\Mod{\Gamma}$ can be called
\textbf{elementary classes}
(though all this means is that they are the classes of models of sets of formulas).

\begin{theorem}[Stone Representation]\label{thm:Stone}
Every Boolean algebra embeds in an algebra $\pow{\Omega}$
for some set $\Omega$.
\end{theorem}

\begin{proof}
If we replace $L$ with an arbitrary Boolean algebra $B$,
then we can also replace $\powo$ with $\Stone B$,
and $\models$ with $\in$.
When we define the map $x\mapsto[x]$ from $B$ to $\pow{\Stone B}$ by
\begin{equation*}
[a]=\{U\in\Stone B\colon a\in U\},
\end{equation*}
then
\begin{gather*}
[a]\cap[b]=[a\land b],\\
	[a]\comp=[\lnot a],
\end{gather*}
so the map is a homomorphism of Boolean algebras.
It is an embedding, by the Axiom of Choice,
or rather by the weaker axiom called the
\textbf{Prime Ideal Theorem}
(which is that every proper ideal of a ring is included in a prime ideal;
the Axiom of Choice gives that every proper ideal is included in a maximal ideal;
maximal ideals are always prime, but in Boolean rings,
prime ideals are also maximal).
\end{proof}

In the proof, the subsets $[a]$ of $\Stone B$
serve as the clopen sets of a topology,
the \textbf{Stone topology;} the closed sets are
\begin{equation*}
\bigcap_{x\in I}[x],
\end{equation*}
where $I\included B$.
This topology is always compact:
showing this comes down to observing that
if $\bigcap_{x\in I_0}[x]$ is never empty
when $I_0$ is a finite subset of $I$,
then $I$ is included in a proper filter,
and therefore (by the Prime Ideal Theorem) an ultrafilter $U$;
but this just means $U\in\bigcap_{x\in I}[x]$.

A \textbf{first-order logic,} such as the logic of set theory,
defines formulas as in propositional logic,
except that the atomic formulas are not propositional variables,
but (in the case of set theory) formulas $x\in y$;
also, if $\phi$ is a formula, and $x$ is a variable,
then so is $\Exists x\phi$.
One has the notion of a \textbf{free variable} of a formula;
if a formula has no free variable, the formula is a \textbf{sentence.}
Every sentence has a class of \textbf{models,}
which, considered in themselves, are \textbf{structures.}
Defining logical equivalence as before,
one obtains a Boolean algebra of sentences,
called a \textbf{Lindenbaum algebra} after a student of Tarski,
murdered by the Nazis.
The Stone space of this algebra is automatically compact.
The Compactness Theorem can then be understood as being that every ultrafilter of the Lindenbaum algebra
is in fact the theory of some structure.

Finally,
in the Stone Representation Theorem,
instead of a Boolean algebra,
we may start with an arbitrary topological space
and extract its algebra of clopen subsets.
However, the Stone space of this algebra
will not be homeomorphic with the original space
unless this is compact and \textbf{totally disconnected}
(for any two points, some clopen set contains only one of them).

\end{document}

