# What would the rational Urysohn space and the random graph look like if they
were uncountable?

Ziemowit Kostana 111Research of Z. Kostana was supported by the GAČR project
GAČR project EXPRO 20-31529X and RVO: 67985840.
Institute of Mathematics Czech Academy of Sciences
Žitná 25, 115 67 Prague, Czech Republic;
University of Warsaw,
Banacha 2, 02-097 Warsaw, Poland
<EMAIL_ADDRESS>
###### Abstract

Building on the work of Avraham, Rubin, and Shelah, we aim to build a variant
of the Fraïssé theory for uncountable models built from finite submodels. With
this aim, we generalize the notion of an increasing set of reals to other
structures. As an application, we prove that the following is consistent:
there exists an uncountable, separable metric space $X$ with rational
distances, such that every uncountable partial 1-1 function from $X$ to $X$ is
an isometry on an uncountable subset. We aim for a general theory of
structures with this kind of properties. This includes results about the
automorphism groups, and partial classification results.

Keywords: Fraisse limit, Martin’s Axiom, homogeneous structure, generic
structure
MSC classification: 06A05 03C25 03C55 03E35

##  0 Introduction

###  0.1 History and Motivation

Assuming $CH$ we can build models of size $\omega_{1}$ homogeneous with
respect to countable substructures. This is a consequence of the Fraïssé-
Jónsson theory, developed in [6]. However, such models are highly "non-
separable". Can we (generically) build uncountable models from finite
submodels? One indication that such theory should be possible to formulate is
the famous theorem of Baumgartner, about separable $\omega_{1}$-dense linear
orders. Recall that a linear order is $\omega_{1}$-dense if each non-empty
open interval has cardinality $\omega_{1}$.

######  Theorem (Baumgartner, [3]).

It is consistent with $ZFC$ that there exists a unique up to isomorphism
separable $\omega_{1}$-dense linear order.

Once the conclusion of this theorem holds, we can take any subfield of the
reals of size $\omega_{1}$ as a model of this ordering. This shows that the
(unique) $\omega_{1}$-dense separable linear order is homogeneous with respect
to finite subsets (as is any subfield of reals). Ideas of Baumgartner were
extended by Avraham, Rubin, and Shelah in [2] and [1]. Among other things,
they show that Baumgartner’s Theorem does not follow from $MA+\lnot CH$, but
the latter axiom is a significant step in the direction of Baumgartner’s
Theorem. They introduce another axiom, $OCA_{ARS}$, and show that
$MA_{\omega_{1}}+OCA_{ARS}$ implies that either the conclusion of
Baumgartner’s Theorem holds, or there are up to isomorphism exactly three
homogeneous separable $\omega_{1}$-dense linear orders ([1], Sec. 6). This
gives some insight that $MA_{\omega_{1}}$ might be used in place of induction
in some uncountable variant of the Fraïssé theory.

We continue the line of research started in [7]. We consider the structures we
introduced in [7], and use them to extend certain ideas from [2] and [1]. For
example, the generic structures from [7], although initially rigid, become
highly homogeneous in suitable forcing extensions satisfying
$MA_{\omega_{1}}$. Inductive arguments from the classical Fraïssé theory are
replaced by Martin’s Axiom, and in some cases it is enough to imply certain
uniqueness.

Even if aiming towards a new variant of the Fraïssé theory is perhaps too
ambitious, we still find new applications for some techniques developed in
[2]. As an example, let us look at one Ramsey-type result from [2].

######  Theorem (Thm. 2, [2]).

It is consistent with $ZFC+MA+"2^{\omega}=\omega_{2}"$ that there exists an
uncountable set $A\subseteq\mathbb{R}$ with the property that each uncountable
1-1 function $f\subseteq A\times A$ is strictly increasing on an uncountable
set.

In this spirit, we prove in Section 2

######  Theorem.

It is consistent with $ZFC+MA+"2^{\omega}=\omega_{2}"$ that there exists an
uncountable, separable rational metric space $(X,d)$ such that each
uncountable 1-1 function $f\subseteq X\times X$ is an isometry on an
uncountable set.

This phenomenon is more general. In Section 3, we prove similar results for
other classes of structures, although they are more technical, and require
some introduction (what is a "separable" graph?). In Section 4, we prove some
results on the number of isomorphism types of models we built.

###  0.2 Acknowledgements

This article is based on the results from the author’s PhD dissertation. I
thank my advisor Wiesław Kubiś for his guidance, and creating a warm and
welcoming atmosphere for the research work in the Institute of Mathematics of
the Czech Academy of Sciences. Also, I thank Assaf Rinot for stimulating
discussions that helped to improve the final presentation of the theory.

##  1 Preliminaries

By an _embedding_ we always mean an isomorphism into its image. A subset of a
model is a _substructure_ if the identity inclusion is an embedding. We will
say that a language is _purely relational_ if it doesn’t contain any function
or constant symbols. We write $\operatorname{dom}{f}$ and
$\operatorname{rg}{f}$ to denote respectively the domain and the image of a
function $f$.

We study structures added generically by forcings

$\operatorname{Fn}(S,\mathcal{K},\lambda),$

that we introduced in [7]. The variable $\mathcal{K}$ always stands for a
class of structures in some purely relational language. All unspecified
forcing terminology follows [10].

######  Definition 1.1.

Let $\lambda$ be an infinite cardinal, and $S$ an infinite set. For any model
$A\in\mathcal{K}$ we denote by $F(A)$ its underlying set. We introduce the
forcing $\operatorname{Fn}(S,\mathcal{K},\lambda)$ as the set

$\\{A\in\mathcal{K}|\;F(A)\in[S]^{<\lambda}\\},$

ordered by the reversed substructure relation.

We proved in [7] that models added generically by

$\operatorname{Fn}(\omega_{1},\mathcal{K},\omega)$

tend to be rigid, while those added by

$\operatorname{Fn}(\omega,\mathcal{K},\omega)$

are isomorphic to the usual Fraïssé limits of $\mathcal{K}$. We must impose
some restrictions on the class $\mathcal{K}$ for
$\operatorname{Fn}(\omega,\mathcal{K},\omega)$ to be an interesting forcing
notion. The following is sufficient to ensure the c.c.c. property in all cases
in the range of our interest. The name _Splitting Property_ was coined by W.
Kubiś. Two embeddings $f:A\hookrightarrow B$ and $g:A\hookrightarrow C$ are
_isomorphic_ , if there exists an isomorphism $h:B\hookrightarrow C$, such
that $h\circ f=g$.

######  Definition 1.2.

$\mathcal{K}$ has the Splitting Property (SP) if for all $R\in\mathcal{K}$,
all pairs of isomorphic extensions $R\subseteq X$, $R\subseteq Y$, there
exists $Z\in\mathcal{K}$, containing $X\cup Y$.

######  Proposition 1.3.

Let $\mathcal{K}$ be a class of structures in a purely relational language,
that satisfies the following

  * •

$\mathcal{K}$ has countably many isomorphism types of finite models,

  * •

$\mathcal{K}$ is hereditary (if $A\in\mathcal{K},\;B\subseteq A,$ then
$B\in\mathcal{K}$),

  * •

$\mathcal{K}$ has the SP.

Then the forcing $\operatorname{Fn}(\lambda,\mathcal{K},\omega)$ has the
c.c.c. for any cardinal $\lambda$.

###### Proof.

Consider a family of conditions $\\{{A}_{\xi}|\;\xi<\omega_{1}\\}$. Using
$\Delta$-system Lemma, we can trim the sequence, so that the sets
$\\{F({A}_{\xi})|\;\xi<\omega_{1}\\}$ form a $\Delta$-system with the root
$K\in[\lambda]^{<\omega}$. There are at most countably many structures from
$\mathcal{K}$ with the universe $K$, so we can assume that we have
$\mathbb{K}\in\mathcal{K}$ with $F(\mathbb{K})=K$, and for all
$\xi\neq\eta<\omega_{1}$

${A}_{\xi}\cap{A}_{\eta}=\mathbb{K}.$

We can also assume that the extensions $\mathbb{K}\subseteq{A}_{\xi}$ and
$\mathbb{K}\subseteq{A}_{\eta}$ are isomorphic. Now we can use the SP for the
diagram

${{A}_{\xi}}$${\mathbb{K}}$${{A}_{\eta}}$

to get a condition stronger than ${A}_{\xi}$ and ${A}_{\eta}$. ∎

##  2 Following Avraham, Rubin, and Shelah

###  2.1 Rectangular Metric Spaces

We adapt the technology from [2] and [1] to prove that it is relatively
consistent with $ZFC$ that there exists a separable rational metric space
$(X,d)$ of size $\omega_{1}$, such that any uncountable 1-1 function from $X$
to itself is an isometry on an uncountable subset. The original result states
that it is relatively consistent with $ZFC$ that there exists an uncountable
set $A\subseteq\mathbb{R}$, such that every function $f:A\rightarrow A$ is
non-decreasing on an uncountable set. Unlike the latter statement, our result
does not seem to follow from Semiopen Coloring Axiom, Open Coloring Axiom or
any other combinatorial principle described in [1].

We first introduce a metric analog of a $k$-increasing linear order,
introduced in [2].

######  Definition 2.1.

Let $(X,d)$ be a metric space.

  * •

We call a pair of tuples
$\overline{x}=(x_{1},\ldots,x_{n}),\overline{y}=(y_{1},\ldots,y_{n})\in X^{n}$
_alike_ if they satisfy the following axioms:

    * A1

$\forall\;i,j=1,\ldots,n\;(d(x_{i},y_{i})=d(x_{j},y_{j}))$

    * A2

$\forall\;i,j=1,\ldots,n\;(d(x_{i},x_{j})=d(y_{i},y_{j}))$

    * A3

$\forall\;i,j=1,\ldots,n\;(x_{i}\neq x_{j}\implies
d(x_{i},x_{j})=d(x_{i},y_{j}))$

We then write $\overline{x}\circledast\overline{y}$.

  * •

We call $(X,d)$ _rectangular_ if it is uncountable, and for any sequence of
pairwise disjoint tuples
$\\{(x_{1}^{\xi},\ldots,x_{n}^{\xi})|\;\xi<\omega_{1}\\}\subseteq X^{n}$,
there are $\xi\neq\eta<\omega_{1}$, such that
$(x_{1}^{\xi},\ldots,x_{n}^{\xi})\circledast(x_{1}^{\eta},\ldots,x_{n}^{\eta})$.

Denote by $Metr$ the class of rational metric spaces. Keeping up with the
general notation, $\operatorname{Fn}(\kappa,Metr,\omega)$ is the partial order

$\\{(Y,d)|\;Y\in[\kappa]^{<\omega},\text{ and $(Y,d)$ is a rational metric
space}\\},$

with the ordering relation being the reversed inclusion preserving the metric.

We begin with a technical Lemma to ensure that we can amalgamate metric spaces
in a specific way.

######  Lemma 2.2.

Let $(R,d_{R}),(X,d_{X}),(Y,d_{Y})$ be finite metric spaces, such that
$(X,d_{X})\cap(Y,d_{Y})=(R,d_{R})$, and suppose that
$h:(X,d_{X})\rightarrow(Y,d_{Y})$ is an isometric bijection, which is identity
on $R$.

${(X,d_{X})}$${(R,d_{R})}$${(X\cup Y,d^{*})}$${(Y,d_{Y})}$$\scriptstyle{h}$

Then there exists a metric $d^{*}$ on $X\cup Y$ extending both $d_{X}$ and
$d_{Y}$, such that if $(x_{1},\ldots,x_{n})$ is a bijective enumeration of
$X\setminus R$, then
$(x_{1},\ldots,x_{n})\circledast(h(x_{1}),\ldots,h(x_{n}))$.

###### Proof.

