 Proof: Consider the set S of all natural numbers smaller than n. The descriptive complexity of this set in bits is \( \log_2 n + c\). Now construct A by selecting half of the elements of S randomly. Observe that: 