About the origin of the names "immune" and "simple"

Question

I have been wondering for a while about the origin of the names "immune" and "simple". I also posed the same question to Andrea Sorbi, who in turn involved a few more colleagues in the discussion.

About "simple" we have a few conjectures. Martin Davis suggests that the name derives from an analogy with simple groups. Simple groups have no non-trivial normal subgroups; complements of simple sets have no infinite r.e. subsets.

Other people (Stephan, Nerode) seem to think that "simple" just refers to the fact that they are simpler than creative sets, the latter being considered a useful property of a human mind.

This is Nerode's account:

"Post originally hoped to get computably enumerable sets with degrees of unsolvability different from one of his creative sets by controlling the lattice of re subsets of their complements. Simple sets are those infinite re sets with infinite complements for which the lattice of re subsets of the complement is as small as possible. So "simple" was chosen to connote "fewest re subsets of complement", in stark contrast with "creative set" which connotes "effectively uncountable number of re subsets of the complement", which informally represents the perpetual incompleteness of mathematics."

About "immune" we have no clue, however. Apparently, the word was introduced by Dekker, in an article with Myhill in the fifties. Again this is Nerode's affectionate opinion:

"As to why "immune", Dekker also introduced "isolated" and "regressive". Stanley Tennenbaum always said that this was because Jim Dekker lived an isolated life. He was an engaging homebody. I think that I and Myhill and Stanley Tennenbaum were his main friends, scientifically and personally. We all met at U Chicago in about 1952 just after Myhill proved that all creative sets were recursively isomorphic, still one of my favorite theorems."

If anybody has better information, I would be extremely grateful if he could share this bit of knowledge.

Answer 1

I don't know the history, but "immune" always struck me as fairly appropriate terminology. ("Simple" never really did, but I never thought of the analogy with simple groups before - it's nice, even though it's not quite a perfect fit.) The English word immune has two general uses: (1) biological (immune to disease), and (2) more general ("not affected or influenced by something"), and both of these seem to fit with the computability definition. Immune sets are immune (in the non-technical sense) to the effects of (containing infinite) ce sets, in some sense.

It also ties well with "productive", as immune sets are somewhat the opposite of productive sets, and in that context, I think of the use of productive as in "productive cough."