MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider the following basic theorem.

Theorem. If $M$ is a c.t.m of ZFC and $\mathbb{P}$ a c.c.c forcing notion in $M$ and $G$ a $\mathbb{P}$ - generic filter on $M$ then for all $A,B$ in $M$ and for all function $f:A\longrightarrow B$ in $M[G]$ there is a function $F:A\longrightarrow P(B)$ in $M$ such that $\forall a\in A~~~f(a)\in F(a)~\wedge~(|F(a)|\leq \aleph_{0})^{M}$.

$F$ is an approximation for $f$ in $M$. But in classic proof we use $AC$ in order to prove countability of the set $F(a)$ in $M$ for each given $a\in A$.

Question. If we remove $AC$ from the ground model $M$ can we guarantee the countability of the set $F(a)$ for each $a\in A$? Can we put an upper bound for the size of the sets $F(a)$ at all?

share|cite|improve this question
Clearly the size of $B$ is an upper bound. Also size of $P$ is an upper bound,as we can take $F(a)=\{b\in B: \exists p\in P, p \Vdash \dot{f}(a)=b \}.$ – Mohammad Golshani Mar 2 '14 at 10:03
@MohammadGolshani, Yes, Of course but I mean a fixed upper bound which works for all sets $A,B$ and for all functions $f:A\longrightarrow B$ in $M$, for example $\forall a\in A~~(|F(a)|\leq \aleph_{\aleph_{0}})^{M}$. – user47679 Mar 2 '14 at 10:13

This is a delicate issue, because antichains break easily when you're not using the axiom of choice.

More to the point, it is consistent that there is a partial order which satisfies the countable chain condition, simply because every antichain is finite and there are no infinite maximal antichains. In other partial orders there might not be maximal antichains at all.

While we're at it, the maximality principle in forcing is equivalent to the axiom of choice, so that one fails to (I mean the fact that $p\Vdash\exists\tau\varphi(\tau)\iff \exists\dot\tau\ p\Vdash\varphi(\dot\tau)$ which is often used in forcing).

Moreover, in peculiar forcings as I mentioned above it is generally expected for the maximality principle to fail. Making this a double-trouble problem.

But then again, not all is lost. As Mohammad points out, the cardinality of the forcing poset is an upper bound. And that upper bound works out for every function, and every two sets in the ground model. While this is not necessarily an $\aleph$ number, it is still an upper bound in some sense.

If $1_P\Vdash\dot f\colon\check A\to\check B$, then every condition must agree that $\dot f$ is a name for a function. Therefore if $p\Vdash\dot f(\check a)=\check b$, then this $b$ is unique. So if we define $F(a)=\{b\in B\mid\exists p\ p\Vdash\dot f(\check a)=\check b\}$, then there is a surjection from $P$ onto $F(a)$, if $p$ doesn't decide the value of $\dot f(\check a)$ then map it to some fixed element; otherwise map it to the value it decided upon.

Of course, in the absence of choice, the existence of a surjection need not imply the existence of an injection, so if you want an upper bound in the sense of injections ($\leq$) rather than surjections ($\leq^*$) you need to consider $2^P$ instead.

The above can be circumvented if $P$ is already a complete Boolean algebra. In that case we define an injection from $F(a)$ into $P$ defined by $b\mapsto\sum\{p\mid p\Vdash\dot f(\check a)=\check b\}$. Since $P$ is a complete Boolean algebra this condition exists, and it is unique. As Andreas Blass points out, in the case of a complete Boolean algebra which satisfy c.c.c. the different values of $\dot f(\check a)$ form an antichain, which is therefore countable.

share|cite|improve this answer
I believe that what you call the maximality principle is more commonly known as fullness. – Joel David Hamkins Mar 2 '14 at 12:32
I'm also accustomed to calling it the maximality principle. – Andreas Blass Mar 2 '14 at 15:10
Concerning the complete Boolean algebra case in the last paragraph of your answer, the situation is even better. If $P$ is a complete Boolean algebra and satisfies the c.c.c., then $F(a)$ will be countable because the truth values $\Vert \dot f(\check a)=\check b\Vert$ constitute an antichain. – Andreas Blass Mar 2 '14 at 15:15
@Andreas: Oh yeah, you're absolutely right there. Generally, though, if $P$ satisfies c.c.c., it doesn't imply that $B(P)$, its Boolean completion, satisfies c.c.c. as well, right? – Asaf Karagila Mar 2 '14 at 15:19
@AsafKaragila Right; Ccc for a poset is, as far as I can see, weaker than ccc for its Boolean completion. – Andreas Blass Mar 2 '14 at 19:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.