On the number of non-isomorphic subgraphs

S. Shelah ^{∗}

Institute of Mathematics Hebrew University, Jerusalem

L. Soukup ^{†}

Mathematical Institute of the Hungarian Academy of Sciences

March 27, 1996

Abstract

Let K be the family of graphs on ω_{1} without cliques or independent subsets of size ω_{1}. We prove that

(a) it is consistent with CH that every G ∈ K has 2^{ω_{1}} many pairwise non-isomorphic subgraphs,

(b) the following proposition holds in L: (∗) there is a G ∈ K such that for each partition (A, B) of ω_{1} either G ≅ G[A] or G ≅ G[B],

(c) the failure of (∗) is consistent with ZFC.

1 Introduction

We assume only basic knowledge of set theory — simple combinatorics for section 2, believing in L ⊧ ♢^{+} defined below for section 3, and finite support iterated forcing for section 4.

∗The first author was supported by the United States Israel Binational Science Foundation, Publication 370

†The second author was supported by the Hungarian National Foundation for Scientific Research grant no. l805

Answering a question of R. Jamison, H. A. Kierstead and P. J. Nyikos [5] proved that if an n-uniform hypergraph G = ⟨V, E⟩ is isomorphic to each of its induced subgraphs of cardinality |V |, then G must be either empty or complete. They raised several new problems. Some of them will be investigated in this paper. To present them we need to introduce some notions.

An infinite graph G = ⟨V, E⟩ is called non-trivial iff G contains no clique or independent subset of size |V |. Denote the class of all non-trivial graphs on ω_{1} by K. Let I(G) be the set of all isomorphism classes of induced subgraphs of G = ⟨V, E⟩ with size |V |.

H. A. Kierstead and P. J. Nyikos proved that |I(G)| ≥ ω for each G ∈ K and asked whether |I(G)| ≥ 2^{ω} or |I(G)| ≥ 2^{ω_{1}} hold or not. In [3] it was shown that (i) |I(G)| ≥ 2^{ω} for each G ∈ K, (ii) under ♢^{+} there exists a G ∈ K with |I(G)| = ω_{1}. In section 2 we show that if ZFC is consistent, then so is ZFC + CH + “|I(G)| = 2^{ω_{1}} for each G ∈ K”. Given any G ∈ K we will investigate its partition tree. Applying the weak ♢ principle of Devlin and Shelah [2] we show that if this partition tree is a special Aronszajn tree, then |I(G)| > ω_{1}. This result completes the investigation of problem 2 of [5] for ω_{1}.

Consider a graph G = ⟨V, E⟩ . We say that G is almost smooth if it is isomorphic to G[W] whenever W ⊂ V with |V \ W | < |V |. The graph G is called quasi smooth iff it is isomorphic either to G[W] or to G[V \ W] whenever W ⊂ V. H. A. Kierstead and P. J. Nyikos asked (problem 3) whether an almost smooth, non-trivial graph can exist. In [3] various models of ZFC was constructed which contain such graphs on ω_{1}. It was also shown that the existence of a non-trivial, quasi smooth graph on ω_{1} is consistent with ZFC. But in that model CH failed. In section 3 we prove that ♢^{+}, and so V=L, too, implies the existence of such a graph.

In section 4 we construct a model of ZFC in which there is no quasismooth G ∈ K. Our main idea is that given a G ∈ K we try to construct a partition (A_{0}, A_{1}) of ω_{1} which is so bad that not only G ≅ G̸[A_{i}] in the ground model but certain simple generic extensions can not add such isomorphisms to the ground model. We divide the class K into three subclasses and develop different methods to carry out our plan.

The question whether the existence of an almost-smooth G ∈ K can be proved in ZFC is still open.

We use the standard set-theoretical notation throughout, cf [4]. Given a graph G = ⟨V, E⟩ we write V (G) = V and E(G) = E. If H ⊂ V (G) we define G[H] to be ⟨H, E(G)∩[H]^{2}⟩. Given x ∈ V take G(x) = {y ∈ V : {x, y} ∈ E}.

If G and H are graphs we write G ≅ H to mean that G and H are isomorphic. If f : V (G) → V (H) is a function we denote by f : G ≅ H the fact that f is an isomorphism between G and H.

Given a set X let Bij_{p}(X) be the set of all bijections between subsets of X. If G = ⟨V, E⟩ is a graph take

Iso_{p}(G) = {f ∈ Bij_{p}(V) : f : G[dom(f)] ≅ G[ran(f)]} .

We denote by Fin(X, Y) the set of all functions mapping a finite subset of X to Y.

Given a poset P and p, q ∈ P we write p∥_{P} q to mean that p and q are compatible in P.

The axiom ♢^{+} claims that there is a sequence ⟨S_{α} : α < ω_{1}⟩ of countable sets such that for each X ⊂ ω_{1} we have a closed unbounded C ⊂ ω_{1} satisfying X ∩ ν ∈ S_{ν} and C ∩ ν ∈ S_{ν} for each ν ∈ C.

We denote by TC(x) the transitive closure of a set x. If κ is a cardinal take H_{κ} = {x : |TC(x)| < κ} and H_{κ} = ⟨H_{κ}, ∈⟩.

Let us denote by D_{ω_{1}} the club filter on ω_{1}.

2 I(G) can be always large

Theorem 2.1 Assume that GCH holds and every Aronszajn-tree is special. Then |I(G)| = 2^{ω_{1}} for each G ∈ K.

Remark: S.Shelah proved, [7, chapter V. §6,7], that the assumption of theorem 2.1 is consistent with ZFC.

During the proof we will apply the following definitions and lemmas.

