\documentclass{amsart}
\usepackage{a4wide}

  % \usepackage{amsmath}\usepackage{amsthm}
\usepackage{mathrsfs}
\def\xx#1 {\newtheorem{#1}[thm]{#1}}
\theoremstyle{definition}
\newtheorem{thm}{Theorem}
\xx Lemma
\xx Theorem
\xx Definition
\xx Suggestion
\xx Construction
\xx Notation
\xx Remark
\xx Conclusion
\xx {Definition and Fact}
\xx Fact
\xx Assumption
\newcommand{\dom}{{\rm dom}}
\newcommand{\vareps}{\mathrel{\varepsilon}}


\title{Set theory with complements}
\author{Martin Goldstern}
\address{Algebra\\Technische Universit\"at\\
Wiedner Hauptstr 8-10\\A-1040 Wien, Austria}
\email{Martin.Goldstern@tuwien.ac.at}
\subjclass{Primary 03E70; secondary 03E30}
\date{2000-03-27}

% 
% 03E02 Partition relations
% 03E04 Ordered sets and their cofinalities; pcf theory
% 03E05 Other combinatorial set theory
% 03E10 Ordinal and cardinal numbers 
% 03E15 Descriptive set theory
% 03E17 Cardinal characteristics of the continuum
% 03E20 Other classical set theory (including functions, relations, and set algebra)
% 03E25 Axiom of choice and related propositions 
% 03E30 Axiomatics of classical set theory and its fragments
% 03E35 Consistency and independence results
% 03E40 Other aspects of forcing and Boolean-valued models
% 03E45 Inner models, including constructibility, ordinal definability, and core models
% 03E47 Other notions of set-theoretic definability
% 03E50 Continuum hypothesis and Martin's axiom 
% 03E55 Large cardinals 
% 03E60 Determinacy principles
% 03E65 Other hypotheses and axioms
% 03E70 Nonclassical and second-order set theories 
% 03E72 Fuzzy set theory
% 03E75 Applications of set theory
% 03E99 None of the above, but in this section






\def\itm#1 {\item[{#1}]}
\renewcommand{\P}{{\mathscr P}}

\begin{document}



\begin{abstract}
We show that the following theory ZFCK
 is consistent (assuming the consistency
of ZFC)

ZFCK consists of the usual ZFC axioms with the following modifications:
\begin{itemize}
\item Foundation is not required.   Call a set grounded if the
$\varepsilon$-relation on its transitive closure is well-founded. 
\item Separation only postulates that subclasses of grounded sets exists,
\item Replacement postulates that the images of grounded sets exist.
\item Power set postulates that the power set of any grounded set exists. 
\item The infinity axiom postulates that there is a smallest
inductive set (or: a smallest limit ordinal $>0$).
\item In addition, we require that {\bf every set has a complement},
so in particular the universal set (=complement of $\emptyset$, the 
``set of all set'') exists. 
\end{itemize}
\end{abstract}


\maketitle

\newcommand{\M}{{\bf M}}
\newcommand{\E}{{\boldsymbol{ \epsilon}}}
\newcommand{\notE}{{\not\!\boldsymbol{ \epsilon}}}
\newcommand{\Ext}{{\bf Ext}}
\newcommand{\F}{{\bf F}}
\newcommand{\A}{{\bf A}}
\newcommand{\V}{{\bf V}}
\newcommand{\Ord}{{\bf Ord}}


This note deals with set theories that admit non-wellfounded sets. 
We will use the following definitions. 

\begin{itemize}
\item A set $x$ is called wf if the structure $(x,\in)$ is
well-founded.
\item A set $x$ is called grounded if it is contained in a
well-founded transitive set.
\end{itemize}
If transitive closures exist, then $x$ is grounded iff its transitive
closure is well-founded.  If $\omega$ exists and certain instances of
replacement and AC hold, then a set $x$ is grounded iff there is no
$\in$-decreasing $\omega$-sequence starting with $x$. 

In ZF minus Foundation, the statements ``every set is well-founded''
and  ``every set is grounded'' are equivalent, and either of them can
be called the ``regularity axiom.''


\bigskip
\bigskip


T.E.Forster's book ``Set theory with a universal set'', discusses
(among others) set theories of Church and Mitchell.  

In both theories, foundation is not required, 
 every set has a complement, and replacement and
Aussonderung are only required for grounded sets. 

In Church's set theory (CUS), arbitrary unions and intersections exist, but
the power set axiom is restricted to grounded sets. 

In Mitchell's set theory, all power set exist, but not all unions; not
even all unions of two sets. 



