\documentclass[10pt]{article} % 
\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{graphics}
\usepackage{psfrag}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{enumerate}
\usepackage{xspace}

\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}

\newcommand{\cP}{\mathcal{P}}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\cL}{\mathcal{L}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\points}[1]{{\it (#1 Points)}}
\newcommand{\tpoints}[1]{{\bf #1 Total points.}}
\newcommand{\im}{\mathop{\mbox{Im}}\xspace}
\title{Math 214 -- Foundations of Mathematics\\
Homework 10\\
{\large{\bf Due Nov 16, 2012}}
}
\date{}
\author{Your name}
\newenvironment{answer}{\medskip \noindent
}
{}


\begin{document} 
\maketitle

Each problem is worth 4 points. 

\begin{enumerate}

\item Let $\alpha=
  \begin{pmatrix}
    1 & 2 & 3 & 4 & 5 \\
    2 & 3 & 4 & 5 & 1 
  \end{pmatrix}$ and $\beta=
  \begin{pmatrix}
    1 & 2 & 3 & 4 & 5 \\
    3 & 5 & 2 & 4 & 1 
  \end{pmatrix}$ be permutations in $S_5$. \\
 Determine $\alpha\circ \beta$, $\beta\circ \alpha$,  and $\beta^{-1}$. 
    



\item Let $f: A\to \N$ and $g: B\to \N$ be bijections.  Show that $h: A\times B\to \N^2$ with $h(a,b)=(f(a), g(b))$ is also a bijection.  (Remark: this fact was used to show that $A\times B$ is denumerable if $A$ and $B$ are. )

\item Show that if $A$ and $B$ are denumerable sets, then $A\cup B$ is also denumerable (hint: consider the cases when $A$ and $B$ are disjoint or not). 

\item Prove that $S=\{(a,b): a, b\in \N, a\ge 2b\}$ is denumerable. 

\item \label{li:1} For $k \in \N$, let $S_k = \{A \subset \N : |A| =k\}$. Show that $|S_2| = | \N |$  (hint:  construct a bijection from $S_2$ to a subset of $\N^2$).

\item show that $|\Q|=|\Q-\{2\}|$.


 
\item ({\it Bonus, 4 points}) Using the definition of $S_k$ from
  problem \ref{li:1}, show that
  \begin{enumerate}[(a)]
    \item for all $k \in \N$, $S_k$ is denumerable.
    \item $\cS = \bigcup_{k=1}^\infty S_k$  is denumerable.
\end{enumerate}

\item (Bonus, 4 points) In class we mentioned that according to the ``diagonal method'', the elements in $\N^2$ can be listed as $$(1, 1), (1,2), (2, 1), (1,3), (2,2), (3,1), (1,4), (2,3), (3,2), (4,1), \ldots.$$ Construct the explicit bijection from $\N^2$ to $\N$.
   

    
    
    
    
    
\end{enumerate}

\end{document}



%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
