\documentclass[11pt]{article} \usepackage{fullpage} \usepackage{url} \usepackage{amsmath} % This is a file of macros and definitions that may come up in % ANY LATEX paper. Typically I'll use this file and some other file in the % directory of the paper, this one for general math things, that one for % things specific to that paper. % % font's used and general paper things. \font\tenrm=cmr10 \font\ninerm=cmr9 \font\eightrm=cmr8 \font\sevenrm=cmr7 % \font\title=cmbx10 scaled \magstep1 % extra big title font \font\ss=cmss10 % used by \proof \font\smallcaps=cmcsc10 % used to label Theorems, etc. % imhibit black bars on overflows % \overfullrule=0pt % % today's date % % % English words that I always italizice in papers. % Some words that appear in math mode alot that I wasn roman % \newcommand{\R}{\rm R} \newcommand{\B}{\rm B} \newcommand{\G}{\rm G} \newcommand{\Y}{\rm P} \newcommand{\IO}{\exists^\infty} \newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil} \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} \newcommand{\into}{{\rightarrow}} \newcommand{\D}{{\sf D}} \newcommand{\N}{{\sf N}} \newcommand{\Z}{{\sf Z}} \newcommand{\Q}{{\sf Q}} \newcommand{\reals}{{\sf R}} \newcommand{\qd}{{\rm qd}} \newcommand{\GE}[1]{{\equiv^{G}_{#1}}} \newcommand{\TE}[1]{{\equiv^{T}_{#1}}} \newcommand{\TES}[1]{{\equiv^{T}_{#1,{\rm S}}}} \newcommand{\TEB}[1]{{\equiv^{T}_{#1,{\rm BOOL(S)}}}} \newcommand{\LL}{{\cal{L}}} \newcommand{\onepe}{1+\epsilon} \newcommand{\oneme}{1-\epsilon} \newcommand{\cool}{cool} \newcommand{\nze}{numzeros} \newcommand{\non}{numones} \newcommand{\LR}[2]{ {\rm LR}_{{#2}}({#1})} \newcommand{\LH}[2]{ {\rm LH}({#1};{#2})} \newcommand{\bbb}{{\gamma}} \newcommand{\COL}{{\rm COL}} \newcommand{\card}[1]{\#(#1)} \newcommand{\st}{\mathrel{:}} \newcommand{\fhat}{{\hat{f}}} \newcommand{\Ahat}{{\hat{A}}} \begin{document} \centerline{\bf Homework 04, Morally Due 12:30PM, Tue Feb 24, 2026} \newif{\ifshowsoln} %\showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks. \begin{enumerate} \item (0 points) What is your name? \vfill \centerline{\bf GO TO NEXT PAGE} \newpage \item (35 point) Let $X=\N^\omega=\N\times\N\times\N \cdots$ Let $\preceq$ be the ordering on $\N^\omega$ defined by: $(x_1,x_2,\ldots) \preceq (y_1,y_2,\ldots)$ iff $(\forall i)[x_i\le y_i].$ Does $(X,\preceq)$ have an $\infty$ antichain? Either say YES it does have an $\infty$ antichain and describe it OR say NO and prove that there is no $\infty$ antichain. \vfill \centerline{\bf GO TO NEXT PAGE} \newpage \item (35 points) Let $(X,\preceq_1)$ and $(Y,\preceq_2)$ be wqos. Then we define $\preceq$ on $X\times Y$ by $(x,y) \preceq (x',y')$ iff $x\preceq_1 x'$ and $y\preceq_2 y'$. Show that $(X\times Y,\preceq)$ is a wqo. \vfill \centerline{\bf GO TO NEXT PAGE} \newpage \item (30 points) Let $X$ be the set of all trees (graphs with no cycles). Let $H \preceq G$ mean that $H$ is a subgraph of $G$. Give an $\infty$ antichain of trees using this ordering. (That is, for all $i,j$, $T_i$ is not a subgraph of $T_j$ and $T_j$ is not a subgraph of $T_i$.) \vfill \centerline{\bf GO TO NEXT PAGE} \newpage \item (0 points but you must do it) In class I said that the Bernoulli's and the Kruskal's are the two best math families ever. This is not a formal statement; however, I am sure its true. In baseball we really can ask such questions formally. We will just look at brothers who are both pitchers. Phil Niekro won 318 games. His brother Joe won 221. So their total is 529 which is the most of any pair of brothers. So they are in first place. Name the pairs of brothers who are in second place, third place, fourth place, and fifth place, in terms of total number of wins. I don't expect anyone to know this off of their top of their heads so of course you can look it up. Despite looking silly there really is a point to this question so you need to do it. \vfill \centerline{\bf GO TO NEXT PAGE} \newpage \item (Extra Credit 0 points) We present some STATEMENTS and some QUESTIONS. {\bf STATEMENT $TST_n$:} For ALL FUNCTIONS $f(x_1,\ldots,x_n)$ that map $\N^n$ to $\N$ there exists an infinite $\D\subseteq \N$ such that $f$ restricted to $\D^n$ is NOT onto. ($TST_n$ stands for {\it Thin Set Theorem with $n$ variables.} {\bf STATEMENT $PRTST_n$:} For ALL PRIMITIVE RECURSIVE FUNCTIONS $f(x_1,\ldots,x_n)$ that map $\N^n$ to $\N$ there exists an infinite $\D\subseteq \N$ such that $f$ restricted to $\D^n$ is NOT onto. ($PRTST_n$ stands for {\it Primitive Recursive Thin Set Theorem with $n$ variables.} Clearly $TST_n$ implies $PRTST_n$. Here is what we know from class, what we are going to learn later, and some QUESTIONS for you. $n=1$: $TST_1$ is true. You proved this on a HW. Hence $PRTST_n$ is true. $n=2$: $TST_2$ is true. I proved this in class in the slide set called {\it The Thin Set Theorem}. The proof used Ramsey Theory. Since $TST_2$ is true, $PRTST_2$ is true. {\bf QUESTION:} Is there a proof of $PRTST_2$ that does NOT use Ramsey's Theorem? (I mean REALLY does not use it. DO NOT prove it in context.) (I REALLY DO NOT KNOW THE ANSWER TO THIS ONE. I DO NOT KNOW IF ITS KNOWN.) General $n$: $TST_n$ is true. I will prove this in class once we cover the $n$-ary Ramsey Theorem. {\bf QUESTION:} Is there a proof of $PRTST_n$ that does NOT use Ramsey's Theorem. (I mean REALLY does not use it. DO NOT prove it in context.) (I REALLY DO NOT KNOW THE ANSWER TO THIS ONE. I DO NOT KNOW IF ITS KNOWN.) {\bf QUESTION FOR LATER IN THE TERM:} Once I prove the $n$-ary Ramsey Theorem I will ask if $PRTST_n$ can be proven with the $m$-ary Ramsey Theorem for some $m