% Here is the LateX version of the letter I wrote to you.
% Please feel free to use any part of it in the updated version of
% your book.
%    A.Miller

\documentclass[12pt]{article}
\usepackage{amssymb}

\def\infsets{[\omega]^\omega} \def\res{|_}
\def\qed{\nopagebreak\par\noindent\nopagebreak $\Box$ \par}
\def\proof{{\par\noindent{\bf Proof: }}} 
\def\forces{\mid\vdash}

\newtheorem{theorem}{Theorem}  \newtheorem{lemma}[theorem]{Lemma}

\begin{document}

\begin{flushright}
 Arnold W. Miller\\
 Department of Mathematics\\
 University of Wisconsin\\
 Madison, WI 53706\\
 July 1, 1987 \\
\end{flushright}


\bigskip
\hrule

\bigskip

\noindent Dear Professor Fra\"{i}ss\'{e}


I enjoyed very much reading your book, {\bf Theory of Relations}.
Thank you for writting it.

Probably someone has already answered the problem of
Hagendorf\footnote{I have sent copies of this letter to Hagendorf, Kunen,
 Pouzet, and Veli\v{c}kovi\'{c}.}
which you mention on page 136:

\begin{quote}
Existence of a strictly decreasing $\omega_1$-sequence of denumerable
partial orderings.
\end{quote}

The following result, which I proved jointly with Ken Kunen,
answers this question in the affirmative.

\begin{theorem}
There exists $\langle P_X: X\in\infsets\rangle$
where each $P_X$ is a countable
poset and
$$P_X \mbox{ embeds into } P_Y \iff X\subseteq^* Y$$
where $\infsets$ is the set of infinite subsets of $\omega=\{0,1,2,\ldots\}$
and $X\subseteq^* Y$ means inclusion mod finite, i.e. $X\setminus Y$ is finite.
\end{theorem}

Since there are decreasing mod finite $\omega_1$ sequences in $\infsets$
we get that the same is true for countable posets under embedding.
\begin{lemma}
There is a set $\langle C_n: n\in\omega\rangle$  of finite partial orders
such for any $n\in\omega$, $C_n$ cannot be embedded in the disjoint
union of $\{C_m: m\neq n\}$.  Furthermore no $C_n$ contains a chain
of length three.
\end{lemma}
\proof
For $n\geq 3$ let $C_{n-3}$ be the following ordering on $2n$ points
$$\{a_i,b_i: i<n\}$$
$$a_i<b_j \iff i=j \mbox{ or $j=i+1$ mod n}$$
Otherwise incomparable.
Hence the a's are all minimal and the b's maximal. I picture them as being
wrapped around a cylindar or ring. The embedding claim is true for the
same reason that a cyclic graph cannot be embedded into another
one of different cycle length.
\qed

For any $Y\in\infsets$ let $Q(Y)$ be the partial order
which  consists of
the disjoint union of $\{C_m: m\in Y\}$
and in addition has a unique minimal element $c$.

Now we describe $P_X$ for any $X\in\infsets$.
Let $\{X_n: n\in\omega\}$ be all $Y\in\infsets$ such that $Y=^*X$.
$P_X$ is the disjoint union of $\{Q(X_n): n\in\omega\}$.

It easy to show that if $Y\subseteq Z$ then $Q(Y)$ can be embedded into
$Q(Z)$ and hence if $X\subseteq^* Y$ then $P_X$ can be embedded into
$P_Y$.  On the other hand if $P_X$ can be embedded into $P_Y$
then for some n, $Q(X_0)$ can be embedded into $Q(Y_n)$ and
thus $X_0\subseteq Y_n$ and so $X\subseteq^* Y$.
This proves the theorem.
\qed

B. Veli\v{c}kovi\'{c} (CalTech) asked whether it is possible to get a
decreasing chain of countable posets of length $2^{\aleph_0}$.
Assuming MA the answer to Veli\v{c}kovi\'{c}'s question is yes, since such
chains exist in $\infsets / \mbox{finite}$. However in the Cohen real
model (adding say $\kappa\geq\omega_2$ Cohen reals to a model of GCH)
the continuum is large, but $\omega_2$ does not embed into
$\infsets / \mbox{finite}$.  This in fact, follows from  an
unpublished result in Kunen's Thesis.
(The theorem in Kunen's thesis is that in the Cohen real model no
well-order of $\omega_2$ is in the $\sigma-$algebra generated by rectangles
$\{A\times B: A,B\subseteq\omega_2\}$.)

His argument can be generalized to show:

\begin{theorem}
It consistent relative to the consistency of ZFC that
the continuum is arbitrarily large but there does not exist countable
structures $\langle A_{\alpha}: \alpha<\omega_2\rangle$ such that
for all $\alpha,\beta<\omega_2$
$$ \alpha<\beta \iff A_{\alpha}\mbox{ embeds into } A_{\beta}$$
\end{theorem}

\proof Let M be a countable transitive model of ZFC+GCH and
let P be $FIN(\kappa)$ the partial order of finite partial functions from
$\kappa$ into 2  where $\kappa$ is any cardinal of M
$\geq\omega_2^M$. Suppose for contradiction that in M[G] where G is
P-generic over M there is such an $\omega_2$ sequence.

Working in M,
let $\langle A_{\alpha}: \alpha<\omega_2\rangle$ be a sequence of names
for countable structures with $\omega$ as thier universe
and $p\in P$ be such that

$$ p\forces\forall \alpha,\beta \;[\alpha<\beta\iff
A_{\alpha}\mbox{ embedds into }A_{\beta}]$$

Since P has c.c.c. we can assume that the names have countable support,
i.e. we can
find $\Gamma_{\alpha}$ countable subsets of $\kappa$
such that $A_{\alpha}^G\in M[G\res{\Gamma_{\alpha}}]$.

By the delta systems lemma we can find $X\in[\omega_2]^{\omega_2}$ and
root  R such that for $\alpha,\beta\in X$ and distinct
$$\Gamma_{\alpha}\cap\Gamma_{\beta}=R$$

We can assume that the order type of every $\Gamma_{\alpha}$ for
$\alpha\in X$ is the same (say $\alpha_0$)
 and furthermore that the unique order
preserving map between any two
is the identity on R. (Since M satisfies CH.)

Let $\pi_{\alpha}$ be the partial order isomorphism from
$FIN(\Gamma_{\alpha})$ to $FIN(\alpha_0)$ induced by the unique order
preserving map from $\Gamma_{\alpha}$ to $\alpha_0$.

Let $\pi_{\alpha}(A_{\alpha})=\tau_{\alpha}$.  Since M satisfies
CH we can assume that all $\tau_{\alpha}$ are the same. It follows then
that if $\pi$ is the automorphism of $FIN(\kappa)$ induced by
interchanging $\Gamma_{\alpha}\setminus R$ and $\Gamma_{\beta}\setminus R$
order preservingly
and the identity outside of these, then $\pi(A_{\alpha})=A_{\beta}$
and $\pi(A_{\beta})=A_{\alpha}$

If we take $\alpha,\beta\in X$ such that $\alpha<\beta$ and
$\Gamma_{\alpha}\setminus R$ and $\Gamma_{\beta}\setminus R$
are both disjoint from the domain of p (so $\pi(p)=p$) then
since
$$p\forces A_{\alpha}\mbox{ embedds into } A_{\beta}$$
so
$$\pi(p)\forces \pi(A_{\alpha})\mbox{ embedds into }\pi( A_{\beta})$$
hence
$$p\forces A_{\beta}\mbox{ embedds into } A_{\alpha}$$
contradicting $\alpha <\beta$.
\qed

\vspace{.5in}

\hspace{2in}  sincerely,



\vspace{.5in}


\hspace{2in}  Arnold W. Miller




\end{document}