How to prove representation-independent independence results (Q1091820)

A true assertion about the input-output behavior of a Turing machine M may be independent of (i.e., impossible to prove in) a theory \({\mathbb{T}}\) because the computational behavior of M is particularly opaque, or because the function or set computed by M is inherently subtle. The latter sorts of representation-independent independence results are more satisfying. For \(\Pi_ 2\) assertions, the best-known techniques for proving independence yield representation-independent results as a matter of course. This paper illustrates current understanding of unprovability for \(\Pi_ 2\) assertions by demonstrating that very weak conditions on classes of sets S and R guarantee that there exists a set \(L_ 0\in R-S\) such that \(L_ 0\) is not provably infinite (hence, not provably nonregular, nondeterministic, noncontext-free, not in P, etc.). Under slightly stronger conditions, such \(L_ 0's\) may be found within every \(L\in R-S\).