% LaTeX2e
% The maximum principle in forcing and the axiom of choice
% A. Miller May 2011
\def\lastrevised{June 7, 2011.}
\documentclass[12pt]{article}
\usepackage{amssymb}
\pagestyle{myheadings}
\def\header{\today}
\def\header{A.Miller\hfill Maximum Principle \hfill}
\markboth\header\header
\def\al{\alpha}
\def\be{\beta}
\def\checkcheck#1{\check{\check{#1}}}
\def\dom(#1){{\rm dom}(#1)}
\def\ff{{\mathcal F}}
\def\forces{{\;\Vdash}}
\def\ga{\gamma}
\def\gg{{\mathcal G}}
\def\ka{{\kappa}}
\def\la{\langle}
\def\name#1{\stackrel{\circ}{#1}}
\def\namecheck#1{\name{\check{#1}}}
\def\namecheckxx#1{^\circ\check{#1}}
\def\namexxx#1{\accentset{\circ}{#1}}
\def\nn{{\mathcal N}}
\def\om{\omega}
\def\one{{\bf 1}}
\def\pnames{(\poset{-{\rm names}})^M}
\def\poset{{\mathbb P}}
\def\power(#1){{\mathcal P}(#1)}
\def\proof{\par\noindent Proof\par\noindent}
\def\pr{\prime}
\def\qed{\par\noindent QED\par\bigskip}
\def\ra{\rangle}
\def\res{\upharpoonright}
\def\rmand{\mbox{ and }}
\def\rmiff{{\mbox{ iff }}}
\def\rmor{\mbox{ or }}
\def\si{\sigma}
\def\sm{{\setminus}}
\def\sqleq{\sqsubseteq}
\def\st{\;:\;} % such that
\def\su{\subseteq}
\def\tlG{\tilde{G}}
\def\tleq{\unlhd}
\def\tlpi{\tilde{\pi}}
\def\zz{{\mathbb Z}}
\newtheorem{theorem}{Theorem}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{define}[theorem]{Definition}
\begin{document}
\begin{center}
{\large The maximum principle in forcing and the axiom of choice}
\end{center}
\begin{flushright}
Arnold W. Miller
\footnote{
\par Mathematics Subject Classification 2000: 03E25 03E40
\par Keywords: Forcing, Maximum Principle, Maximal Antichains,
Countable Axiom of Choice, Dedekind finite
\par Last revised \lastrevised
}
\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 the maximum principle in forcing
is equivalent to the axiom of choice. We also look
at some specific partial orders in the basic Cohen model.
\end{quote}
Lately we have been thinking about forcing over models
of set theory which do not satisfy the axiom of choice
(see Miller \cite{longbor,ded}).
One of the first uses of the axiom of choice in forcing
is:
\begin{center}
Maximum Principle \\
$p\forces \;\exists x \;\theta(x)\;\;\;\;$ iff
$\;\;\;$ there exists a name $\tau$
$\;\;\;p\forces \;\theta(\tau)$.
\end{center}
Recall some definitions.
For a partial order $\poset=(\poset,\tleq)$ and $p,q\in\poset$
we say that $p$ and $q$ are compatible iff there exists an $r\in\poset$
with $r\tleq p$ and $r\tleq q$. Otherwise $p$ and $q$ are incompatible.
A subset $A\su\poset$ is an antichain iff any two distinct elements
of $A$ are incompatible. It is maximal iff every $p\in\poset$
is compatible with some $q\in A$.
The standard definition of $p\forces \;\exists x \;\theta(x)$ is given by:
$$p\forces \;\exists x \;\theta(x)\;\;\; \rmiff \;\;\;
\forall q\tleq p\;\exists r\tleq q\;\exists \tau \;\; r\forces \theta(\tau)$$
here $p,q,r$ range over $\poset$ and $\tau$ is a $\poset$-name.
The usual proof of the maximum principle is to choose a maximal antichain $A$
beneath $p$ of such $r$ and then choose names $(\tau_r\st r\in A)$
such that $r\forces\theta(\tau_r)$ for each $r\in A$.
Finally name $\tau$ is constructed from $(\tau_r\st r\in A)$
in an argument which does not use the axiom of choice.
For details the reader is referred to Kunen \cite{kunen} page 226,
who calls it the Maximal Principle.
Shelah \cite{shelah} and Bartosyznski-Judah \cite{barto} refer to
the maximum principle as the ``Existential Completeness Lemma''.
Takeuti-Zaring \cite{takeuti} use ``Maximum Principle''
to title their Chapter 16.
Jech \cite{jech} uses boolean valued models to do
forcing proofs. He refers to the boolean algebra version of
the maximum principle as: ``$V^B$ is full'' , see Lemma 14.19
p.211. He notes that this is the only place in his
chapter where the axiom of choice is used.
We don't know if anyone\footnote{Yes they have. Philip Welch points out
Problem 1.30 in Bell \cite{bell}.}
has ever wondered if the axiom
of choice is necessary to prove the maximum principle.
First note that the axiom of choice is needed to give
the first step of the proof: Finding a maximal antichain.
\begin{theorem} \label{equiv}
The axiom of choice is equivalent to the
statement that every partial order contains a maximal
antichain.
\end{theorem}
\proof
Let $(X_i\st i\in I)$ be any family of nonempty pairwise
disjoint sets.
Let $$\poset=\bigcup_{i\in I}\;\;\om\times X_i$$ strictly ordered by:
$(n,x)\lhd (m,y)$ iff $n>m$ and $\exists i\in I \;\;x,y\in X_i$.
Note that any maximal antichain must
consist of picking exactly one element out of each $\om\times X_i$.
Hence we get a choice function.
\qed
The partial order used here is trivial in the forcing sense.
What happens if we only consider partial orders in which
every condition has at least two incompatible extensions?
In the literature on the axiom of choice
there is a property called the Antichain Property (A).
However, it is antichain in the sense of pairwise
incomparable not pairwise incompatible. The property
(A) states that every partial order contains a maximal subset
$A$ of pairwise incomparable elements (i.e. for all $p,q\in A$
if $p\tleq q$, then $p=q$).
In ZF property (A) is equivalent to the axiom
of choice (but unlike Theorem \ref{equiv}) property (A) is
strictly weaker in set theory with atoms, i.e.,
it holds in some Fraenkel-Mostowski permutation model
in which the axiom of choice is false.
These two results are due to H.Rubin \cite{rubin} and Felgner-Jech
\cite{felgnerjech}. See Chapter 9 of Jech \cite{jechac}.
\begin{theorem} \label{failure}
The axiom of choice is equivalent to the maximum principle.
\end{theorem}
\proof
Let $(X_i\st i\in I)$ be any family of nonempty pairwise
disjoint sets.
Let $\poset=I\cup\{\one\}$ strictly ordered by
$i\lhd \one$ for each $i\in I$ and the elements of $I$ pairwise
incomparable.
As usual the standard names for elements of the ground
model are defined by induction
$$\check{x}=\{(\one,\check{y})\st y\in x\}$$
and
$$\name{G}=\{(p,\check{p})\st p\in\poset\}$$ is a
name for the generic filter.
Then
$$\one\forces \exists x (\;\exists i\in \check{I}\cap \name{G}
\;\;x\in \check{X}_i)$$
which we may write as:
$$\one\forces \exists x \theta(x).$$
Applying the maximum principle, there exists
$\poset$-name $\tau$ such that
$$\one\forces \theta(\tau).$$
Then for each $i\in I$ we would have
to have a unique $x_i\in X_i$ such that
$$i\forces\tau=\check{x_i}.$$
This gives us a choice function.
\qed
This partial order is also trivial from the forcing point of view.
A nontrivial partial order which works is
$$\poset= (I\times 2^{<\om}) \cup \{\one\}$$
which is forcing equivalent to $2^{<\om}$. In either
of these examples one can show (without using the axiom of choice)
that every
dense subset contains a maximal antichain. Hence we can
think of them as showing that the second use of the axiom
of choice in the proof of the maximum principle, the choosing of names,
is also equivalent to the axiom of choice.
Note that the maximum principle holds for the suborder
$I\su \poset$. So the maximum principle could fail for a partial
order but hold for a dense suborder.
What can be proved without the axiom of choice in the ground model?
For example,
if a partial order can be well-ordered in type $\ka$ and
choice holds for families of size $\ka$, then the usual
proof of the maximal principle goes thru.
We note a special case for which the maximum principle holds.
\begin{prop}\label{wellorder}(ZF)
Suppose $\ka$ is an ordinal and
$$p\forces \exists \al<\check{\ka} \;\;\; \theta(\al)$$
then there exists a name $\tau$ such that
$$p\forces \theta(\tau)$$
\end{prop}
\proof
Take $\tau$ to be a name for the least ordinal satisfying $\theta$:
$$\tau=\{(q,\check{\be})\st q\tleq p\rmand \forall \ga\leq\be
\;\; q\forces \;\neg\;\theta(\check{\ga})\}.$$
\qed
\section*{Basic Cohen model}
The Basic Cohen model $\nn$ for the negation of the axiom of choice
is described in Cohen \cite{cohen} and Jech \cite{jechac}.
It is the analogue of Fraenkel's 1922 permutation model.
\bigskip
\noindent
One could\footnote{Since this model is the original and
simplest model in which the axiom of choice fails,
we think it is interesting to study its
properties just for its own sake.} ask:
In $\nn$ which partial orders have the maximum principle?
\bigskip
\def\inj(#1,#2){Inj(#1,#2)}
\begin{define}
Given infinite sets $I$ and $J$ let
$\inj(I,J)$ be the partial order of finite injective maps
from $I$ to $J$, i.e., $r\in\inj(I,J)$ iff
$r\su I\times J$ is finite and $u,v)$
It is ordered by reverse inclusion: $r_1\tleq r_2$ iff
$r_1\supseteq r_2$.
\end{define}
Recall that in $\nn$ the failure of the countable
axiom of choice is witnessed by
an infinite Dedekind finite $X\su \power(\om)$.
We consider the following three partial orders:
$\inj(\om,\om)$, $\inj(X,X)$, and $\inj(\om,X)$.
We show that the maximum principle holds for one of these
partial orders and fails for the other two.
The easiest case is $\inj(\om,\om)$. The following lemma takes
care of it.
\begin{lemma} Suppose that the countable axiom of choice fails and
$\poset$ is a nontrivial partial order which can be well-ordered.
Then $\poset$ fails to satisfy the maximum principle.
\end{lemma}
\proof
By nontrivial we mean that every condition has at least
two incompatible extensions.
Hence we can find $\la p_n\in\poset\st n\in\om\ra$
such that $p_n$ and $p_m$ are incompatible whenever
$n\neq m$.
Suppose $\{X_n\st n\in \om\}$ is a family of nonempty sets
without a choice function.
Note that
$$\one\forces \exists x \;\forall n\in\check{\om}\;\;
(\check{p}_n \in\name{G} \to x\in \check{X}_n).$$
We claim that this is a witness for the failure of
the maximum principle. Suppose not and
let $\tau$ be $\poset$-name for which
$$\one\forces \forall n\in\check{\om}\;\;
(\check{p}_n \in\name{G} \to \tau\in \check{X}_n).$$
Since $\poset$ can be well-ordered, we may choose for
each $n$ a $q_n\tleq p_n$ and $x_n\in X_n$ such
that
$$q_n\forces \tau=\check{x}_n.$$
But this would give a choice function for the family
$\{X_n\st n\in \om\}$.
\qed
\begin{theorem}
In $\nn$ the maximum principle fails for $\inj(\om,\om)$.
\end{theorem}
\proof
This follows from the Lemma, since $\inj(\om,\om)$ is well-orderable
and nontrivial,
and the countable axiom of choice fails in $\nn$.
\qed
Of course, there are many partial orders for which this
applies. We choose to highlight $\inj(\om,\om)$ because
it is simple and superficially similar to
the other two partial orders $\poset_0=\inj(X,X)$ and
$\poset_1=\inj(\om,X)$.
\begin{theorem}
In $\nn$ the maximum principle fails for $\poset_0=\inj(X,X)$.
\end{theorem}
\proof
We start with a description of $\nn$. Fix $M$ a countable
standard transitive model of ZFC.
Working in $M$ let
$\poset=Fn(\om\times\om,2,\om)$ be the poset of
finite partial functions, i.e., $p\in\poset$ iff
$p:D\to 2$ for some finite $D\su\om\times\om$.
Each bijection $\tlpi:\om\to\om$ induces
an automorphism $\pi:\poset\to\poset$ defined by:
Given $p:D\to 2$ then
$\pi(p):E\to 2$
where $E=\{(\tlpi(i),j)\st (i,j)\in D\}$
and $\pi(p)(\tlpi(i),j)=p(i,j)$
for each $(i,j)\in D$.
Let $\gg$ be the group of automorphisms of $\poset$
generated by $\{\pi_{i,j}\st in$ with $dom(q)\su N\times\om$, $n\leq mn$ and $\pi\in H_n^\infty$
then there exists $\pi_1\in H_n$ and $\pi_2\in H_k^\infty$ such that
$\pi=\pi_1\circ\pi_2$.
\end{lemma}
\proof
Consider any orbit of $\tlpi$
which contains at least one of the $jn$ so
that $\dom(p)\su k\times\om$ and $H_k$ fixes $\si$. By Lemma
\ref{decompose}
there exists $\pi_1\in H_n$ and $\pi_2\in H_k^\infty$ such that
$\pi=\pi_1\circ\pi_2$. It follows that
$(\pi(p),\pi(\si))=(\pi_1(p),\pi_1(\si))$ since $\tlpi_2$
is that identity on $k$, so $\pi_2(p)=p$, and since by induction on
rank $\pi_2(\si)=\si$. Since $\pi_1$ fixes $\tau$ we have that
$(\pi(p),\pi(\si))\in\tau$. It follows that
$\pi(\tau)\su\tau$. Applying the same argument to $\pi^{-1}$ shows
that $\pi^{-1}(\tau)\su\tau$ and therefore $\tau\su\pi(\tau)$ and
so $\pi(\tau)=\tau$.
\qed
\begin{lemma}\label{key}
Suppose $G$ is $\poset$-generic over $M$ and $\nn=\nn_G$ is
the symmetric inner model with $M\su\nn\su M[G]$.
Working in $M[G]$ define $$x_i=\{j\in\om\st \exists p\in G\; p(i,j)=1\}$$
and let
$$G_1=\{r\in\poset_1\st \forall i\in \dom(r)\;\; r(i)=x_i\}.$$
Then $G_1$ is $\poset_1$-generic over $\nn$ and $\nn[G_1]=M[G]$.
\medskip
\noindent Conversely, if $\tlG_1$ is $\poset_1$-generic over
$\nn$, then
$$\tlG=\{s\in\poset\st \forall (i,j)\in\dom(s)
\;\;[s(i,j)=1 \rmiff \exists p\in \tlG_1
\; j\in p(i)]\}$$
is $\poset$-generic over $M$ and
$\nn=\nn_{\tlG}$.
\end{lemma}
\proof
First we see that $G_1$ is $\poset_1$-generic
over $\nn$. In this proof we will use
$r_\si\in \poset_1$ for $\si\in\inj(\om,\om)$ to
refer to the condition satisfying
$r_\si(i)=x_{\si(i)}$ for each $i\in\dom(\si)$.
Working in $M$ suppose that $\name{D}$ is a symmetric
name and $s\in \poset$ satisfies:
$$s\forces \name{D}\;\su\;\name{\poset}_1\mbox{ is dense open.}$$
Choose $n$ so that every $\pi$ in $H_n$ fixes $\name{D}$ and
$\dom(s)\su n\times\om$.
Choose $t\tleq s$, $m>n$, and a one-to-one $\si:m\to\om$ such that
$\si\supseteq id_n$ and
$$t\forces \name{r}_\si\in \name{D}$$
where
$$\name{r}_\si=\{(\check{j},\name{x}_{\si(j)})^\circ\st j