 Proof: Consider the set S of natural numbers smaller then \(2^n\). The cardinality of S is \(2^n\). The descriptive complexity of this set is \(\log n + c\) bits, but for half of the elements of S we need n bits to describe them. \(\Box\)