\documentclass{article}
\usepackage{amssymb}
\usepackage{amstext}

\newcommand{\Z}{{\mathbb Z}}
\renewcommand{\P}{{\frak{P}}}
\newcommand{\cut}{\cap}

\newcommand{\tcl}{{\rm tcl}}
\title{Two Models of $\lnot \exists \tcl(x)$}
\author{Martin Goldstern}
\date{September 1998}

\begin{document}
\maketitle


Let $\tcl(x) = \{x\} \cup x \cup \bigcup x \cup \cdots $ be the
transitive closure of $x$.  The usual proof that $\tcl(x)$ exists
invokes the replacement axiom.    

To show that some form of replacement is necessary, we give a model of
ZC (i.e., ZFC except for the replacement axiom), in which there is a
set which has no transitive closure. 

(Note that the ``usual'' model of ZC, the sets of rank $ < \alpha$,
satisfy  $\forall x\, \exists tcl(x)$.)


\bigskip\noindent{\bf First model:}
   Let $ \kappa = \sup\{\kappa _n: n \in
\omega \}$, where $\kappa_0\ge {\aleph_0} $ and $2^{\kappa_n}\le
\kappa_{n+1}$ for all $n$.   
Define $H(\kappa)$ as 
$$ H(\kappa) := \{ x: \ \forall n \ge 0 \,\, \biggl|\bigcup^n x
\biggr| < \kappa \}$$
where $\bigcup^0 x = x$, $\bigcup^{n+1} x = \bigcup\bigl(\bigcup^n
x\bigr)$. 

It is easy to see that $H(\kappa)$ satisfies ZC.   Let $a:=
\{\kappa_0, \{\kappa_1\},\{\{ \kappa_2\}\}, \{\{\{ \kappa_3\}\}\}$.
Then $a\in H(\kappa)$, but $H (\kappa) \models $ ``there is no
transitive set containing $a$.''


\bigskip
\noindent{\bf Second model: [suggested by Bernhard Bodenstorfer]}
For convenience we will  work in the theory $ZFC \setminus \{{\rm
Foundation }\} + \exists A= \{a_n:n \in \Z\}\, \forall n : a_{n+1}
=\{a_n\}$, all $a_n$ distinct.  (The argument can be translated into
ZFC.)

Let $A = \{a_n:n \in \Z\}$ be as above. For every ordinal $\alpha $
we define sets $R_\alpha$ (the ``pure'' sets) and $M_\alpha$: 
\begin{itemize}
\item[--] $R_0 = \emptyset$, $M_0 = A$.
\item[--] $R_{\alpha+1} = \P(R_\alpha) = \{x: x \subseteq M_\alpha, x
\cut (M_\alpha \setminus R_\alpha) = \emptyset\}$
\item[--] $M_{\alpha+1} = \{x: x \subseteq M_\alpha, 
x\cut (M_\alpha \setminus R_\alpha) \text{ is finite}\}$
\item[--] $M_\delta = \bigcup_{\alpha < \delta } M_\alpha$, 
 $R_\delta = \bigcup_{\alpha < \delta } R_\alpha$ for $\delta $  a
 limit ordinal
\end{itemize}
Check that for any limit ordinal $\delta > \omega$ we have $M_\delta
\models ZC$, and $M_\delta \models $ ``$a_0$ has no transitive
closure''. 

For example, to check the separation axiom, let $B \in
M_{\alpha+1}$. We show that every $ C \subseteq B$ is in $M_{\alpha
+1}$:

Let $B_0 = B \cap R_\alpha$, $B_1 = B \setminus B_0$.  So $B_1$ is
finite.  Let $C_0 = C \cap B_0$, $C_1 = C \cap B_1$. Now  $C
\subseteq R_\alpha $ and $C_1$ is a finite subset of $M_\alpha
\setminus R_\alpha$, so $C\in M_{\alpha+1}$. 


Each model $M_\alpha$ will satisfy the axiom of foundation.
This can be proved by induction. (Note that $A\notin M_\alpha$, for
all $\alpha$)



\end{document}