Both theories are consistent. For the proof of the 
consistency of Church's set theory, 
the compactness theorem is invoked; this means that it is conceivable
that there is no model whose $\omega$ is (externally) well-founded. 


Schimanovich has asked if it is possible to have complements of all
sets, replacement for grounded sets, and power sets of all sets. 
We give a partial answer to this question by 
sketching a model of the fragment of CUS described above, i.e.,
of the following axioms: 


 \begin{itemize}
\itm - Extensionality. 
\itm - There exists an empty set (it is unique; call it $0$). 
\itm - small union:  For all $x,y$:  $x\cup y $ exists (this follows
from pairing and big union)
\itm - Pairing:  For all $x,y$: $\{x,y\}$ exists (this follows from
replacement as soon as we have a set with two elements)
\itm - Big union:  For all $x$, $\bigcup x$ exists. 
\itm -  Infinity:  There exists a smallest inductive set, call it $\omega$.
($w$ is inductive iff $0\in w \wedge \forall y\in w: y\cup \{y\}\in
w$)
 \itm -  Complements:   The complement of every set exists. 
\\
(I.e., $\forall x \, \exists y: \forall z(z\in y\Leftrightarrow
z\notin x)$)
\itm - Replacement: For any definable function class $F$ and any
grounded set $x$, $F[x]$ exists. 
\itm - Aussonderung:  For every definable class $C$ and every set $x$,
$x\cap C$ exists. (This follows from replacement and the empty set axiom.)
 \end{itemize} 
We will write {\bf ZFPK} for this axiom system. 


The natural numbers of the  model  $M$ we construct will be naturally
isomorphic to the true natural numbers; moreover, the classes $ORD^M$
 of all ordinals of $M$  and
even the class 
$WF^M$
of all grounded sets of our model will be 
naturally isomorphic to the true ordinals, and the all sets,
respectively. 


\bigskip
\bigskip

\begin{Notation}
Let $(\V,\in)$ be a 
model of ZFC.   Everything we do from now on will take place in
$\V$, 
so we may as well assume that $\V$ is  the whole universe (a class). 


We will use boldface letters to denote (definable) classes of $\V$. 
\end{Notation}


\begin{Assumption}
We will assume that
there is a class $\F$ which is a bijection between $\V$ and
$\Ord^\V$, so $\V=HOD^\V$, e.g., $\V=L$.  

(This assumption is harmless since we are interested in a consistency
result only.)

This implies that every proper class of $\V$ can be mapped bijectively
to the ordinals of $\V$ (using a class function). 
\end{Assumption}


\begin{Notation}
Let $\E$ and $\M$ be classes, $\E \subseteq \M \times \M$. 
\begin{enumerate}
\item For $m\in \M$ we let $m_\E: = \{ x\in \M: \   x \E m\}$ be the
``extension'' of $m$.  
\item For clarity we may write ${\rm Ext}_\M(m)$ or $\Ext_\M(m)$ for $m_\E$,
depending on whether $m_\E \subseteq \M$ is a set or possibly a proper
class. 
\item Let $\A \subseteq \M$.   If there is a unique $m\in \M$ with $m_\E
= \A$, then we write $\A^\E$ for this $m$, and we say ``$m$ realizes $\A$''.
   Otherwise,  we say ``$\A^\E$ does not exist'' or ``$\A$ is not
   realized.''
\end{enumerate}
Hence, $(\A^\E)_\E= \E$ if $\A^\E$ exists, and $(m_\E)^\E = m$  if $(\M,\E)$
satisfies (the relevant instance of) the axiom of extensionality.   

The extensionality axiom says:
 For all $m\not= m'$: $m_\E \not= m'_{\E}$. 
\end{Notation}



The pairing axiom, union axiom, empty set axiom, infinity axiom,
replacement axiom and separation axiom are all instances of the same
scheme, namely the comprehension axiom.  The validity of each of these
axioms in a structure $(\M,\E)$ can be phrased as the existence of $X
^\E$ for certain sets $X \subseteq \M$.  For example, $(\M,\E)$ satisfies 
the power set axiom iff: 
\begin{quote}
For all $m\in \M$, $\{ x\in \M:  (\M,\E) \models x \subseteq m\}^\E$
exists. 
\end{quote}


% { \small 2000-03-14,16}




We will define two subclasses $\M \subseteq \V$, $\E \subseteq \M \times
\M$, such that $(\M,\E)$ satisfies ZFPK where power set is
restricted to grounded sets. 

\newcommand{\s}{{\tt s}}
\renewcommand{\b}{{\tt b}}

