Abstract:
Every finite and every co-finite set of non-negative integers is decidable. This is
true and it is not, depending on whether the set is given constructively. A similar
constraint is applicable in language theory and many other fields. The constraint is
usually understood and, hence, omitted.
The phenomenon of a set being finite, but possibly undecidable, is, of course,
a consequence of allowing non-constructive arguments in proofs. In this note we
discuss a few ramifications of this fact. We start out with showing that every number
theoretic statement that can be expressed in first-order logic can be reduced to a finite set, to be called a test set. Thus, if one knew the test set, one could determine
the truth of the statement. The crucial point is, of course, that we may not able to
know what the finite test set is. Using problems in the class II1 of the arithmetic
hierarchy as an example, we establish that the bound on the size of the test set is
Turing-complete and that it is upper-bounded by the busy-beaver function.
This re-enforces the fact that there is a vast difference between finiteness and
constructive finiteness. In the context of the present re-opened discussion about the
notion of computability – possibly extending its realm through new computational
models derived from physics – the constraint of constructivity of the model itself
may add another twist.