\documentclass{article}

\usepackage{amssymb,amsmath,amsthm}

% general definitions

\newcommand{\Z}{\ensuremath{\mathbb Z} }
\newcommand{\R}{\ensuremath{\mathbb R} }
\newcommand{\E}{\exists~}
\newcommand{\of}[1]{\left(#1\right)}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\union}{\cup}
\newcommand{\inter}{\cap}
\newcommand{\Union}{\bigcup}
\newcommand{\Inter}{\bigcap}
\newcommand{\sbs}{\subseteq}
\newcommand{\sps}{\supseteq}
\newcommand{\defn}{\overset{\text{def}}{=}}

\newcommand{\st}{~\text{s.t.}~}
\newcommand{\fs}{~\text{for~some}~}

\newcommand{\eg}{\textit{e.g.} }
\newcommand{\ie}{\textit{i.e.} }
\newcommand{\Eg}{\textit{E.g.} }
\newcommand{\Ie}{\textit{I.e.} }

\newcommand{\eqn}[1]{\begin{align*} #1 \end{align*}}
\newcommand{\EQN}[1]{\begin{align} #1 \end{align}}

\newcommand{\axiom}[1]{{\bfseries #1.}}
\newcounter{axiom}
\newenvironment{axioms}[1]
	{\begin{list}
		{\axiom{#1\arabic{axiom}}}
		{\usecounter{axiom}}}
	{\end{list}}

\newtheorem*{lemma*}{Lemma}

\DeclareMathOperator{\Ext}{Ext}
\DeclareMathOperator{\Int}{Int}
\newcommand{\Bdy}{\partial}

% definitions for solution sets

\newcommand{\problem}[1]{\section*{Problem #1}}
\renewcommand{\labelenumi}{\bfseries{(\alph{enumi})}}

% definitions for math101

\newcommand{\K}{\ensuremath{\mathcal K}}

% definitions for this problem set

\newcommand{\LL}{\ensuremath{\mathbb L}}
\newcommand{\Zg}[1]{\set{ x \in \Z : #1 \leq x }}

% document info

\title{Math 101 \\ Problem Set 1 Solutions}

\author{Thomas Allen and Stefan Karpinski}

\begin{document}

\maketitle

\problem{N 1.3.1}

\begin{enumerate}

	\item	$\K A = \set{ x \in \Z : \E a \in A \st a < x }$.
		Not a closure operator:
		\eqn{ \set{0} \not\sbs \K \set{0} = \set{1,2,3,\dots}. }
	\item	$\K A = \set{ x \in \Z : \E a \in A \st a \leq x }$.
		A closure operator:
		
		\begin{axioms}{C}
		
			\item	If $A$ has no minimum then $\K A = \Z$ which contains $A$.
				If $A$ has a minimum, $a_0$, then $\K A = \Zg{a_0}$ which also contains $A$.
				
			\item	If either $A$ or $B$ has no minimum (or both) then
				\eqn{ \K A \union \K B = \K(A \union B) = \Z }
				so we're done.
				If both $A$ and $B$ have minima, $a_0$ and $b_0$, respectively
				\eqn{ \K(A \union B)
					& = \Zg{\min\set{a_0, b_0}} \\
					& = \Zg{a_0} \union \Zg{b_0} \\
					& = \K A \union \K B. }
					
			\item	If $A$ has no minimum then $\K\K A = \K A = \Z$.
				If it has a minimum, $a_0$ then $\K\K A$ and $\K A$ both equal
				\eqn{ \Zg{a_0}. }
			\item	$\K \emptyset = \emptyset$ is clear.

		\end{axioms}
		
	\item	$\K A = \set{x \in \Z : \E a \in A, k \in \Z \st x = ka }$.
		A closure operator. \\
		For $A,B \sbs \Z$ denote $AB = \set{ x \in \Z : x = yz \fs y,z \in \Z}$.
		Observe that
		\EQN{	\label{obs1}	\Z\Z & = \Z \\
			\label{obs2}	\K A & = \Z A \\
			\label{obs3}	(AB)C & = A(BC) }
			
		for $A,B,C \sbs \Z$.

		\begin{axioms}{C}
		
			\item	Use observation \eqref{obs2}: $\K A = \Z A \sps \set{1} A = A$.
			
			\item	Calculate using observation \eqref{obs2} again
				\begin{alignat*}{2} % this is some not-so-slick persian bizzare formatting
					\K(A \union B)
					& = &~& \Z(A \union B) \\
					& = &&\!\set{ y \in \Z : y = nx \fs n \in \Z, x \in A \union B } \\
					& = &&\!\set{ y \in \Z : y = nx \fs n \in \Z, x \in A } \union \\
					&   &&\!\set{ y \in \Z : y = nx \fs n \in \Z, x \in B } \\
					& = && \Z A \union \Z B \\
					& = && \K A \union \K B
				\end{alignat*}
		
			\item	Using observations \eqref{obs1} through \eqref{obs3} we get
				\eqn{ \K\K A = \K(\Z A) = \Z(\Z A) = (\Z\Z) A = \Z A = \K A. }
			
			\item	$\K \emptyset = \emptyset$ is clear.
				
		\end{axioms}
		
	\item	$\K A = \set{ x \in \Z : \E a_1, a_2 \in A \st a_1 \leq x \leq a_2 }$.
		Not a closure operator:
		\eqn{	\K\set{1} \union \K\set{3} & = \set{1} \union \set{3},~\text{but} \\
			\K(\set{1} \union \set{3}) & = \K\set{1,3} = \set{1,2,3}. }
	
\end{enumerate}

\problem{N 1.3.2}

Check that $(L,\K)$ satisfies the Kuratowski Axioms:

\begin{axioms}{C}
	
	\item	Since both $A \sbs A$ and $A \sbs A \union \set\infty$, $A \sbs \K A$ for all $A$.

	\item	If both $A$ and $B$ are finite then $A \union B$ is finite too so
		\eqn{ \K(A \union B) = A \union B = \K A \union \K B. }
		Otherwise, say $A$ is infinite, and thus so is $A \union B$.  Then
		\eqn{ \K A \union \K B = A \union B \union \set\infty = \K(A \union B) }
	\item	If $A$ is finite we have $\K A = A \implies \K\K A = \K A = A$.
		Otherwise we have
		\eqn{ \K\K A = \K(A \union \set\infty) = \K A \union \set\infty = A \union \set\infty = \K A. }
	
	\item	$\K \emptyset = \emptyset$ is clear.
		
\end{axioms}
	
\problem{N 1.4.1}

\begin{enumerate}

	\item	Apply axiom \axiom{C2} twice:
		\eqn{ \K(A_1 \union A_2 \union A_3)
			= \K(A_1 \union A_2) \union \K A_3
			= \K A_1 \union \K A_2 \union \K A_3 }
	
	\item	Apply axiom \axiom{C2} three times.  (It's the same.)

	\item	The general conjecture is that for $n \in \Z$
		\eqn{ \K\Union_{k = 1}^n A_k = \Union_{k = 1}^n \K A_k. }
		We could simply say here that we apply axiom \axiom{C2} $n-1$ times
		but that would be glossing over something very important which is happening here---induction.
		We've already done the base case and now we simply observe that
		\eqn{ \K\Union_{k = 1}^n A_k = \K\Union_{k = 1}^{n - 1} A_k \union A_n }
		and by the \textit{induction hypothesis}
		($=$ the assumption that what you'd like to prove is true for smaller $n$)
		we already know that
		\eqn{ \K\Union_{k = 1}^{n - 1} A_k = \Union_{k = 1}^{n - 1} \K A_k, }
		so we're done.

\end{enumerate}
	
If we replace unions with intersections
then the resulting conjecture is blatantly false already in the case $n = 2$.
(Consider \eg on the real line \R with the standard Euclidean topology:
	$\K([0,1) \inter (1,2]) = \K(\emptyset) = \emptyset$ but
	$\K [0,1) \inter \K (1,2] = [0,1] \inter [1,2] = \set{1}$.)
However, Theorem N 1.10 says that we do have
$\K(A \inter B) \sbs \K A \inter \K B$
and using induction as before we get the more general result
\eqn{ \K\Inter_{k = 1}^n A_k \sbs \Inter_{k = 1}^n \K A_k. }
	
\problem{N 1.4.2}

\begin{enumerate}

	\item	Let $X = \Z$,
		let $\K$ be the closure operator defined in Problem N 1.3.1(b)
		(which we showed was in fact a closure operator)
		and let $A = \set{1}$ and $B = \set{2}$.
		Then $\K A = \set{1,2,3,\dots}$ and $\K B = \set{2,3,4,\dots}$ so
		\eqn{	\K(A - B) = \K A = \set{1,2,3,\dots} \not\sbs \set{1} = \K A - \K B. }
	
	\item	Begin with the following lemma:
		\begin{lemma*}
			$C - D \sbs E \iff C \sbs D \union E$.
		\end{lemma*}
		\begin{proof}
			Suppose $C - D \sbs E$.
			If $x \in C$ then $x \in E$ or $x \in D$ (and $x \not\in C - D$).
			This in turn implies $x \in D \union E$.
			So, $C \sbs D \union E$.
			
			Now, if $C - D \not\sbs E$,
			then there exists $x \in C - D$ such that $x \not\in E$.
			Furthermore, $x \in C$ but $x \not\in D$
			implies $x \not\in D \union E$
			and finally $C \not\sbs D \union E$.
		\end{proof}
		Now clearly $A \sbs A \union B = B \union (A - B)$.
		By Theorem N 1.9 (that $C \sbs D$ implies $\K C \sbs \K D$),
		we therefore have that
		\eqn{ \K A \sbs \K(B \union (A - B)) = \K B \union \K(A - B), }
		which---by the Lemma---happens if and only if
		\eqn{ \K A - \K B \sbs \K(A - B). }
				
\end{enumerate}

\problem{N 1.4.3}

Recall the following definitions.
\eqn{	\Ext A & \defn (\K A)^c = X - \K A \\
	\Int A & \defn (\K A^c)^c = X - \K (X - A) \\
	\Bdy A & \defn \K A \inter \K A^c = \K A \inter \K (X - A) }
For brevity we denote the complement of a set $S$ by $S^c = X - S$.

\begin{enumerate}

	\item	There are four properties to verify:
		\EQN{	\label{prop1}	X		& = \Ext A \union \Int A \union \Bdy A \\
			\label{prop2}	\emptyset	& = \Ext A \inter \Int A \\
			\label{prop3}	\emptyset	& = \Ext A \inter \Bdy A \\
			\label{prop4}	\emptyset	& = \Int A \inter \Bdy A. }
		First we verify \eqref{prop1} using De Morgan's Law repeatedly and cancelling as we go:
		\eqn{ \Ext A \union \Int A \union \Bdy A
			& = (\K A)^c \union (\K A^c)^c \union (\K A \inter \K A^c) \\
			& = (\K A)^c \union \Big[ \big[ (\K A^c)^c \union \K A \big] \inter \big[ (\K A^c)^c \union \K A^c \big] \Big] \\
			& = (\K A)^c \union \Big[ \big[ (\K A^c)^c \union \K A \big] \inter X \Big] \\
			& = (\K A)^c \union (\K A^c)^c \union \K A \\
			& = X \union (\K A^c)^c \\
			& = X. }
				
		Next we verify \eqref{prop2} by noting that for any set $B \sbs X$ we have
		\eqn{ (\K B^c)^c \sbs B. }
		Using this twice, first with $B = A$ and second with $B = A^c$, we get
		\eqn{ \Ext A \inter \Int A
			& =	(\K A)^c \inter (\K A^c)^c \\
			& \sbs	(\K A)^c \inter A \\
			& \sbs	A^c \inter A \\
			& =	\emptyset. }
								
		Finally we verify \eqref{prop3} and \eqref{prop4} by simply cancelling in the obvious fashion:
		\eqn{	\Ext A \inter \Bdy A = (\K A)^c \inter \K A \inter \K A^c	& = \emptyset, \\
			\Int A \inter \Bdy A = (\K A^c)^c \inter \K A \inter \K A^c	& = \emptyset. }

\end{enumerate}

\end{document}













