What is a bookkeeping argument?

I've been studying Kunen's book, I don't understand when he talks about to do a proof by bookkeeping argument.

I would like to see a simple example of proof by bookkeeping argument.

Can someone explain to me what is bookkeeping argument or give any reference?

Thank you.

Solution 1:

When I first read Kunen's book, I also was confused about bookkeeping arguments. Today I found myself being confused for a moment yet again, and I didn't feel like reading through Kunen's proof again, so I worked out a simple example of what bookkeeping refers to without the context of the consistency of Martin's Axiom.

Let $\kappa$ be some infinite cardinal. Suppose we have a sequence $\langle X_\alpha\mid \alpha<\kappa\rangle$ of sets of ordinals and let $\bigcup_{\alpha<\kappa} X_\alpha=X$. Suppose that we also know that $|X|=\kappa$.

Our goal will be to recursively construct a sequence of sets $\langle Y_\alpha\mid \alpha<\kappa\rangle$ such that $|Y_\alpha|\leq \alpha$ and $Y_\alpha\subseteq \bigcup_{\xi\leq\alpha} X_\xi$ and such that $\bigcup_{ \alpha<\kappa}Y_\alpha=X$. How do we do this?

In a way it's simple: at each step $\alpha$, we may just pick some ordinal $\beta_\alpha\in\bigcup_{\xi\leq\alpha}X_\xi$ and add it to $Y_\alpha$ to get $Y_{\alpha+1}$. This makes sure that $Y_\alpha\subseteq \bigcup_{\xi\leq \alpha} X_\xi$ and that $|Y_\alpha|\leq \alpha$. But there's a problem here: which ordinal should we pick? Just picking any arbitrary ordinal can lead us to failure. For example, if $X_0$ is equal to the set $\kappa+1$, and we let $\beta_\alpha$ be the least element of $\bigcup_{\xi\leq\alpha}X_\xi$ that we haven't picked yet in a previous stage, then in the end we will never have picked $\kappa$ itself: we missed an ordinal.

That is where bookkeeping enters the picture: by keeping track of our sets, we can make sure that we will not "forget" to add any of the ordinals during our recursion. We fix some bijection $f:\kappa\times \kappa\to \kappa$ with the property that $f(\alpha,\beta)\geq \alpha$ for any $\alpha,\beta\in \kappa$, and for each $\gamma<\kappa$ we fix some injective function $g_\gamma: X_\gamma\to\{\gamma\}\times\kappa$.

For each $\alpha<\kappa$, let $(\gamma,\beta)=f^{-1}(\alpha)$, then $\gamma\leq\alpha$. Now, if there is some $\beta_\alpha\in X_\gamma$ such that $g_\gamma(\beta_\alpha)=(\gamma,\beta)$, then we let $Y_{\alpha+1}=Y_\alpha\cup \{\beta_\alpha\}$. Otherwise, we let $Y_{\alpha+1}=Y_\alpha$.

How can we make sure that we picked all the necessary ordinals? Well, in the end, for every ordinal $\delta\in X$ we can find $\gamma<\kappa$ such that $\delta\in X_\gamma$, and thus $g_\gamma(\delta)=(\gamma,\beta)$ for some $\beta$, and then $f(\gamma,\beta)=\alpha$ for some $\alpha\geq\gamma$, thus at stage $\alpha$ of our recursion we have $Y_{\alpha+1}=Y_\alpha\cup\{\delta\}$. Therefore $X\subseteq\bigcup_{\alpha<\kappa}Y_\alpha$.

In the above, bookkeeping may seem a bit silly: why wouldn't we start with some bijection $e: \kappa\to X$ and just add $e(\alpha)$ at stage $\alpha$? That this seems silly, is because from the start we were aware of the whole sequence $\langle{X_\alpha}\rangle$ and thus of the set $X$ itself. However, generally in a proof we want to construct the sets $X_\alpha$ and $Y_\alpha$ simultaneously. Therefore, at the $\alpha$-th stage of the recursion, we have no access yet to the $X_\beta$'s with $\beta>\alpha$ that will follow later in the recursion. Indeed: those $X_\beta$'s that will come later may even depend on the $Y_\alpha$ that you choose.

Yet, bookkeeping works despite of this: we may recursively define the sets $Y_\alpha$ and the injections $g_\gamma$ using only our knowledge of the sets $X_\xi$ with $\xi\leq \alpha$. At no stage do we need any of the information provided by the later stages. That is what makes bookkeeping a powerful tool in such recursive constructions.