% LaTeX2e
% The axiom of choice and two-point sets in the plane
% A. Miller Jun 08 last revised Sep 08
\documentclass[12pt]{article}
\usepackage{amssymb}
\pagestyle{myheadings}
\def\header{A.Miller\hfill AC and 2-point sets \hfill}
\markboth\header\header
%\pagestyle{myheadings} \def\header{\today} \markboth\header\header
\def\res{\upharpoonright}
\def\fin{{\rm Fn}(\om_2,2)}
\def\ff{{\mathcal F}}
\def\supp{{\rm supp}}
\def\gg{{\mathcal G}}
\def\ga{\gamma}
\def\dom{{\rm dom}}
\def\ka{\kappa}
\def\cn{{CN}}
\def\rmiff{\mbox{ iff }}
\def\be{\beta}
\def\rmand{\mbox{ and }}
\def\name#1{\stackrel{\circ}{#1}}
\def\namexxx#1{\accentset{\circ}{#1}}
\def\forces{{\;\Vdash}}
\def\om{\omega}
\def\al{\alpha}
\def\proof{\par\noindent Proof\par\noindent}
\def\st{\;:\;} % such that
\def\qed{\par\noindent QED\par\bigskip}
\def\poset{{\mathbb P}}
\def\posetx{{\mathbb F}}
\def\su{\subseteq}
\def\ll{{\mathcal L}}
\def\reals{{\mathbb R}}
\def\sm{\setminus}
\def\pr{\prime}
\newtheorem{theorem}{Theorem}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{define}[theorem]{Definition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{remark}[theorem]{Remark}
\begin{document}
\begin{center}
{\large The axiom of choice and two-point sets in the plane }
\end{center}
\begin{flushright}
Arnold W. Miller
\footnote{
\par Mathematics Subject Classification 2000: 03E25 03E15
\par Keywords:
countable axiom of choice
}
\end{flushright}
\def\address{\begin{flushleft}
Arnold W. Miller \\
miller@math.wisc.edu \\
http://www.math.wisc.edu/$\sim$miller\\
University of Wisconsin-Madison \\
Department of Mathematics, Van Vleck Hall \\
480 Lincoln Drive \\
Madison, Wisconsin 53706-1388 \\
\end{flushleft}}
\begin{center} Abstract \end{center}
\begin{quote}
In this paper we prove that it consistent to have a two-point
set in a model of ZF in which the real line cannot be well-ordered.
We prove two results related to a construction of Chad of a two-point set
inside the countable union of concentric circles.
We show that if the reals are the countable union of countable
sets, then every well-orderable set of reals is countable. However,
it is consistent to have a model of ZF in which the reals are
the $\om_1$ increasing union of sets of size $\om_1$ and $\om_2$
can be embedded into the reals.
\end{quote}
A two-point set is a subset of the plane which meets
every line in exactly two points. It is an open question
whether a two-point set can be Borel.
In work on the two-point problem Chad \cite{chad} came up with the
question of whether it might be possible to have a model of ZF
in which the reals are the countable union of countable sets and
there is an uncountable well-orderable set of reals.\footnote{In
the first draft of \cite{chad} it was stated that
we had shown that in the Feferman-Levy model there is no uncountable
well-orderable set of reals. But this is already known, see Cohen
\cite{cohen} page 146.} If this were possible, then Chad's method
of construction of two-point sets inside concentric circles could
be used to construct a Borel example of a two-point set.
However, it is impossible:
\begin{theorem}\label{one}
Suppose the reals are the countable union of countable
sets. Then every well-orderable set of reals is countable.
\end{theorem}
\proof
Let $p:\om\times\om\to\om$ be a fixed bijection. For each $n\in\om$
define the map $\pi_n:2^\om\to 2^\om$ by:
$$\pi_n(x)=y \mbox { iff } \forall m\in\om\;\;y(m)=x(p(n,m)).$$
Suppose there exists $(F_n\st n\in\om)$ such that
$2^\om=\bigcup_{n\in\om}F_n$ and each $F_n$ is countable.
Define $(H_n\st n\in\om)$ by
$$H_n=\pi_n(F_n)=\{\pi_n(x)\st x\in F_n\}.$$
Since the image of a countable set is countable each $H_n$ is
countable.
Suppose for contradiction that there exists $(u_\al \st \al\in\om_1)$
distinct elements of $2^\om$. Then for all $n$ there exists $\al\in\om_1$
such that $u_\al\notin H_n$. Define $(\al_n\st n\in\om)$ by
$$\al_n = \mbox{ the least $\al$ such that }u_\al\notin H_n.$$
Let $x\in 2^\om$ be the unique real such that
$$\forall n\;\; \pi_n(x)=u_{\al_n}.$$
But this is a contradiction since then $x\notin \bigcup_{n\in\om}F_n$.
\qed
The following answers a question raised by Chad.
\begin{theorem}\label{two}
It is consistent to have a model of ZF in which
$\om_2$ embeds into the real line and the real line
is the $\om_1$ increasing union of sets of size $\om_1$.
\end{theorem}
\proof
Before doing this we prove the following lemma. Our model is
analogous to the Feferman-Levy model (see Cohen \cite{cohen} p.143, Jech
\cite{jech} p.142) but one cardinal higher.
\begin{lemma}
There is a countable transitive model $N$ of:
\begin{enumerate}
\item ZF + DC + CH (i.e, $|2^\om|=\om_1$,
there is bijection between $2^\om$ and $\om_1$),
\item the power set of $\om_1$ is the $\om_1$-union of sets of size $\om_1$,
\item $cof(\om_2)=\om_1$, and
\item $|[\om_2]^{\om}|=\om_2$.
\end{enumerate}
\end{lemma}
\proof
Let be $M$ be a countable transitive model of ZFC+GCH. Working
in $M$ let $\ka=(\aleph_{\om_2})^M$. Define $\poset$ to be the
standard Levy collapse of $\kappa$ to $\om_1$ using countable partial
functions. This means $p\in\poset$ iff there is a countable
$F\su \om_1\times\om_1$, such that $p:F\to\ka$ and $p(\al,\be)<\aleph_\al$
for every $(\al,\be)\in F$. For $G$ which is $\poset$-generic over
$M$ define $(g_\al:\al<\om_1)$ by $g_\al(\be)=\ga$ iff
there exists $p\in G$ such that $p(\al,\be)=\ga$.
Standard density arguments show that each $g_\al:\om_1\to\aleph_\al$
is onto.
Consider any permutation $\hat{\pi}:\om_1\times\om_1\to \om_1\times\om_1$
which fixes the first coordinate, i.e.,
$\hat{\pi}(\al,\be)=(\al^\pr,\be^\pr)$
implies $\al=\al^\pr$.
Such a permutation induces an automorphism $\pi$ of $\poset$ by defining:
\begin{enumerate}
\item $\dom(\pi(p))=\hat{\pi}(\dom(p))$ and
\item $\pi(p)(\hat{\pi}(\al,\be))=p(\al,\be)$
\end{enumerate}
Working in $M$, the group $\gg$ of permutations are those $\pi$ such that
$\hat{\pi}$ has countable support, i.e.,
$$\supp(\hat{\pi})=\{(\al,\be)\st \hat{\pi}(\al,\be)\neq(\al,\be)\}$$
is countable.
Let $\{H_\al\st \al<\om_1\}$ generate the
filter $\ff$ of subgroups of $\gg$ where
$$H_\al=\{\pi\in \gg\st
\hat{\pi}\res \al\times\al \mbox{ is the identity }\}.$$
It is easily checked that $\ff$ is normal. Let
$N$ be the symmetric model determined by $\gg,\ff$.
The forcing is countably closed and the filter
of subgroups is closed under countable intersections. It
follows that $[\om_2]^\om$ is the same in all the models
$M\su N\su M[G]$.
The rest of the arguments to prove the lemma are
analogous to Feferman-Levy and left to the reader.
\qed
Working in the model $N$ of
the lemma consider the usual Cohen forcing order
for adding $\om_2$ subsets of $\om$:
$$\fin=\{p\st dom(p)\in [\om_2]^{<\om} \rmand range(p)=\{0,1\}$$
Since $\fin$ just consists of finite sequences
of ordinals, it is clear that it can be well-ordered in type $\om_2$
in any model of ZF (without using the axiom of choice).
The set of canonical names,
$\cn(\fin)$, for
subsets of $\om$ is defined to be the set of all countable
$\tau$ such that $\tau$ is a subset of
$$\tau\su\fin \times \{\name{n}\st n\in\om\}$$
This set need not be well-orderable in a model of ZF. However,
it is easy to see that it always has the same cardinality as the
set $[\om_2]^\om$.
If we now take $N[G]$ for $G$ which is $(\fin)^N$-generic over
$N$, then $N$ is the model we want and Theorem \ref{two} is proved.
\qed
\begin{remark}
Note that in the model for Theorem \ref{two} DC (Dependent Choice)
holds and there is a bijection between $\om_2$ and the real
line. So in fact, the usual inductive construction of a two-point
set could be done.
\end{remark}
In response to a question of Chad we show:
\begin{theorem}\label{twopt}
It is consistent to have a model of ZF in which there is a two-point
set but the real line cannot be well-ordered.
\end{theorem}
\proof
\def\fn(#1){{\rm{Fn}(#1,2)}}
Here is a sketch of the proof. Start with
$M$ a countable transitive model of ZF such that
there exists an infinite Dedekind-finite set of
reals and $\om_1$ is regular. For example, the
standard Cohen model see Jech \cite{jech}
page 61. Working in $M$ let $\fn(\om_1)$ be the usual poset for
adding $\om_1$ Cohen reals, i.e. $p$ in $\fn(\om_1)$ is a
finite partial function from $\om_1$ to $2$.
The model we want is $M[G]$ for any $G$ which is
$\fn(\om_1)$-generic over $M$.
Since $\fn(\om_1)$ can be well-ordered in $M$ it is not hard
to see that forcing with $\fn(\om_1)$ will preserve Dedekind
finite sets (Lemma \ref{preserve}).
Hence the reals of $M[G]$ cannot be well-ordered.
Also since $\om_1$ is regular in
$M$ for $x$ a real in $M[G]$ there exists an
$\al<\om_1$ such that $x$ is in $M[G_\al]$
(Lemma \ref{regular}).
Then using the $\al^{th}$ Cohen real to determine
the radius of a circle centered at the origin
we can inductively construct a 2-point set in $M[G]$.
\bigskip
We give this last argument in more detail:
Suppose $N$ is a countable transitive model of ZF.
Suppose that $X\in N$ is a partial two-point set, i.e.,
$X$ is a subset of the plane which does not contain three collinear
points.
Fix $n\in\om$.
Working in $N$ define $\ll_n$ to be the set of
all lines which meet the circle of radius $n+1$
centered at the origin.
Suppose that $x\in 2^\om$ is $2^{<\om}$-generic over $N$ and
define
$$r(n,x)=(n+1)+\sum_{k<\om} x(k)2^{-k-1}.$$
Let $C$ be the circle of radius $r(n,x)$ centered at the origin.
For each line $L$ in $\ll_n$ since the radius
of $C$ is greater than $n+1$, the line $L$ will meet it in
two distinct points. Let $L\cap C=\{p^L,q^L\}$ where
$p^L$ is lexicographically less than $q^L$.
Define $F(L)$ as follows:
$$F(L)=\left\{
\begin{array}{ll}
\emptyset & \mbox{ if } |L\cap X|=2 \\
\{p^L\} & \mbox{ if } |L\cap X|=1 \\
\{p^L,q^L\} & \mbox{ if } |L\cap X|=0
\end{array}\right.$$
Define
$$Y=X\cup \bigcup\{F(L)\st L\in\ll_n\}.$$
It is easy to see by the genericity of its radius
that the circle $C$ cannot contain
any point of $N$.
It follows that for any $L\in\ll_n$ that $|L\cap Y|=2$.
Now we verify that $Y$ does not contain three distinct collinear
points. Suppose $a,b,c\in Y$ are collinear. It cannot be
that all three are from $X$ since the set $X$ is a partial
two-point set. It cannot be that all three are new, i.e.,
from $Y\sm X$ since all of these points are on the same circle, $C$.
It cannot be that two are old and one is new, say
$a,b\in X$ and $c\in Y\sm X$. This means that $c\in F(L)$ for
some $L\in\ll_n$. But by the definition of $F(L)$ it cannot
be that $L$ is the line $L^\pr$ containing $a$ and $b$.
But then $L^\pr$ and $L$ are distinct lines in $N$ meeting at the
point $c$, which contradicts the fact that the radius
$C$ is not in $N$.
So finally we are left with the case of one old and two new points,
i.e., $a\in X$ and $b,c\in Y\sm X$. Say $b\in F(L)$ and
$c\in F(L^\pr)$. It is impossible that $L=L^\pr$ by the way
we defined $F$. According to Lemma 4.1 of \cite{chad}
for distinct lines $L,L^\pr$ and point $a$ there
are at most 22 radii $r>0$ such that if $C_r$ is the circle
of radius $r$ centered at the origin, then there exists
$b\in C_r\cap L$ and $c\in C_r\cap L^\pr$ such that $a,b,c$ are
collinear. These radii are the solutions of polynomial equations
and hence would lie in $N$. Again by genericity this cannot happen.
This is the construction at each step. We now describe
the transfinite construction.
\begin{define}\label{omegaone}
For any ordinal $\al$ define
$$\fn(\al)=\{p:D\to 2\st D\in [\al]^{<\om}\}$$
ordered in the usual way by inclusion, $p\leq q$ iff $p\supseteq q$.
For any $G_\al$ which is a $\fn(\al)$-filter
and $\be<\al$ define
$$G_\be=G_\al\cap \fn(\be)$$
and define $x_\be\in 2^\om$ by
$$x_\be(n)=i \rmiff \exists q\in G_\al\;\; q(\be+n)=i.$$
\end{define}
Standard iteration arguments show that for limit ordinals $\be<\al$
in a countable transitive model $M$ of ZF
if $G_\al$ is $\poset_{\al}$ generic over $M$, then
$G_\be$ is $\poset_{\be}$-generic over $M$ and $x_\be$
is $2^{<\om}$ generic over $M[G_\be]$.
For each $\be<\om_1^M$ if $\be=\lambda+n$ where $\lambda$
is a limit ordinal, let $C_\be$ be the circle of radius
$r(n,x_\be)$ centered at the origin. Note that the sequence
$(x_\be:\be<\om_1^M)$ is in the model $M[G_{\om_1^M}]$. Hence
working in this model we may construct inductively without
using choice an increasing sequence of partial two-point sets
$(X_\be:\be<\om_1^M)$ using the argument we described above
at each successor step.
Since every line will appear at some countable stage (by
Lemma \ref{regular}) the set $X=\bigcup_{\al<\om_1^M}X_\al$
will be a two-point set in $M[G_{\om_1^M}]$. Since
our forcing can be well-ordered the Dedekind finite set
in the ground model $M$ is preserved (by Lemma \ref{preserve})
and hence Theorem \ref{twopt} is proved.
\qed
\begin{lemma}\label{preserve}
Suppose that $M$ is a countable transitive model of ZF. Suppose
that $\poset$ is a partially ordered set in $M$ such that
$$M\models \poset \mbox{ can be well-ordered}.$$
Suppose that $D\in M$ satisfies
$$M\models D\su 2^\om \mbox{ is an infinite Dedekind finite set}.$$
Then for any $G$ which $\poset$-generic over $M$:
$$M[G]\models D \mbox{ is a Dedekind finite set}.$$
\end{lemma}
\proof
Suppose not. Working in $M$ take $p\in G$ and $\name{f}$ a $\poset$-name
such that
$$p\forces \name{f}:\om\to D \mbox{ is one-one.}$$
For each $n<\om$ let
$$E_n=\{q\in\poset\st q\leq p \rmand \exists d\in D\;\;\;
q\forces \name{f}(n)=\check{d}\}.$$
Define $g_n:E_n\to D$ by $g_n(q)=d$ iff $q\forces \name{f}(n)=\check{d}$.
Since $E_n$ can be well-ordered and $D$ is Dedekind finite, the
range $R_n$ of the map $g_n$ is finite. But since
$2^\om$ is a linearly ordered set, it follows that
$\bigcup_{n<\om}R_n$ is a finite set.
But this is contradiction since in $M[G]$ the range of
$f$ is a subset of $\bigcup_{n<\om}R_n$.
\qed
\begin{lemma}\label{regular}
Suppose that $M$ is a countable transitive model of ZF such that
$$M\models \om_1 \mbox{ is regular}.$$
Then for any $G$ which is $\fn({\om_1^M})$-generic over $M$
$$M[G]\cap 2^\om=\bigcup_{\al<\om_1^M} (M[G_\al]\cap 2^\om).$$
\end{lemma}
\proof
Suppose $x\in M[G]\cap 2^\om$.
Working in $M$ let $\name{x}$ be
a name for $x$ and take $p\in G$ so that
$$p\forces \name{x}\in 2^\om.$$
For each $n<\om$ let
$$E_n=\{q\in \poset_{\om_1^M}\st q\leq p \rmand \exists i\in\{0,1\}
\;\;q\forces \name{x}(n)=i\}.$$
Since $\poset_{\om_1^M}$ can be well-ordered and the sequence
$(E_n: n<\om)$ is in $M$ we can (without using choice) find
$(A_n\su E_n:n<\om)$ in $M$ so that each $A_n$ is a maximal antichain
beneath $p$. One needs to check that
$$M\models \mbox{ antichains in $\fn({\om_1})$ are countable.}$$
This is true because in $M$ there is bijection between
$\om_1^M$ and $\fn({\om_1^M})$ and since $\om_1^M$ is
regular in $M$ the countable union of countable subsets of
$\fn({\om_1^M})$ is countable.
Hence there exists $\al<\om_1^M$ such
that $\bigcup_{n<\om}A_n\su \poset_\al$. It follows by standard
canonical name arguments that $x\in M[G_\al]$.
\qed
\begin{remark}
The method of proof of Theorem \ref{twopt} also yields models of ZFC in
which the continuum is arbitrarily large and there is a two-point
set which is included in the union of $\om_1$ circles.
\end{remark}
\begin{thebibliography}{99}
\bibitem{chad}
Chad, Ben; Knight, Robin; Suabedissen, Rolf;
Set-theoretic constructions of two-point sets, eprint aug08
\bibitem{cohen} Cohen, Paul J.; {\bf Set theory and the
continuum hypothesis.} W. A. Benjamin, Inc.,
New York-Amsterdam 1966 vi+154 pp.
\bibitem{jech} Jech, Thomas J.; {\bf The axiom of choice.} Studies in Logic and
the Foundations of Mathematics, Vol. 75. North-Holland Publishing Co.,
Amsterdam-London; Amercan Elsevier Publishing Co., Inc., New York, 1973. xi+202
pp.
\bibitem{longbor} Miller, Arnold W.; Long Borel hierarchies, Math Logic
Quarterly, 54(2008), 301-316.
\bibitem{ded}
Miller, Arnold W.; A Dedekind finite Borel set, eprint jun08.
\end{thebibliography}
\address
\end{document}