\input amstex
\NoBlackBoxes
\documentstyle{amsppt}
\settabs\+\hskip.1in&\hskip.55in& \cr
\def\psc#1#2{{\tabalign & #1 & \vtop{\hsize=4.325in\parindent 0pt
#2\strut }&\cr}\vskip2pt}
\def\ps{\hangindent .3in\hangafter 1}
\def\iput#1{}
\def\icopy#1{#1}
\font \sc cmcsc10
\font\Large=cmr8 scaled \magstep2
\magnification=\magstep1
\loadmsbm
\loadbold
\loadeusb
\def\ac#1{#1}
\pageheight{8.75truein}
\pagewidth{6.5truein}
\centerline{Additions to Part IV: Notes, January 2001}
\smallskip
\noindent{\bf New Notes}
\medskip
\head{NOTE 154}\endhead Definitions from \icopy{constructive order
theory} (for forms [0 AT], [0 AU], [1 DH], [1 DI], [1 DJ], [67 AB],
[67 AC], [144 B] through [144 M] and 413 through 416).
\definition{Definition} A {\it subset selection} $\Cal Z$ is a (class) function
defined on the class of all partial orderings such that if
$(P,\le)$ is a partial ordering then $\Cal Z (P,\le)$ (or $\Cal Z
P$ for short) is a subset of $\Cal P(P)$. The subset selection
$\Cal Z$ is a {\it subset system} if for any two partial
orderings $(P_1,\le_1)$ and $(P_2,\le_2)$ if $f:P_1\to P_2$ is
order preserving then for all $Z\in \Cal Z P_1$, $f[Z]\in \Cal Z
P_2$. \iput{subset system} \iput{subset selection}
\enddefinition
In \ac{Ern\'e} \cite{2000} the following subset selectors are
considered
\item{a.} $\Cal A P = \Cal P(P)$ (arbitrary subsets of $P$)
\item{b.} $\Cal B P = $ one or two element subsets of $P$
\item{c.} $\Cal C P = $ all non-empty chains in $(P,\le)$
\item{d.} $\Cal D P = $ all directed subsets in $(P,\le)$
($Z\subseteq P$ is {\it directed} by $\le$ if any two elements of
$Z$ have a common upper bound.) \iput{directed set}
\item{e.} $\Cal E P = $ all one element subsets of $P$
\item{f.} $\Cal F P = $ all finite subsets of $P$
\item{g.} $\Cal W P = $ all non-empty subsets of $P$ well ordered
by $\le$.
\item{h.} $\Cal U P = $ all $U\subseteq P$ such that $\forall
x,y\in U$, $x\lor y$ exists in $P$ and is in $U = $ all
$\bigvee$-subsemilattices of $P$.
\par
Note that all of the above except $\Cal U$ are subset systems.
\par
\definition{Definition} Assume $(P\le)$ is a partially ordered
set and $\Cal Z$ is a subset selection.
\item{1.} $(P,\le)$ is $\Cal Z$-{\it complete} (or
$\Cal Z$-$\bigvee$-complete) if every element $Z$ of $\Cal Z$
has a $\sup$ (denoted $\bigvee Z$ or $\bigvee_P Z$).
\item{2.} A subset $X$ of $P$ is {\it $\Cal Z$-subcomplete} if
each $Z\in \Cal Z\cap \Cal P(X)$ has a supremum $s$ in $P$ that is
contained in $X$
\item{3.} If $Y\subset P$ then $s$ is a {\it \icopy{constructive
supremum}} of $Y$ if either $Y = \emptyset$ and $s$ is the least
element of $P$ (if it exists) or $s$ is an upper bound of $Y$ and
there is a function $\psi:P\to Y$ such that $(\forall x\in
P)(s \nleq x \leftrightarrow \psi(x) \nleq x)$.
\item{4.} $(P,\le)$ is {\it constructively $\Cal Z$-complete} if
each $Z\in \Cal Z P$ has a constructive supremum.
\iput{constructively complete partial order}
\item{5.} A {\it \icopy{constructively complete lattice}} is a
complete lattice in which every supremum is constructive.
\item{6.} $\Cal Z^\lor$ is the class function whose domain is the class
of all partial orderings and which is defined by
$$\align
\Cal Z^\lor P = \{ Y\subseteq P : &(\forall x\in Y)(\forall z\in
P)(z\le x\to z\in Y)\hbox{ and }\\ &(\forall Z\in \Cal P(Y)\cap \Cal Z
P)(\hbox{If }x =\bigvee_P Y \hbox{ then} x\in Y \}\endalign
$$
\item{7.} $(P,\le)$ is \it{constructively directed} if there is a
function assigning an upper bound to each non-empty finite subset of $P$.
\iput{constructively directed set}
\item{8.} If $S$ is a set and $\Cal X \subseteq \Cal P(S)$ then
$\Cal X$ is {\it $\Cal Z$-inductive} (or {\it $\Cal Z$-union complete}
if for each $\Cal Y\in \Cal
Z\Cal X$, $\bigcup \Cal Y \in \Cal X$. \iput{$\Cal Z$-inductive set}
\iput{$\Cal Z$-union complete set}
\item{9.} $^c\Cal D P$ (or $^c\Cal D (P,\le)$) is the system of
all constructively directed subsets of $P$.
\item{10.} If $S$ is a set and $\Cal X\subseteq \Cal P(S)$ then
$\Cal X$ is a {\it closure system} (on $S$) if $\Cal X$ is closed
under arbitrary intersections (with $\bigcap\emptyset = S$).
\iput{closure system}
\item{11.} An element $x$ of a $\Cal Z$-complete poset $P$ is
$\Cal Z$-compact if for all $Z\in\Cal Z P$, if $x\le \bigvee Z$,
then $x\in \downarrow Z$. ($\downarrow Z = \{t\in P : (\exists y\in
Z)(t\le y)\}$. The $\Cal D$-compact elements are called the {\it compact
elements}. \iput{compact element}
\item{12.} A $\Cal Z$-complete poset is {\it $\Cal Z$-compactly
generated} if each of its elements is a supremum of $\Cal
Z$-compact elements. \iput{compactly generated poset}
\item{13.} An {\it\icopy{algebraic lattice}} is a $\Cal D$-compactly
generated complete lattice.
\item{14.} If $S$ is a set and $\Cal X\subseteq \Cal P(S)$ then
$\Cal X$ is a {\it system of finite character} for all $X$,
$X\in \Cal X \Leftrightarrow \Cal F X\subseteq \Cal X$
\item{15.} A {\it Scott closed} subset of $P$ is an element of
$\Cal D^\lor P$. \iput{Scott closed}
\item{16.} A map $\phi:P\to Q$ between posets {\it preserves
$\Cal Z$-suprema} if for each $Z\in \Cal Z P$ having a supremum
$s$, the image $\phi(s)$ is the supremum of $\phi[Z]$.
\item{17.} A {\it $\Cal Z$-frame} is a complete lattice in which
the distributive law $x\land \bigvee Z = \bigvee(x\land Z)$ holds
for all $x\in P$ and all $Z\in\Cal Z P$. \iput{$\Cal Z$-frame}
\enddefinition
\medskip
\head{Note 155}\endhead A proof that 144 is true in $\Cal N14$,
$\Cal N15$, $\Cal N17$, $\Cal N18$, $\Cal N36(\beta)$, $\Cal N37$, and
$\Cal N41$. We will prove that form [144 B], the set induction
principle, is true in $\Cal N41$. The proof can be modified to
show that 413 is true in the other models listed above. It
suffices to show that in $\Cal N41$, every set $S$ is the union
of a family $Y$ of well ordered sets such that $Y$ is well ordered by
$\subseteq$. Assume $S$ is a set in $\Cal N41$. For each $m\in\omega$,
let $S_m = \{ z\in S : z\hbox{ has a support contained in }
\bigcup_{n\le m} B_n\}$. (See the description of $\Cal N41$ for
the definition of $B_n$.) Each element of $S_m$ has support
$\bigcup_{n\le m} B_n$ and therefore $S_m$ is well ordered in
$\Cal N41$. Further, $S_m$ has empty support and therefore the
ordering $\le*$ on $Y = \{ S_m : m\in\omega\}$ defined by
$S_m\le* S_k$ if and only if $m\le k$ is in the model. But
this ordering has order type $\omega$. Since it is clear that $S
= \bigcup Y$ the proof is completed.
\medskip
\head{Note 156}\endhead A proof that 144 and [144 B] are
equivalent. For the proof we need an generalization of the
function $W$ defined in note 25. For any class $C$ we define the
function $W_C$ on ordinals as follows: $W_C(0)$ is the set of
well orderable subsets of $C$, $W_{\alpha+1} = \{ \bigcup Q :
Q\subseteq W_{\alpha}\hbox{ and }Q\hbox{ is well orderable}\}$ and
(for limit ordinals $\lambda$) $W_C(\lambda) = \bigcup_{\beta <
\lambda} W_C(\beta)$. (Then for each ordinal $\alpha$, $W(\alpha)
= W_V(\alpha)$ where $V$ is the universe.) Proceeding with the
proof we first assume that form 144 (the set induction
principle) is true and we let $S$ be any set. We need to show that
$S$ is almost well orderable, i.e., that $S\in\bigcup_{\alpha\in
\hbox{On}} W(\alpha)$. Since it is clear from the definition that
$\bigcup_{\alpha\in \hbox{On}} W_S(\alpha) \subseteq
\bigcup_{\alpha\in \hbox{On}} W(\alpha)$, it suffices to show that
$S \in \bigcup_{\alpha\in \hbox{On}} W_S(\alpha)$. But this
follows from the fact that
$\bigcup_{\alpha\in \hbox{On}} W_S(\alpha)$ satisfies the
hypotheses of the set induction principle.\par
Now assume that that every set is almost well orderable (form
144). Let $X$ and $S$ satisfy the hypotheses of the set induction
principle.
By form 144, $S \in W(\alpha)$ for some ordinal $\alpha$. Using
the definition of $W_S(\alpha)$ and induction on ordinals we
obtain $W_S{\beta} = W(\beta) \cap \Cal P(S)$ for all ordinals
$\beta$. Therefore $S\in W_S(\alpha)$. Another easy induction
argument using the fact that $X$ and $S$ satisfy the hypotheses of the
set induction principle gives us $W_S(\beta)\subseteq X$ for all
ordinals $\beta$. Hence we can conclude that $S\in X$.
\par
Since it is known that form 144 does not imply the axiom of
multiple choice (form 67),
this answers a question of \ac{Ern\'e} \cite{2000}: Does the set
induction principle imply the axiom of multiple choice?
\medskip
\noindent{\bf Add to note 120:}
\smallskip
\item{66.} $10 + 144 \to 9$, \ac{Ern\'e} \cite{2000}.
\end