\documentclass[12pt,ifthen]{article}
\usepackage{amsmath}
\usepackage{hyperref}
\usepackage{comment}
\newcommand{\N}{{\sf N}}
\newcommand{\Q}{{\sf Q}}
\newcommand{\Z}{{\sf Z}}
\newcommand{\into}{{\rightarrow}}
\newcommand{\st}{\mathrel{:}}

\begin{document}

\centerline{\bf CMSC/MATH 858R Homework 3}
\centerline{\bf Morally Due TUESDAY  Feb 25 at 3:30PM.}


\newif{\ifshowsoln}
\showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks.

\begin{enumerate}

\item
(0 points)
What is your name? When is the midterm? By what day must you tell Dr.\ Gasarch you can't make the
midterm? (While this problem is 0 points, if you miss the midterm and do not tell Dr.\ Gasarch, 
you will get $-100$ on every single homework problem 1). When is the final? 

\item
(45 points)
Let $(X,\preceq)$ be a well quasi order.
Let $2^{{\rm fin } X}$ be the set of FINITE subsets of $X$.
We DEFINE an order $\preceq_{\mathrm{BILL}}$ on 
$2^{{\rm fin } X}$:

$A\preceq_{\mathrm{BILL}} B$ if there is an injection $f$ from $A$ to $B$ such that $x\preceq f(x)$ for all $x$.

($\emptyset \preceq_{\mathrm{BILL}} B$ is always true: use the empty function and the condition holds vacuously.)

Show that $(2^{{\rm fin } X},\preceq_{\mathrm{BILL}})$ is a well quasi order.

(NOTE- You may use the fact, proven in class, that well-quasi orders are closed under cross product)

\item
(45 points) 
Let $TREE$
be the set of trees.
We define $T\preceq_{\mathrm{CLYDE}} T'$ if
$T$ is a minor of $T'$
(recall that $T$ is a minor of $T'$ if you can get $T$ by removing vertices, removing edges, and contracting edges from $T'$)

Show that $TREE$ under $\preceq_{\mathrm{CLYDE}}$ is a wqo. 

\textbf{HINT:} You will need to use
the theorem you proved in problem 2 of this homework. As an additional
hint, your proof should begin like this:

\emph{Assume, BWOC that the set of trees under minor is NOT a wqo.}

\emph{Let $T_1,T_2,\ldots$ be a MINIMAL BAD SEQUENCE defined in some fashion (you figure it out).}

\emph{None of the trees is the empty tree, so they all have a root.}

\emph{Assume the root of $T_i$ has degree $d_i$. 
For each $T_i$ remove the root to obtain $d_i$ trees $T_{i,1},\ldots,T_{i,d_i}$
}

\centerline{\textbf{GO TO NEXT PAGE}}

\newpage

\item (10 points) Listen to the following songs all set to the tune of Coolio's \emph{Gangsta Paradise}

\begin{itemize}
\item
\emph{Gangsta Paradise} (not math): \url{https://www.youtube.com/watch?v=fPO76Jlnz6c}

\item
\emph{Mathematics paradise} by Klein Four: \url{https://www.youtube.com/watch?v=ncUm362M_gc}

LYRICS: \url{https://genius.com/The-klein-four-mathematics-paradise-lyrics}

\item
\emph{Mathematics Paradise} diff song entirely, not by Klein four: \url{https://www.youtube.com/watch?v=nskSfmeCFic}

\item
\emph{Amish Paradise} (not math): \url{https://www.youtube.com/watch?v=lOfZLb33uCg}
\end{itemize}

Which math version is your favorite? Is it better than the other math songs we have heard so far?

\end{enumerate}

\end{document}

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