Essential bit content - prove that we can't use less bits than that Let $H_0$ be $\log_2(|A|)$, where $A$ is a set.
Let $C$ be a compressor $C\colon A \to \{1,0\}^l \cup \bot$.
This is a silly question, because intuitively it seems obvious.
How can I prove that $l$ can't be less than $H_0$?
I can prove that $l = H_0$ is sufficient, but how can I prove that it can't be less.
The function wouldn't be one-to-one otherwise.
The size of the set in the left is $|A|$, and its image would be of size at most $2^l&lt;2^{H_0}=|A|$, therefore, the function wouldn't be injective and thus you wont be able to de-compress some of the data.
Therefore it will be a lossy-compression for any $l&lt;H_0$.