The simple set was an attempt prior to the Friedberg-Muchnik theorem to solve Post’s problem; Are there degrees that lie -strictly- between 0 and 0′?
One of Post’s later attempts was to construct a set called the Simple Set.
Definition: A set is Simple if it’s complement is immune.
Definition: A set is immune if for every program whose domain is infinite (that is, the set of all values for which our program halts with an output is infinite), .
So what do these definitions mean? Well, these definitions point to a set that is simple and has some pretty nifty properties:
- They are enumerable – that is, they can be ‘enumerated’, i.e. we can discover which numbers are members, by means of a Turing Program (or, rather, a computer)
- The complement of (that is, the set of all things not in ) is infinite.
- The simple set ‘touches’ every infinite enumerable set. That means, that for any infinite set that is enumerable, our simple set shares at least one number.
What is interesting is how we create this set. We start by ‘numbering’ all of our enumerable sets, so that , that means that every enumerable set is different.
We now go through each set with a goal that changes for each set, but remains more or less the same. Post’s original idea was to ask ‘does this set have a member that is greater than twice it’s number?’. This means that the number we choose from will be different from , etc. Once we have a number from some then we move on to and so on. So, for any it either won’t give us some number from within it (as it won’t have any numbers in it that are larger than twice it’s number) or will give us at least one number.
So, you can see that the procedure is quite straightforward, and yields this set with some rather interesting properties.
EDIT: I should have stated, the simple set didn’t solve Post’s problem! It was shown, for those who know, it was shown by Martin (1966) that all effectively simple sets are complete; if is simple, then …