Arnold W. Miller

Department of Mathematics University of Wisconsin Madison, WI 53706

July 1, 1987

Dear Professor Fraïssé

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

Probably someone has already answered the problem of Hagendorf^{1} which you mention on page 136:

Existence of a strictly decreasing ω_{1}-sequence of denumerable partial orderings.

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

Theorem 1 There exists ⟨P_{X} : X ∈ [ω]^{ω}⟩ where each P_{X} is a countable poset and

P_{X} embeds into P_{Y} ⟺ X ⊆^{∗} Y

where [ω]^{ω} is the set of infinite subsets of ω = {0, 1, 2, …} and X ⊆^{∗} Y means inclusion mod finite, i.e. X \ Y is finite.

Since there are decreasing mod finite ω_{1} sequences in [ω]^{ω} we get that the same is true for countable posets under embedding.

Lemma 2 There is a set ⟨C_{n} : n ∈ ω⟩ of finite partial orders such for any n ∈ ω, C_{n} cannot be embedded in the disjoint union of {C_{m} : m ≠ n}. Furthermore no C_{n} contains a chain of length three.

Proof: For n ≥ 3 let C_{n−3} be the following ordering on 2n points

{a_{i}, b_{i} : i < n}
a_{i} < b_{j} ⟺ i = j or j = i + 1 mod n

1I have sent copies of this letter to Hagendorf, Kunen, Pouzet, and Veličković.

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. □

For any Y ∈ [ω]^{ω} let Q(Y) be the partial order which consists of the disjoint union of {C_{m} : m ∈ Y } and in addition has a unique minimal element c.

Now we describe P_{X} for any X ∈ [ω]^{ω}. Let {X_{n} : n ∈ ω} be all Y ∈ [ω]^{ω} such that Y =^{∗} X. P_{X} is the disjoint union of {Q(X_{n}) : n ∈ ω}.

It easy to show that if Y ⊆ Z then Q(Y) can be embedded into Q(Z) and hence if X ⊆^{∗} 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} ⊆ Y_{n} and so X ⊆^{∗} Y. This proves the theorem. □

B. Veličković (CalTech) asked whether it is possible to get a decreasing chain of countable posets of length 2^{ℵ_{0}}. Assuming MA the answer to Veličković’s question is yes, since such chains exist in [ω]^{ω}/finite. However in the Cohen real model (adding say κ ≥ ω_{2} Cohen reals to a model of GCH) the continuum is large, but ω_{2} does not embed into [ω]^{ω}/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 ω_{2} is in the σ−algebra generated by rectangles {A × B : A, B ⊆ ω_{2}}.)

His argument can be generalized to show:

Theorem 3 It consistent relative to the consistency of ZFC that the continuum is arbitrarily large but there does not exist countable structures ⟨A_{α} : α < ω_{2}⟩ such that for all α, β < ω_{2}

α < β ⟺ A_{α} embeds into A_{β}

Proof: Let M be a countable transitive model of ZFC+GCH and let P be F IN(κ) the partial order of finite partial functions from κ into 2 where κ is any cardinal of M ≥ ω_{2}^{M}. Suppose for contradiction that in M[G] where G is P-generic over M there is such an ω_{2} sequence.

Working in M, let ⟨A_{α} : α < ω_{2}⟩ be a sequence of names for countable structures with ω as thier universe and p ∈ P be such that

p |⊢ ∀α, β [α < β ⟺ A_{α} embedds into A_{β}]

Since P has c.c.c. we can assume that the names have countable support, i.e. we can find Γ_{α} countable subsets of κ such that A_{α}^{G} ∈ M[G|_{Γ_{α}}].

By the delta systems lemma we can find X ∈ [ω_{2}]^{ω_{2}} and root R such that for α, β ∈ X and distinct

Γ_{α} ∩ Γ_{β} = R

We can assume that the order type of every Γ_{α} for α ∈ X is the same (say α_{0}) and furthermore that the unique order preserving map between any two is the identity on R. (Since M satisfies CH.)

Let π_{α} be the partial order isomorphism from F IN(Γ_{α}) to F IN(α_{0}) induced by the unique order preserving map from Γ_{α} to α_{0}.

Let π_{α}(A_{α}) = τ_{α}. Since M satisfies CH we can assume that all τ_{α} are the same. It follows then that if π is the automorphism of F IN(κ) induced by interchanging Γ_{α} \ R and Γ_{β} \ R order preservingly and the identity outside of these, then π(A_{α}) = A_{β} and π(A_{β}) = A_{α}

If we take α, β ∈ X such that α < β and Γ_{α} \ R and Γ_{β} \ R are both disjoint from the domain of p (so π(p) = p) then since

p |⊢ A_{α} embedds into A_{β}

so

π(p) |⊢ π(A_{α}) embedds into π(A_{β})

hence

p |⊢ A_{β} embedds into A_{α}

contradicting α < β. □

sincerely,

Arnold W. Miller