Lemma 2.2 Assume that G ∈ K, A ∈ [ω_{1}]^{ω_{1}} and |{G(x) ∩ A : x ∈ ω_{1}| = ω_{1}. Then |I(G)| = 2^{ω_{1}}.

Proof: See [3, theorem 2.1 and lemma 2.13].

Definition 2.3 Consider a graph G = ⟨ω_{1}, E⟩.

1. For each ν ∈ ω_{1} let us define the ordinal γ_{ν} ∈ ω_{1} and the sequence ⟨ξ_{γ}^{ν} : γ ≤ γ_{ν}⟩ as follows: put ξ_{0}^{ν} = 0 and if ⟨ξ_{α}^{ν} : α < γ⟩ is defined, then take

ξ_{γ}^{ν} = min {ξ : ∀α < γ ξ > ξ_{α}^{ν} and ({ξ_{α}^{ν}, ξ} ∈ E iff {ξ_{α}^{ν}, ν} ∈ E)} .

If ξ_{γ}^{ν} = ν, then we put γ_{ν} = γ.

2. Given ν, μ ∈ ω_{1} write ν ≺^{G} μ iff ξ_{γ}^{ν} = ξ_{γ}^{μ} for each γ ≤ γ_{ν}.

3. Take T^{G} = ⟨ω_{1}, ≺^{G}⟩. T_{G} is called the partition tree of G.

Lemma 2.4 If G = ⟨ω_{1}, E⟩ ∈ K with |I(G)| < 2^{ω_{1}}, then T^{G} is an Aronszajn tree.

Proof: By the construction of T^{G}, if ν, μ ∈ ω_{1}, ν < μ and G(ν) ∩ ν = G(μ) ∩ ν, then ν ≺^{G} μ. So the levels of T^{G} are countable by lemma 2.2. On the other hand, T^{G} does not contain ω_{1}-branches, because the branches are prehomogeneous subsets and G is non-trivial.

Definition 2.5 1. Let F : (2^{ω})^{<ω_{1}} → 2 and A ⊂ ω_{1}. We say that a function g : ω_{1} → 2 is an A-diamond for F iff, for any h ∈ (2^{ω})^{ω_{1}}, {α ∈ A : F (h⌈α) = g(α)} is a stationary subset of ω_{1}.

2. A ⊂ ω_{1} is called a small subset of ω_{1} iff for some F : (2^{ω})^{<ω_{1}} → 2 no function is an A-diamond for F.

3. J = {A ⊂ ω_{1} : A is a small subset of ω_{1}}.

In [2] the following was proved:

Theorem 2.6 If 2^{ω} < 2^{ω_{1}}, then J is a countably complete, proper, normal ideal on ω_{1}.

After this preparation we are ready to prove theorem 2.1. Proof: Assume that G = ⟨ω_{1}, E⟩ ∈ K.

|I(G)| < 2^{ω_{1}} and a contradiction will be derived.

Since 2^{ω_{1}} = ω_{2}, we can fix a sequence {G_{ν} : ν < ω_{1}} of graphs on ω_{1} such that for each Y ∈ [ω_{1}]^{ω_{1}} there is a ν < ω_{1} with G[Y] ≅ G_{ν}. Write G_{ν} = ⟨ω_{1}, E_{ν}⟩.

Consider the Aronszajn-tree T^{G} = ⟨ω_{1}, ≺^{G}⟩. Since every Aronszajn-tree is special and I is a countably complete ideal on ω_{1}, there is an antichain S in T^{G} with S ∉ J. Take

A = {α ∈ ω_{1} : ∃σ ∈ S(α ≺^{G} σ)} .

Now property (∗) below holds:

(∗) ∀σ ∈ S ∀ρ ∈ (S ∪ A) \ σ + 1 ∃α ∈ A ∩ σ ({σ, α} ∈ E iff {ρ, α} ∉ E).

Indeed, if for each α ∈ A ∩ σ we had {σ, α} ∈ E iff {ρ, α} ∈ E, then σ ≺^{G} ρ would hold by the construction of T^{G}.

Let ν ∈ ω_{1}, σ ∈ S, T ⊂ S ∩ σ and f : G[(A ∩ σ) ∪ T] → G_{ν} be an embedding. Define F (ν, σ, T, f) ∈ 2 as follows:

F (ν, σ, T, f) = 1 iff ∃x ∈ G_{ν}(∀α ∈ A ∩ σ)({x, f(α)} ∈ E_{ν} iff {σ, α} ∈ E).

In case ωσ = σ, under suitable encoding, F can be viewed as a function from (2^{ω})^{<ω_{1}} to 2.

Since S ∉ J, there is a g ∈ 2^{ω_{1}} such that for every ν ∈ ω_{1} = 2^{ω}, T ⊂ S and f : G[A ∪ T] ≅ G_{ν}, the set

S_{T} = {σ ∈ S : g(σ) = F (ν, σ, T ∩ σ, f⌈σ)}

is stationary. Take T = {σ ∈ S : g(σ) = 0}. Choose an ordinal ν < ω_{1} and a function f with f : G[A ∪ T] ≅ G_{ν}. For each σ < ω_{1} with σ = ωσ it follows, by (∗), that

σ ∈ T iff ∃x ∈ ω_{1} ∀α ∈ S ∩ σ ({x, f(α)} ∈ E_{ν} iff {σ, α} ∈ E).

Thus g(σ) = 0 iff F (ν, σ, T ∩ σ, f⌈σ) = 1, for each σ ∈ S, that is, S_{T} = ∅, which is a contradiction.

3 A quasi-smooth graph under ♢^{+}

Theorem 3.1 If ♢^{+} holds, then there exists a non-trivial, quasi-smooth graph on ω_{1}.

Proof: Given a set X, A⊂P(X) and F⊂Bij_{p}(X) take

Cl(A, F) = ⋂ {B : B ⊃ A and ∀B_{0}, B_{1} ∈ B ∀f ∈ F ∀Y ∈ [X]^{<ω} {B_{0} ∪ B_{1}, f′′B_{0}, B_{0}△Y } ⊂B} .

We say that A is F-closed if A = Cl(A, F). Given A, D⊂P (X), we say that D is uncovered by A if |D\A| = ω for each A ∈ A and D ∈ D.

Lemma 3.2 Assume that F⊂Bij_{p}(X) is a countable set, A^{0}, A^{1}⊂P(X) are countable, F-closed families. If D⊂P (X) is a countable family which is uncovered by A^{0} ∪ A^{1}, then there is a partition (B_{0}, B_{1}) of X such that D is uncovered by Cl(A^{i} ∪ {B_{i}} , F) for i < 2.

Proof: We can assume that F is closed under composition. Fix an enumeration {⟨D_{n}, k_{n}, F_{n}, i_{n}, A_{n}⟩ : n ∈ ω} of D × ω × F^{<ω} × {⟨i, A⟩ : i ∈ 2, A ∈ A^{i}}. By induction on n, we will pick points x_{n} ∈ X and will define finite sets, B_{n}^{0} and B_{n}^{1}, such that B_{n}^{0} ∩ B_{n}^{1} = ∅ and B_{n}^{i}⊂B_{n+1}^{i}.

Assume that we have done it for n − 1. Write F_{n} = ⟨f_{0}, …, f_{k−1}⟩. Take B_{n−1} = B_{n−1}^{0} ∪ B_{n−1}^{1} and

B_{n}^{−} = B_{n−1} ∪ ⋃ {f′′_{j}B_{n−1} : j < k} .

Pick an arbitrary point x_{n} ∈ D_{n}\(A_{n} ∪ B_{n}^{−}). Put

B_{n}^{i_{n}} = B_{n−1}^{i_{n}}

and

B_{n}^{1−i_{n}} = B_{n−1}^{1−i_{n}} ∪ {x_{n}} ∪ {f_{j}^{−1}(x_{n}) : j < k} .

Next choose a partition (B^{0}, B^{1}) of X with B^{i} ⊃ ∪{B_{n}^{i} : n < ω} for i < 2. We claim that it works. Indeed, a typical element of Cl(A^{i} ∪ {B^{i}}, F) has the form

C = A ∪ ⋃ {f′′_{j}B^{i} : j < k} ,

where A ∈ A, k < ω and f_{0}, …, f_{k−1} ∈ F. So, if D ∈ D, then

D\C ⊃ {x_{n} : D_{n} = D, A_{n} = A, i_{n} = i and F_{n} = ⟨f_{0}, …, f_{k−1}⟩}

because x_{n} ∉ A and f_{j}^{−1}(x_{n}) ∈ B^{1−i} by the construction.

Consider a sequence F = ⟨f_{0}, …, f_{n−1}⟩. Given a family F⊂Bij_{p}(X) we say that F is an F-term provided f_{i} = f or f_{i} = f^{−1} for some f ∈ F, for each i < n. We denote the function f_{0} ∘ ⋯ ∘ f_{n−1} by F as well. We will assume that the empty term denotes the identity function on X. If l ≤ n take (l)F = ⟨f_{0}, …, f_{l−1}⟩ and F_{(l)} = ⟨f_{l}, …, f_{n−1}⟩. Let

Sub(F) = {⟨f_{i_{0}}, …, f_{i_{l−1}}⟩ : l ≤ n, i_{0} < … < i_{l−1} < n} .

Given f ∈ F and x, y ∈ X with x ∉ dom(f) and y ∉ ran(f) let F^{f,x,y} be the term that we obtain replacing each occurrence of f and of f^{−1} in F with f ∪ {⟨x, y⟩} and with f^{−1} ∪ {⟨y, x⟩}, respectively.

Lemma 3.3 Assume that F⊂Bij_{p}(X), A⊂P (X) is F-closed, F_{0}, …, F_{n−1} are F-terms, z_{0}, …, z_{n−1} ∈ X, A_{0}, …, A_{n−1} ∈ A such that for each i < n

(∗) z_{i} ∉ ⋃ {F′′A_{i} : F ∈ Sub(F_{i})} .

If f ∈ F, x ∈ X\dom(f), Y ∈ [X\ran(f)]^{ω} with |A ∩ Y | < ω for each A ∈ A, then there are infinitely many y ∈ Y such that (∗) remains true when replacing f with f ∪ {⟨x, y⟩}, that is,

(∗∗) z_{i} ∉ ⋃ {F′′A_{i} : F ∈ Sub(F_{i}^{f,x,y})}

for each i < n.

Proof: It is enough to prove it for n = 1. Write F = ⟨f_{0} …, f_{k−1}⟩, A = A_{0}, z = z_{0}. Take

Y_{F,A} = {y ∈ Y : (∗∗) holds for y} .

Now we prove the lemma by induction on k.

If k = 0, then Y_{F,A} = Y \A. Suppose we know the lemma for k − 1. Using the induction hypothesis we can assume that (†) below holds:

(†) Y = ⋂ {Y_{G,F′′_{(l)}A} : l ≤ n, G ∈ Sub(_{(l)}F^{f,x,y}), G ≠ F^{f,x,y}} .

Assume that |Y_{F,A}| < ω and a contradiction will be derived.

First let us remark that either f_{k−1} = f or f_{k−1} = f^{−1} by (†). Case 1:f_{k−1} = f^{−1}.

Then Y_{F,A}⊃Y \A by (†), so we are done. Case 2:f_{k−1} = f.

In this case x ∈ A and for all but finitely many y ∈ Y we have z = F^{f,x,y}(x). Then for each y, y′ ∈ Y take

l(y, y′) = max {l ≤ n : ∀i < l F_{(i)}^{f,x,y}(x) = F_{(i)}^{f,x,y′}(x)} .

By Ramsey’s theorem, we can assume that l(y, y′) = l whenever y, y′ ∈ Y. Clearly l < n. Then F_{(l)}^{f,x,y}(x) ≠ F_{(l)}^{f,x,y′}(x) but F_{(l−1)}^{f,x,y}(x) = F_{(l−1)}^{f,x,y′}(x), so f_{l} = f^{−1} and F_{(l−1)}^{f,x,y}(x) = x for each y ∈ Y. Thus z = _{(l−1)}F^{f,x,y}(x) for each y ∈ Y, which contradicts (†) because x ∈ A.

The lemma is proved.

We are ready to construct our desired graph.

First fix a sequence ⟨M_{α} : α < ω_{1}⟩ of countable, elementary submodels of some H_{λ} with ⟨M_{γ} : γ < α⟩ ∈ M_{α} for each α < ω_{1}, where λ is a large enough regular cardinal.

Then choose a ♢-sequence ⟨S_{α} : α < ω_{1}⟩ ∈ M_{0} for the uncountable subsets of ω_{1}, that is , {α < ω_{1} : X ∩ α = S_{α}} ∉ NS(ω_{1}) whenever X ∈ [ω_{1}]^{ω_{1}}. We can also assume that S_{α} is cofinal in α for each limit α.

We will define, by induction on α,

1. graphs G_{α} = ⟨ωα, E_{α}⟩ with G_{β} = G_{α}[ωβ] for β < α,

2. countable sets F_{α} ∈ Iso_{p}(G_{α}),

satisfying the induction hypotheses (I)–(II) below:

(I) {S_{ωγ} : γ ≤ α} is uncovered by I_{α} ∪ J_{α} where

I_{α} = Cl({G(ν) ∩ ν : ν ∈ ωα} , ⋃_{β≤α} F_{β})

and

J_{α} = Cl({ν\G(ν) : ν ∈ ωα} , ⋃_{β≤α} F_{β}).

To formulate (II) we need the following definition.

Definition 3.4 Assume that α = β + 1 and Y ⊂ωα. We say that Y is large if ∀n ∈ ω, ∀ ⟨⟨f_{i}, x_{i}⟩ : i < n⟩, ∀h if

1. ∀i < n ∃α_{i} < β f_{i} ∈ F_{α_{i}},

2. ∀i < n ωα_{i} ≤ x_{i} < ωβ,

3. ∀i < n ran(f_{i})⊂Y,

4. ∀i ≠ j < n ran(f_{i}) ∩ ran(f_{j}) = ∅

5. h ∈ Fin(Y ∩ ωβ, 2) and dom(h) ∩ ⋃ {ran(f_{i}) : i < n} = ∅,

then ∃y ∈ Y ∩ [ωβ, ωα) such that 6. ∀i < n ∀x ∈ dom(f_{i}) ({y, f_{i}(x)} ∈ E_{α} iff {x_{i}, x} ∈ E_{α}),

7. ∀z ∈ dom(h) {y, z} ∈ E_{α} iff h(z) = 1.

Take

(II) If α = β + 1, then ωα is large.

The construction will be carried out in such a way that ⟨G_{β} : β ≤ α⟩ ∈ M_{α} and ⟨F_{β} : β < α⟩ ∈ M_{α}.

To start with take G_{0} = ⟨∅, ∅⟩ and F = {∅}. Assume that the construction is done for β < α. Case 1:α is limit.

We must take G_{α} = ∪ {G_{β} : β < α}. We will define sets F_{α}^{0}, F_{α}^{1}⊂Iso_{p}(G_{α}) and will take F_{α} = F_{α}^{0} ∪ F_{α}^{1}.

Let

F_{α}^{0} = {f ∈ Iso_{p}(G_{α}) ∩ M_{α} : ∃ ⟨α_{n} : n < ω⟩ ⊂α sup {α_{n} : n < ω} = α,

f⌈ωα_{n} ∈ F_{α_{n}} and f⌈ωα_{n} : G_{α_{n}} ≅ G_{α_{n}}[ran(f)] for each n ∈ ω} .

Take F^{−} = ⋃_{β<α} F^{β} ∪ F_{α}^{0}, I_{α}^{−} = ⋃_{β<α} I_{β} and J_{α}^{−} = ⋃_{β<α} J_{β}. Clearly F^{−}⊂M_{α}

with F^{−} ∈ M_{α+1}, so M_{α+1} ⊧ “|F^{−}| = ω”. Obviously both I_{α}^{−} and J_{α}^{−} are F^{−}-closed and S = {S_{ωβ} : β ≤ α} is uncovered by them.

From now on we work in M_{α+1} to construct F_{α}^{1}. For W ⊂ωα write L_{W} = {ν < α : W ∩ (ων + ω) is large}.

Take

W_{α} = {⟨W, f⟩ ∈ (P (ωα) ∩ M_{α}) × (∪_{β<α}F_{β}) : L_{W} is cofinal in α

and f : G_{γ_{f}} ≅ G_{γ_{f}} [W ∩ ωγ_{f}] for some γ_{f} < α} .

We want to find functions g^{W,f} ⊃ f for ⟨W, f⟩ ∈ W_{α} such that

(A) g^{W,f} : G_{α} ≅ G_{α}[W]

(B) taking F_{α}^{1} = {g^{W,f} : ⟨W, f⟩ ∈ W_{α}} the induction hypothesis (I) remains true.

First we prove a lemma:

Lemma 3.5 If ⟨W, f⟩ ∈ W_{α}, g ∈ Iso_{p}(G_{α}, G_{α}[W]), g ⊃ f, |g\f| < ω, then

(i) for each x ∈ W \dom(f) the set

{y ∈ W : g ∪ {⟨x, y⟩} ∈ Iso_{p}(G_{α}, G_{α}[W])}

is cofinal in ωα.

(ii) for each y ∈ W \ran(f) the set

{x ∈ W : g ∪ {⟨x, y⟩} ∈ Iso_{p}(G_{α}, G_{α}[W])}

is cofinal in ωα.

Proof: (i): Define the function h : ran(g)\ran(f) → 2 with h(g(z)) = 1 iff {z, x} ∈ E_{α}. Choose β ∈ L_{W} with ran(h)⊂ωβ and γ_{f} ≤ β. Since W ∩(ωβ+ω) is large, we have a y ∈ W ∩ [ωβ, ωβ + ω) such that

1. {y, f(z)} ∈ E_{α} iff {x, z} ∈ E_{α} for each z ∈ dom(f)

2. {y, g(z)} ∈ E_{α} iff h(g(z)) = i for each z ∈ dom(g)\dom(f).

But this means that g ∪ {⟨x, y⟩} ∈ Iso_{p}(G_{α}, G_{α}[W]). (ii) The same proof works using that ωβ + ω is large for each β < α.

By induction on n, we will pick points z_{n} ∈ ωα and will construct families of partial automorphisms, {g_{n}^{W,f} : ⟨W, f⟩ ∈ W_{α}} such that g^{W,f} =

∪ {g_{n}^{W,f} : n < ω} will work.

During the inductive construction we will speak about F_{α}-terms and about functions which are represented by them in the n^{th} step.

If F = ⟨h_{0}, … h_{k−1}⟩ is an F_{α}-term and n ∈ ω take F_{[n]} = j_{0} ∘ ⋯ ∘ j_{k−1} where

j_{i} = \{ \begin{matrix}g_{n}^{W,f} & if h_{i} = g^{W,f}, \\ (g_{n}^{W,f})^{−1} & if h_{i} = (g^{W,f})^{−1}, \\ h_{i} & otherwise. \end{matrix}

First fix an enumeration {⟨⟨W_{n}, f_{n}⟩ , u_{n}, i_{n}⟩ : 1 ≤ n < ω} of W_{α} × ωα × 2 and an enumeration ⟨⟨⟨F_{n,i} : i < l_{n}⟩ , j_{n}, ⟨A_{n,i} : i < l_{n}⟩ , D_{n}⟩ n < ω⟩ of the quadruples ⟨⟨F_{0}, …, F_{k−1}⟩ , j, ⟨A_{0}, …, A_{k−1}⟩ , D⟩ where k < ω, F_{0}, …, F_{k−1} are F_{α}- terms, j ∈ 2, D ∈ S and either j = 0 and A_{0}, …, A_{k−1} ∈ I_{α}^{−} or j = 1 and A_{0}, …, A_{k−1} ∈ J_{α}^{−}.

During the inductive construction conditions (i)–(v) below will be satisfied:

(i) g_{0}^{W,f} = f

(ii) g_{n}^{W,f} ∈ Iso_{p}(G_{α}, G_{α}[W])

(iii) g_{n}^{W,f} ⊃ g_{n−1}^{W,f}, |g_{n}^{W,f}\f| < ω

(iv) z_{k} ∉ ⋃ {F′′_{[n]}A_{k,i} : F ∈ Sub(F_{k,i})} for each i < l_{k} and k < n

(v) if i_{n} = 1, then u_{n} ∈ dom(g_{n}^{W_{n},f_{n}}), if i_{n} = 0, then either u_{n} ∉ W_{n} or u_{n} ∈ ran(g_{n}^{W_{n},f_{n}}).

If n = 0, then take g_{0}^{W,f} = f.

If n > 0, then let g_{n}^{W,f} = g_{n−1}^{W,f} whenever ⟨W, f⟩ ≠ ⟨W_{n}, f_{n}⟩. Assume that i_{n} = 0, ⟨W, f⟩ = ⟨W_{n}, f_{n}⟩ and u_{n} ∉ dom(g_{n−1}^{W_{n},f_{n}}). Then, by lemma 3.5, the set Y = {y ∈ W : g_{n−1}^{W,f} ∪ {⟨u_{n}, y⟩} ∈ Iso_{p}(G_{α}, G_{α}[W])} is unbounded in ωα. Since the members of I_{α}^{−} ∪ J_{α}^{−} are bounded in ωα, we can apply lemma 3.3 to pick a point y ∈ Y such that taking g_{n}^{W_{n},f_{n}} = g_{n−1}^{W_{n},f_{n}} ∪ {⟨u_{n}, y⟩} condition (iv) holds.

If i_{n} = 1 and ⟨W, f⟩ = ⟨W_{n}, f_{n}⟩, then the same argument works.

Finally pick a point

z_{n} ∉ D_{n}\ ⋃ {F′′_{[n]}A_{n,i} : F ∈ Sub(F_{n,i}), i < l_{n}} .

The inductive construction is done.

Take g^{W,f} = ∪ {g_{n}^{W,f} : n < ω}. By (v),

g_{n}^{W,f} : G_{ωα} ≅ G_{ωα}[W].

By (iv), we have

z_{k} ∈ D_{k}\ ⋃ {F′′_{k,i}A_{k,i} : i < l_{k}}

and so it follows that {S_{ωβ} : β ≤ α} is uncovered by I_{α} ∪ J_{α}. Case 2:α = β + 1.

To start with we fix an enumeration {⟨⟨⟨f_{i}^{k}, x_{i}^{k}⟩ : i < n_{k}⟩, h_{k}⟩ : k ∈ ω} of pairs ⟨⟨⟨f_{i}, x_{i}⟩ : i < n⟩ , h⟩ satisfying 3.4.1–5.

If k ∈ ω take

B_{k}^{0} = h_{k}^{−1} {0} ∪ {f_{i}^{k}(ν) : i < n_{k}, ν ∈ dom(f_{i}^{k}) and {ν, x_{i}^{k}} ∉ E_{β}} and

B_{k}^{1} = h_{k}^{−1} {1} ∪ {f_{i}^{k}(ν) : i < n_{k}, ν ∈ dom(f_{i}^{k}) and {ν, x_{i}^{k}} ∈ E_{β}} .

Applying lemma 3.2 ω-many times we can find partitions (C_{k}^{0}, C_{1}^{k}), k < ω, of ωβ such that taking

I_{β}^{+} = Cl((I_{β} ∪ {C_{k}^{1} : k ∈ ω} , ⋃_{γ≤β} F_{γ})

and

J_{β}^{+} = Cl((I_{β} ∪ {C_{k}^{0} : k ∈ ω} , ⋃_{γ≤β} F_{γ})

the set {S_{ωγ} : γ ≤ β} is uncovered by I_{β}^{+} ∪ J_{β}^{+}.

We can assume that B_{k}^{i}⊂C_{k}^{i} for i < 2 and k < ω because B_{k}^{0} ∈ J_{β} and B_{k}^{1} ∈ I_{β}. Take

E_{α} = E_{β} ∪ {{ν, ωβ + n} : ν < ωβ, n ∈ ω and ν ∈ B_{n}^{1}}

and

F_{α} = ∅.

By the construction of G_{α} = ⟨ωα, E_{α}⟩, it follows that ωα is large, so (II) holds. On the other hand

I_{α} = {X ∪ Y : X ∈ I_{β}^{+}, Y ∈ [ωα]^{<ω}}

and

J_{α} = {X ∪ Y : X ∈ J_{β}^{+}, Y ∈ [ωα]^{<ω}} .

so {S_{ωγ} : γ < α} is uncovered by I_{α} ∪ J_{α}. Finally S_{ωα} is cofinal in ωα but the elements of I_{α} ∪ J_{α} are all bounded, so the induction hypothesis (I) also holds.

The construction is done. Take E = ∪ {E_{α} : α < ω_{1}} and G = ⟨ω_{1}, E⟩. By (I), G is non-trivial. Finally, we must prove that G is quasi smooth. Consider a set Y ⊂ω_{1}. The following lemma is almost trivial.

Lemma 3.6 For each α < ω_{1} either Y ∩ (ωα + ω) or (ωα + ω)\Y is large.

Proof: Assume on the contrary that there are pairs ⟨⟨⟨f_{i}, x_{i}⟩ : i < n⟩ , h⟩ and ⟨⟨⟨f_{i}, x_{i}⟩ : n ≤ i < n + k⟩ , h′⟩ showing that neither Y ∩ (ωα + ω) nor (ωα + ω)\Y is large. Then ⟨⟨⟨f_{i}, x_{i}⟩ : i < n + k⟩ , h ∪ h′⟩ shows that ωα + ω is not large.

So we can assume that the set

L = {α < ω_{1} : Y ∩ (ωα + ω) is large}

is uncountable and to complete the proof of theorem 3.1 it is enough to show that in this case G ≅ G[Y]. By ♢^{+}, we can find a club subset C⊂L′ such that Y ∩ ωγ ∈ M_{γ}, C ∩ ωγ ∈ M_{γ} and ωγ = γ whenever γ ∈ C. We can assume that 0 ∈ C.

Write C = {γ_{ν} : ν < ω_{1}}. By induction on ν < ω_{1}, we will construct functions f_{ν} such that

(a) f_{ν} : G_{γ_{ν}} ≅ G_{γ_{ν}}[Y], f_{ν} ∈ F_{γ_{ν}},

(b) ⟨f_{μ} : μ < ν⟩ ∈ M_{sup{γ_{μ}+1:μ<ν}}.

Take f_{0} = ∅. If ν = μ + 1, then let f_{ν} = g^{Y ∩ωγ_{ν},f_{μ}}. If ν is limit, then put f_{ν} = ∪ {f_{μ} : μ < ν}. Clearly (a) and (b) remains valid. Finally put f = ∪ {f_{ν} : ν < ω_{1}}. Then f : G ≅ G[Y], so the theorem is proved.

4 A model without quasi-smooth graphs

Given an Aronszajn-tree T = ⟨ω_{1}, ≺⟩ define the poset Q_{T} as follows: the underlying set of Q_{T} consists of all functions f mapping a finite subset of ω_{1} to ω such that f^{−1}{n} is antichain in T for each n ∈ ω. The ordering on Q_{T} is as expected: f ≤_{Q_{T}} g iff f ⊃ g. For γ < ω_{1} denote by T_{γ} the set of elements of T with height γ. Take T_{<δ} = ⋃_{γ<δ} T_{γ}. If x ∈ T_{δ} and γ < δ, let

x⌈γ be the unique element of T_{γ} which is comparable with x. We write C for the poset ⟨Fin(ω_{1}, 2), ⊃⟩, that is, forcing with C adds ω_{1}-many Cohen reals to the ground model.

Theorem 4.1 If ZF is consistent, then so is ZFC + “there are no non-trivial quasi-smooth graphs on ω_{1}”.

Proof: Assume that GCH holds in the ground model. Consider a finite support iteration ⟨P_{i}, Q_{j} : i ≤ ω_{2}, j < ω_{2}⟩ satisfying (a)–(c) below:

(a) If j < ω_{2} is even, then Q_{j} = C.

(b) If j < ω_{2} is odd, then V^{P_{j}} ⊧ “Q_{j} = Q_{T_{j}} for some Aronszajn-tree T_{j}”.

(c) V^{P_{ω_{2}}} ⊧“every Aronszajn tree is special”.

We will show that V^{P_{ω_{2}}} does not contain non-trivial, quasi-smooth graphs on ω_{1}.

To start with we introduce some notation. Consider a graph G = ⟨V, E⟩. For x ∈ V define the function tp_{G}(x) : V \ {x} → 2 by the equation G(x) = tp_{G}(x)^{−1}{1}. Given A ⊂ V write tp_{G}(x, A) = tp_{G}(x)⌈A.

If A ⊂ V and t ∈ 2^{A}, take rl_{G}(t) = {x ∈ V \ A : tp_{G}(x, A) = t} and rl_{G}^{∗}(t) = {x ∈ V \ A : |tp_{G}(x, A)△t| < ω}. For x ∈ V and A ⊂ V put twin_{G}(x, A) = rl_{G}(tp_{G}(x, A)).

For A ⊂ V define the equivalence relation ≡_{G,A} on V \ A as follows:

x ≡_{G,A} y iff |tp_{G}(x, A)△tp_{G}(y, A))| < ω.

For x ∈ V \ A denote by [x]_{G,A} the equivalence class of x in ≡_{G,A}. Clearly [x]_{G,A} = rl_{G}^{∗}(tp_{G}(x, A)). Write G/ ≡_{G,A} for the family of equivalence classes of ≡_{G,A}.

We divide K into three subclasses, K_{0}, K_{1} and K_{2}, and investigate them separately to show that V^{P_{ω_{2}}} ⊧ “(∀G ∈ K_{i}) G is not quasi-smooth” for i < 3. Take

K_{0} = {G ∈ K : ∃A ∈ [ω_{1}]^{ω} |G/ ≡_{G,A} | = ω_{1}},
K_{1} = {G ∈ K : ∀A ∈ [ω_{1}]^{ω} ∃x |ω_{1} \ [x]_{G,A}| < ω_{1}}

and

K_{2} = K \ (K_{0} ∪ K_{1}).

4.1 G ∈ K_{0}

First we recall a definition of [1].

Definition 4.2 A poset P is stable if

∀B ∈ [P]^{ω} ∃B^{∗} ∈ [P]^{ω} ∀p ∈ P ∃p′ ≤ p ∃p^{∗} ∈ B^{∗} ∀b ∈ B (p′∥_{P} b iff p^{∗}∥_{P} b).

We will say that p′ and p^{∗} are twins for B and that B^{∗} shows the stability of P for B.

Lemma 4.3 P_{ω_{2}} is stable.

Proof: First let us remark that it is enough to prove that both C and Q_{T} are stable for any Aronszajn-tree for in [1] it was proved that any finite support iteration of stable, c.c.c. posets is stable.

It is clear that C is stable. Assume that T is an Aronszajn tree and B ⊂ [Q_{T}]^{ω}. Fix a countable ordinal δ with {dom(p) : p ∈ B} ⊂ T_{<δ} and take B^{∗} = {p ∈ Q_{T} : dom(p) ⊂ T_{<δ+ω}}. It is not hard to see that B^{∗} shows the stability of P for B.

For G ∈ K take G ∈ K_{0}^{∗} iff there is an A ∈ [ω_{1}]^{ω} such that the set {x : |[x]_{G,A}| ≤ ω} is uncountable.

Given G ∈ K_{0} we will write G ∈ K′_{0} iff there are disjoint sets A_{0}, A_{1} ∈ [ω_{1}]^{ω} such that

(1) x ≡_{G,A_{0}} y iff x ≡_{G,A_{1}} y for each x, y ∈ ω_{1} \ A_{0} ∪ A_{1},

(2) the set {x : |[x]_{G,A_{0}}| ≤ ω} is uncountable.

Lemma 4.4 Assume CH. If G ∈ K′_{0}, then there is a partition (V_{0}, V_{1}) of ω_{1} so that for each stable c.c.c. poset P we have

V^{P} ⊧ “G is not isomorphic to G[V_{i}] for i ∈ 2”.

Proof: Pick A_{0}, A_{1} ∈ [ω_{1}]^{ω} witnessing G ∈ K′_{0}. Write A = A_{0} ∪ A_{1}. Take E = E(G).

Let κ be a large enough regular cardinal and fix an increasing sequence ⟨N_{ν} : ν < ω_{1}⟩ of countable, elementary submodels of H_{κ} such that

(i) G, A, A_{0}, A_{1} ∈ N_{0},

(ii) ⟨N_{ν} : ν < μ⟩ ∈ N_{μ} for μ < ω_{1}.

For x ∈ ω_{1} \ A take

rank(x) = min{ν : x ∈ N_{ν}}.

Fix a partition (S_{0}, S_{1}) of ω_{1} with |S_{0}| = |S_{1}| = ω_{1}. Take

V_{i} = A_{i} ∪ rank^{−1}S_{i}

for i ∈ 2.

We show that the partition (V_{0}, V_{1}) works.

Assume on the contrary that P is a stable c.c.c. poset, ḟ is a P -name of a function, p_{0} ∈ P and

p_{0}^{∥}—“ḟ : G ≅ G[V_{0}]”.

Without loss of generality we can assume that p_{0} = 1_{P}. Now for each c ∈ A_{0} choose a maximal antichain J_{c} ⊂ P and a function h_{c} : J_{c} → V such that q^{∥}—“ḟ^{−1}(ĉ) = ĥ_{c}(r)” for each q ∈ J_{c}.

Take B = ⋃{J_{c} : c ∈ A_{0}} and pick a countable B^{∗} ⊂ P showing the stability of P for B.

For b ∈ P define the partial function dt_{b} : ω_{1} → 2^{A_{0}} as follows. Let x ∈ ω_{1}. If there is a function t ∈ 2^{A_{0}} so that

(a) t(c) = 1 ⟺ for each q ∈ I_{c} if q and b are compatible conditions, then {x, h_{c}(q)} ∈ E,

(b) t(c) = 0 ⟺ for each q ∈ I_{c} if q and b are compatible conditions, then {x, h_{c}(q)} ∉ E,

then take dt_{b}(x) = t. Otherwise x ∉ dom dt_{b}.

Sublemma 4.4.1 If p^{∥}—“ḟ(x) = y”, then there are p′ ≤ p and b ∈ B^{∗} such that b and p′ are twins for B and dt_{b}(x) = tp_{G}(y, A_{0}).

Proof: By the choice of B^{∗}, we can find a p′ ≤ p and a b ∈ B^{∗} so that p′ and b are twins for B. Let c ∈ A_{0}. For each q ∈ J_{c}, if q and p′ are compatible in P, then {y, c} ∈ E iff {x, h_{c}(q)} ∈ E , because, taking r as a common extension of q and p′, we have r^{∥}—“ḟ(x̂) = ŷ and ḟ(ĥ_{q}(c)) = ĉ”. So {y, c} ∈ E iff for each q ∈ I_{c} if q and p′ are compatible, then {x, h_{c}(q)} ∈ E. But p′ and b are twins for ⋃{J_{c} : c ∈ A_{0}}, so dt_{b}(x) = dt_{p}(x) = tp_{G}(y, A_{0}).

Sublemma 4.4.2 There is a b ∈ B^{∗} such that

(∗)  |{t ∈ ran dt_{b} : |rl_{G}^{∗}(t)| ≤ ω}| = ω_{1}.

Proof: Let G be a P -generic filter over V. Put

F = {tp_{G}(y, A_{0}) : y ∈ V_{0} \ A_{0}, |[y]_{G,A_{0}}| ≤ ω}.

Then |F| = ω_{1}, so we can write F = {t_{ν} : ν < ω_{1}}. Fix sequences ⟨p_{ν} : ν < ω_{1}⟩ ⊂ G, ⟨x_{ν} : ν < ω_{1}⟩ ⊂ ω_{1} and ⟨y_{ν} : ν < ω_{1}⟩ ⊂ ω_{1} such that p_{ν}^{∥}—“ḟ(x_{ν}) = y_{ν}” and tp_{G}(y_{ν}, A_{0}) = t_{ν}. By sublemma 4.4.1,

⋃_{b∈B^{∗}} ran dt_{b} ⊇ F.

But B^{∗} is countable, so we can find a b ∈ B^{∗} satisfying (∗) above. Fix b ∈ B^{∗} with property (∗). Consider the structure

N = ⟨P ⌈(B ∪ B^{∗}), B, B^{∗}, ⟨J_{c}, h_{c} : c ∈ A_{0}⟩⟩ .

By CH, there is a ν < ω_{1} with N ∈ N_{ν}. Pick μ ∈ S_{1} \ ν. Since G, N, b ∈ N_{ν}, it follows that dt_{b} ∈ N_{ν} ⊂ N_{μ}. By (∗) and (ii), there is a

t ∈ ran dt_{b} ∩ (N_{μ} \ ⋃_{ξ<μ} N_{ξ})

with |rl_{G}^{∗}(t)| ≤ ω. Then

(†)  rl_{G}^{∗}(t) ⊂ N_{μ} \ ⋃_{ξ<μ} N_{ξ}.

Pick x ∈ ω_{1} with dt_{b}(x) = t. Find p ∈ G and y ∈ V_{0} such that p ≤ b and p^{∥}—“ḟ(x) = y”. By sublemma 4.4.1, there are p′ ≤ p and b′ ∈ B^{∗} such that p′ and b′ are twins for B and dt_{b′}(x) = tp_{G}(y, A_{0}). But p ≤ b, so dt_{b}(x) = dt_{b′}(x). Indeed, let c ∈ A_{0} and assume that dt_{b′}(x)(c) = 1. Pick q ∈ J_{q} which is compatible with b′. By the definition of dt_{b′}, it follows that {h_{c}(q), x} ∈ E. Since p′ and b′ are twins for B, so p′ and q also have a common extension q′ in P. But p′ ≤ p ≤ b, so q′ witnesses that b and q are compatible. Thus, by the definition of dt_{b}, we have dt_{b}(x)(c) = 1.

Thus tp_{G}(y, A_{0}) = dt_{b′}(x) = dt_{b}(x) = t. By (†), this implies that rank(y) = μ. But, by the construction of the partition (V_{0}, V_{1}), there are no y ∈ V_{0} with rank(y) = μ. Contradiction, the lemma is proved.

Lemma 4.5 Assume CH. If G ∈ K_{0}^{∗}, then V^{C} ⊧“ there is a partition (V_{0}, V_{1}) of ω_{1} so that

for each stable c.c.c. poset P we have:

V^{C∗P} ⊧ “G is not isomorphic to G[V_{i}] for i ∈ 2”. ”

Proof: . Fix a set A ∈ [ω_{1}]^{ω} witnessing G ∈ K_{0}^{∗} and a bijection f : A → ω in V. Let r : ω → 2 be the characteristic function of a Cohen real from V^{C}. Take A_{i} = (f ∘ r)^{−1}{i} for i < 2. Then (A_{0}, A_{1}) is a partition of A. Using a trivial density argument we can see that x ≢_{G,A} y implies x ≢_{G,A_{i}} y for i < 2 and for x, y ∈ ω_{1} \ A. Thus V^{C} ⊧ “A_{0} and A_{1} witness G ∈ K′_{0}”. Applying lemma 4.4 in V^{C} we get the desired partition of ω_{1}.

Lemma 4.6 In V^{P_{ω_{2}}}, if G ∈ K_{0} is quasi-smooth, then G ∈ K_{0}^{∗}.

Proof: Choose a set A ∈ [ω_{1}]^{ω} witnessing G ∈ K_{0} and a bijection f : A → ω. Pick α < ω_{2}, α is even, with A, f, G ∈ V^{P_{α}}. From now on we work in V^{P_{α}}. Let {[x_{ν}]_{G,A} : ν < ω_{1}} be an enumeration of the equivalence classes of ≡_{G,A}. Fix a partition (I_{0}, I_{1}) of ω_{1} into uncountable pieces. Let r : ω → 2 be the characteristic function of a Cohen real from V^{P_{α}∗C}. Take A_{i} = (f ∘ r)^{−1}{i} for i < 2. Then (A_{0}, A_{1}) is a partition of A. Using a trivial density argument we can see that x ≢_{G,A} y implies x ≢_{G,A_{i}} y for i < 2 and for x, y ∈ ω_{1} \ A. For i ∈ 2 put

B_{i} = A_{i} ∪ {x_{ν} : ν ∈ I_{i}} ∪ {[x_{ν}]_{G,A} \ {x_{ν}} : ν ∈ I_{1−i}}.

Clearly (B_{0}, B_{1}) is a partition of ω_{1} and

B_{i} ∩ [x_{ν}]_{G,A_{i}} = B_{i} ∩ [x_{ν}]_{G,A} = {x_{ν}}.

So G[B_{i}] ∈ K^{∗}. But G is quasi-smooth, so G ≅ G[B_{i}] for some i ∈ 2 in V^{P_{ω_{2}}}. Thus G ∈ K_{0}^{∗} is proved.

4.2 G ∈ K_{1}

We say that a poset P has property Pr iff for each sequence ⟨p_{ν} : ν < ω_{1}⟩ ⊂ P there exist disjoint sets U_{0}, U_{1} ∈ [ω_{1}]^{ω_{1}} such that whenever α ∈ U_{0} and β ∈ U_{1} we have p_{α}∥_{P} p_{β}.

Lemma 4.7 C has property Pr.

Indeed, C has property K.

Lemma 4.8 If T is an Aronszajn-tree, then Q_{T} has property Pr.

Proof: Let ⟨p_{α} : α < ω_{1}⟩ ⊂ P be given. We can assume that there are a stationary set S ⊂ ω_{1}, p^{∗} ∈ Q_{T}, γ^{∗} < ω_{1}, n ∈ ω and {z_{i} : i < n} ⊂ T such that for each α ∈ S

(a) x⌈α ∈ dom(p_{α}) for each x ∈ dom(p_{α}) with height_{T} (x) ≥ α,

(b) p_{α}⌈T_{<α} = p^{∗},

(c) |dom(p_{α}) ∩ T_{α}| = n,

(d) writing dom(p_{α}) ∩ T_{α} = {x_{0}^{α}, …, x_{n−1}^{α}}, x_{0}^{α} <_{On} … <_{On} x_{n−1}^{α}, the sequence ⟨p_{α}(x_{0}^{α}), …, p_{α}(x_{n−1}^{α})⟩ is independent from α,

(e) γ^{∗} < α and the elements x_{0}^{α}⌈γ^{∗}, …, x_{n−1}^{α}⌈γ^{∗} are pairwise distinct,

(f) x_{i}^{α}⌈γ^{∗} = z_{i} for i < n.

For each β < ω_{1} and ȳ = ⟨y_{0}, …, y_{n−1}⟩ ∈ (T_{β})^{n} take

Sȳ = {α ∈ S \ β : x_{i}^{α}⌈β = y_{i} for each i < n}.

Let

C^{∗} = {δ < ω_{1} \ γ^{∗} : ∀β < δ ∀ȳ ∈ (T_{β})^{n} (|Sȳ| ≤ ω → Sȳ ⊂ δ)}.

Now {p_{α} : α ∈ S ∩ C^{∗}} are ω_{1} members of P, so for some α < β ∈ S ∩ C^{∗} the conditions p_{α} and p_{β} are compatible. Since p_{α}(x_{l}^{α}) = p_{β}(x_{l}^{β}), x_{l}^{α} and x_{l}^{β} are incomparable in T for l < n. So for some ν < α, x_{l}^{α}⌈ν ≠ x_{l}^{β}⌈ν whenever l < n. On the other hand, for l ≠ m < n we have x_{l}^{α}⌈ν ≠ x_{m}^{β}⌈ν because x_{l}^{α}⌈γ^{∗} = z_{l} ≠ z_{m} = x_{m}^{β}⌈γ^{∗}. Take y_{l}^{a} = x_{l}^{α}⌈ν and y_{l}^{b} = x_{l}^{β}⌈ν for l < n and write ā = ⟨y_{0}^{a}, …, y_{n−1}^{a}⟩, b̄ = ⟨y_{0}^{b}, …, y_{n−1}^{b}⟩ . The elements {y_{i}^{a}, y_{i}^{b} : i < n} are pairwise different, so for each α′ ∈ Sā and β′ ∈ Sb̄ the conditions p_{α′} and p_{β′} are compatible. But |Sā| = |Sb̄| = ω_{1}, because α ∈ Sā, β ∈ Sb̄, ν < α and α ∈ C^{∗}.

A poset P is called well-met if any two compatible elements p_{0} and p_{1} of P have a greatest lower bound denoted by p_{0} ∧ p_{1}.

Lemma 4.9 Assume that the poset P has property Pr and V^{P} ⊧ “the poset Q has property Pr”. Let {⟨p_{α}, q_{α}⟩ : α < ω_{1}} ⊂ P ∗Q. Then there are disjoint sets U_{0}, U_{1} ∈ [ω_{1}]^{ω_{1}} such that for each γ ∈ U_{0} and δ ∈ U_{1} the conditions ⟨p_{γ}, q_{γ}⟩ and ⟨p_{δ}, q_{δ}⟩ are compatible, in other words, p_{γ} and p_{δ} have a common extension p_{γ,δ} in P with p_{γ,δ}^{∥}—“q_{γ} ∥_{Q} q_{δ}”. If P is well-met, then we can find conditions {p′_{α} : α ∈ U_{0}∪U_{1}} in P with p′_{α} ≤ p_{α} such that p′_{γ} ∧p′_{δ}^{∥}—“q_{γ} ∥_{Q} q_{δ}” for each γ ∈ U_{0} and δ ∈ U_{1}.

Proof: Let U̇ be a P -name for the set U = {α : p_{α} ∈ G_{P} }, where G_{P} is the P - generic filter. Since P satisfies c.c.c., there is a p^{∗} ∈ P with p^{∗}^{∥}—“|U̇| = ω_{1}”. Since V^{P} ⊧“Q has property Pr”, there is a condition p ≤ p^{∗} and there are P -names such that p^{∥}— “V_{i} = {α̇_{γ}^{i} : γ < ω_{1}} ∈ [U]^{ω_{1}}, for i ∈ 2, and q_{}_{α̇_{γ}^{0}} and q_{}_{α̇_{δ}^{1}} are compatible whenever γ, δ ∈ ω_{1}”. Choose conditions p_{γ}^{∗} ≤ p and ordinals β_{γ}^{0}, β_{γ}^{1}, with p_{γ}^{∗}^{∥}—“ α̇_{γ}^{i} = β̂_{γ}^{i}” for i < 2.

Now consider the sequence A = {p_{γ}^{∗} : γ < ω_{1}}. Since P has property Pr, there are disjoint, uncountable sets C_{0}, C_{1} ⊂ A such that p_{γ}^{∗} and p_{δ}^{∗} are compatible whenever γ ∈ C_{0} and δ ∈ C_{1}. Take U_{i} = {β_{γ}^{i} : γ ∈ C_{i}} for i ∈ 2. We can assume that U_{0} ∩ U_{1} = ∅. Let γ ∈ C_{0} and δ ∈ C_{1} and let p′′ be a common extension of p_{γ}^{∗} and p_{δ}^{∗}. Then p′′^{∥}—“β_{γ}^{0}, β_{δ}^{1} ∈ U̇, that is, p_{β_{γ}^{0}} and p_{β_{δ}^{1}} are in G_{P} ”, so p′′, must be a common extension of p_{β_{γ}^{0}} and p_{β_{δ}^{1}}. So p′′^{∥}—“β_{γ}^{0} ∈ V_{0} and β_{δ}^{1} ∈ V_{1}”, thus p′′^{∥}—“q_{β_{γ}^{0}} and q_{β_{δ}^{1}} are compatible in Q”, so ⟨p_{β_{γ}^{0}}, q_{β_{γ}^{0}}⟩ ∥_{P ∗Q} ⟨p_{β_{δ}^{1}}, q_{β_{δ}^{1}}⟩.

Suppose that P is well-met. Take p′_{β_{γ}^{0}} = p_{γ}^{∗} ∧ p_{β_{γ}^{0}} and p′_{β_{δ}^{1}} = p_{δ}^{∗} ∧ p_{β_{δ}^{1}}. It works because we can use p_{γ}^{∗} ∧ p_{δ}^{∗} as p′′ in the argument of the previous paragraph.

Lemma 4.10 If ⟨R_{α} : α ≤ μ, S_{β} : β < μ⟩ is a finite support iteration such that V^{R_{α}} ⊧“S_{α} has property Pr” for α < μ, then R_{μ} has property Pr, as well.

Proof: We prove this lemma by induction on μ. The successor case is covered by lemma 4.9. Assume that μ is limit. Let ⟨p_{ξ} : ξ < ω_{1}⟩ ⊂ R_{μ}. Without loss of generality we can assume that ⟨supp(p_{ξ}) : ξ < ω_{1}⟩ forms a Δ-system with kernel d. Fix ν < μ with d ⊂ ν. By the induction hypothesis, the poset R_{ν} has property Pr, so there exist disjoint sets U_{0}, U_{1} ∈ [ω_{1}]^{ω_{1}} such that whenever ξ ∈ U_{0} and η ∈ U_{1} we have p_{ξ}∥_{Rν} p_{η}. But p_{ξ}∥_{Rν} p_{η} implies p_{ξ}∥_{Rμ}p_{η} because supp(p_{ξ}) ∩ supp(p_{η}) ⊂ ν, so R_{μ} has property Pr, as well.

The previous lemmas yield the following corollary.

Lemma 4.11 P_{ω_{2}} has property Pr.

Given G = ⟨ω_{1}, E⟩ ∈ K_{1} and ξ, α, β ∈ ω_{1} with ξ ∈ α ∩ β take

D_{ξ}^{G}(α, β) = {ν ∈ ξ : {α, ν} ∈ E iff {β, ν} ∉ E}.

Lemma 4.12 If G ∈ K_{1}, then

(∗)  ∀ξ ∈ ω_{1} ∃ϵ_{G}(ξ) ∈ ω_{1} ∀α, β ∈ ω_{1} \ ϵ_{G}(ξ) |D_{ξ}^{G}(α, β)| < ω.

Proof: Since G ∈ K_{1}, we have an x ∈ ω_{1} with |ω_{1} \ [x]_{ξ}| < ω_{1}. Choose ϵ_{G}(ξ) ∈ ω_{1} \ ξ with ω_{1} \ [x]_{ξ} ⊂ ϵ_{G}(ξ). It works because α, β > ϵ_{G}(ξ) implies α, β ∈ [x]_{ξ}.

The bipartite graph ⟨ω_{1} × 2, {{⟨ν, 0⟩ , ⟨μ, 1⟩} : ν < μ < ω_{1}}⟩ will be denoted by [ω_{1}; ω_{1}].

Lemma 4.13 If G ∈ K_{1}, then neither G nor its complement may have a — not necessarily spanned — subgraph isomorphic to [ω_{1}; ω_{1}].

Proof: Let G = ⟨ω_{1}, E⟩. Write E(α) = {ξ ∈ ω_{1} : {ξ, α} ∈ E}. Assume on the contrary that A, B ∈ [ω_{1}]^{ω_{1}} are disjoint sets such that {α, β} ∈ E whenever α ∈ A and β ∈ B with α < β. Without loss of generality we can assume that (A \ α + 1) ∩ ϵ(α) = ∅ for each α ∈ A. Write A = {α_{ξ} : ξ < ω_{1}}. Then for ξ ∈ ω_{1} the set F (ξ) = (A∩α_{ξ})\E(α_{ξ+1}) is finite because α_{ξ+1} > ϵ(α_{ξ}) and (A∩α_{ξ})\E(β) = ∅ for all but countable many β ∈ B. By Fodor’s lemma, we can assume that F (ξ) = F for each ξ ∈ S, where S is a stationary subset of ω_{1} containing limit ordinals only. Let T = {ξ ∈ S : F ⊂ α_{ξ}} and take W = {α_{ξ+1} : ξ ∈ T }. Then G[W] is an uncountable complete subgraph of G. Contradiction.

Lemma 4.14 If G ∈ K_{1} and V^{C} ⊧“Q has property Pr”, then

V^{C∗Q} ⊧ “G ≅ G̸[f^{−1}{i}] for i < 2”,

where f : ω_{1} → 2 is the C-generic function over V.

Proof: Assume on the contrary that

⟨p, q⟩^{∥}—“ḣ : G ≅ G[f^{−1}{0}]”.

To simplify our notations, we will write E for E(G), D_{ξ}(α, β) for D_{ξ}^{G}(α, β) and ϵ(ξ) for ϵ_{G}(ξ).

Let C_{0} = {δ < ω_{1} : ξ < δ implies ϵ(ξ) < δ}. Clearly C_{0} is club. Take C_{1} = {δ < ω_{1} : ⟨p, q⟩^{∥}—“ḣ′′δ̂ = f^{−1}{0} ∩ δ̂”}. Since C ∗ Q satisfies c.c.c, the set C_{1} is club. Put C_{2} = C_{0} ∩ C_{1}.

Now for each α < ω_{1} let δ_{α} = min(C_{2} \ α + 1) and choose a condition ⟨p_{α}, q_{α}⟩ ≤ ⟨p, q⟩ and a countable ordinal γ_{α} such that

⟨p_{α}, q_{α}⟩^{∥}—“ḣ(δ̂_{α}) = γ̂_{α}”.

Since γ_{α} ≥ δ_{α} > ϵ(α) for each α ∈ ω_{1}, we can fix a stationary set S ⊂ ω_{1} and a finite set D such that D_{α}(δ_{α}, γ_{α}) = D for each α ∈ S. Since C is wellmet, applying lemma 4.9 we can find disjoint uncountable subsets S_{0}, S_{1} ⊂ S and a sequence ⟨p′_{α} : α ∈ S_{0} ∪ S_{1}⟩ ⊂ C with p′_{α} ≤ p_{α} such that p′_{α} ∧ p′_{β}^{∥}— “q_{α} ∥_{Q} q_{β}” for each α ∈ S_{0} and β ∈ S_{1}.

We can assume that the sets {dom(p′_{α}) : α ∈ S_{0}} and {dom(p′_{β}) : β ∈ S_{1}} form Δ-systems with kernels d_{0} and d_{1}, respectively.

Take Y_{ξ}^{0} = {α ∈ S_{0} : {ξ, δ_{α}} ∈ E} and Y_{ξ}^{1} = {α ∈ S_{1} : {ξ, δ_{α}} ∉ E} for ξ < ω_{1}. Write Y_{i} = {ξ < ω_{1} : |Y_{ξ}^{i}| = ω_{1}} and Z_{i} = ω_{1} \ Y_{i} for i < 2.

By 4.13, the sets Z_{i} are countable. Pick ξ ∈ C_{2} with D∪d_{0}∪d_{1}∪Z_{0}∪Z_{1} ⊂ ξ. Let ξ′ = min(C_{2} \ ξ + 1) and ξ′′ = min(C_{2} \ ξ′ + 1) . Since d_{0} ∪ d_{1} ⊂ ξ and |Y_{ξ}^{0}| = |Y_{ξ}^{1}| = ω_{1}, we can choose α_{i} ∈ Y_{ξ}^{i} \ ξ′′ with dom(p′_{α_{i}}) ∩ [ξ, ξ′) = ∅ for i = 0, 1. The set W = D_{ξ′}(δ_{α_{0}}, δ_{α_{1}}) ∩ [ξ, ξ′)is finite because δ_{α_{i}} ≥ α_{i} ≥ ξ′′ > ϵ(ξ′) for i < 2. Choose a C-name q such that p′_{α_{0}} ∧ p′_{α_{1}}^{∥}— “q is a common extension of q_{α_{0}} and q_{α_{1}} in Q” and take

r = ⟨p′_{α_{0}} ∪ p′_{α_{1}} ∪ {⟨ν, 1⟩ : ν ∈ W }, q⟩ .

Since W ∩ (dom(p′_{α_{0}}) ∪ dom(p′_{α_{1}})) = ∅, r is a condition.

Pick a condition r′ ≤ r from C ∗Q and an ordinal η such that r′^{∥}—“ḣ(ξ̂) = η̂”. Now η ∈ [ξ, ξ′) because ξ, ξ′ ∈ C_{1}. Since

r′^{∥}—“ḣ(δ_{α_{i}}) = γ̂_{α_{i}}, ḣ(ξ̂) = η̂ and ḣ is an isomorphism”,

so {δ_{α_{0}}, ξ} ∈ E and {δ_{α_{1}}, ξ} ∉ E imply that {γ_{α_{0}}, η} ∈ E and {γ_{α_{1}}, η} ∉ E. But D_{α_{i}}(δ_{α_{i}}, γ_{α_{i}}) = D and D ⊂ ξ so {δ_{α_{0}}, η} ∈ E and {δ_{α_{1}}, η} ∉ E, that is, η ∈ W. But r^{∥}—“ran(ḣ) = f^{−1}{0} and f^{−1}{0} ∩ Ŵ = ∅”, contradiction.

4.3 G ∈ K_{2}

Given a non-trivial graph G = ⟨V, E⟩ with V ∈ [ω_{1}]^{ω_{1}} define

Γ(G) = {δ ∈ ω_{1} : ∃α ∈ V α ≥ δ and |twin_{G}(α, V ∩ δ)| ≤ ω}.

The following lemma obviously holds.

Lemma 4.15 If G_{0} and G_{1} are graphs on uncountable subsets of ω_{1}, G_{0} ≅ G_{1}, then Γ(G_{0}) = Γ(G_{1}) mod NS_{ω_{1}}.

Lemma 4.16 Given G ∈ K \ K_{0} and S ⊂ ω_{1} there is a partition (V_{0}, V_{1}) of ω_{1} such that Γ(G[V_{0}]) ⊂ S mod NS_{ω_{1}} and Γ(G[V_{1}]) ⊂ ω_{1} \ S mod NS_{ω_{1}}.

Proof: Let κ be a large enough regular cardinal and fix an increasing, continuous sequence ⟨N_{ν} : ν < ω_{1}⟩ of countable, elementary submodels of H_{κ} = ⟨H_{κ}, ∈⟩ such that G, S ∈ N_{0} and ⟨N_{ν} : ν ≤ μ⟩ ∈ N_{μ+1} for μ < ω_{1}.

Write γ_{ν} = N_{ν} ∩ ω_{1} and C = {γ_{ν} : ν < ω_{1}}. Take V_{0} = ⋃_{ν∈S}(γ_{ν+1} \ γ_{ν}) and

V_{1} = ω_{1} \ V_{0} = ⋃_{ν∈ω_{1}\S}(γ_{ν+1} \ γ_{ν}).

It is enough to prove that Γ(G[V_{0}]) ⊂ S mod NS_{ω_{1}}. Assume that γ_{ν} ∈ Γ(G[V_{0}]), γ_{ν} = ν, α ≥ γ_{ν}, α ∈ V_{0} and |twin_{G[V_{0}]}(α, γ_{ν} ∩ V_{0})| = ω. Since G, ν, γ_{ν} ∩ V_{0} ∈ N_{ν+1} and |G/ ≡_{G,V_{0}∩γ_{ν}} | ≤ ω, we have tp_{G}_{G[V_{0}]}(α, γ_{ν} ∩ V_{0}) ∈ N_{ν+1} and so twin_{G[V_{0}]}(α, γ_{ν}) ⊂ N_{ν+1} as well. Thus α ∈ γ_{ν+1} \ γ_{ν}. Hence α ∈ V_{0} implies γ_{n} = ν ∈ S which was to be proved.

Lemma 4.17 If G ∈ K \ K_{0} and Γ(G) ≠ ∅ mod NS_{ω_{1}}, then G is not quasismooth.

Proof: Assume that S = Γ(G) is stationary and let (S_{0}, S_{1}) be a partition of S into stationary subsets. By lemma 4.16, there is a partition (V_{0}, V_{1}) of ω_{1} with Γ(G([V_{i}]) ∩ S ⊂ S_{i}. Then G[V_{i}] and G can not be isomorphic by lemma 4.15.

Let us remark that G ∈ K_{2} iff G ∈ K \ K_{0} and there is an A ∈ [ω_{1}]^{ω} and x ∈ ω_{1} \ A such that |[x]_{G,A}| = |ω_{1} \ [x]_{G,A}| = ω_{1}.

Given G ∈ K_{2} we will write G ∈ K′_{2} iff there are two disjoint, countable subsets of ω_{1}, A_{0} and A_{1}, and there is an x ∈ ω_{1}, such that |[x]_{G,A_{0}}| = |ω_{1} \ [x]_{G,A_{0}}| = ω_{1} and [x]_{G,A_{0}} \ A_{1} = [x]_{G,A_{1}} \ A_{0}.

Lemma 4.18 If G ∈ K_{2}, then G ∈ (K′_{2})^{V^{C}}.

Proof: Assume that A ∈ [ω_{1}]^{ω} and x ∈ ω_{1} witness G ∈ K_{2} in the ground model. Fix a bijection f : A → ω in V. Let r : ω → 2 be the characteristic function of a Cohen real from V^{C}. Take A_{i} = (f ∘ r)^{−1}{i}. By a simple density argument, we can see that [x]_{G,A_{0}} = [x]_{G,A} = [x]_{G,A_{1}}. Thus A_{0}, A_{1} and x show that g ∈ K′_{2}.

Lemma 4.19 Assume that every Aronszajn tree is special. If G ∈ K′_{2}, then there is a partition (V_{0}, V_{1}) of ω_{1} such that Γ(G[V_{i}]) is stationary for i < 2.

Proof: Choose A_{0}, A_{1} and x witnessing G ∈ K′_{2}. Let A = A_{0} ∪ A_{1}. Take C_{0} = [x]_{G,A_{0}} \ A, C_{1} = (ω_{1} \ [x]_{G,A_{0}}) \ A and consider the partition trees T_{i} of G[C_{i}] for i ∈ 2 (see definition 2.3). These trees are Aronszajn-trees because G is non-trivial. Fix functions h_{i}: C_{i} → ω specializing T_{i}. We can find natural numbers n_{0} and n_{1} such that the sets S_{i} = {ν : h_{i}^{−1}{n_{i}} ∩ (T_{i})_{ν} ≠ ∅} are stationary, that is, h_{i}^{−1}{n_{i}} meets stationary many level of T_{i}. Take B_{i} = h_{i}^{−1}{n_{i}} and Y_{i} = {c ∈ C_{i} : ∃b ∈ B_{i} c ⪯_{T_{i}} b}.

Pick any δ ∈ S_{i}. Let b ∈ B_{i} ∩ (T_{i})_{δ}. If c ∈ Y_{i} \ (T_{i})_{<δ}, c ≠ b, then c⌈δ ≠ b by the construction of Y_{i}. So tp_{G}_{G[Y_{i}]}(c, (T_{i})_{<δ}) = tp_{G}_{G[Y_{i}]}(c⌈δ, (T_{i})_{<δ}) ≠ tp_{G}_{G[Y_{i}]}(b, (T_{i})_{<δ}) by the definition of the partition tree. This means that twin_{G[Y_{i}]}(b, (T_{i})_{<δ}) = {b}. Thus δ ∈ Γ(G[Y_{i}]) provided (T_{i})_{<δ} ⊂ δ and b ≥ δ. But these requirements exclude only a non-stationary subset of S_{i}. So Γ(G[Y_{i}]) ⊃ S_{i} mod NS_{ω_{1}}.

Let V_{i} = Y_{i} ∪A_{i} ∪(C_{1−i} \Y_{1−i}) for i ∈ 2 and consider the partition (V_{0}, V_{1}) of ω_{1} . If z ∈ V_{i}\(Y_{i}∪A_{i}), then tp_{G}(z, A_{i}) ≠ tp_{G}(b, A_{i}) for any b ∈ B_{i} because C_{0} ⊂ [x]_{G,A_{i}} and C_{1} ⊂ ω_{1} \ [x]_{G,A_{i}}. So Γ(G[V_{i}]) ⊃ S_{i} mod NS_{ω_{1}} holds.

Now we are ready to conclude the proof of theorem 4.1. We will work in V^{P_{ω_{2}}}. Assume that G ∈ K. We must show that G is not quasi-smooth.

Pick a ν < ω_{2} with G ∈ (K)^{V^{Pν}} and Q_{ν} = C. Assume first that G ∈ (K_{0})^{V^{Pν}}. If G were quasi-smooth in V^{P_{ω_{2}}}, G ∈ (K_{0}^{∗})^{P_{ω_{2}}} would hold by lemma 4.6. So we can assume that G ∈ (K_{0}^{∗})^{P_{ν}}. Since P_{ω_{2}} is a stable, c.c.c. poset, so is P_{ω_{2}}/P_{ν+1}. So, by lemma 4.5, there is a partition (V_{O}, V_{1}) of ω_{1} in V^{P_{ν+1}} such that V^{P_{ω_{2}}} ⊧“G is not isomorphic to G[V_{i}] for i < 2”.

Assume that G ∈ (K_{1})^{V^{Pν}}. Since P_{ω_{2}} has property Pr, so is P_{ω_{2}}/P_{ν+1}. Thus, by lemma 4.14, the partition (V_{O}, V_{1}) of ω_{1} given by the Q_{ν}-generic Cohen reals in V^{P_{ν+1}} has the property that V^{P_{ω_{2}}} ⊧“G is not isomorphic to G[V_{i}] for i < 2”.

Finally assume that G ∈ (K_{2})^{V^{Pν}}. By lemma 4.18, we have G ∈ (K′_{2})^{V^{P_{ν+1}}}. Since P_{ω_{2}} satisfies c.c.c, it follows that G ∈ (K′_{2})^{V^{Pω_{2}}} . So applying lemma 4.19 we can find a partition (V_{0}, V_{1}) of ω_{1} such that both Γ(G[V_{0}]) and Γ(G[V_{1}]) are stationary. Thus, by lemma 4.17, neither G[V_{0}] nor G[V_{1}] are quasi-smooth. So G itself can not be quasi-smooth.

References

[1] U. Abraham, S. Shelah, Forcing with stable posets, Journal of Symbolic Logic 47 (1982) no 1, 37–42

[2] K. J. Devlin, S. Shelah, A weak version of ♢ which follows from 2^{ω} < 2^{ω_{1}}, Israel J. Math 28 (1978) no 2–3, 239–247

[3] A. Hajnal, Zs. Nagy, L. Soukup, On the number of non-isomorphic subgraphs of certain graphs without large cliques and independent subsets, to appear in “A tribute to Paul Erdős ”, Oxford University Press

[4] T. Jech, Set Theory, Academic Press. New York, 1978

[5] H. A. Kierstead, P. J. Nyikos, Hypergraphs with Finitely many Isomorphism Subtypes, preprint.

[6] D. Macpherson, A. H. Mekler, S. Shelah, The number of Infinite Substructures, preprint

[7] S. Shelah, Proper Forcing, Springer-Verlag, Berlin Heilderberg New York,