\documentclass{article}
\input{../notes/preamble.tex}
\usepackage{url,enumerate}
\title{Assignment 6}
\date{Friday June 15, 2012}
\newcommand{\df}{\textbf}
\begin{document}
\maketitle
\section{Final Project on Sets}
It is intended that this section be completed on Tuesday June 12h. It is a comprehensive test on your knowledge of sets.
\begin{prob}
Consider a nonempty set $S$ and let $f:\wp(S)\to \wp(S)$ be a function which is monotone with respect to $\sbs$, that is for any $A,B\in\wp(S)$, whenever $A\sbs B$ then $f(A)\sbs f(B)$.
Define $F := \bigcap \set{ X\in \wp(S) \mid f(X)\sbs X }$
\begin{enumerate}[\qquad(a)]
\item For fun, give an example of a monotone function $g:\wp(\N)\to\wp(\N)$ that is not the identity map. This does not relate to any other part of the problem, just to get you thinking about what it means to be monotone. \textit{Hint: One way is to start with your favorite function from $\N\to\N$. What is an easy way to make a function on $\wp(\N)$ using this? Is it monotone?}
\item Prove the set being intersected to form $F$ is nonempty, that is, there is a set $X\in\wp(S)$ such that $f(X)\sbs X$.
\item Prove $f(F) \sbs F$
\item Prove $F\sbs f(F)$, then conclude $f(F) = F$. \textit{Hint: show $f(F)$ is in the intersection}
\item Suppose $B$ has the property that $f(B) = B$. Prove that $F\sbs B$.
\end{enumerate}
Congratulations! You just proved the Knaster-Tarski fixed point theorem for sets (or at least the spirit of it):
\begin{thm*}[Knaster-Tarski Fixed Point Theorem (for sets)]
For any set $S\neq \emptyset$ and any monotone (wrt. $\sbs$) function $f:\wp(S) \to \wp(S)$ there is a unique least fixed point.
\end{thm*}
\end{prob}
\section{Functions!}
\subsection{Basic Properties}
It is intended that this section be completed on Tuesday June 12th. Here we will practice some of the properties of functions that we have learned during class. We should be experts on what 1-1 and onto mean after this!
\begin{prob}
Let $f:A\to B$ be injective. Prove that for every $X,Y\sbs A$
\[
f[X\minus Y] \sbs f[X]\minus f[Y]
\]
Underline where you use injectivity of $f$.
\end{prob}
\begin{prob}
Consider the following function $f:\R\times\R \to \R\times\R$
\[
f(x,y) = (x+y, y-3x)
\]
Prove that $f$ is a bijection.
\end{prob}
\begin{prob}
Assume $f:A\to B$ and $g:B\to C$. Prove or Disprove:
\begin{enumerate}[\qquad(a)]
\item If $f\circ g$ is surjective then $g$ is surjective
\item If $f\circ g$ is surjective then $f$ is surjective
\item If $f\circ g$ is injective then $g$ is injective
\item If $f\circ g$ is injective then $f$ is injective
\end{enumerate}
\end{prob}
\begin{prob} Let $f:A\to B$. Let $X\sbs A$ and $Y\sbs B$. {\bf Justify} all your answers with proofs or counterexamples.
\begin{enumerate}[\qquad(a)]
\item Is it true that $f^{-1}[f[Y]] = X$? If not, what conditions can you put on $f$ so that it is true (ie. surjectivity or injectivity).
\item Is it true that $f[ f^{-1}[Y]] = Y$? If not, what conditions can you put on $f$ so that it is true (ie. surjectivity or injectivity)
\end{enumerate}
\end{prob}
\subsection{Cardinality}
It is intended that this section be completed on Wednesday June 13th. Here will will do some practice with cardinality.
\begin{prob}
Prove that if $A$ and $B$ are disjoint, finite sets then
\[
|A| + |B| = |A \cup B|
\]
By exhibiting a bijection between $A\cup B$ and $[n+m]$ where $|A|=n$ and $|B|=m$.
\end{prob}
\subsection{To Infinity and Beyond}
Recall that a set is countable if it is finite or there is a bijection between that set and the natural numbers $\N$. Otherwise, we say that a set is uncountable.
We have prove that the countable union of countable sets is countable. Keep that in mind for the next problem.
\begin{prob}
We will prove that the reals are uncountable. Here is an alleged proof that they are countable. Find the mistake.
\begin{proof}
Well, it is clear that one can achieve any real number by taking a number in $(0,1)$ and adding some integer to it. Thus, $\R = \bigcup_{x\in(0,1)} \set{ x + k \mid k\in \Z }$. As $\Z$ is countable, this is a countable union of countable sets, so $\R$ is countable.
\end{proof}
\end{prob}
\begin{prob}
Show that
\[
|\R| = |\mathbb{C}|
\]
{\it Show that $|\R| = |\R \times \R|$.}
\end{prob}
\end{document}