Let $s=\min\\{d_{X}(x,x^{\prime})|\;x\neq x^{\prime}\in X\\}$. Given that
$d^{*}$ must extend the metrics of $X$ and $Y$, we must set the distances
between elements from $X\setminus R$ and $Y\setminus R$. Therefore we set
$d^{*}(x,h(x))=s$ and $d^{*}(x,h(x^{\prime}))=d_{X}(x,x^{\prime})$, for all
$x\neq x^{\prime}\in X\setminus R$. A standard computation shows that this
definition gives a well-defined metric structure on $X\cup Y$, satisfying the
required conditions. ∎

In the light of Proposition 1.3, we have the c.c.c. property for forcings
$\operatorname{Fn}(\kappa,Metr,\omega)$. Even more generally, for any
countable set $K\subseteq[0,\infty)$ the proof of Lemma 2.2 shows that the
class of finite metric spaces with distances in $K$ has the SP.

######  Proposition 2.3.

For any uncountable cardinal $\kappa$,
$\operatorname{Fn}(\kappa,Metr,\omega)\Vdash\text{"$(\kappa,\dot{d})$ is
rectangular"}$.

###### Proof.

Let $\\{(\dot{x}_{1}^{\xi},\ldots,\dot{x}_{n}^{\xi})|\;\xi<\omega_{1}\\}$ be a
sequence of $\operatorname{Fn}(\kappa,Metr,\omega)$-names for pairwise
disjoint $n$-tuples from $(\kappa,\dot{d})$. Fix a condition $p$. For every
$\xi<\omega_{1}$, we find a condition $p_{\xi}=(p_{\xi},d_{\xi})\leq p$,
deciding values of $\dot{x}^{\xi}_{i}$ and
$\dot{d}\restriction\\{x^{\xi}_{1},\ldots,x^{\xi}_{n}\\}\times\\{x^{\xi}_{1},\ldots,x^{\xi}_{n}\\}$.
We choose an uncountable set $S\subseteq\kappa$, satisfying the following
conditions:

  * •

$\\{p_{\xi}|\;\xi\in S\\}$ is a $\Delta$-system with the root $R=(R,d_{R})$,

  * •

$\forall\;\xi,\eta\in S$ there exists an isometry $h:p_{\xi}\rightarrow
p_{\eta}$, which is identity on $R$, and $h(x^{\xi}_{i})=x^{\eta}_{i}$, for
$i=1,\ldots,n$, as shown in the diagram.

${(p_{\xi},d_{\xi})}$${(R,d_{R})}$${(p_{\eta},d_{\eta})}$$\scriptstyle{h}$

This can be easily done, since given any point $\alpha\in\omega_{1}$ outside
of $R$, there are only countably many possible configurations of distances
between this point and $R$. Now we choose $\xi\neq\eta\in S$, and apply Lemma
2.2 to obtain $q\leq p_{\xi},p_{\eta}$, which forces that
$(x^{\xi}_{1},\ldots,x^{\xi}_{n})\circledast(x^{\eta}_{1},\ldots,x^{\eta}_{n})$.
∎

Let $(\mathcal{M},d)$ be the metric space we added to our model by
$\operatorname{Fn}(\kappa,Metr,\omega)$. Our next task is to force
$MA_{\omega_{1}}$, while preserving $(\mathcal{M},d)$ being rectangular.
Following the ideas from [2], we introduce a special class of partial orders.

######  Definition 2.4.

A partial order $\mathbb{P}$ satisfies $(\mathcal{M},d)$_-c.c._ if given any
natural number $n>0$, for each family consisting of pairwise disjoint tuples

$\\{(p_{\xi},x_{1}^{\xi},\ldots,x_{n}^{\xi})|\;\xi<\omega_{1}\\}\subseteq\mathbb{P}\times(\mathcal{M},d)^{n},$

there exist $\xi\neq\eta<\omega_{1}$, such that $p_{\xi}$ and $p_{\eta}$ are
comparable, and

$(x_{1}^{\xi},\ldots,x_{n}^{\xi})\circledast(x_{1}^{\eta},\ldots,x_{n}^{\eta}).$

######  Proposition 2.5.

If $\mathbb{P}$ satisfies $(\mathcal{M},d)$-c.c. then
$\mathbb{P}\Vdash\text{"$(\mathcal{M},d)$ is rectangular"}$.

###### Proof.

Fix a sequence of $\mathbb{P}$-names
$\\{(\dot{x}_{1}^{\xi},\ldots,\dot{x}_{n}^{\xi})|\;\xi<\omega_{1}\\}\subseteq(\mathcal{M},d)^{n}$
for pairwise disjoint $n$-tuples. For a given condition $p\in\mathbb{P}$, and
$\xi<\omega_{1}$, we fix a condition $p_{\xi}\leq p$ deciding
$(\dot{x}_{1}^{\xi},\ldots,\dot{x}_{n}^{\xi})$. Then we apply
$(\mathcal{M},d)$-c.c. to the family
$\\{(p_{\xi},x_{1}^{\xi},\ldots,x_{n}^{\xi})|\;\xi<\omega_{1}\\}$. This way we
obtain $\xi\neq\eta<\omega_{1}$, and $q\leq p_{\xi},p_{\eta}$, such that
$q\Vdash(\dot{x}_{1}^{\xi},\ldots,\dot{x}_{n}^{\xi})\circledast(\dot{x}_{1}^{\eta},\ldots,\dot{x}_{n}^{\eta})$.
∎

The argument showing that $(\mathcal{M},d)$-c.c. is preserved under iterations
is really not different than the one showing that the c.c.c. is preserved,
applied for example in [10]. We include it for completeness.

######  Proposition 2.6.

Finite support iterations of $(\mathcal{M},d)$-c.c. posets are
$(\mathcal{M},d)$-c.c..

###### Proof.

Assume that $\mathbb{P}$ is $(\mathcal{M},d)$-c.c., and
$\mathbb{P}\Vdash\text{"$\dot{\mathbb{Q}}$ is $(\mathcal{M},d)${-c.c.}"}$.
Take a sequence

$\\{(p_{\xi},\dot{q}_{\xi},x_{1}^{\xi},\ldots,x_{n}^{\xi})|\;\xi<\omega_{1}\\},$

and towards contradiction assume that it witnesses
$\mathbb{P}\ast\dot{\mathbb{Q}}$ not being $(\mathcal{M},d)$-c.c.. Let
$\dot{\sigma}$ be a $\mathbb{P}$-name defined
$\dot{\sigma}=\\{(\xi,p_{\xi})|\;\xi<\omega_{1}\\}$. If $G\subseteq\mathbb{P}$
is an $M$-generic filter, then

$M[G]\models(\xi\in\sigma\iff p_{\xi}\in G).$

We claim that in $M[G]$, for any two conditions $\eta,\xi\in\sigma$, if
$(x_{1}^{\xi},\ldots,x_{n}^{\xi})\circledast(x_{1}^{\eta},\ldots,x_{n}^{\eta})$,
then $q_{\xi}$ and $q_{\eta}$ are inconsistent. For otherwise, there exist
$q\leq q_{\eta},q_{\xi}$, and $p\in G$, which forces it. Since $p_{\xi}$ and
$p_{\eta}$ are in $G$, which is a filter, we may choose $p\leq
p_{\xi},p_{\eta}$. Then
$(p,\dot{q})\leq(p_{\xi},\dot{q}_{\xi}),(p_{\eta},\dot{q}_{\eta})$, and
$(x_{1}^{\xi},\ldots,x_{n}^{\xi})\circledast(x_{1}^{\eta},\ldots,x_{n}^{\eta})$
contrary to the choice of the sequence
$\\{(p_{\xi},\dot{q}_{\xi},x_{1}^{\xi},\ldots,x_{n}^{\xi})|\;\xi<\omega_{1}\\}$.

$G$ was an arbitrary generic filter, and remember that
$\mathbb{P}\Vdash\text{"$\dot{\mathbb{Q}}$ is $(\mathcal{M},d)${-c.c.}"}$. The
conclusion of this is that $\mathbb{P}\Vdash|\dot{\sigma}|<\omega_{1}$. Then
there exists a $\mathbb{P}$-name for a countable ordinal $\dot{a}$, for which
$\mathbb{P}\Vdash\dot{\sigma}\subseteq\dot{a}$. Since $\mathbb{P}$ is c.c.c.
there are only countably many possible values of $\dot{a}$, and by taking
supremum of them, we can replace $\dot{a}$ by a canonical name $a$. But note
that $p_{a}\Vdash a\in\dot{\sigma}$. This is a contradiction, and it finishes
the proof for $\mathbb{P}\ast\dot{\mathbb{Q}}$.

Consider now a finite support iteration of an infinite length $\theta$ of
$(\mathcal{M},d)$-c.c. forcings
$\overline{\mathbb{P}}=\\{\mathbb{P}_{\alpha}\ast\dot{\mathbb{Q}}_{\alpha}|\;\alpha<\theta\\}$.
We prove by induction on $\theta$, that $\overline{\mathbb{P}}$ is
$(\mathcal{M},d)$-c.c.. The successor step has just been taken care of, so
suppose that the conclusion holds for any ordinal less than $\theta$, and
$\theta$ is limit. Take any disjoint sequence
$\\{(\overline{p}_{\alpha},\overline{x}_{\alpha})|\;\alpha<\omega_{1}\\}\subseteq\overline{\mathbb{P}}\times(\mathcal{M},d)^{n}$.
We can assume that the supports of conditions $\overline{p}_{\alpha}$ form a
$\Delta$-system with the root $R$, and that for any $\alpha$,
$\operatorname{supp}{\overline{p}_{\alpha}}\setminus R$ is above $R$. Let
$\delta=\max{R}$. There exist two different $\alpha,\beta<\omega_{1}$, for
which the relation $\overline{x}_{\alpha}\circledast\overline{x}_{\beta}$
holds and $\overline{p}_{\alpha}\restriction\delta$ is comparable with
$\overline{p}_{\beta}\restriction\delta$. From the general theory of finite
support iterations it follows that $\overline{p}_{\alpha}$ and
$\overline{p}_{\beta}$ are comparable. ∎

It may look suspicious that in the proof above we never actually used
$\mathbb{P}$ being $(\mathcal{M},d)$-c.c., only c.c.c. However one can verify
that if some c.c.c. forcing forces a poset to be $(\mathcal{M},d)$-c.c., then
it must be $(\mathcal{M},d)$-c.c. itself. So equally good we could have
assumed that $\mathbb{P}$ is c.c.c. The immediate consequence of this
proposition is

######  Lemma 2.7.

It is consistent with
$ZFC+MA(\text{$(\mathcal{M},d)${-c.c.}})+``2^{\omega}=\omega_{2}"$ that
$(\mathcal{M},d)$ is rectangular.

Conveniently, the full Martin’s Axiom will hold in such model. Recall that if
$\mathbb{P}$ is a forcing notion, a set $D\subseteq\mathbb{P}$ is _predense_
if each element of $\mathbb{P}$ is comparable with an element of $D$. A set
$D$ is _predense below $p$_ if each element of $\mathbb{P}$ stronger that $p$
is comparable with an element of $D$.

######  Lemma 2.8.

Let $\mathbb{P}$ be a c.c.c. forcing notion of size $\omega_{1}$. There exists
$p\in\mathbb{P}$ and a family of $\omega_{1}$ many subsets of $\mathbb{P}$,
predense below $p$, such that any filter $G\subseteq\mathbb{P}$ containing $p$
and intersecting all of them is uncountable.

###### Proof.

Enumerate bijectively $\mathbb{P}$ as $\\{p_{\gamma}|\;\gamma<\omega_{1}\\}$.
Let $D_{\alpha}=\\{p_{\gamma}|\;\alpha<\gamma<\omega_{1}\\}$. We aim to find
$p\in\mathbb{P}$ such that uncountably many of sets $D_{\alpha}$ are predense
below $p$ – clearly this will finish the proof. If $p$ with this property
doesn’t exist, then the following assertion holds:

$\forall{\gamma<\omega_{1}}\;\exists{\gamma^{\prime}>\gamma}\;\text{"$D_{\gamma^{\prime}}$
is not predense below $p_{\gamma}$"},$

and consequently

$\forall{\gamma<\omega_{1}}\;\exists{p_{\gamma}^{\prime}\leq
p_{\gamma}}\;\exists{\gamma^{\prime}>\gamma}\;\forall{\eta>\gamma^{\prime}}\;p_{\gamma}^{\prime}\bot
p_{\eta}.$

Using this, we can easily define an uncountable antichain
$\\{p_{\gamma}|\;\gamma\in E\\}$, ensuring at each step of induction that

$\forall{\gamma\in
E}\;\exists{\gamma^{\prime}>\gamma}\;\forall{\eta>\gamma^{\prime}}\;p_{\gamma}\bot
p_{\eta}.$

∎

######  Lemma 2.9.

$MA_{\omega_{1}}(\text{$(\mathcal{M},d)${-c.c.}})$ implies that any family of
pairwise disjoint tuples
$\\{(x_{1}^{\xi},\ldots,x_{n}^{\xi})|\;\xi<\omega_{1}\\}\subseteq(\mathcal{M},d)^{n}$
contains an uncountable subfamily of pairwise alike tuples.

###### Proof.

Let $\mathbb{P}=\\{F\in[\omega_{1}]^{<\omega}|\;\forall{\xi\neq\eta\in
F}\;\overline{x}_{\xi}\circledast\overline{x}_{\eta}\\}$, where
$\overline{x}_{\xi}=(x_{1}^{\xi},\ldots,x_{n}^{\xi})$. The ordering is given
by the reversed inclusion. We claim that $\mathbb{P}$ is
$(\mathcal{M},d)$-c.c.. Fix an uncountable family
$\\{F_{\alpha}|\;\alpha<\omega_{1}\\}\subseteq\mathbb{P}$, and a family of
tuples
$\\{(v^{\alpha}_{1},\ldots,v^{\alpha}_{s})|\;\alpha<\omega_{1}\\}\subseteq(\mathcal{M},d)^{s}$.
Without loss of generality we may assume that

$F_{\alpha}=\\{e_{1},\ldots,e_{k},e^{\alpha}_{k+1},\ldots,e^{\alpha}_{k+m}\\},$

where sets $\\{e^{\alpha}_{k+1},\ldots,e^{\alpha}_{k+m}\\}$ are pairwise
disjoint for different $\alpha$. For each $\alpha$, let
$\overline{y}_{\alpha}\in(\mathcal{M},d)^{n\cdot m+s}$ be a concatenation of
all tuples
$\overline{x}_{e^{\alpha}_{k+1}},\ldots,\overline{x}_{e^{\alpha}_{k+m}}$, and
$(v^{\alpha}_{1},\ldots,v^{\alpha}_{s})$. There exists
$\alpha\neq\beta<\omega_{1}$, such that
$\overline{y}_{\alpha}\circledast\overline{y}_{\beta}$, and we claim that they
witness the fact that $\mathbb{P}$ is $(\mathcal{M},d)$-c.c.. Let us write:

$\overline{y}_{\alpha}=(x_{1}^{1},\ldots,x^{1}_{n},x^{2}_{1},\ldots,x^{2}_{n},\ldots,x^{m}_{1},\ldots,x^{m}_{n},v_{1},\,\ldots,v_{s}),$
$\overline{y}_{\beta}=(y_{1}^{1},\ldots,y^{1}_{n},y^{2}_{1},\ldots,y^{2}_{n},\ldots,y^{m}_{1},\ldots,y^{m}_{n},u_{1},\,\ldots,u_{s}).$

What is clear, is that $(v_{1},\ldots,v_{s})\circledast(u_{1},\ldots,u_{s})$,
and for all $k\leq m$,
$(x_{1}^{k},\ldots,x_{n}^{k})\circledast(y_{1}^{k},\ldots,y_{n}^{k})$. What is
not clear, is that in this case the $\circledast$ relation is "shift-
invariant", i.e. for all $1\leq p\neq r\leq m$ we have
$(x_{1}^{p},\ldots,x_{n}^{p})\circledast(y_{1}^{r},\ldots,y_{n}^{r})$. We will
check that this is the case.

  1. A1

For all $1\leq r\neq p\leq m$, and $1\leq i,j\leq n$, we have

$\displaystyle d(x_{i}^{p},y_{i}^{r})=d(x_{i}^{p},x_{i}^{r})$ by A3 for
$\overline{y}_{\alpha}$ and $\overline{y}_{\beta}$, $\displaystyle
d(x_{i}^{p},x_{i}^{r})=d(x_{j}^{p},x_{j}^{r})$ by A1 for
$(x_{1}^{p},\ldots,x_{n}^{p})$ and $(x_{1}^{r},\ldots,x_{n}^{r})$,
$\displaystyle d(x_{j}^{p},x_{j}^{r})=d(x_{j}^{p},y_{j}^{r})$
$\displaystyle\text{ by A3 for $\overline{y}_{\alpha}$ and
$\overline{y}_{\beta}$}.$

  2. A2

For all $1\leq r\neq p\leq m$, and $1\leq i,j\leq n$, we have

$\displaystyle d(x_{i}^{p},x_{j}^{p})=d(x_{i}^{r},x_{j}^{r})$ by A2 for
$(x_{1}^{p},\ldots,x_{n}^{p})$, $(x_{1}^{r},\ldots,x_{n}^{r})$, $\displaystyle
d(x_{i}^{r},x_{j}^{r})=d(y_{i}^{r},y_{j}^{r})$ by A2 for
$\overline{y}_{\alpha}$, $\overline{y}_{\beta}$.

  3. A3

If $x^{r}_{i}\neq x^{r}_{j}$ then

$\displaystyle d(x_{i}^{r},x_{j}^{r})=d(x_{i}^{r},x_{j}^{p})$ by A3 for
$(x_{1}^{p},\ldots,x_{n}^{p})$, $(x_{1}^{r},\ldots,x_{n}^{r})$, $\displaystyle
d(x_{i}^{r},x_{j}^{p})=d(x_{i}^{r},y_{j}^{p})$ by A3 for
$\overline{y}_{\alpha}$, $\overline{y}_{\beta}$.

Therefore $F_{\alpha}\cup F_{\beta}\in\mathbb{P}$, and this concludes the
proof that $\mathbb{P}$ is $(\mathcal{M},d)$-c.c.. Notice that all singletons
belong to $\mathbb{P}$, so $|\mathbb{P}|=\omega_{1}$. Applying Martin’s Axiom
to the family of predense sets given by the Lemma 2.8, we find an uncountable
filter $G\subseteq\mathbb{P}$. The set
$\\{\overline{x}_{\alpha}|\;\alpha\in\bigcup G\\}$ is an uncountable family of
tuples, and each two of them are alike. ∎

######  Proposition 2.10.

$MA_{\omega_{1}}(\text{$(\mathcal{M},d)${-c.c.}})$ implies that any c.c.c.
partial order of size $\omega_{1}$ satisfies $(\mathcal{M},d)$-c.c..

###### Proof.

Suppose that $\mathbb{P}$ is a c.c.c. partial order of cardinality
$\omega_{1}$, and fix some disjoint family
$\\{(p_{\xi},x_{1}^{\xi},\ldots,x_{n}^{\xi})|\;\xi<\omega_{1}\\}\subseteq\mathbb{P}\times(\mathcal{M},d)^{n}$.
If $MA_{\omega_{1}}(\text{$(\mathcal{M},d)${-c.c.}})$ holds, we can assume
that all tuples $(p_{\xi},x_{1}^{\xi},\ldots,x_{n}^{\xi})$ are pairwise alike,
and since $\mathbb{P}$ is c.c.c. we will find two $p_{\xi}$ and $p_{\eta}$,
which are comparable. ∎

The immediate consequence is

######  Theorem 2.11.

It is consistent with $ZFC+MA+``2^{\omega}=\omega_{2}"$ that $(\mathcal{M},d)$
is rectangular.

######  Theorem 2.12.

Let $(X,d)$ be a rectangular rational metric space of size $\omega_{1}$.
$MA_{\omega_{1}}$ implies that any uncountable 1-1 function $f\subseteq
X\times X$ is an isometry on an uncountable set.

###### Proof.

Let $f\subseteq X\times X$ be an uncountable 1-1 function. Consider the
partial order

$\mathbb{P}_{f}=(\\{E\in[\operatorname{dom}{f}]^{<\omega}|\;f\restriction
E\text{ is an isometry}\\},\subseteq).$

We will check that $\mathbb{P}_{f}$ is c.c.c. Take a sequence
$\\{e_{\xi}|\;\xi<\omega_{1}\\}\subseteq\mathbb{P}_{f}$. Applying
$\Delta$-system Lemma we may assume that

  * •

$\forall\;\xi<\omega_{1}\;|e_{\xi}|=m$,

  * •

$\forall\;\xi\neq\eta<\omega_{1}\;e_{\xi}\cap e_{\eta}=r$,

  * •

$e_{\xi}=(e_{1}^{\xi},\ldots,e_{l}^{\xi},e_{l+1}^{\xi},\ldots,e_{m}^{\xi})$,
where $\\{e_{1}^{\xi},\ldots,e_{l}^{\xi}\\}=r$.

Look at the family of tuples

$\\{(e_{l+1}^{\xi},\ldots,e_{m}^{\xi},f(e_{l+1}^{\xi}),\ldots,f(e_{m}^{\xi}))|\;\xi<\omega_{1}\\}.$

Using for example $\Delta$-system Lemma one can easily trim this sequence so
that all tuples are pairwise disjoint. Now, given that $(X,d)$ is rectangular,
we find $\xi\neq\eta<\omega_{1}$, such that

$(e_{l+1}^{\xi},\ldots,e_{m}^{\xi},f(e_{l+1}^{\xi}),\ldots,f(e_{m}^{\xi}))\circledast(e_{l+1}^{\eta},\ldots,e_{m}^{\eta},f(e_{l+1}^{\eta}),\ldots,f(e_{m}^{\eta})).$

We must check that $e_{\xi}$ and $e_{\eta}$ are comparable, that is
$f\restriction(e_{\xi}\cup e_{\eta})$ is an isometry. But notice that for
$i\neq j=l+1,\ldots,m$,

$d(e_{i}^{\xi},e_{j}^{\eta})=d(e_{i}^{\xi},e_{j}^{\xi})=d(f(e_{i}^{\xi}),f(e_{j}^{\xi}))=d(f(e_{i}^{\xi}),f(e_{j}^{\eta})).$

This proves that $e_{\xi}\cup e_{\eta}\in\mathbb{P}_{f}$.

Notice that all singletons belong to $\mathbb{P}_{f}$, so
$|\mathbb{P}|=\omega_{1}$. Applying Martin’s Axiom to the family of predense
sets given by the Lemma 2.8, we find an uncountable filter
$G\subseteq\mathbb{P}_{f}$. The set $\bigcup\\{E|\;E\in G\\}$ is an
uncountable set on which $f$ is an isometry. ∎

######  Corollary 2.13.

It is consistent with $ZFC+MA+``2^{\omega}=\omega_{2}"$ that there exists an
uncountable, separable (even hereditarily separably saturated) rational metric
space $(X,d)$ such that each uncountable function $f\subseteq X\times X$ is an
isometry on an uncountable set.

###  2.2 Rectangular Models for General Binary Relations

The reader might have noticed that in the previous section the triangle
inequality for the space $(\mathcal{M},d)$ was never applied. The crucial
property we used was a variant of the SP, which ensures that "remainders" will
be alike (see Lemma 2.2). In this section we will define a version of the SP
that allows to proceed with the proof of Theorem 2.12 in case of other classes
of structures. One assumption which seems hard to be removed is that the
language consists only of binary relational symbols.

Each language consisting of finitely many binary relational symbols can be
identified with a finite coloring of ordered pairs – given a model $A$, we
assign to each element of $A^{2}$ its isomorphism type. There are only
finitely many symbols in the language, so this coloring is indeed finite, and
moreover, it determines the model $A$ completely. Also, any function is a
homomorphism precisely when it preserves this coloring. This observation
allows to generalize results from Section 2 to other classes, besides metric
spaces. In fact, the finiteness of language is not relevant as long as there
are only countably many isomorphism types of 2-element models. Let
$\mathcal{K}$ be some class of structures in a countable language
$\\{\mathcal{R}_{i}\\}_{i<\omega}$ consisting of binary relational symbols.
Assume also that $\mathcal{K}$ has only countably many isomorphism types of
finite models. Let $c$ be the corresponding coloring of pairs in models from
$\mathcal{K}$ – by the remark above we may forget about the relational
symbols, and think of models from $\mathcal{K}$ as having only one "relation",
namely $c$. We introduce the $\circledast$ relation by axioms similar to the
metric case, but unlike metrics, the coloring $c$ might not be symmetric. This
is the only significant difference.

######  Definition 2.14.

Let $X\in\mathcal{K}$, and $(x_{1},\ldots,x_{n}),(y_{1},\ldots,y_{n})\in
X^{n}$ be disjoint. We will say that they are _alike_ , and write
$(x_{1},\ldots,x_{n})\circledast(y_{1},\ldots,y_{n})$, if the following axioms
are satisfied

  1. A1a

$\forall\;i,j=1,\ldots,n\;c(x_{i},y_{i})=c(x_{j},y_{j})$

  2. A1b

$\forall\;i,j=1,\ldots,n\;c(y_{i},x_{i})=c(y_{j},x_{j})$

  3. A2a

$\forall\;i,j=1,\ldots,n\;c(x_{i},x_{j})=c(y_{i},y_{j})$

  4. A3a

$\forall\;i,j=1,\ldots,n\;(x_{i}\neq x_{j}\implies
c(x_{i},x_{j})=c(x_{i},y_{j})=c(y_{i},x_{j}))$

If all relations $\mathcal{R}_{k}$ are anti-reflexive ($\forall
x\;\lnot\mathcal{R}_{k}(x,x)$), then we can omit the clause $(x_{i}\neq
x_{j})\implies$ in A3a. It is standard to check that

$(x_{1},\ldots,x_{n})\circledast(y_{1},\ldots,y_{n})\iff(y_{1},\ldots,y_{n})\circledast(x_{1},\ldots,x_{n}).$

######  Definition 2.15.

$X\in\mathcal{K}$ is _rectangular_ if $|X|>\omega$, and for any family of
pairwise disjoint tuples
$\\{(x_{1}^{\xi},\ldots,x_{n}^{\xi})|\;\xi<\omega_{1}\\}\subseteq X^{n}$,
there exist $\xi\neq\eta<\omega_{1}$, such that
$(x_{1}^{\xi},\ldots,x_{n}^{\xi})\circledast(x_{1}^{\eta},\ldots,x_{n}^{\eta}).$

######  Definition 2.16.

$\mathcal{K}$ has the _Rectangular Splitting Property_ (RSP) if for all
$R\in\mathcal{K}$, for all pairs of isomorphic extensions $R\subseteq X$,
$R\subseteq Y$, with the corresponding isomorphism $h:X\rightarrow Y$, there
exists $Z\in\mathcal{K}$, with the universe $X\cup Y$, such that for any
sequence $(x_{1},\ldots,x_{n})$ enumerating bijectively $X\setminus R$, $Z$
satisfies $(x_{1},\ldots,x_{n})\circledast(h(x_{1}),\ldots,h(x_{n}))$.

The RSP ensures the conclusion of Lemma 2.2. Moreover, since the definition of
$\circledast$ relation is independent of the ordering of the tuples, if there
exists an enumeration $(x_{1},\ldots,x_{n})$ like above, it can be replaced by
any other enumeration, even not 1-1.

######  Theorem 2.17.

If $\mathcal{K}$ has the RSP then
$\operatorname{Fn}(\kappa,\mathcal{K},\omega)$ forces the generic structure to
be rectangular, for any uncountable cardinal $\kappa$.

###### Proof.

Exactly like the proof of Proposition 2.3. ∎

Let us fix a rectangular model $(\mathcal{X},c)$. The $(\mathcal{X},c)$-c.c.
is defined in the same way as in Definition 2.4:

######  Definition 2.18.

A partial order $\mathbb{P}$ satisfies _$(\mathcal{X},c)$ -c.c._ if given any
natural number $n>0$, for each disjoint family
$\\{(p_{\xi},x_{1}^{\xi},\ldots,x_{n}^{\xi})|\;\xi<\omega_{1}\\}\subseteq\mathbb{P}\times(\mathcal{X},c)^{n}$,
there exist $\xi\neq\eta<\omega_{1}$, such that $p_{\xi}$ and $p_{\eta}$ are
comparable, and
$(x_{1}^{\xi},\ldots,x_{n}^{\xi})\circledast(x_{1}^{\eta},\ldots,x_{n}^{\eta})$.

######  Proposition 2.19.

If $\mathbb{P}$ satisfies $(\mathcal{X},c)$-c.c. then $\mathbb{P}\Vdash\text{
"$(\mathcal{X},c)$ is rectangular".}$

###### Proof.

Exactly like the proof of Proposition 2.5. ∎

######  Proposition 2.20.

$MA_{\omega_{1}}(\text{$(\mathcal{X},c)$-c.c.})$ implies that any family of
pairwise disjoint tuples
$\\{(x_{1}^{\xi},\ldots,x_{n}^{\xi})|\;\xi<\omega_{1}\\}\subseteq(\mathcal{X},c)^{n}$
contains an uncountable subfamily of pairwise alike tuples.

###### Proof.

Same as Lemma 2.9. ∎

What follows, is a generalization of Theorem 2.11.

######  Theorem 2.21.

It is consistent with $ZFC+MA+``2^{\omega}=\omega_{2}"$ that $(\mathcal{X},c)$
is rectangular.

The proof that the $(\mathcal{X},c)$-c.c. is preserved under finite support
iterations is also the same.

######  Proposition 2.22.

Let $(X,c)\in\mathcal{K}$ be a rectangular model of size $\omega_{1}$.
$MA_{\omega_{1}}$ implies that any uncountable 1-1 function $f\subseteq
X\times X$ is a homomorphism on an uncountable set.

###### Proof.

Almost exactly like the proof of Theorem 2.12 – the only difference is that we
write $c$ instead of $d$, _isomorphism_ instead of _isometry_ , and in the end
use A1a and A1b instead of A1, since $c$ might not be symmetric. ∎

######  Proposition 2.23.

The classes of graphs, directed graphs, tournaments, linear orders, and
partial orders have the RSP.

###### Proof.

We will prove the RSP for linear and partial orders. Arguments for other
classes are easy and left to the reader. For each partial order $\leq$ there
exists a corresponding quasi-ordering relation $<$, which is anti-reflexive.

Suppose we have a diagram of linear quasi-orders $R,X,Y$, and $h:X\rightarrow
Y$, like in the definition of the RSP. We define a quasi-ordering on $Z=X\cup
Y$, extending both $<_{X}$ and $<_{Y}$, by conditions:

  * •

$\forall{i<\omega}\;(x_{i}<h(x_{i}))$,

  * •

$\forall{i\neq j<\omega}\;(x_{i}<h(x_{j})\iff x_{i}<_{X}x_{j}).$

Clearly $<$ is an anti-reflexive relation on $Z$. For checking transitivity we
must go through several (somewhat boring) cases.

  1. 1.

$x_{i}<h(x_{j}),\;h(x_{j})<x_{k}$. Either $x_{i}=x_{j}$ or $x_{i}<x_{j}$. In
the first case $h(x_{i})<x_{k}$, and so $x_{i}<x_{k}$. In the second,
$x_{i}<x_{k}$, and $x_{i}<x_{k}$ follows from transitivity of $<$ on $X$.

  2. 2.

$h(x_{i})<x_{j},\;x_{j}<x_{k}$. In this case $x_{i}<x_{j}$, so $x_{i}<x_{k}$,
and $h(x_{i})<x_{k}$.

  3. 3.

$x_{i}<x_{j},\;x_{j}<h(x_{k})$. Either $x_{j}=x_{k}$ or $x_{j}<x_{k}$. In both
cases $x_{i}<x_{k}$, so $x_{i}<h(x_{k})$.

  4. 4.

$h(x_{i})<h(x_{j}),\;h(x_{j})<x_{k}$. In this case $x_{i}<x_{j}$, and
$x_{j}<x_{k}$. By transitivity $x_{i}<x_{k}$, and $h(x_{i})<x_{k}$ follows.

  5. 5.

$x_{i}<h(x_{j}),\;h(x_{j})<h(x_{k})$. If $x_{i}<x_{j}$, then we proceed like
before. If $x_{i}=x_{j}$, $h(x_{i})<h(x_{k})$. It follows that $x_{i}<x_{k}$,
and $x_{i}<h(x_{k})$.

  6. 6.

$h(x_{i})<x_{j},\;x_{j}<h(x_{k})$. We see that $x_{i}<x_{j}$. If
$x_{j}<x_{k}$, we use transitivity of $<$ on $X$. If $x_{j}=x_{k}$, then
$h(x_{i})<x_{k}$, and so $x_{i}<x_{k}$. It follows that $h(x_{i})<h(x_{k})$.

The proof for partial orders is strictly simpler – we define the quasi-
ordering by conditions:

  * •

$\forall{i<\omega}\quad x_{i}\text{ is incomparable with }h(x_{i})$,

  * •

$\forall{i,j<\omega}\quad x_{i}<h(x_{j})\iff x_{i}<x_{j},$

  * •

$\forall{i,j<\omega}\quad\lnot h(x_{i})<x_{j}.$

Verification of transitivity is a run through the same cases, except this time
we do not have to care if $x_{i},x_{j},x_{k}$ are distinct. ∎

For each class $\mathcal{K}$ having the RSP, one can prove a variant of
Corollary 2.13. We could of course state a general theorem, after introducing
a notion of "separable model" for arbitrary binary relational class. We will
refrain from doing so, and provide just two such variants as an illustration.
Interested reader will easily formulate corresponding results for tournaments,
directed graphs, etc.

######  Theorem 2.24.

Each of the following is consistent with $ZFC+MA+``2^{\omega}=\omega_{2}"$:

  1. 1.

There exists a graph $G$ of size $\omega_{1}$, with a countable subset
$D\subseteq G$, satisfying the following properties:

     * •

For all pairs of disjoint finite subsets $A,B\subseteq G$, there exists a
vertex $d\in D$, connected with each point in $A$, and with no point in $B$.

     * •

Each uncountable 1-1 function $f\subseteq G\times G$ is a graph homomorphism
on an uncountable set.

  2. 2.

(Avraham-Shelah, [2]) There exists a separable, $\omega_{1}$-dense linear
order
$(L,\leq)$, such that each uncountable 1-1 function $f\subseteq L\times L$ is
order preserving on an uncountable subset.

The first point of this theorem is also a consequence of Theorem 2.12 – we can
turn a metric space into a graph by connecting two vertices iff the distance
between them is $\geq 1$.

###  2.3 HSS Models

After forcing with $\operatorname{Fn}(\omega_{1},\mathcal{LO},\omega)$, each
infinite subset of $\omega_{1}$ from the ground model becomes a dense subset
of the generic structure. This can be checked by a standard density argument,
and analogous property holds for other classes. Specifically, uncountable
generic models contain many countable subsets which realize every finite type.
We present one way to capture this property. It will be useful in proving
classification theorems in the next Section.

######  Definition 2.25.

Let $X$ be a structure in some relational language. A subset $D\subseteq X$ is
a _saturating subset_ if for any finite subset $E\subseteq X$, for any single-
point extension $E\subseteq E\cup\\{f\\}$, there exists $d\in D$ such that the
following diagram commutes

${E\cup\\{f\\}}$${E}$${E\cup\\{d\\}}$$\scriptstyle{f\mapsto d}$

To phrase it shortly, every finite type can be realized in $D$. In case of
metric spaces, it this is just to say that any finite configuration of
distances from points in $X$ can be realized inside $D$. A saturating subset
of a metric space is dense in a very strong sense.

######  Definition 2.26.

Let $X$ be any structure in a relational language.

  1. 1.

$X$ is _separably saturated_ if it has a countable saturating subset.

  2. 2.

$X$ is _hereditarily separably saturated_ (HSS) if for any countable subset
$A\subseteq X$, $X\setminus A$ is separably saturated.

######  Proposition 2.27.

If $\mathcal{K}$ is a class with the RSP then
$\operatorname{Fn}(\kappa,\mathcal{K},\omega)$ forces the generic structure to
be HSS, for any uncountable cardinal $\kappa$.

###### Proof.

A standard density argument shows that every infinite set from the ground
model is a saturating subset. ∎

##  3 Classification Results

If the uncountable models we are considering are to resemble Fraïssé limits,
we should be able to do some kind of "back-and-forth" arguments, like in the
classical theory. There is no way inductive arguments can work, but thanks to
Theorem 2.21 we can rely on Martin’s Axiom instead of induction.

###  3.1 HSS Rectangular Metric Spaces

We will be looking at metric spaces with distances in a given countable set
$K\subseteq[0,\infty)$.

######  Theorem 3.1.

Assume $MA_{\omega_{1}}$. Let $(X,d)$ be any rectangular HSS metric space of
size $\omega_{1}$, with distances in $K$. Let $Y\subseteq X$ be any HSS
uncountable subspace. Then $X$ and $Y$ are isometric.

###### Proof.

Since $X$ is hereditarily separably saturated, we can decompose it into a
disjoint union of countable saturating subsets
$\\{X_{\alpha}\\}_{\alpha<\omega_{1}}$. Of course we can do the same with $Y$,
so let us write $Y=\displaystyle{\bigcup_{\alpha<\omega_{1}}Y_{\alpha}}$. Let
$\mathbb{P}$ consist of finite partial isometries between $X$ and $Y$, which
map elements from $X_{\alpha}$ to $Y_{\alpha}$ for all $\alpha<\omega_{1}$. It
is standard to check that the following sets are dense for $x\in X$, $y\in Y$:

$D_{x}=\\{p\in\mathbb{P}|\;x\in\operatorname{dom}{p}\\},$
$E_{y}=\\{p\in\mathbb{P}|\;y\in\operatorname{rg}{p}\\}.$

We are left with the task of verifying the c.c.c. property. Fix any
uncountable subset $\\{p_{\gamma}|\;\gamma<\omega_{1}\\}\subseteq\mathbb{P}$.
Using $\Delta$-system Lemma we can write

$\operatorname{dom}{p_{\gamma}}=(x_{1},\ldots,x_{k},x_{k+1}^{\gamma},\ldots,x_{m}^{\gamma}),$
$\operatorname{rg}{p_{\gamma}}=(y_{1},\ldots,y_{k},y_{k+1}^{\gamma},\ldots,y_{m}^{\gamma}),$

where tuples $(x_{k+1}^{\gamma},\ldots,x_{m}^{\gamma})$ are pairwise disjoint,
and moreover $p_{\gamma}(x_{i})=y_{i}$, and
$p_{\gamma}(x_{i}^{\gamma})=y_{i}^{\gamma}$ for each $\gamma<\omega_{1}$.
Recall that $X$ is rectangular, so we can find $\xi\neq\eta<\omega_{1}$, such
that

$(x^{\xi}_{k+1},\ldots,x_{m}^{\xi},y_{k+1}^{\xi},\ldots,y_{m}^{\xi})\circledast(x^{\eta}_{k+1},\ldots,x_{m}^{\eta},y_{k+1}^{\eta},\ldots,y_{m}^{\eta}).$

If $k<i\neq j\leq m$, then

$\displaystyle d(x_{i}^{\eta},x_{j}^{\xi})=$ $\displaystyle
d(x_{i}^{\eta},x_{j}^{\eta})=$ $\displaystyle d(y_{i}^{\eta},y_{j}^{\eta})=$
$\displaystyle d(y_{i}^{\eta},y_{j}^{\xi})$

Also for $k<i\leq m$

$\displaystyle d(x_{i}^{\eta},x_{i}^{\xi})=$ $\displaystyle
d(y_{i}^{\eta},y_{i}^{\xi})$

Clearly $p_{\xi}\cup p_{\eta}\in\mathbb{P}$. ∎

######  Corollary 3.2.

Assume $MA_{\omega_{1}}$. Let $(X,d)$ be any rectangular HSS metric space of
size $\omega_{1}$, with distances in $K$. $X$ can be decomposed into a
disjoint union of $\lambda$ many its isometric copies for any
$\lambda\in\\{2,\ldots,\omega_{1}\\}$.

###### Proof.

Let $X=\displaystyle{\bigcup_{\alpha<\omega_{1}}X_{\alpha}}$ be a
decomposition of $X$ into countable saturating subsets. Let
$\omega_{1}=\displaystyle{\bigcup_{\alpha<\lambda}A_{\alpha}}$ be a
decomposition of $\omega_{1}$ into pairwise disjoint uncountable subsets. For
any $\gamma<\lambda$ the space

$X_{\gamma}=\displaystyle{\bigcup_{\alpha\in A_{\gamma}}X_{\alpha}}$

is isometric to $(X,d)$. ∎

After taking $X=Y$ and obvious adjustments to the forcing used, we obtain the
classical homogeneity.

######  Corollary 3.3.

Assume $MA_{\omega_{1}}$. If $(X,d)$ is any rectangular HSS metric space of
size $\omega_{1}$, with distances in $K$, then any finite partial isometry of
$(X,d)$ extends to a full isometry.

Still, this kind of homogeneity is not sufficient to prove uniqueness, like
for the rational Urysohn space.

######  Theorem 3.4.

Assume $MA_{\omega_{1}}$. If there exists a rectangular HSS rational metric
space of size $\omega_{1}$, then there exist infinitely many pairwise non-
isometric such spaces.

###### Proof.

If $(X,d)$ is a rectangular, hereditarily separably saturated rational metric
space of size $\omega_{1}$, we introduce a family of metrics on $X$

$d_{k}(x,y)=k\cdot d(x,y),$

for positive integers $k$. If $k<l$ are positive integers, the spaces
$(X,d_{k})$ and $(X,d_{l})$ are not isometric. Indeed, if $f:X\hookrightarrow
X$ is a bijection, then by Theorem 2.12, $f$ is an isometry of the space
$(X,d)$ on some pair of distinct points $x,y\in X$. Then $d_{k}(x,y)=k\cdot
d(x,y)=k\cdot d(f(x),f(y))<l\cdot d(f(x),f(y))=d_{l}(f(x),f(y))$. ∎

###  3.2 HSS Rectangular Graphs

If we take $K=\\{0,1,2\\}$, metric spaces with distances in $K$ are graphs –
think of two points in distance $1$ as connected, and two points in distance
$2$ as not connected. Notions of a saturating set and separably saturated
space translate to the following.

######  Definition 3.5.

Let $G$ be a graph. A subset $D\subseteq G$ is a _saturating subset_ of $G$ if
for any pair of disjoint finite subsets $A,B\subseteq G$, there exists $d\in
D\setminus(A\cup B)$ which is connected with each vertex in $A$ and with no
vertex in $B$.

######  Definition 3.6.

If $G$ is any graph, then

  1. 1.

$G$ is _separably saturated_ if it has a countable saturating subset.

  2. 2.

$G$ is _hereditarily separably saturated_ (HSS) if for any countable subset
$E\subseteq G$, the graph $G\setminus E$ is separably saturated.

######  Proposition 3.7.

$\operatorname{Fn}(\omega_{1},Graphs,\omega)\Vdash\text{"$(\omega_{1},\dot{E})$
is a rectangular HSS graph"}$.

###### Proof.

Rectangularity is a consequence of Theorem 2.17, HSS follows from Proposition
2.27. ∎

From Theorem 3.1, with $K=\\{0,1,2\\}$, it follows that HSS rectangular graphs
are in certain sense minimal.

######  Theorem 3.8.

Assume $MA_{\omega_{1}}$. If $G$ is a HSS rectangular graph of size
$\omega_{1}$, then each uncountable HSS subgraph of $G$ is isomorphic with
$G$.

######  Theorem 3.9.

Assume $MA_{\omega_{1}}$. If $G$ and $H$ are two HSS rectangular graphs of
size $\omega_{1}$, then $G\simeq H$ if and only if $G$ and $H^{c}$ do not
contain a common uncountable subgraph ($H^{c}$ denotes the complement of $H$).

###### Proof.

"$\Rightarrow$." We must show that $G$ and $G^{c}$ do not contain a common
uncountable subgraph. Fix arbitrary graph $F$ of size $\omega_{1}$, and
suppose towards contradiction that there exists a pair of embeddings
$i:F\hookrightarrow G$, $j:F\hookrightarrow G^{c}$. The partial function given
by $i(\alpha)\mapsto j(\alpha)$ is a bijection between uncountable subsets of
$G$. By Proposition 2.22 it is a homomorphism on some pair of points
$\alpha\neq\beta$. This contradicts the choice of $i$ and $j$.

"$\Leftarrow$." Assume that there is no uncountable graph which embeds both
into $G$ and $H$. We proceed like in the proof of Theorem 3.1. $G$ and $H$ are
HSS, so we can decompose them into disjoint unions of countable saturating
subsets $\\{G_{\alpha}\\}_{\alpha<\omega_{1}}$, and
$\\{H_{\alpha}\\}_{\alpha<\omega_{1}}$ respectively. Let $\mathbb{P}$ consist
of finite partial isomorphisms between $G$ and $H$, which map elements from
$G_{\alpha}$ to $H_{\alpha}$ for all $\alpha<\omega_{1}$. The following sets
are dense for $g\in G$, $h\in H$:

$D_{g}=\\{p\in\mathbb{P}|\;g\in\operatorname{dom}{p}\\},$
$E_{h}=\\{p\in\mathbb{P}|\;h\in\operatorname{rg}{p}\\}.$

We verify the c.c.c. property. Fix any uncountable subset
$\\{p_{\gamma}|\;\gamma<\omega_{1}\\}\subseteq\mathbb{P}$. Using
$\Delta$-system Lemma we can write

$\operatorname{dom}{p_{\gamma}}=(x_{1},\ldots,x_{k},x_{k+1}^{\gamma},\ldots,x_{m}^{\gamma}),$
$\operatorname{rg}{p_{\gamma}}=(y_{1},\ldots,y_{k},y_{k+1}^{\gamma},\ldots,y_{m}^{\gamma}),$

where tuples $(x_{k+1}^{\gamma},\ldots,x_{m}^{\gamma})$ are pairwise disjoint,
and moreover $p_{\gamma}(x_{i})=y_{i}$, and
$p_{\gamma}(x_{i}^{\gamma})=y_{i}^{\gamma}$ for each $\gamma<\omega_{1}$. By
rectangularity and Proposition 2.20 we can assume that tuples

$\\{(x_{k+1}^{\gamma},\ldots,x_{m}^{\gamma})|\;\gamma<\omega_{1}\\},$

as well as

$\\{(y_{k+1}^{\gamma},\ldots,y_{m}^{\gamma})|\;\gamma<\omega_{1}\\}$

are pairwise alike.

For all $k<i\neq j\leq m$, and $\xi\neq\eta<\omega_{1}$ we have

$\displaystyle x_{i}^{\eta}\;E\;x_{j}^{\xi}\iff$ $\displaystyle
x_{i}^{\eta}\;E\;x_{j}^{\eta}\iff$ $\displaystyle
y_{i}^{\eta}\;E\;y_{j}^{\eta}\iff$ $\displaystyle
y_{i}^{\eta}\;E\;y_{j}^{\xi}$

What remains is the case $i=j$. But look at the function given by
$x_{k+1}^{\eta}\mapsto y_{k+1}^{\eta}$, for $\eta<\omega_{1}$. This is a
bijection between an uncountable subgraph of $G$ and an uncountable subgraph
of $H$, or equivalently, $H^{c}$. By our assumption, it cannot be a
homomorphism into $H^{c}$. We conclude that there are $\eta\neq\xi<\omega_{1}$
such that

$x_{k+1}^{\eta}\;E\;x_{k+1}^{\xi}\iff y_{k+1}^{\eta}\;E\;y_{k+1}^{\xi},$

and by rectangularity

$x_{i}^{\eta}\;E\;x_{i}^{\xi}\iff y_{i}^{\eta}\;E\;y_{i}^{\xi},$

for all $i=k+1,\ldots,m$. Clearly $p_{\xi}\cup p_{\eta}\in\mathbb{P}$. ∎

######  Corollary 3.10.

Assume $MA_{\omega_{1}}$. If there exists a HSS rectangular graph of size
$\omega_{1}$ then it is unique up to taking the complement.

###### Proof.

Fix two HSS rectangular graphs $G$ and $H$, both of size $\omega_{1}$. It is
sufficient to prove that either no uncountable graph $F$ can be embedded both
into $G$ and $H$, or no uncountable graph $F$ can be embedded both into $G$
and $H^{c}$. Suppose towards contradiction that $F_{0},F_{1}\subseteq G$ are
uncountable subgraphs, and there exist embeddings $i_{0}:F_{0}\hookrightarrow
H$, $i_{1}:F_{1}\hookrightarrow H^{c}$. The function given by $i_{0}(f)\mapsto
i_{1}(f)$ is a bijection between uncountable subsets of $H$. By Proposition
2.22, on some two points it must be a homomorphism. But this contradicts the
choice of $i_{0}$ and $i_{1}$. ∎

######  Theorem 3.11.

Assume $MA_{\omega_{1}}$. If $G$ is a rectangular graph of size $\omega_{1}$,
then either $G$ contains an uncountable clique or uncountable anticlique.

###### Proof.

In the light of Proposition 2.22, $G$ clearly can’t contain both. Assume that
$G$ doesn’t contain an uncountable anticlique. We can represent $G$ as
$(\omega_{1},E)$, and consider the partial order

$\mathbb{P}=\\{F\subseteq\omega_{1}|\;F\text{ is a finite clique in }G\\},$

ordered by reversed inclusion. If we can show that $\mathbb{P}$ is c.c.c,
Lemma 2.8 will provide us with an uncountable clique in $G$. Suppose that
$\\{F_{\xi}|\;\xi<\omega_{1}\\}$ is an uncountable subset of $\mathbb{P}$. We
can write

$F_{\xi}=(f_{1},\ldots,f_{k},f_{k+1}^{\xi},\ldots,f_{m}^{\xi}),$

where tuples $(f_{k+1}^{\xi},\ldots,f_{m}^{\xi})$ are pairwise disjoint. By
the virtue of Martin’s Axiom, and Proposition 2.20, we can also assume that
they are pairwise alike. By our assumption the set
$\\{f_{k+1}^{\xi}|\;\xi<\omega_{1}\\}$ is not an anticlique, so we will find
$\xi\neq\eta<\omega_{1}$, such that $f_{k+1}^{\eta}\;E\;f_{k+1}^{\xi}$. It is
now standard to check that $F_{\eta}\cup F_{\xi}\in\mathbb{P}$. ∎

###  3.3 Separable $\omega_{1}$-dense Linear Orders

What do rectangular linear orders look like? After unwinding the axioms for
the $\circledast$ relation, we see that
$(x_{1},\ldots,x_{n})\circledast(y_{1},\ldots,y_{n})$ translates to the
following three axioms:

  * A1c

$\forall\;i,j=1,\ldots,n\;(x_{i}<y_{i}\iff x_{j}<y_{j})$

  * A2c

$\forall\;i,j=1,\ldots,n\;(x_{i}<x_{j}\iff y_{i}<y_{j})$

  * A3c

$\forall\;i,j=1,\ldots,n\;((x_{i}\neq x_{j})\implies(x_{i}<x_{j}\iff
x_{i}<y_{j}\iff y_{i}<x_{j}))$

If we omitted A3c, we would obtain what the authors of [1] call an _increasing
order_ (actually, one can show that in the class of separable, dense linear
orders these two notions coincide). An order added by
$\operatorname{Fn}(\omega_{1},\mathcal{LO},\omega)$ is a rectangular,
separable, $\omega_{1}$-dense linear order, which under $MA_{\omega_{1}}$ is
also homogeneous. $MA_{\omega_{1}}$ imposes a great deal of regularity on the
class of separable, homogeneous $\omega_{1}$-dense linear orders – for example
two such orderings are isomorphic precisely when they are bi-embeddable.
Implications of $MA_{\omega_{1}}$ for this class, as well as other axioms like
$OCA_{ARS}$, have been extensively studied in [1]. Not surprisingly, many
properties of rectangular linear orders resemble those of graphs.

######  Theorem 3.12.

Assume $MA_{\omega_{1}}$, and suppose that $L$ is a separable,
$\omega_{1}$-dense, rectangular linear order. If $K$ is any other separable,
$\omega_{1}$-dense, rectangular linear order, then $K\simeq L$ if and only if
$K$ and $L^{*}$ do not contain a common uncountable suborder ($L^{*}$ denotes
$L$ with the reversed ordering).

###### Proof.

"$\Rightarrow$." We must show that there is no uncountable strictly decreasing
function $f\subseteq L\times L$. But this follows directly from Proposition
2.22.

"$\Leftarrow$." Assume that there is no uncountable linear order which embeds
both into $L$ and $L^{*}$. We proceed like in the proofs of Theorems 3.1 and
3.9. We can decompose $L$ and $K$ into disjoint unions of countable dense
subsets $\\{L_{\alpha}\\}_{\alpha<\omega_{1}}$, and
$\\{K_{\alpha}\\}_{\alpha<\omega_{1}}$ respectively. Let $\mathbb{P}$ consist
of finite partial isomorphisms between $L$ and $K$ which map elements from
$K_{\alpha}$ to $L_{\alpha}$, for all $\alpha<\omega_{1}$. The following sets
are dense for $l\in L$, $k\in K$:

$D_{k}=\\{p\in\mathbb{P}|\;k\in\operatorname{dom}{p}\\},$
$E_{l}=\\{p\in\mathbb{P}|\;l\in\operatorname{rg}{p}\\}.$

We verify the c.c.c. property. Fix any uncountable subset
$\\{p_{\gamma}|\;\gamma<\omega_{1}\\}\subseteq\mathbb{P}$. Using
$\Delta$-system Lemma, we can write

$\operatorname{dom}{p_{\gamma}}=(x_{1},\ldots,x_{k},x_{k+1}^{\gamma},\ldots,x_{m}^{\gamma}),$
$\operatorname{rg}{p_{\gamma}}=(y_{1},\ldots,y_{k},y_{k+1}^{\gamma},\ldots,y_{m}^{\gamma}),$

where tuples $(x_{k+1}^{\gamma},\ldots,x_{m}^{\gamma})$ are pairwise disjoint,
and moreover $p_{\gamma}(x_{i})=y_{i}$, and
$p_{\gamma}(x_{i}^{\gamma})=y_{i}^{\gamma}$, for each $\gamma<\omega_{1}$. By
rectangularity and Proposition 2.20 we can assume, that tuples

$\\{(x_{k+1}^{\gamma},\ldots,x_{m}^{\gamma})|\;\gamma<\omega_{1}\\},$

as well as

$\\{(y_{k+1}^{\gamma},\ldots,y_{m}^{\gamma})|\;\gamma<\omega_{1}\\},$

are pairwise alike.

For all $k<i\neq j\leq m$, and $\xi\neq\eta<\omega_{1}$ we have

$\displaystyle x_{i}^{\eta}<x_{j}^{\xi}\iff$ $\displaystyle
x_{i}^{\eta}<x_{j}^{\eta}\iff$ $\displaystyle y_{i}^{\eta}<y_{j}^{\eta}\iff$
$\displaystyle y_{i}^{\eta}<y_{j}^{\xi}$

What remains is the case $i=j$. Look at the function given by
$x_{k+1}^{\eta}\mapsto y_{k+1}^{\eta}$, for $\eta<\omega_{1}$. This is a
bijection between an uncountable subset of $L$ and an uncountable subset of
$K$. By our assumption it cannot be decreasing, so there are
$\eta\neq\xi<\omega_{1}$ such that

$x_{k+1}^{\eta}<x_{k+1}^{\xi}\iff y_{k+1}^{\eta}<y_{k+1}^{\xi},$

and by rectangularity

$x_{i}^{\eta}\;<\;x_{i}^{\xi}\iff y_{i}^{\eta}\;<\;y_{i}^{\xi},$

for all $i=k+1,\ldots,m$. Clearly $p_{\xi}\cup p_{\eta}\in\mathbb{P}$. ∎

Just like in the case of graphs, one can easily prove

######  Corollary 3.13.

Assume $MA_{\omega_{1}}$. If there exists a rectangular, separable,
$\omega_{1}$-dense linear order then it is unique up to reversing the order.

These orders are also mimimal in the same sense as metric spaces from Theorem
3.1. The reader will have no difficulty in adjusting its proof to obtain

######  Theorem 3.14.

Assume $MA_{\omega_{1}}$ and let $K$, $L$ be a pair of separable,
$\omega_{1}$-dense linear orders. If $K$ embeds into $L$, and $L$ is
rectangular, then $L$ and $K$ are isomorphic.

##  4 More About Rectangularity

We will be considering models of the form $\chi=(\omega_{1},c)$, where
$c:\omega_{1}\times\omega_{1}\rightarrow K$ for some, usually finite, set $K$.
A set $A\subseteq\omega_{1}$ is called _monochromatic_ if

$c\restriction A\times A\setminus\\{(a,a)|\;a\in A\\}$

is constant. A set $A\subseteq\omega_{1}$ _hits_ a color $k$, if there are
points $a_{0}\neq a_{1}\in A$ for which $c(a_{0},a_{1})=k$. If $c$ will be
symmetric, we will regard it as a function with the domain $[\omega_{1}]^{\leq
2}\setminus\\{\emptyset\\}$. By a _rectangle_ we understand a set of the form
$I\times J$, for $I,J\subseteq\omega_{1}$.

######  Theorem 4.1.

Assume $MA_{\omega_{1}}$. If $\chi$ is a rectangular model in a language
consisting of finitely many symmetric binary relations, then $\chi$ is a
countable union of monochromatic sets.

######  Lemma 4.2.

Under the hypothesis of Theorem 4.1, there exists exactly one color $k\in K$
that is hit on every uncountable subset of $\omega_{1}$.

###### Proof.

We proceed by induction on $|K|$. For $|K|=1$ the conclusion is obvious, so
let us assume that $|K|>1$, and fix any $k_{0}\in K$. First, we show that at
least one such color exists. If every uncountable set $X\subseteq\omega_{1}$
hits $k_{0}$, we are done. Otherwise, there exists an uncountable set $X$, for
which we have

$c\restriction[X]^{2}:\;[X]^{2}\rightarrow K\setminus\\{k_{0}\\}.$

Notice that any uncountable subset of a rectangular model is rectangular
itself. Therefore, by the induction hypothesis, there exists some color
$k_{1}\in K\setminus\\{k_{0}\\}$, that is hit on every uncountable subset of
$X$. We will show that $k_{1}$ is also hit on every uncountable subset of
$\omega_{1}$. Indeed, fix an uncountable set $A\subseteq\omega_{1}$. By
Proposition 2.22, any bijection $\phi:A\hookrightarrow X$ preserves the
coloring $c$ on some uncountable set $A^{\prime}\subseteq A$. But we know that
$\phi[A^{\prime}]$ hits $k_{1}$, and so does $A^{\prime}$. By applying
Martin’s Axiom to the set of finite $k_{1}$-monochromatic sets, we see that
$X$ contains an uncountable $k_{1}$-monochromatic set (see the proof of
Theorem 3.11). This shows that the conclusion cannot hold for any color other
than $k_{1}$. ∎

###### Proof of Theorem 4.1.

Let us fix a color $k\in K$ that is hit by $c$ on every uncountable subset of
$\omega_{1}$. We will apply Martin’s Axiom to the forcing

$\\{f:\operatorname{dom}{f}\rightarrow[\omega_{1}]^{<\omega}|\;\operatorname{dom}{f}\in[\omega]^{<\omega},\;\forall
n\in\operatorname{dom}{f}\;f(n)\text{ is monochromatic of the color $k$}\\}.$

The proof of the c.c.c. is standard. ∎

Recall that a graph $G$ is _countably chromatic_ if it can be decomposed into
a countable union of anticliques, i.e. there exist a function
$h:G\rightarrow\omega$, such that any two connected vertices are mapped into
different values. We say that $G$ is _co-countably chromatic_ if $G^{c}$ is
countably chromatic.

######  Corollary 4.3.

Assume $MA_{\omega_{1}}$. If $G$ is a rectangular graph of size $\omega_{1}$,
then either $G$ or $G^{c}$ is countably chromatic.

The next theorem holds in a broader generality, not only for symmetric
relations.

######  Theorem 4.4.

Assume $MA_{\omega_{1}}$. If $\chi=(\omega_{1},c)$ is a rectangular model,
then $c$ is a countable union of rectangles.

###### Proof.

We apply Martin’s Axiom to the forcing consisting of finite partial functions
from $\omega$ to the set
$([\omega_{1}]^{<\omega}\setminus\\{\emptyset\\})^{2}$, with the following
additional properties

  * •

$\forall n\in\operatorname{dom}{f}$, if $f(n)=(f^{n}_{0},f^{n}_{1})$, then
$f^{n}_{0}\cap f^{n}_{1}=\emptyset$,

  * •

$\forall n\in\operatorname{dom}{f}$, $c\restriction f^{n}_{0}\times f^{n}_{1}$
is constant.

This forcing produces a partition of $c$ into countable many rectangles: for
every pair $(v_{0},v_{1})$ of distinct ordinals, the set of conditions
containing $(v_{0},v_{1})$ in some coordinate is dense. The non-trivial part
is to prove the c.c.c. Let us fix a family of conditions
$\\{f_{\xi}|\;\xi<\omega_{1}\\}$. Without loss of generality, they all have
the same domain $R\subseteq\omega$. Let us fix $n\in R$. By $\Delta$-system
Lemma, we can assume that

$\forall\xi<\omega_{1}\quad
f_{\xi}(n)=(\\{a_{1},\ldots,a_{s},a_{s+1}^{\xi},\ldots,a_{t}^{\xi}\\},\\{b_{1},\ldots,b_{s^{\prime}},b_{s^{\prime}+1}^{\xi},\ldots,b_{t^{\prime}}^{\xi}\\}),$

for distinct elements
$a_{1},\ldots,a_{t}^{\xi},b_{1},\ldots,b_{t^{\prime}}^{\xi}\in\omega_{1}$.
Next, we can trim our sequence again, so that for all
$\xi\neq\eta<\omega_{1}$, we have

$(a_{s+1}^{\xi},\ldots,a_{t}^{\xi},b_{s^{\prime}+1}^{\xi},\ldots,b_{t^{\prime}}^{\xi})\circledast(a_{s+1}^{\eta},\ldots,a_{t}^{\eta},b_{s^{\prime}+1}^{\eta},\ldots,b_{t^{\prime}}^{\eta}).$

Note that this implies, in particular, that the sets

$\\{a_{s+1}^{\xi},\ldots,a_{t}^{\xi},a_{s+1}^{\eta},\ldots,a_{t}^{\eta}\\},$
$\\{b_{s^{\prime}+1}^{\xi},\ldots,b_{t^{\prime}}^{\xi},b_{s^{\prime}+1}^{\eta},\ldots,b_{t^{\prime}}^{\eta}\\}$

are disjoint. We perform the similar trimming procedure for each element of
$R$. Finally, we choose any distinct $\xi,\eta<\omega_{1}$, and define

$g(n)=f_{\xi}(n)\cup f_{\eta}(n),$

for all $n\in R$. It is straightforward that $g\leq f_{\xi},f_{\eta}$. ∎

Take note that when we say _$G$ is a countable union of rectangles_, we refer
to both the connectedness relation, and its complement. This means that the
graph is both closed and open in the topology generated by the sides of the
(countably many) rectangles. If $|G|\leq 2^{\omega}$, we can easily refine
this topology to be Hausdorff.

######  Definition 4.5.

A graph $G=(V,E)$ is _open_ (resp. _closed_), if $E$ is an open (resp. closed)
subset of $V\times V$ with respect to some second countable Hausdorff topology
on $V$.
A graph $G=(V,E)$ is _clopen_ , if both $E$ and $V\times V\setminus E$ are
open subsets of $V\times V$ with respect to some second countable Hausdorff
topology on $V$.

######  Theorem 4.6.

Let $G=(V,E)$ be any graph. The following conditions are equivalent:

  1. 1.

$G$ is rectangular,

  2. 2.

There exists a c.c.c. partial order forcing that $G$ is a countably or co-
countably chromatic clopen graph,

  3. 3.

There exists an $\omega_{1}$-preserving partial order forcing that $G$ is a
countably or co-countably chromatic clopen graph.

###### Proof.

$"1.\Rightarrow 2."$ Using the methods from Section 2, we can define a forcing
that forces $MA_{\omega_{1}}$ while preserving $1.$. Next, we force $MA_{|V|}$
the usual way. This second forcing will not destroy rectangularity, because
under $MA_{\omega_{1}}$, each c.c.c. forcing is Knaster, and thus $G$-c.c.
Finally, we apply $MA_{|V|}$ to the forcing from Theorem 4.4 (perhaps
replacing $\omega_{1}$ with $|V|$).
$"2.\Rightarrow 3."$ Clear.
$"3.\Rightarrow 1."$ Let $\mathbb{P}$ denote a forcing from $3.$ By the
pigeonhole principle, any countably chromatic clopen graph is a rectangular
graph without an uncountable clique. Therefore $G$ will satisfy $1.$ after
forcing with $\mathbb{P}$. But $1.$ is a $\Pi_{1}$ statement in the language
of set theory with $\omega_{1}$ as a parameter, therefore it must have been
true in the ground model. ∎

It is worth to note a curious analogy. _Gaps_ are well-known combinatorial
structures, introduced by Hausdorff [5], among which much attention was gained
by _Suslin gaps_ (or destructible gaps/S-gaps). They are characterized by an
internal property, that is is equivalent to the property that they remain gaps
in any $\omega_{1}$-preserving generic extension (see for example [8] for the
details).

######  Theorem 4.7.

Let $G=(V,E)$ be a closed graph. The following conditions are equivalent:

  1. 1.

For every family
$\\{(x_{0}^{\xi}.\ldots,x_{n-1}^{\xi})|\xi<\omega_{1}\\}\subseteq V^{n}$,
where $n<\omega$, there exist $\xi\neq\eta<\omega_{1}$ such that

$\neg\;x_{0}^{\xi}\;E\;x_{0}^{\eta},\;\ldots,\;\neg\;x_{n-1}^{\xi}\;E\;x_{n-1}^{\eta};$

  2. 2.

There exists a c.c.c. partial order forcing that $G$ is countably chromatic;

  3. 3.

There exists an $\omega_{1}$-preserving partial order forcing that $G$ is
countably chromatic.

###### Proof.

$"1.\Rightarrow 2."$ We use the forcing

$\mathbb{P}=\\{f:\operatorname{dom}{f}\rightarrow\omega|\;\operatorname{dom}{f}\in[V]^{<\omega}\quad\forall
x\neq y\in\operatorname{dom}{f}\;xEy\implies f(x)\neq f(y)\\}.$

In order to prove the c.c.c. fix a family
$\\{f_{\xi}|\;\xi<\omega_{1}\\}\subseteq\mathbb{P}$. Without loss of
generality the domains of $f_{\xi}$ form a $\Delta$-system

$\operatorname{dom}{f_{\xi}}=(x_{1},\ldots,x_{k},x_{k+1}^{\xi},\ldots,x_{m}^{\xi}).$

We can moreover assume that the values $f_{\xi}(x_{i})$ and
$f_{\xi}(x_{j}^{\xi})$ are independent of $\xi$, for all $i=1,\ldots,k$,
$j=k+1,\ldots,m$. For every $\xi$, we fix a family of pairwise disjoint basic
open neighbourhoods

$\\{U_{x}^{\xi}\ni x|\;x\in\operatorname{dom}{f_{\xi}}\\},$

with the property that

$\forall x\neq
y\in\operatorname{dom}{f_{\xi}}\quad\neg\;x\;E\;y\implies\forall x^{\prime}\in
U^{\xi}_{x}\quad\forall y^{\prime}\in
U^{\xi}_{y}\quad\neg\;x^{\prime}\;E\;y^{\prime}.$

By another trimming, we can assume that the sets $U^{\xi}_{x}$ are independent
of $\xi$. Finally, we choose $\xi\neq\eta<\omega_{1}$ satisfying $1.$ It is
standard to check that $f_{\xi}$ and $f_{\eta}$ are compatible.
$"2.\Rightarrow 3."$ Clear.
$"3.\Rightarrow 1."$ By the pigeonhole principle, any countably chromatic
graph $G$ satisfies $1.$ Therefore $G$ will satisfy $1.$ after forcing with
$\mathbb{P}$. But $1.$ is a $\Pi_{1}$ statement in the language of set theory
with $\omega_{1}$ as a parameter, therefore it must have been true in the
ground model. ∎

######  Theorem 4.8.

Assume $MA_{\omega_{1}}$. Then any rectangular tournament of size $\omega_{1}$
is a countable union of transitive tournaments.

###### Proof.

We apply Martin’s Axiom to the forcing

$\\{f:\operatorname{dom}{f}\rightarrow[\omega_{1}]^{<\omega}|\;\operatorname{dom}{f}\in[\omega]^{<\omega},\;\forall
n\in\operatorname{dom}{f}\;f(n)\text{ is transitive.}\\}$

∎

For the proof of the c.c.c. just recall that transitive tournaments are
essentially linear orders, so they satisfy the Strong Amalgamation Property.

##  5 Rectangular Structures from $CH$

We prove that non-trivial (i.e. HSS) rectangular models exist assuming $CH$.
This is essentially an abstract version of a similar theorem for linear
orders, proved in [2].

######  Theorem 5.1.

Assume $CH$. Let $\mathcal{K}$ be a class of structures in a language
consisting of countably many binary relations, and assume that $\mathcal{K}$
satisfies RSP and SAP. Then $\mathcal{K}$ has a HSS rectangular model of size
$\omega_{1}$.

###### Proof.

Without loss of generality we can assume that every $A\in\mathcal{K}$ is of
the form $(A,c)$, where $A$ is a set, and $c:A^{2}\rightarrow\omega$. Let
$\\{M_{\alpha}|\;\alpha<\omega_{1}\\}$ be a continuous sequence of countable
elementary submodels of $H(\omega_{1})$, and put
$C=\\{\alpha<\omega_{1}|\;M_{\alpha}\cap\omega_{1}=\alpha\\}$. It is well-
known that $C$ is a closed unbounded subset of $\omega_{1}$. For $\alpha\in
C$, we denote by $\alpha^{\prime}$ the successor of $\alpha$ in $C$. By
induction on $\alpha\in C$ we define an increasing sequence of filters
$G_{\alpha}\subseteq\operatorname{Fn}(\alpha,\mathcal{K},\omega)$, ensuring
that for any $\alpha\in C$

$G_{\alpha^{\prime}}\subseteq\operatorname{Fn}(\alpha^{\prime},\mathcal{K},\omega):G_{\alpha}\quad\text{
is
}\quad\operatorname{Fn}(\alpha^{\prime},\mathcal{K},\omega):G_{\alpha}\text{-generic
over }M_{\tau{(\alpha)}},$

where $\tau{(\alpha)}$ is big enough, so that
$\\{\alpha^{\prime},G_{\alpha}\\}\in M_{\tau({\alpha})}$ (recall that
$\operatorname{Fn}(\alpha^{\prime},\mathcal{K},\omega):G_{\alpha}$ denotes the
set of those conditions from
$\operatorname{Fn}(\alpha^{\prime},\mathcal{K},\omega)$ that are compatible
with every element from $G_{\alpha}$). Note that each of these filters is
definable from a real, so $\tau(\alpha)$ is well defined. Let
$X=(\omega_{1},c)$ be the union of all filters $G_{\alpha}$.
Why is $X$ HSS? We will show that for any $\alpha\in C$, each final segment of
$\alpha^{\prime}$ is a saturating subset of $X$. Let
$E\subseteq(\omega_{1},c)$ be a finite substructure, with an extension
$E\subseteq(E\cup\\{e^{*}\\},c^{*})$. For $e\in E$ we set

$l_{e}=c^{*}(e,e^{*}),$ $l^{*}_{e}=c^{*}(e^{*},e).$

#### Case 1.

Suppose that $E\subseteq\alpha^{\prime}$. We will show that for every
$\beta<\alpha^{\prime}$ there exists $\delta\in(\beta,\alpha^{\prime})$, such
that for any $e\in E$, we have

$c(e,\delta)=l_{e},$ $c(\delta,e)=l_{e}^{*}.$

Indeed, it is sufficient to show that the following set (belonging to
$M_{\tau(\alpha)}$) is dense in the partial order
$\operatorname{Fn}(\alpha^{\prime},\mathcal{K},\omega):G_{\alpha}$:

$\\{p\in\operatorname{Fn}(\alpha^{\prime},\mathcal{K},\omega):G_{\alpha}|\;\exists\;\delta\in(\beta,\alpha^{\prime})\quad\forall\;e\in
E\quad p\Vdash\dot{c}(e,\delta)=l_{i},\;\dot{c}(\delta,e)=l^{*}_{e}\\}.$

To see this, fix some
$p\in\operatorname{Fn}(\alpha^{\prime},\mathcal{K},\omega):G_{\alpha}$, and
assume that $E\subseteq\operatorname{dom}{p}$ (otherwise we can extend $p$, so
that this is satisfied). Next, we fix
$\delta\in(\beta,\alpha^{\prime})\setminus\operatorname{dom}{p}$ and extend
$p$ to $p^{*}$ by amalgamating the diagram

${p\ }$${E}$${p^{*}=p\cup\\{\delta\\}}$${E\cup\\{e^{*}\\}}$

To make sure that $p^{*}$ is compatible with any condition from $G_{\alpha}$,
notice that for any $q\in G_{\alpha}$ we can find $p^{\prime}\leq p,q$, not
containing $\delta$, and disjointly amalgamate over the diagram

${p^{*}}$${p^{*}\cap p^{\prime}=p}$${p^{\prime}}$

#### Case 2.

Let $\alpha_{1}$ be the minimal ordinal in $C$ such that
$\alpha_{1}\geq\alpha$, and $E\subseteq\alpha_{1}^{\prime}$. We will prove by
induction on $\alpha_{1}$ that

$\forall\;\beta<\alpha^{\prime}\;\exists\;\delta\in(\beta,\alpha^{\prime})\;\forall\;e\in
E\quad c(e,\delta)=l_{e},\;c(\delta,e)=l_{e}^{*}.$

If $\alpha_{1}=\alpha$, our task reduces to the previous case, so let as
assume that whenever $\alpha_{0}\in C\cap\alpha_{1}$, the conclusion holds for
every $E\subseteq\alpha_{0}^{\prime}$. In particular, it holds for
$E\cap\alpha_{1}$. Define

$I=\\{\delta\in(\beta,\alpha^{\prime})|\;\forall\;e\in E\cap\alpha_{1}\quad
c(e,\delta)=l_{e},\;c(\delta,e)=l_{e}^{*}\\}.$

By the inductive hypothesis, $I$ is nonempty for any value of $\beta$, and so
$|I|=\omega$. We must verify that the following set (belonging to
$M_{\tau(\alpha_{1})}$) is dense in the partial order
$\operatorname{Fn}(\alpha_{1}^{\prime},\mathcal{K},\omega):G_{\alpha_{1}}$:

$\\{p\in\operatorname{Fn}(\alpha_{1}^{\prime},\mathcal{K},\omega):G_{\alpha_{1}}|\;\exists\;\delta\in
I\quad\forall\;e\in E\setminus\alpha_{1}\quad
p\Vdash\dot{c}(e,\delta)=l_{i},\;\dot{c}(\delta,e)=l^{*}_{e}\\}.$

Notice that this set is in $M_{\tau(\alpha_{1})}$. The density argument
exactly follows the Case 1, with $\alpha_{1}$ in place of $\alpha$, and
$E\setminus\alpha_{1}$ in place of $E$.

Why is $X$ rectangular? Consider a pairwise disjoint family

$\\{(x_{0}^{\xi},\ldots,x_{n-1}^{\xi})|\;\xi<\omega_{1}\\}\subseteq X^{n}.$

We will be working with a fixed ordinal $\alpha\in C$ with an additional
property that $\alpha=N\cap\omega_{1}$, for some countable elementary submodel
$N\prec H(\omega_{2})$, which contains the set

$\\{X,\\{(x_{0}^{\xi},\ldots,x_{n-1}^{\xi})|\;\xi<\omega_{1}\\}\\}.$

This property of $N$ ensures the following

######  Claim.

  1. 1.

$\forall\;\beta<\alpha\quad\\{x_{0}^{\beta},\ldots,x_{n-1}^{\beta}\\}\subseteq\alpha$,

  2. 2.

$\forall\;\beta>\alpha\quad\\{x_{0}^{\beta},\ldots,x_{n-1}^{\beta}\\}\cap\alpha=\emptyset.$

###### Proof of the Claim.

  1. 1.

For any $\beta<\alpha$, $\\{x_{0}^{\beta},\ldots,x_{n-1}^{\beta}\\}\in N$.
Since $\alpha=N\cap\omega_{1}$, the conclusion follows.

  2. 2.

Suppose towards contradiction that
$\gamma\in\alpha\cap\\{x_{0}^{\beta},\ldots,x_{n-1}^{\beta}\\}$, for some
$\beta>\alpha$. By the elementarity,

$N\models\exists\;\delta<\omega_{1}\quad\gamma\in\\{x_{0}^{\delta},\ldots,x_{n-1}^{\delta}\\}.$

Therefore we can choose $\delta<\alpha$, such that

$\gamma\in\\{x_{0}^{\beta},\ldots,x_{n-1}^{\beta}\\}\cap\\{x_{0}^{\delta},\ldots,x_{n-1}^{\delta}\\}.$

But this contradicts the assumption that the tuples are pairwise disjoint.

∎

Fix some ordinal $\beta<\alpha$. We want to show that the following set is
dense in $\operatorname{Fn}(\alpha^{\prime},\mathcal{K},\omega):G_{\alpha}$:

$\\{p\in\operatorname{Fn}(\alpha^{\prime},\mathcal{K},\omega):G_{\alpha}|\;\exists\;l<\omega\quad
x^{\alpha+l}_{0},\ldots,x^{\alpha+l}_{n-1},x^{\beta}_{0},\ldots,x^{\beta}_{n-1}\in\operatorname{dom}{p},\quad$
$p\Vdash(x^{\alpha+l}_{0},\ldots,x^{\alpha+l}_{n-1})\circledast(x^{\beta}_{0},\ldots,x^{\beta}_{n-1})\\}.$

To see that this is the case, fix
$p\in\operatorname{Fn}(\alpha^{\prime},\mathcal{K},\omega):G_{\alpha}$. We can
of course assume that
$\\{x^{\beta}_{0},\ldots,x^{\beta}_{n-1}\\}\subseteq\operatorname{dom}{p}$,
and choose $l<\omega$ such that
$\\{x^{\alpha+l}_{0},\ldots,x^{\alpha+l}_{n-1}\\}\cap\operatorname{dom}{p}=\emptyset$.
Let $p^{\circ}$ denote the condition obtained by replacing each
$x_{i}^{\beta}\in\operatorname{dom}{p}$ with $x_{i}^{\alpha+l}$, and defining
relations so that the extensions

$p\setminus\\{x^{\beta}_{0},\ldots,x^{\beta}_{n-1}\\}\subseteq p,$

and

$p\setminus\\{x^{\beta}_{0},\ldots,x^{\beta}_{n-1}\\}\subseteq(p\setminus\\{x^{\beta}_{0},\ldots,x^{\beta}_{n-1}\\})\cup\\{x^{\alpha+l}_{0},\ldots,x^{\alpha+l}_{n-1}\\}$

become isomorphic (via the function $x_{i}^{\beta}\mapsto x_{i}^{\alpha+l}$).
We extend $p$ to $p^{*}$ by applying the RSP to the following diagram of
isomorphic extensions

${p\
}$${p\setminus\\{x^{\beta}_{0},\ldots,x^{\beta}_{n-1}\\}}$${p^{*}}$${p^{\circ}}$

By the RSP, we can amalgamate so that
$p^{*}\Vdash(x^{\alpha+l}_{0},\ldots,x^{\alpha+l}_{n-1})\circledast(x^{\beta}_{0},\ldots,x^{\beta}_{n-1})$.
To see that $p^{*}$ is compatible with every element of $G_{\alpha}$, note
that whenever $q\in G_{\alpha}$, we can find $p^{\prime}\leq p,q$ disjoint
with $\\{x^{\alpha+l}_{0},\ldots,x^{\alpha+l}_{n-1}\\}$, and then disjointly
amalgamate over the diagram

${p^{*}}$${p^{\prime}\cap p^{*}=p}$${p^{\prime}}$

∎

##  6 Conclusions

Is the theory we develop entitled to be called "the uncountable Fraïssé theory
with finite supports"? We left it to the reader’s opinion. Obviously,
similarity of forcing notions

$\operatorname{Fn}{(\omega,\mathcal{K},\omega)}$

and

$\operatorname{Fn}{(\omega_{1},\mathcal{K},\omega)}$

shows that some "genericity" is common to Fraïssé limits and rectangular
models. On the other hand, properties of models added by the latter forcing
seem heavily dependent on the set-theoretic background, unlike those of
countable homogeneous models. Moreover, it looks like Proposition 2.22
exhibits some strange asymmetry of rectangular models in the presence of
$MA_{\omega_{1}}$, which distinguishes them from their countable counterparts.

## References

  * [1]
  * [1] U. Avraham, M. Rubin, S. Shelah, On the consistency of some partition theorems for continuous colorings, and the structure of $\aleph_{1}$-dense real order types, Annals of Pure and Applied Logic 29 (1985), 123-206
  * [2] U. Avraham, S. Shelah, Martin’s Axiom does not imply that every two $\aleph_{1}$-dense sets of reals are isomorphic, Israel Journal of Mathematics, vol. 38, Nos. 1-2, 1981
  * [3] J.E. Baumgartner, All $\aleph_{1}$-dense sets of reals can be isomorphic, Fund. Math. 79 (1973), 101-106
  * [4] R. Fraïssé, Sur quelques classifications des systémes de relations, Publ. Sci. Univ. Alger. Sér. A. 1 (1954)
  * [5] F. Hausdorff, Summen von $\aleph_{1}$-mengen, Fund. Math. 26 (1936), 241–255
  * [6] B. Jónsson, Homogeneous universal relational systems, Mathematica Scandinavica, 8(1) (1960), 137-142
  * [7] Z. Kostana, Cohen-like first order structures, to appear in Annals of Pure and Applied Logic, https://arxiv.org/abs/2009.03552
  * [8] F. López, S. Todorčević, Trees and gaps from a construction scheme, Proceedings of the American Mathematical Society 145.2 (2017), 871-879.
  * [9] W. Kubiś, Fraïssé sequences: category-theoretic approach to universal homogeneous structures, Annals of Pure and Applied Logic 165(11), 2014 1755-1811
  * [10] K. Kunen, Set Theory. Introduction to Independence Proofs, 1980 Elsevier Science B.V.