% 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}