% LaTeX2e % A Dedekind finite Borel set % A. Miller Feb 2008 last revised June 2010 \documentclass[12pt]{article} \usepackage{amssymb} \pagestyle{myheadings} %\def\header{\today} \def\header{A.Miller\hfill A Dedekind Finite Borel Set \hfill} \markboth\header\header \def\Si{\Sigma} \def\aa{{\mathcal A}} \def\al{\alpha} \def\bb{{\mathcal B}} \def\be{\beta} \def\cl{{\rm cl}} \def\concat#1{{\hat{\phantom{a}}\la #1\ra}} \def\concatx{{\hat{\phantom{a}}}} \def\de{\delta} \def\emp{\emptyset} \def\ff{{\mathcal F}} \def\fix{{\rm fix}} \def\forces{{\;\Vdash}} \def\ga{\gamma} \def\gg{{\mathcal G}} \def\hh{{\mathcal H}} \def\ka{\kappa} \def\lam{\lambda} \def\la{\langle} \def\mm{{\mathcal M}} \def\name#1{\stackrel{\circ}{#1}} \def\namexxx#1{\accentset{\circ}{#1}} \def\nn{{\mathcal N}} \def\om{\omega} \def\one{{\bf 1}} \def\poset{{\mathbb P}} \def\proof{\par\noindent Proof\par\noindent} \def\pr{\prime} \def\qed{\par\noindent QED\par\bigskip} \def\qq{{\mathcal Q}} \def\ra{\rangle} \def\res{\upharpoonright} \def\rmand{\mbox{ and }} \def\rmiff{{\mbox{ iff }}} \def\rmor{\mbox{ or }} \def\rr{{\mathcal R}} \def\si{\sigma} \def\sm{{\setminus}} \def\st{\;:\;} % such that \def\sumposet{\Si_{n<\om}\poset(D+E_n)} \def\su{\subseteq} \newtheorem{theorem}{Theorem}[section] \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 A Dedekind Finite Borel Set} \end{center} \begin{flushright} Arnold W. Miller \footnote{ \par Mathematics Subject Classification 2000: 03E25 03E15 \par Keywords: Dedekind finite, Perfect set, countable sets of reals, countable axiom of choice \par We would like to thank Mark Fuller and Daniel Kane for bringing this problem to our attention and especially Mark for his enthusiastic interest. } \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 three theorems about the theory of Borel sets in models of ZF without any form of the axiom of choice. We prove that if $B\su 2^\om$ is a $G_{\de\si}$-set then either $B$ is countable or $B$ contains a perfect subset. Second, we prove that if $2^\om$ is the countable union of countable sets, then there exists an $F_{\si\de}$ set $C\su 2^\om$ such that $C$ is uncountable but contains no perfect subset. Finally, we construct a model of ZF in which we have an infinite Dedekind finite $D\su 2^\om$ which is $F_{\si\de}$. \end{quote} {\small \tableofcontents} \section{ Introduction } In this paper we assume the theory ZF but we do not assume any form of the axiom of choice, in particular, we do not assume the countable axiom of choice (which says that choice functions exist for countable families of nonempty sets). For example, we do not assume that the countable union of countable sets is countable. Early researchers in set theory while critical of the use of the axiom of choice to prove that every set can be well-ordered seem to have been unaware of their own use of the countable axiom of choice (see Moore \cite{moore}, Maddy \cite{maddy} p.487-9). A classical result is that (assuming the countable axiom of choice) every uncountable Borel set contains a perfect set. In fact, it is not hard to see, that assuming the countable axiom of choice every Borel subset of $2^\om$ is the projection of a closed subset of $2^\om\times \om^\om$, i.e., an analytic set, and that every uncountable analytic set contains a perfect set. \begin{define} \begin{enumerate} \item For $s\in 2^{<\om}$ define the basic clopen set: $$[s]=\{x\in 2^\om\st s\su x\}.$$ \item A set $U\su 2^\om$ is open iff it is the union of basic clopen sets. \item A set $A\su 2^\om$ is $G_{\de}$ iff it is the intersection of a countable family of open sets. \item A set $B\su 2^\om$ is $G_{\de\si}$ iff it is the union of a countable family of $G_\de$-sets. \item Similarly define $F$ be the closed sets, i.e., complements of open sets, $F_\si$ the countable unions of closed sets, and $F_{\si\de}$ the countable intersections of $F_\si$'s. \item A subset $P\su 2^\om$ is perfect iff it is homeomorphic to $2^\om$. \end{enumerate} \end{define} \begin{theorem}\label{perfthm} If $A\su 2^\om$ is a $G_{\de\si}$ set, then $A$ is countable or contains a perfect set. \end{theorem} \begin{theorem} \label{thmctble} Suppose that $2^\om$ is the countable union of countable sets. Then there exists an $F_{\si\de}$ set $B\su 2^\om$ which is uncountable but contains no perfect subset. \end{theorem} In the Feferman-Levy model $2^\om$ is the countable union of countable sets (see Cohen \cite{cohen} p.143, Jech \cite{jech} p.142). Note that this implies that every set $B\su 2^\om$ is the countable union of countable sets. Since a countable subset of $2^\om$ is $F_\si$, it follows that every subset of $2^\om$ is $F_{\si\si}$, i.e., a countable union of countable unions of closed sets. By taking complements every subset of $2^\om$ is $G_{\de\de}$. So the set $B$ in Theorem \ref{thmctble} is $F_{\si\de}$, $F_{\si\si}$, and $G_{\de\de}$. The fact that in the Feferman-Levy model, there is an uncountable Borel set without a perfect subset was observed by Juris Steprans (see Moore \cite{moore} p.103 footnote 27). In ZF without using any choice at all there exists a $G_{\de\si}$-set which is not $F_{\si\de}$, see Theorem 2.1 of Miller \cite{longbor}. A set $D$ is Dedekind finite iff every one-one map of $D$ into itself is onto. Equivalently, there is no one-one map of $\om$ into $D$. Assuming the countable axiom of choice every Dedekind finite set is finite. The book Herrlich \cite{herrlich} pp.43-50 summarizes many of the basic results about Dedekind finite sets. By infinite set we simply mean that the set is not finite, i.e., cannot be put into one-to-one correspondence with some finite ordinal $n\in\om$. \begin{theorem}\label{thmded} Suppose that $M$ is a countable transitive model of ZF and $$M\models D\su 2^\om \mbox{ is an infinite Dedekind finite set. }$$ Then there exists a symmetric submodel $\nn$ of a generic extension of $M$ such that $$\nn\models D \mbox{ is a Dedekind finite $F_{\si\de}$-set.}$$ \end{theorem} For our forcing terminology and basic facts about forcing over models of ZF see Miller \cite{longbor} section 3. \begin{remark} If $2^\om$ is the countable union of countable sets, then there are no infinite Dedekind finite $D\su 2^\om$. This is because the countable union of finite subsets of a linearly orderable set is countable. \end{remark} Besides the notion of Dedekind finite there are many other ``definitions of finiteness'', i.e., properties which are equivalent to finite assuming the axiom of choice (see Truss \cite{trussded}, L\'{e}vy \cite{levy}, Howard and Yorke \cite{howard}, De la Cruz \cite{cruz}). Most of them are inconsistent with being an infinite subset of $2^\om$. One exception is $\Delta_5$ (see Truss \cite{trussded}): A set $D$ is $\Delta_5$ iff there does not exist an onto map $f:D\to D\cup\{*\}$ where $*$ is not an element of $D$. It is possible to have an infinite $\Delta_5$ subset of $2^\om$. Let us say $D\su 2^\om$ has the density-Dedekind property iff it is a dense subset of $2^\om$ and for any $E\su D$ there exists an open set $U\su 2^\om$ such that $d\in E$ iff $d\in U\cap D$ for all but finitely many $d\in D$. Density-Dedekind implies $\Delta_5$. In the basic Cohen model of ZF in which choice fails (see Jech \cite{jech} p.66-68) there is a generic Dedekind finite set $A\su 2^\om$. It is not hard to show that in fact $A$ has the density-Dedekind property and hence is $\Delta_5$. The notion of density-Dedekind seems to us to be analogous to that of Luzin set in set theory with choice. We don't know if it is possible to have an infinite Borel $\Delta_5$-set. Almost-disjoint sets forcing destroys the density-Dedekind property. A set is amorphous iff every subset of it is finite or cofinite. This is analogous in model theory with the Baldwin and Lachlan notion of strongly minimal set (see Truss \cite{trussamor}, Creed, Truss \cite{creedomin}, Mendick, Truss \cite{mend}, and Walczak-Typke \cite{wal}). An infinite $D\su 2^\om$ cannot be amorphous. We don't know if there could be an uncountable Borel set $D\su 2^\om$ such that every subset is countable or co-countable (i.e., quasi-amorphous, see Creed, Truss \cite{creedquasi}). Monro \cite{monro} constructed Dedekind finite sets which are large in the sense that they can be mapped onto a cardinal $\ka$. The ones he constructed were subsets of $2^\ka$. It is possible to have a Dedekind finite Borel set which maps onto $\om_1$ (or any other larger $\om_\al$ if desired). By Theorem \ref{thmded} it is enough to find a Dedekind finite set $D\su 2^\om$ which maps onto $\om_\al$. Such a $D$ can be constructed by using a slight variant of the second Cohen model, see Jech \cite{jech} pp. 68-71. In computability theory, the notion of Dedekind finite is analogous to that of Dekker's notion of an isol. There are over 180 of papers on the theory of isols, although currently the subject seems to have fallen out of fashion. Two which connect the theory of isols and Dedekind finite cardinals are Ellentuck \cite{ellen} and McCarty \cite{mccarty}. Perhaps there are analogies between Borel Dedekind finite sets and co-simple isols, i.e., complements of simple sets. See for example, Downey and Slaman \cite{downey} which contains work on co-simple isols. \section{Proof of Theorem \ref{perfthm}} \begin{define} Recall the following: \label{treedef} \begin{enumerate} \item A nonempty $T\su 2^{<\om}$ is a tree iff $\forall s,t\in 2^{<\om}$ if $s\su t\in T$, then $s\in T$. \item For $T$ a tree $$[T]=\{x\in 2^\om\st \forall n<\om\;\; x\res n\in T\}$$ \item For $T$ a tree and $s\in T$ $$T(s)=\{t\in T\st t\su s\rmor s\su t\}.$$ \item A tree $T$ is perfect iff $\forall s\in T\;\;\exists t\in T \;\;s\su t$ and both $t\concat 0\in T$ and $t\concat 1\in T$. \end{enumerate} \end{define} \noindent The proof of the following proposition is left to the reader. \begin{prop} A set $C\su 2^\om$ is closed iff there exists a tree $T\su 2^{<\om}$ such that $C=[T]$. A set $P\su 2^\om$ is perfect iff there is a perfect tree $T\su 2^{<\om}$ such that $P=[T]$. In both cases we may demand that the tree $T$ have no terminal nodes, i.e., for any $s\in T$ either $s\concat 0\in T$ or $s\concat 1\in T$. \end{prop} \begin{lemma}\label{perflem1} Let $\bb$ be the family of nonempty countable closed subsets of $2^\om$. Then there is a function $\ff:\bb\to (2^\om)^\om$ such that if $\ff(C)=f$, then $f:\om\to C$ is an onto map. \end{lemma} \proof This argument is ancient set theory, the Cantor-Bendixson derivative. (Recall we must not use the axiom of choice.) Let $C$ be a nonempty countable closed set. Define $$T=\{s\in 2^{<\om}\st [s]\cap C\neq\emp\}.$$ Hence $[T]=C$. Inductively define a sequence of trees $T_\al\su 2^{<\om}$ for $\al$ an ordinal as follows: \begin{enumerate} \item $T_0=T$ \item $T_\lam=\bigcap_{\al<\lam} T_\al$ if $\lam$ is a limit ordinal \item $T_{\al+1}=T_\al\sm \{t\in T_\al\st |[T_\al(t)]| \leq 1\}.$ \end{enumerate} Note that $\al\leq \be$ implies $T_\be\su T_\al$. If $T_{\al+1}=T_\al$, then $T_\al=T_\be$ for all $\be>\al$. By the replacement axiom there must be an ordinal $\al$ such that $T_{\al+1}=T_\al$. Since $T_\al\su T$ we have that $[T_\al]\su C$ and since $C$ is countable, it must be that $T_\al$ is empty, since otherwise it is easy to check that it is a perfect tree. For each $x\in C$ there exists a unique ordinal $\al_x<\al$ such that $$x\in [T_{\al_x}]\sm [T_{\al_x+1}].$$ Let $n$ be the least such that $x\res n \notin T_{\al_x+1}$ and put $s_x=x\res n$. We claim that the map $q:C\to 2^{<\om}$ defined by $q(x)=s_x$ is one-to-one. To see this suppose that $s_x=s_y$. If $\al_x<\al_y$, then we get a contradiction since $s_x\notin T_{\al_x+1}$ and $T_{\al_y}\su T_{\al_x+1}$. So $\al_x=\al_y$ and from the definition of $T_{\al_x+1}$ we see that $x=y$. To get our onto map $f:\om\to C$, let $x_0$ be the lexicographically least element of $C$ and let $\{t_n\st n<\om\}$ be a fixed enumeration of $2^{<\om}$. Given any $n$ if $t_n=s_x$ for some $x\in C$ let $f(n)=x$ and otherwise let $f(n)=x_0$. No choice is being used in our definition of $f$, so we may define $\ff(C)=f$. \qed \begin{cor} The countable union of closed subsets of $2^\om$ each of which is countable is countable. \end{cor} \begin{lemma}\label{perflem2} Let $\hh$ be the family of nonempty countable $G_\de$ subsets of $2^\om$. Then there is a function $\gg:\hh\to (2^\om)^\om$ such that if $\gg(H)=g$, then the map $g:\om\to H$ is onto. \end{lemma} \proof This argument is also ancient set theory (although perhaps not as well known), the Hausdorff difference hierarchy. Hausdorff proved that disjoint $G_\de$ sets can be separated by a set which is in the difference hierarchy of closed sets (see Kechris \cite{kechris} p.176). Let $H,K\su 2^\om$ be disjoint $G_\de$-sets. Define closed sets $C_\al\su 2^\om$ for $\al$ an ordinal as follows: $C_0=\cl(H)$ (we use $\cl(X)$ to denote the closure of $X$) $C_1=\cl(C_0\cap K)$ $C_2=\cl(C_1\cap H)$ $\vdots$ $C_\om=\bigcap_{n<\om}C_n$, $C_{\om+1}=\cl(C_\om\cap K)$ $C_{\om+2}=\cl(C_\om\cap H)$ and so forth, in general, for $\lambda$ a limit ordinal and $n<\om$: $$C_\lam=\bigcap_{\al<\lam}C_\al$$ $$C_{\lam+n+1}=\left\{ \begin{array}{ll} \cl(C_{\lam+n}\cap H) & \mbox{if $n$ is odd}\\ \cl(C_{\lam+n}\cap K) & \mbox{if $n$ is even}\\ \end{array}\right.$$ It is clear that if $\al\leq \be$ then $C_\be\su C_\al$. Also if\footnote{With a little more work it is enough that $C_\al=C_{\al+1}$.} $C_\al=C_{\al+2}$ then for all $\be>\al$, $C_\be=C_\al$. Hence there must be an ordinal $\al_0$ such that $C_{\al_0}=C_\be$ for all $\be>\al_0$. We claim that $C_{\al_0}$ is empty, otherwise, $H$ and $K$ are both dense in it and it would follow that $H\cap K\neq \emp$. To see this, let $$T_{\al_0}=\{s\in 2^{<\om}\st [s]\cap C_{\al_0}\neq\emp\}.$$ Write $H=\bigcap_{n<\om} U_n$ and $K=\bigcap_{n<\om} V_n$ where $U_n$ and $V_n$ are open sets. Since $H$ and $K$ are dense in $C_{\al_0}$, it must be that for every $s\in T_{\al_0}$ and $n<\om$, there exists $t\in T_{\al_0}$ with $s\su t$ and $[t]\su U_n\cap V_n$. But now it is easy to construct $x\in [T_{\al_0}]\cap H\cap K$ without using the axiom of choice. Since $C_{\al_0}$ is empty we have that the difference sets: $$D=\bigcup\{(C_\al\sm C_{\al+1}) \st \al \mbox{ is even }\}$$ and $$E=(2^\om\sm C_0)\cup\bigcup \{(C_\al\sm C_{\al+1}) \st \al \mbox{ is odd }\}.$$ are complements of each other.\footnote{The ordinal $\al_0$ must be countable and the unions could be taken over $\al\leq \al_0+2$ but we don't need this for our proof.} We claim that $H\su D$ and $K\su E$. To see why, suppose that $x\in H$. Since $C_0=\cl(H)$ it must be that there is some ordinal $\al$ such that $x\in C_\al\sm C_{\al+1}$. This $\al$ cannot be odd, since $C_{\al+1}=\cl(C_\al\cap H)$. Similarly $K\su E$. Now suppose that $H$ is a countable $G_\de$-set. Then $K=2^\om\sm H$ is also a $G_\de$-set. From which it follows that $$H\;\;= \;\;\bigcup \{(C_\al\sm C_{\al+1}) \st \al \mbox{ is even }\}.$$ Define $$T_\al=\{s\in 2^{<\om}\st [s]\cap C_\al\neq\emp\}.$$ So for $\al<\al_0$ we have that each $T_\al$ is a nonempty tree without terminal nodes such that $C_\al=[T_\al]$. For $s\in 2^{<\om}$ with length greater than $0$, let $s^*\su s$ with $|s^*|=|s|-1$. Let $$Q_\al=\{s\in T_\al\sm T_{\al+1}\st s^*\in T_{\al+1}\}$$ i.e, the minimal nodes of $T_\al\sm T_{\al+1}$. For each even $\al$ since $C_\al\sm C_{\al+1}\su H$ and $H$ is countable we have that $[T_\al(s)]$ is a countable set for each $s\in Q_\al$. Note that the $Q_\al$ are pairwise disjoint. Let $Q\su 2^{<\om}$ be the set of all $s$ such that $s\in Q_\al$ and $\al$ is even. For each $s\in Q$ define $f_s:\om\to 2^{<\om}$ by $\ff([T_\al(s)])=f_s$ where $s\in Q_\al$. It follows that the map $h:Q\times\om\to H$ defined by $h(s,n)=f_s(n)$ is onto $H$ and may easily be readjusted to an onto map $g:\om\to H$. Put $\gg(H)=g$. \qed \begin{cor}\label{perfcor} The countable union of countable $G_\de$ subsets of $2^\om$ is countable. \end{cor} \proof Suppose that $\bigcup_{n<\om}H_n$ is given where each $H_n$ is a countable $G_\de$-set. Let $\gg(H_n)=g_n$. Then define an onto map $$g:\om\times\om\to \bigcup_{n<\om}H_n \;\;\;\;\mbox{ by }\;\;\;\; g(n,m)=g_n(m).$$ \qed \bigskip Proof of Theorem \ref{perfthm}. \bigskip It follows immediately from Corollary \ref{perfcor} that we need only show that an uncountable $G_\de$-set $H\su 2^\om$ must contain a perfect set. Define $$H^\pr=\{x\in H\st \forall n<\om\;\;\; ([x\res n]\cap H) \mbox { is uncountable } \}.$$ Note that $H^\pr$ is nonempty, since otherwise $$H = \bigcup\{[s]\cap H\st [s]\cap H \mbox{ is countable},\;\; s\in 2^{<\om}\}$$ and since any set of the form $[x\res n]\cap H$ is $G_\de$ and the countable union of $G_\de$-sets is countable, we would get a contradiction. Define $$T=\{s\in 2^{<\om}\st [s]\cap H^\pr\neq \emp\}.$$ We claim that $T$ is a perfect tree. To see this suppose that $s\in T$. Then $s$ will have incompatible extensions in $T$ unless $H^\pr\cap [s]=\{x\}$. This would mean that for every extension $t$ of $s$ which is incomparable to $x$ that $H\cap [t]$ is countable. But since $s\su x$ we know that $H\cap [s]$ is uncountable. But this contradicts the fact that the countable union of countable $G_\de$-sets is countable. Now suppose $H=\bigcap_{n<\om} U_n$ where each $U_n$ is open. We construct $$(s_\si\in T:\si\in 2^{<\om})$$ by induction on the length of $\si$. Given $s_\si$ with $|\si|=n$ let $t\in T(s_\si)$ be the first in some fixed ordering of $2^{<\om}$ with $[t]\su U_n$. Then using that $T$ is perfect, find $s_{\si\concat i}\in T$ for $i=0,1$ incomparable extensions of $t$. Then $$T^\pr=\{t\st \exists\si\;\; t\su s_\si\}$$ is a perfect subtree of $T$ such that $[T^\pr]\su H$. \qed \section{Proof of Theorem \ref{thmctble}} \begin{define} Let $\la,\ra:\om\times\om\to\om$ be a fixed bijection, i.e., a pairing function. 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(\la n,m\ra).$$ \end{define} \begin{lemma}\label{lemnice} Suppose that $2^\om$ is the countable union of countable sets. Then there exists $(F_n\st n\in\om)$ such that \begin{enumerate} \item $2^\om=\bigcup_{n<\om}F_n$ and each $F_n$ is countable, \item $F_n$ is a proper subset of $F_{n+1}$ for each $n$, and \item $F_n$ is closed under $\pi_m$ for all $n,m<\om$. \end{enumerate} \end{lemma} \proof Define a map $H:\om^{<\om}\times 2^{\om}\to 2^{\om}$ inductively by $$H(\la \ra,x)=x \rmand H(s\concat m,x)=\pi_m(H(s,x)).$$ Given that $2^\om=\bigcup_{n<\om}L_n$ where each $L_n$ is countable, let $$F_n=H(\om^{<\om}\times \bigcup_{m\leq n}L_m).$$ Then the $F_n$ are countable, increasing, cover $2^\om$, and closed under the projection maps $\pi_m$. To get them to be properly increasing just pass to a subsequence. \qed Define $$B_n=\{x\in 2^\om:\pi_n(x)\in F_{n+1}\sm F_n \rmor [\pi_n(x)\in F_n \rmand \pi_n(x)=\pi_{n+1}(x)] \}.$$ Note that each $B_n$ is an $F_\si$-set. Let $B=\bigcap_{n<\om} B_n$. The set $B$ is uncountable because there is a map $h$ from $B$ onto $2^\om$. Define $h$ by $h(x)=\pi_n(x)$ iff $\pi_n(x)=\pi_m(x)$ for all $m>n$. Such an $n$ must exist because for any $x$ there exists $n$ such that $x\in F_n$ and hence $\pi_m(x)\in F_n$ for all $m$. It is easy to check that $h$ maps $B$ onto $2^\om$. But $B$ cannot contain a perfect set. Suppose for contradiction that $T\su 2^{<\om}$ is a perfect tree and $[T]\su B$. For each $x\in [T]$ define $h(x)=n$ to be the least $n$ so that $\pi_n(x)=\pi_m(x)$ for all $m>n$. For any $n$ the set of all $x\in [T]$ with $h(x)\leq n$ is closed. By Corollary \ref{perfcor} it must be that for some $n$ there exists a perfect subtree $T^\pr\su T$ such that $x\in [T^\pr]$ implies $h(x)< n$. But the map $$k:[T^\pr]\to \prod_{mn\; \forall k>l \;\; x(k)=0\}$$ As usual for $x,y\in 2^\om$ define $x+y$ to be their pointwise sum mod 2, i.e., $$ \forall n\;\;\; (x+y)(n)\equiv x(n)+y(n) \mbox{ mod }2$$ and for $A,B\su 2^\om$ define $$A+B=\{x+y\st x\in A \rmand y\in B\}.$$ \end{define} \begin{lemma} For $D\su 2^\om$ Dedekind finite $$D=\bigcap_{n<\om}(D+E_n).$$ \end{lemma} \proof Since the constant zero function is in every $E_n$ it is clear that $$D\su\bigcap_{n<\om}(D+E_n).$$ Now suppose for contradiction that $x\in \bigcap_{n<\om}(D+E_n)$ but $x\notin D$. Consider the equivalence class of $x$ under ``equal mod finite'': $x+E_0$. Since this class can be well-ordered in type $\om$ we know that the set: $$F=D\cap (x+E_0)$$ is finite. Take $n<\om$ large enough so that for all $u,v\in F\cup\{x\}$ if $u\res n= v\res n$ then $u=v$. But $x\in D+E_n$ which means that there exists $d\in D$ with $d\res n= x\res n$. But $d\in F$ which is a contradiction. \qed \begin{define} We define the poset $\poset$ to be the direct sum of the posets: $\poset(D+E_n)$, i.e., $$\poset=\sumposet.$$ This means $p\in \poset$ iff $p=(p_n:n<\om)$ where each $p_n\in \poset(D+E_n)$ and $p_k=\one$ for all but finitely many $k$. It is ordered coordinatewise: $$p\leq q \rmiff p_n\leq q_n \mbox{ for all }n.$$ As before, given any $G$ a $\sumposet$-filter and $n<\om$ we define $$R_n=R_n^G=\{s\in 2^{<\om}\st \exists p\in G \mbox{ with } s\in Q_{p_n}\}.$$ \end{define} It is clear that for $G$ a $\poset$-generic filter over $M$ that for every $n$ and $x\in D+E_n$ there are at most finitely many $k<\om$ with $x\res k\in R_n$. \begin{lemma} The poset $\poset=\sumposet$ is $\si$-centered. \end{lemma} \proof For any finite sequence $\vec{Q}=(Q_i:in\}.$$ Letting $\rr=\{R_n\st n<\om\}$ we have that $$\bigcap\{H(R)\st R\in\rr\}=\bigcap_{n,m<\om} \bigcup\{[s] \st s\in R_n\rmand |s|>m\}.$$ \qed Note that $H(R_n)$ is a $G_\de$-set disjoint from $D+E_n$. Our goal is to make the complement of $D$ to be a countable union of $G_\de$ sets in a symmetric submodel of $M[G]$. We describe the automorphisms of $\poset$ which we will use. \begin{define} \begin{enumerate} \item For $s\in 2^{<\om}$ define $\hat{\pi}_s:2^{<\om}\to 2^{<\om}$ to be the tree automorphism which swaps $s\concat 0$ and $s\concat 1$, i.e., $$\hat{\pi}_s(r)=\left\{ \begin{array}{ll} s \concat {1-i} \concatx t & \mbox{ if } r=s \concat i \concatx t\\ r & \mbox{ if $r$ does not extend $s$. }\\ \end{array} \right. $$ \item For each $n$ we let $\gg_n$ be the group of automorphisms of $\poset(D+E_n)$ which are generated by $\{\pi_s\st s\in 2^{<\om}\rmand |s|>n\}$. \item We take $\gg$ to be the direct sum of the $\gg_n$, i.e., $\pi\in\gg$ iff $\pi=(\pi_n:n<\om)$ where each $\pi_n\in\gg_n$ and $\pi_k$ is the identity except for finitely many $k$. \item We take $\ff$ to be the filter of subgroups of $\gg$ which is generated by $\{H_n:n<\om\}$ where $$H_n=\{\pi\in\gg\st \forall mn_0$ such that $$q\forces \forall n>\check{N}\;\; \name{x}\res n\notin \name{R}_{n_0}.$$ \bigskip \noindent{\bf Claim}. There exists $r\leq q$ and $s,t_0,t_1\in 2^{<\om}$ with \begin{enumerate} \item $|s|>N>n_0$ \item $\{t\in 2^{<\om}\st s\su t\}\cap Q_{q_{n_0}}=\emp$ \item $[s]\cap F_{q_{n_0}}=\emp$. \item $s\su t_0$, $s\su t_1$, $|t_0|= |t_1|$ \item $t_0\in Q_{r_{n_0}}$ \item $r\forces \check{t}_1\su\name{x}$ \end{enumerate} \bigskip Since $p$ is forcing that $x$ is not in $D+E_{n_0}$ it easy to find $r_1\leq q$ and $s$ such that $$r_1\forces \check{s}\su\name{x}$$ and $s$ satisfies 1,2, and 3. Next choose any $t_0$ with $s\su t_0$ and $t_0\not\su y$ for all $y\in F_{r_{1,n_0}}$ and put $r_2=r_1$ except $$Q_{r_{2,n_0}}=Q_{r_{1,n_0}}\cup\{t_0\}.$$ Finally find $r\leq r_2$ and $t_1$ with $|t_0|=|t_1|$ and $r\forces \check{t}_1\su\name{x}$. This proves the Claim. \bigskip Now find $\hat{\pi}$ a tree automorphism in $\hat{\gg}_{n_0}$ such $\hat{\pi}(t_0)=t_1$ and fixes all $t$ except for possibly those extending $s$. A precise description would be to let: $$\{n\st t_0(n)\neq t_1(n)\}=\{n_1N>n_0$ so necessarily $n_1>n_0$. Let $\pi\in\gg$ also name the automorphism of $\poset$ which is $\pi$ on the $n_0^{th}$ coordinate and the identity on all other coordinates. Then $\pi\in H_{n_0}$ and hence $\pi(\name{x})=\name{x}$ and so by (6) of the Claim $$\pi(r)\forces \check{t}_1\su \name{x}.$$ Note that by (2) and (3) of the Claim, we have $\pi(q)=q$ and so $\pi(r)\leq q$ and thus: $$\pi(r)\forces\forall n>N\;\; \name{x}\res n\notin \name{R}_{n_0}.$$ By (5) of the Claim and the definition of $\pi$ we have that $t_1\in Q_{\pi(r)_{n_0}}$ so we have: $$\pi(r)\forces \check{t}_1\in \name{R}_{n_0}.$$ But $|t_1|>N$ gives us a contradiction. \qed Let $$\rr_n=\{\hat{\pi}(R_n)\st \hat{\pi}\in\hat{\gg}_{n}\}.$$ That is we take the set of all images of $R_n$ under the tree automorphisms which determine $\gg_n$. Since each $R_n$ is in $\nn$ and $\hat{\gg}_{n}$ is in the ground model, it is clear that each $\rr_n$ is in $\nn$. \begin{lemma}\label{lemravel} For each $\pi\in \gg$ and $n<\om$: $$\pi(\name{R}_n)^{G}=\hat{\pi}_n^{-1}(R_n).$$ \end{lemma} \proof This amounts to unraveling the definitions. The following are equivalent: \begin{itemize} \item $s\in \pi(\name{R}_n)^{G}$ \item $\exists p\in G$ such that $(p,\check{s})\in \pi(\name{R}_n)$ and $(p,\check{s})=(\pi(q),\check{s})$ where $s\in Q_{q_n}$ \item $\exists p\in G$ such that $s\in Q_{{\pi}_{n}^{-1}(p_n)}$ (equivalently $\hat{\pi}_{n}(s)\in Q_{p_n}$) \item $\hat{\pi}_n(s)\in R_n$ \item $s\in \hat{\pi}_n^{-1}(R_n)$. \end{itemize} \qed \begin{lemma} The sequence $(\rr_n:n\in\om)$ is in $\nn$. \end{lemma} \proof Letting $$\name{\rr}_n=\{\pi(\name{R}_n)\st \pi\in \gg\}$$ we see that $\fix(\name{\rr}_n)=\gg$ for every $n$, hence the $\om$-sequence has a name fixed by every $\pi$ in $\gg$. \qed Next we show that in the hypothesis of the key lemma (Lemma \ref{keylem}) we may assume that the trivial condition $\one$ is doing the forcing. \begin{lemma} \label{lemone} Fix $G$ a $\poset$-filter generic over $M$. Suppose $x\in (2^\om\sm D)\cap\nn$. Then $x$ has a hereditarily symmetric name $\name{x}$ for which there is an $n_0$ such that $H_{n_0}\su\fix(\name{x})$ and $$\one\forces \name{x}\in 2^\om\sm (D+E_{n_0}).$$ \end{lemma} \proof Let $\tau$ be any hereditarily symmetric name for $x$, i.e., $\tau^G=x$. Let $p\in G$ and $n_0$ be such that $H_{n_0}\su\fix(\tau)$ and $$p\forces \tau\in 2^\om\sm (D+E_{n_0}).$$ Now work in the ground model $M$. Fix $z\in M\cap (2^\om\sm (D+E_{n_0}))$. In $M$ define $\name{x}$ to the set of all $(q,\la m,i\ra)$ such that either $$q\forces \mbox{``} \tau\in 2^\om\sm (D+E_{n_0}) \wedge \tau(m)=i \mbox{''}$$ or $$z(m)=i \rmand q\forces \neg (\tau\in 2^\om\sm (D+E_{n_0})).$$ For our particular $G$, since $p\in G$ the second clause is never invoked when evaluating $\name{x}^G$, hence $x=\tau^G=\name{x}^G$. Clearly, $H_{n_0}\su\fix(\tau)\su\fix(\name{x})$. Finally $\one$ forces what it should because for any generic filter $G^\pr$ either the first clause is invoked and $\tau^{G^\pr}=\name{x}^{G^\pr}$ or the second clause is invoked and $\name{x}^{G^\pr}=z$ where $z$ was chosen to be in $2^\om\sm (D+E_{n_0})$. \qed \begin{lemma} $\nn\models (2^\om\sm D)=\bigcup_{n<\om}\bigcap_{R\in \rr_n}H(R)$. \end{lemma} \proof Recall that $H(R_n)$ is a $G_\de$-set which is disjoint from $D+E_n$ and hence from $D$. For any $R\in\rr_n$ we have that $R=\hat{\pi}(R_n)$ for some $\pi\in\gg_n$. But by Lemma \ref{lemravel} $$R=\hat{\pi}(R_n)=\pi^{-1}(\name{R}_n)^{G}=\name{R_n}^{\pi^{-1}(G)}$$ and so $H(R)$ is disjoint from $D$. Conversely suppose in $\nn$ that $x\in (2^\om\sm D)$. Then by Lemma \ref{lemone} $x$ has a name $\name{x}$ for which there exists $n_0$ such that $H_{n_0}\su\fix(\name{x})$ and $$\one\forces \name{x}\in 2^\om\sm (D+E_{n_0}).$$ By the key Lemma \ref{keylem} $$\one\forces \exists^\infty k\;\; \name{x}\res k\in\name{R}_{n_0}$$ i.e., $$\one\forces \name{x}\in H(\name{R}_{n_0}).$$ Since $H_{n_0}\su\fix(\name{x})$ we have that $$\one\forces \name{x}\in H(\pi(\name{R}_{n_0}))$$ for all $\pi\in H_{n_0}$ and so it follows from Lemma \ref{lemravel} that $$x\in \bigcap_{R\in \rr_n}H(R).$$ \qed It follows from this Lemma that (in $\nn$) the complement of $D$ is a $G_{\de\si}$ set and hence $D$ is an $F_{\si\de}$-set. Since $\poset$ is $\si$-centered we have that $$M[G]\models D\mbox{ is Dedekind finite}$$ and since $M\su\nn\su M[G]$ $$\nn\models D\mbox{ is a Dedekind finite $F_{\si\de}$-set. }$$ This concludes the proof of Theorem \ref{thmded}. \addcontentsline{toc}{section}{References} \begin{thebibliography}{99} \bibitem{cohen} Cohen, Paul J.; {\bf Set theory and the continuum hypothesis.} W. A. Benjamin, Inc., New York-Amsterdam 1966 vi+154 pp. \bibitem{creedomin} Creed, P.; Truss, J. K.; On o-amorphous sets. Ann. Pure Appl. Logic 101 (2000), no. 2-3, 185--226. \bibitem{creedquasi} Creed, P.; Truss, J. K.; On quasi-amorphous sets. Arch. Math. Logic 40 (2001), no. 8, 581--596. \bibitem{cruz} De la Cruz, Omar; Finiteness and choice. Fund. Math. 173 (2002), no. 1, 57--76. \bibitem{downey} Downey, Rod; Slaman, Theodore A.; On co-simple isols and their intersection types. Ann. Pure Appl. Logic 56 (1992), no. 1-3, 221--237. \bibitem{ellen} Ellentuck, Erik; The universal properties of Dedekind finite cardinals. Ann. of Math. (2) 82 1965 225--248. \bibitem{herrlich} Herrlich, Horst; {\bf Axiom of choice}. Lecture Notes in Mathematics, 1876. Springer-Verlag, Berlin, 2006. xiv+194 pp. ISBN: 978-3-540-30989-5 \bibitem{howard} Howard, Paul E.; Yorke, Mary F.; Definitions of finite. Fund. Math. 133 (1989), no. 3, 169--177. \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{kechris} Kechris, Alexander S.; {\bf Classical descriptive set theory.} Graduate Texts in Mathematics, 156. Springer-Verlag, New York, 1995. xviii+402 pp. \bibitem{levy} L\'{e}vy, A.; The independence of various definitions of finiteness. Fund. Math. 46 1958 1--13. \bibitem{mend} Mendick, G. S.; Truss, J. K.; A notion of rank in set theory without choice. Arch. Math. Logic 42 (2003), no. 2, 165--178. \bibitem{longbor} Miller, Arnold W.; Long Borel hierarchies, Math Logic Quarterly, 54(2008), 301-316. \bibitem{mccarty} McCarty, Charles; Markov's principle, isols and Dedekind finite sets. J. Symbolic Logic 53 (1988), no. 4, 1042--1069. \bibitem{maddy} Maddy, Penelope; Believing the axioms. I. J. Symbolic Logic 53 (1988), no. 2, 481--511. \bibitem{moore} Moore, Gregory H.; {\bf Zermelo's axiom of choice. Its origins, development, and influence.} Studies in the History of Mathematics and Physical Sciences, 8. Springer-Verlag, New York, 1982. xiv+410 pp. \bibitem{monro} Monro, G. P.; Independence results concerning Dedekind-finite sets. J. Austral. Math. Soc. 19 (1975), 35--46. \bibitem{trussded} Truss, J. K.; Classes of Dedekind finite cardinals. Fund. Math. 84 (1974), no. 3, 187--208. \bibitem{trussamor} Truss, J. K.; The structure of amorphous sets. Ann. Pure Appl. Logic 73 (1995), no. 2, 191--233. \bibitem{wal} Walczak-Typke, A. C.; The first-order structure of weakly Dedekind-finite sets. J. Symbolic Logic 70 (2005), no. 4, 1161--1170. \end{thebibliography} \address \end{document}