Logic – ‘At Most One’ vs ‘At Most Finitely Many’

lo.logicreverse-math

As shown in Simpson's excellent Subsystems of Second Order Arithmetic, the ‘big five’ system ATR$_0$ from second-order reverse mathematics is equivalent to the following principle:

For arithmetical $\varphi$ such that $(\forall n)(\exists \text{ at most one } X)\varphi(X, n)$, there is $Z$ such that $(\forall m)(m\in Z\leftrightarrow (\exists X)\varphi(X,m))$.

My question is whether this ‘at most one’ comprehension principle is also equivalent to the following ‘at most finitely many’ principle, where $w^{1^*}$ is a finite sequence of sets of length $\lvert w\rvert$.

For arithmetical $\varphi$ such that
$$
(\forall n)(\exists w^{1^*})(\forall X)\Bigl[\varphi(X, n)\rightarrow (\exists i< \lvert w\rvert)(X=w(i))\Bigr],\tag{*}\label{star}
$$

there is $Z$ such that $(\forall m)(m\in Z\leftrightarrow (\exists X)\varphi(X,m))$.

Note that the condition \eqref{star} guarantees that there are only finitely many $X$ satisfying $\varphi(X,n)$, for fixed $n$.

Best Answer

The answer is positive, assuming extra induction, and a sketch is as follows.

Let $\varphi(X,n)$ be as in (*).

  1. Define an analytic code $A_n$ as follows $X\in A_n\leftrightarrow \varphi(X, n)$.

  2. Use induction (say for $\Sigma_2^1$-formulas) to show that $A_n$ can be enumerated (as a finite sequence).

  3. Now use V.4.10 from Subsystems of Second-order Arithmetic to show that $\cup_{n\in\mathbb{N}}A_n$ can be enumerated, say by $(X_m)_{m\in \mathbb{N}}$.

  4. Then for all $n\in \mathbb{N}$, we have

$$ (\exists X\subset \mathbb{N})\varphi(X, n)\leftrightarrow (\exists m\in \mathbb{N})\varphi(X_m, n), $$ and we are done. Note that step 3. makes use of ATR$_0$.

Related Question