% LaTex2e  Feb 2012
% Absoluteness of convexly orderable
% A. Miller

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

\def\conj{\wedge}
\def\al{\alpha}
\def\bb{{\mathcal B}}
\def\be{\beta}
\def\comp(#1){\overline{#1}}
\def\concat(#1){\hat{\phantom{a}}\langle #1\rangle}
\def\dd{{\mathcal D}}
\def\ga{\gamma}
\def\lm{\lambda}
\def\om{\omega}
\def\poset{{\mathbb P}}
\def\proof{\par\noindent Proof\par\noindent}
\def\qed{\par\noindent QED\par\bigskip}
\def\res{{\upharpoonright}}
\def\rmand{{\mbox{ and }}}
\def\sm{\setminus}
\def\star{0}
\def\su{{\;\subseteq\;}}
\def\uu{{\mathcal U}}

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

\begin{document}

\begin{center}
Absoluteness of convexly orderable
\end{center}

\begin{flushright}
A. Miller \\
Feb 2012
\end{flushright}


\bigskip

During a talk by Vincent Guingona \cite{vincent}, Uri
Andrews raised the question of whether the property
of being convexly orderable
is set theoretically absolute.  We show that it
is absolute when the language is countable but it isn't for
uncountable languages.

\begin{define}
An $L$-structure $M$ is convexly orderable iff
there is a linear order $\leq$ on $M$ and
a function $\phi\mapsto k_\phi$ from $L$-formulas
to $\om$ such that for any $\phi(x,\vec{y})$ every
set of the form $\phi(M,\vec{a})$ for some $\vec{a}\in M$
can be written as the union of $\leq k_\phi$ convex
sets.
\end{define}


\begin{theorem}
Suppose $V$ is a transitive model of set theory, $M\in V$,
and $V$ models that $M$ is a structure in a countable 
language $L$ 
which is not convexly orderable.  Then any transitive model
of set theory $W\supseteq V$ also models that $M$ is
not convexly orderable.
\end{theorem}

\proof
In $V$ let $\phi_n$ for $n<\om$ list all $L$-formulas
and suppose that in $W$ there is a function
$f:\om\to\om$ and linear order on $M$ such that
each set of the form $\phi_n(M,\vec{a})$ is the union
of $\leq f(n)$ convex sets.  For each $N<\om$ note
that $V$ models there is a linear order on $M$ such that
for every $n<N$ and each set of the form $\phi_n(M,\vec{a})$
is the union of $\leq f(n)$ convex sets.  This follows
easily from the compactness theorem of propositional logic
using predicate symbols for the linear order and predicate
symbols for convex sets required.

In $V$ define a subtree $T\su \om^{<\om}$ by
$s\in T$ iff there exists a linear order on $M$ such
that for every $n<|s|$ each set of the form $\phi_n(M,\vec{a})$
is the union of $\leq s(n)$ convex sets.

Since $f\in [T]$ is branch thru $T$ by absoluteness of
well-foundedness $T$ must have a branch $g$ in $V$.
Again by compactness $g$ is a witness showing
that $V$ models that $M$ is convexly orderable.

\qed

\begin{theorem}\label{thm2}
There is a structure $M$ in a language of size $\om_1$ which
is not convexly orderable but in every extension of
the universe $V$ in which $\om_1^V$ is countable $M$
is convexly orderable.
\end{theorem}


\begin{lemma} \label{lem1}
Let $L$ be the language consisting of countably many unary
predicate symbols.  Every model in the language of $L$ is
convexly orderable.
\end{lemma}
\proof
Let $P_n$ for $n<\om$ be the unary predicate symbols.
For each $s\in 2^{<\om}$ let
$$\rho_s(x)=(\conj_{s(i)=0}P_i(x))\conj(\conj_{s(i)=1}\neg P_i(x))$$
Using the order on $M$ induced by lexicographical order on
$2^\om$ shows that each $\rho_s(M)$ is convex.
The definable subsets of $M$ are boolean combinations
of these sets and singletons.
\qed

\begin{lemma}  \label{lem2}
Suppose $A_n\su X$ for $n<\om$ is an independent family.
Then there does not exist $k<\om$ and a linear order on
$X$ such that every $A_n$ is the union of $\leq k$ convex
subsets.
\end{lemma}
\proof
Suppose not. By a Lowenheim-Skolem argument we
may assume that $X$ is countable.  Hence we may embed
it in the unit interval $[0,1]$. Taking the
obvious convex closures we may assume that $X$ is
$[0,1]$.  Since changing the elements of
an independent family mod finite does not effect
independence we may assume each $A_n$ is the union
of $\leq k$ open intervals.  Cutting down to an infinite
subfamily we may assume that there are $x^n_i, y^n_i$ for
$i<k$ such that
\begin{enumerate}
\item $0<x^n_0<y^n_0 <x^n_1<y^n_1< \cdots  <x^n_{k-1}<y^n_{k-1}<1$
\item $A_n=\bigcup_{i<k}(x^n_i, y^n_i)=\bigcup_{i<k}I_n^i$
\end{enumerate}

Using the compactness of the unit interval we pass to subsequence
which such that each $x^n_i$ converges to some $x_i$ and
is either strictly increasing, strictly decreasing, or
constant.  The same is true for the $y_i^n$.  Note
that
$$ 0\leq  x_0\leq  y_0 \leq  x_1\leq
y_1\leq   \cdots \leq   x_{k-1}\leq  y_{k-1}\leq  1$$

and some or all may be equal.
Define
$$L_n^i=(x^n_i,x_i^{n+1}] \rmand R_n^i= [y^{n+1}_i,y_i^{n})$$
where we agree that $[a,b)$ and $(a,b]$ are empty when $b\leq a$.
Note that  $x_i$ is not in $L_n^i$ (by monotonicity) and
$L_n^i$ converges to $x_i$.  Similarly for $R_n^i$ and $y_i$.
If $I_n^i=(x^n_i,y^n_i)$ then
$$I_n^i\sm I_{n+1}^i\su L_n^i\cup R_n^i \rmand
A_n\sm A_{n+1}\su \bigcup_{i<k}  I_n^i\sm I_{n+1}^i$$
For large enough $n$ there will be an $\epsilon>0$ such that
$\bigcup_{i<k}L_n^i\cup R_n^i$ is disjoint from
$\bigcup_{i<k}B_\epsilon(x_i)\cup B_\epsilon(y_i)$.
But then we can choose $m>>n$ such that
$$\bigcup_{i<k}L_m^i\cup R_m^i\su
\bigcup_{i<k}B_\epsilon(x_i)\cup B_\epsilon(y_i)$$
and so $(A_n\sm A_{n+1})$ and $(A_m\sm A_{m+1})$ are
disjoint, contradicting independence.

\qed



To prove Theorem \ref{thm2} let
$M$ be the following model in the language consisting
of $\om_1$ unary predicate symbols.
$|M|=2^{\om_1}$ and for each $\al<\om_1$ the unary
predicate
$$A_\al=\{x\in 2^{<\om_1}\;:\; x(\al)=1\}.$$
$M$ is not convexly orderable since if it were
there would be a $k<\om$ and an infinite set
of $\al$ such that every $A_\al$ is the union of
$\leq k$ convex subsets.  Contradicting Lemma \ref{lem2}.
On the other hand if $\om_1^V$ is countable, then
by Lemma \ref{lem1} the structure $M$ is convexly orderable.
\qed



\begin{thebibliography}{99}

\bibitem{vincent}
Vincent Guingona, Logic Colloquium
UW Madison, Feb 2012.


\end{thebibliography}

\end{document}