Skip to main content
1 of 2
Sam Sanders
  • 4.4k
  • 1
  • 21
  • 38

"at most one" versus "at most finitely many"

As shown in Simpson's excellent SOSOA, 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 $|w|$.

For arithmetical $\varphi$ such that $$ (\forall n)(\exists w^{1^*})(\forall X)\Big[\varphi(X, n)\rightarrow (\exists i< |w|)(X=w(i))\Big], \quad (*) $$ there is $Z$ such that $(\forall m)(m\in Z\leftrightarrow (\exists X)\varphi(X,m))$.

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

Sam Sanders
  • 4.4k
  • 1
  • 21
  • 38