We will work inside $\V$.    Fix two distinct sets (e.g., 0 and 1), and
call them ``$\s$'', ``$\b$''  (small , big). 

\begin{Definition} 
Our model $\M$ will be a subclass of $\{\s,\b\} \times \V$. Elements of the
form $(\s,x)$ will have ``small'' extensions (but not 		
necessarily hereditarily small),
elements of the form $(\b,x)$ will be complements of small objects. 
\begin{enumerate}
\item 
   $\M_0':= \Ord^\V$,  $\M_0 := \{\b\} \times \M_0'$. 
\item For $\alpha > 0$,   $\M_\alpha$ and $\M_\alpha '$ will be
defined by transfinite induction: 
\begin{equation*}
\begin{split}
\M_\alpha ' &:= \{x\in \V: x \subseteq \bigcup_{\beta < \alpha}
\M_\alpha\}\\
\M_\alpha &:= \{\s\}\times \M_\alpha ' \\
\end{split}
\end{equation*}
\item $\M:= \bigcup_{\alpha\in \Ord} \M_\alpha$.   
\end{enumerate}
\end{Definition}



\begin{Definition and Fact}
We call an element $(\s,x)$ ``pure'' iff $x\cap \M_0=\emptyset$. 
  Elements $(\b,\alpha)$ are never pure.   $(\s,x)$ is ``hereditarily
  pure'' if $(\s,x)$ is pure and all elements of $x$ are hereditarily
  pure. 

Clearly the class of  hereditarily pure elements of $\M$ is
canonically isomorphic to $\V$. 

There is a class $\F \subseteq \V$ which is a
bijection between $\Ord$ and $\bigcup _{\alpha\in \Ord\setminus\{0\}}
\M_\alpha$. 
\end{Definition and Fact}

\begin{Definition}
We define a relation $\E \subseteq \M\times \M$
 by defining extensions $m_\E$ for
all $m\in \M$: 
$$(\s, x)_\E := x \qquad    \qquad   (\b, \alpha)_\E:= \M \setminus (\s,
\F(\alpha))_\E $$ 
That is, the element $(\b, \alpha)$ represents the complement of 
$(\s, \F(\alpha)$).  

While the $(\s, x)_\E $ is always a set, $(\b, \alpha)_\E$ is always a
proper class. 
\end{Definition}

\begin{Fact}
\begin{enumerate}
\item 
 Whenever $x \subseteq \M$ is a set in $\V$, then $x^\E$
is well-defined. 
\item  Every $(\b, \alpha)$ is not grounded. 

\end{enumerate}
\end{Fact}
\begin{proof}
\ 
\subsubsection*{Part 1}
 Find $ \alpha $ such that $x \subseteq \M_\alpha$,
then $x^\E := (\s, x) \in \M_{\alpha+1}$.]

\subsubsection*{Part  2} 

  Let
$\F(\alpha) = x$.


  Pick a large enough $\beta $ (larger than the rank
of $x$), then $(\b, \beta)\notE x$, so $(\b, \beta)\in (\b,
\alpha)$. 

So we can find (in $\V$) an $\E$-descending sequence $((\b,\alpha_n): n
\in \omega )$, and this sequence is clearly realized in $(\M,\E)$. 

\end{proof}


\begin{Fact}
For all $ x \subseteq \M$, $\bigcup_{y\notE x} y_\E  = \M$. 
\end{Fact}

\begin{proof}
check...
\end{proof}




Now check that $(\M,E)$ satisfies ZFK with a restricted power set
axiom. 


 \begin{itemize}
\itm - Extensionality: clear. 
\itm -   Empty set axiom:  $(\s, \emptyset)_\E = \emptyset$. 
 \itm -  Complements:  $(\b, \alpha)_\E$ is the complement (in $\M$) of
         $(\s, \F(\alpha)_\E)$.  
\itm -  Pairing:  For any $m_1,m_2\in \M$, $(\s, \{m_1,m_2\})_\E =
        \{m_1, m_2\}$. 
\itm - Power set:  Every grounded set is of the form $(\s, x)$.  
\\
     Let $P:= \{ y:   (\M, \E) \models y \subseteq (\s,x)\}$.  Then 
      $P$ is a set, so 
	$P^\E = (\s, P)$. 
\itm - Replacement:  Let $ \F \subseteq \M \times \M$ be a class function, 
      whose domain is a grounded set, say $\dom(\F) = (\s, x)_\E$.
        Then the range of $\F$ is some set $y$, and $y^\E= (\s, y)$. 
