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

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.