Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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<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<H_0$.
