DRMacIver's Notebook
Almost every set is immune
Almost every set is immune
A set \(A \subseteq N\) is recursively enumerable if it can be enumerated by a computable function (formally, if there is some turing machine that halts on an input if and only if it’s in the set). If an infinite set contains no infinite recursively enumerable subsets, it is called immune. I was introduced to this concept by Gary Fredericks:
An “immune set” is an infinite set of natural numbers of which no computer program can print out any infinite subset.
The fact that they “exist” at all is pretty weird.
In fact they are not weird, they are normal. Almost every infinite subset of \(\mathbb{N}\) is immune.
To see this, consider the set \(C = \{0, 1\}^\mathbb{N}\). This can be mapped to the power set of the natural numbers by mapping a set to its indicator function \(1_A\), where \(1_A(x) = 1\) if \(x \in A\) and \(0\) otherwise. Every \(x \in C\) is the indicator function of \(A = \{n: x_n = 1\}\) so this mapping is a bijection.
\(C\) is a probability space, with the probability corresponding to the probability of observing an event with an infinite sequence of uniform coin tosses. This is equivalent to picking a set by randomly assigning every natural number to be an element of it with probability \(\frac{1}{2}\).
In this note I’ll show that a randomly chosen \(x \in C\) corresponds to an immune set with probability one.
To see this, let \(A \subseteq \mathbb{N}\) be any infinite set. The probability that a random element of \(C\) contains \(A\) as a subset of its corresponding set must be zero, because this happens if and only if \(x_n = 1\) for all \(n \in A\). The probability of any \(n\) given coordinates being \(1\) is \(2^{-n}\), so the probability of infinitely many specified coordinates being \(1\) must be \(\leq 2^{n}\) for all \(n\), i.e. \(0\).
There are only countably many infinite recursively enumerable sets (because each is defined by a turing machine and there are only countably many turing machines). Enumerate them as \(R_i\). \(P(x \text{ is not immune}) = P(\bigcup\limits_n \{1_C : R_n \subseteq C\}) \leq \sum\limits_n P(\{1_C: R_n \subseteq C\}) = \sum\limits_n 0 = 0\). So the probability of a randomly picked subset of \(\mathbb{N}\) not being immune is zero, and thus the probability of a randomly picked subset of \(\mathbb{N}\) is \(1\).
Another way of seeing more or less the same thing (they are not actually the same theorem, but they have the same interpretation that the “typical” set is immune - it’s just a different notion of typicality): the set of points containing some infinite set \(A\) is a closed set (because its complement is \(\bigcup\limits_{i \in A} \{x: x_i = 0\}\)) and has empty interior (because for any finite set of natural numbers there is some \(i \in A\) not in that set, so those numbers are not enough to demonstate membership of \(A\)). Therefore the set of non-immune sets is meager. The comeager sets are another type of “large” set, and in particular by the Baire Category Theorem comeager sets are necessarily uncountable.
This kind of reasoning might be a bit strange if you’re not used to it, but it’s fairly common in set theory - rather than constructing objects satisfying a particular property, we show that in some sense it is “typical” that objects satisfy that property, and the ones that don’t that we normally concern ourselves with are a weird uncommon special case (this sort of reasoning is also common in more concrete subjects like combinatorics).