<p>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. </p>

<p>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." </p>

CC BY-SA 3.0
2017-02-13T20:20:41.203Z
2017-02-13T20:20:41.203Z
Joshua Grochow
<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>This is Nerode's
account:</p>

<p>"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."</p>

<p>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:</p>

<p>"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."</p>

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

<reference-request><lo.logic><computability><philosophy>
About the origin of the names "immune" and "simple"
Andrea Asperti
# About the origin of the names "immune" and "simple"

(Asked by: username_0 on 2017-02-13)

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.

**Tags:** reference-request, lo.logic, computability, philosophy


---

## 1 answers

### Answer by username_1 on 2017-02-13. Score: 3

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."


---

