%% Process me in latex2e.

% BEGIN PREAMBLE

\documentclass[12pt]{article}
\pagestyle{empty}   % no page numbers
\nofiles % no aux file


% fonts:
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{latexsym}  % latex2e symbol package

% if needed, to get the format right:
% \addtolength{\textwidth}{1cm}
% \addtolength{\oddsidemargin}{-8mm}
  \addtolength{\textheight}{8mm}
  \addtolength{\topmargin}{-10mm}

\newcommand\RRR{{\mathbb R}} 


% END PREAMBLE

\begin{document}


\begin{center}
MATH 770 HOMEWORK 1 \\
{\it Semester I, 2006-2007} \\
{\it Due September 21}
\end{center}



\bigskip

These should be considered warming-up exercises, 
since we haven't done anything yet.  You should be able to work
these problems using general background knowledge.
Specifically, (4,5) assume you already know about the real numbers.
In (1,2,3), note that you can talk about models for axioms without
knowing any model theory, just like you do in algebra.
Models are, by definition, always non-empty.


\bigskip

\textbf{1.} Describe a finite model for the 
Axiom of Extensionality which satisfies the statement that
there is no empty set ($\neg \exists x \forall y [y \notin x]$).

\bigskip

\textbf{2.} Describe a finite model for the 
Axioms of Extensionality and Comprehension which satisfies the statement that
every set is empty ($\forall x \forall y [y \notin x]$).

\bigskip

Solutions to (1,2) can be found among the pictures in Exercise I.2.1.
When you start adding axioms, it becomes harder to produce models:

\bigskip

\textbf{3.} Prove that there is no finite model for
the Axioms of  Comprehension, and Pairing.
\textit{Hint.}  You only need the following two consequences
of these axioms:  $\exists x \forall y (y \notin x)$ (existence of $\emptyset$)
and
$\forall z \exists x \forall y (y \in x \leftrightarrow y = z)$ (existence
of $\{z\}$).  If you try to draw the $\in$ digraph, you'll
see why it can't be finite.


\bigskip

\textbf{4.} Describe a bijection between an open disc and a closed
disc in the plane.
\textit{Remark.} ``Describe'' means to write down an explicit definition;
you don't need the Axiom of Choice here.
\textit{Hint.} 
Delete a countably infinite set of circles from each so that
the resulting sets are homeomorphic.

Actually, every uncountable Borel set in the plane
contains a Cantor set (Hausdorff, 1916), and hence has size $2^{\aleph_0}$.

\bigskip


The Schr\"oder-Bernstein Theorem tells you how to construct a bijection
between $A$ and $B$ whenever you are given injections $A\to B$ and $B\to A$.
The bijection you get in (4) should be simpler than the one you
read off of the proof of this theorem (in case you know the proof).
However, I don't know a really simple bijection of the
line  onto the plane,
although the proof of the Schr\"oder-Bernstein Theorem tells
you how to define one, using a (trivial) injection of
$\RRR$ into $\RRR\times\RRR$ plus:

\bigskip

\textbf{5.} Describe a 1-1 map from $\RRR\times \RRR$ into $\RRR$.
\textit{Hint.} Shuffle the decimal representations.  Careful with
the sign; you might identify $\RRR$ with $(0,1)$ first.



\end{document}