What is so Basis-y about Basis Theorems?

Question

In computability theory, a basis for some collection C of classes (eg the $\Pi_1$ classes) is a class B such that every member of C contains a member of B.

My question is why a basis is in this sense is called a basis. Is there some connection with bases in algebra or topology? Or is this a completely independent use of the word “basis”?

Answer 1

I don't know the full history of the term, but in "Degrees of Models", J. Symbolic Logic 25(3) 1960, pp. 233-237, (10.2307/2964680, jstor) Shoenfield felt that a footnote was needed for the term "basis theorem", and he simply stated:

A basis theorem is one that asserts that, if some function satisfies a condition, then some function having special properties satisfies that condition.

So it appears Shoenfield did not think to mention any special meaning related to algebra or topology. Of course, there may be some very vague analogy with results such as the normal basis theorem in algebra.

I suspect the original use of "base" was from a paper of Kreisel that Shoenfield cited: "A Variant to Hilbert's Theory of the Foundations of Arithmetic", The British Journal for the Philosophy of Science 4(14), 1953, pp. 107-129.

In this paper, Kreisel is concerned with the ability to interpret one (more complicated) formal system into another (seemingly weaker) system. In particular, among other things, he is interested in when function quantification can be replaced with quantification over a sequence of simple functions. Kreisel writes (p. 120, notation and emphasis in the original):

The reducibility problem may be put more formally thus: a sequence of functions $f_1(a), f_2 (a), \ldots$ is called a strong base for a system if the formula $\underset{f}{V} \mathfrak{A}(f)$ can be proved if, and only if, some $\mathfrak{A}(f_n)$ can be proved (in the system considered); it is a weak base if $\underset{f}V\mathfrak{A}(f)$ cannot be proved when each $\lnot \mathfrak{A}(f_n)$ can be proved. (The numerals constitute a weak base for any $\omega$-consistent system.)

I think this gives the clearest sense in which these basis theorems could be thought to provide a "base" in some way.