\itm - Infinity:   Let $x:= \{0^\M, 1^\M, \ldots\}$.  Clearly $x^\E= (\s,
        x)$ witnesses the infinity axiom. 
 \end{itemize}

It remains to show the union axiom. 


We first check the ``small union'' axiom, i.e., $\forall a \in \M \,
\forall b \in \M:   (a_\E\cup b_\E)^\E $ exists. 

Let $u:= a_\E\cup b_\E$. 


There are three cases to consider: 
\begin{enumerate}
\item  $a, b \in \M_0$
\item  $a, b \notin \M_0$
\item $a\in \M_0$, $b\notin \M_0$ (or conversely). 
\end{enumerate}

Case 1:   $ u = (\b, x)_\E \cup (\b,y)_\E = -( \F(x)_\E \cap \F(y)_\E)$.
Let $z:=  \F(x)_\E \cap \F(y)_\E)$, then $z\in \V$, $z \subseteq \M$, so
$\exists \gamma \, \F(\gamma)=z$.   Clearly $(\b,\gamma)_\E = - \F(\gamma)
= -z$, so $u^\E = (\b, \gamma)$. 

Case 2: trivial. 

Case 3:  
 $ u = (\b, x)_\E \cup (\s,y)_\E = -( \F(x)_\E \cap (-y_\E))$.
Let $z:=  \F(x)_\E \cap (-y_\E)$, then again $z\in \V$, $z \subseteq \M$, so
$\exists \gamma \, \F(\gamma)=z$.   Clearly $(\b,\gamma)_\E = - \F(\gamma)
= -z$, so $u^\E = (\b, \gamma)$. 




Union axiom:   We have to check that for all $m\in \M$, 
the set $U(m):= \{x\in \M: \exists y \in \M \,  x \E y, y  \E m \}$
is  of the form 
$y_\E$ for some $y\in \M$.  

If $m\in \M_0$, then it is easy to see that $U(m) = \M $, so assume $m
\notin \M_0$. 

 Note that $U(m) = \bigcup_{y E m} y_\E = 
 \bigcup_{(\s,y) \E m} (\s,y)_\E \cup  \bigcup_{(\b,y) \E m} (\b,y)_\E $.  

By the previous discussion, it is enough to show that both 
$( \bigcup_{(\s,y) \E m} (\s,y)_\E )^\E$ and 
$( \bigcup_{(\b,y) \E m} (\b,y)_\E )^\E$ exist.   

Note that 
$ u_1:= \bigcup_{(\s,y) \E m} (\s,y)_\E $ is an element of $\V$ and a
subset of $\M$, so $u_1^\E = (\s, u_1)$. 

Let   and 
$u_2 :=  \bigcup_{(\b,y) \E m} (\b,y)_\E $.   If the index set of this
union is not empty, then $-u_2 = 
 \bigcap_{(\b,y) \E m} -(\b,y)_\E  = 
 \bigcap_{(\b,y) \E m} y_\E $, ...
\bigskip
\bigskip

This concludes the proof that the model $(\M, \E)$ satisfies ZFPK.
The usual methods then give a finitary proof of that  Con(ZF) implies
Con(ZFPK):  Assume that $\varphi_1, \ldots, \varphi_n$ is the proof of
a contradiction from ZFPK, then the relativized formulas 
 $\varphi_1^{\M}, \ldots, \varphi_n^\M$ can be used to get a proof of
a contradiction from ZF. 
\bigskip
\bigskip


A drawback of our model is that most set-theoretical constructions
will fail for non-grounded sets.   For example, a non-grounded in our 
model  set can
never be the domain of a function. 


\section*{A note on non-hereditarily well-founded sets}

We show here the inconsistency of a set theory in which complement and
power set exists, and where  replacement
and/or separation are  required for all sets on which the $\in$-relation
is well-founded. 
\bigskip


Call a set $x$ ``good'' if $ \forall y\in x: 0 \in y$. 

Let $M:= P(-P(-\{0\}))$.  It is easy to check that $x\in M$ iff $x$ is
good. 

Note that $y\in x$, $x\in M$ implies $0 \in y$, whereas $y\in M$
implies $0\notin y$. 

Hence $x,y\in M \Rightarrow x\notin y$.  So the $\in$-relation is
well-founded on $M$.   However, $M$ is quite big, so the 
usual proofs will show that  neither replacement nor separation can be
applied to $M$, given a modest amount of other ZF axioms. 

For example, replacement immediately yields the set WF of well-founded
sets, which leads to a contradiction. 

Similarly, WF can be obtained by separation plus two applications of
the union axiom. 










\end{document}
