# Proof of Lower Bound for Deterministic Distinct Elements Algorithm

There is a proof in this document (page 8, Section 4, Lemma 3: https://inst.eecs.berkeley.edu/~cs170/fa16/lecture-11-29.pdf) that mirrors a proof my professor gave in my algorithms class. The lemma states:

Suppose that there is a deterministic exact algorithm for counting distinct elements that uses o(min{|$$\Sigma$$|, $$n$$}) bits of memory to process a stream of $$n$$ elements of $$\Sigma$$.

Then there is a compression algorithm that maps $$L$$-bit strings to bits strings of length o($$L$$).

The conclusion is false, therefore the premise is false. The proof is by contradiction. This is proved by constructing a compression algorithm that encodes an $$L$$-length bit string in fewer than $$L$$ bits. A decoding method is then given for reconstructing the $$L$$-length bit string.

What confuses me is that the paragraph above is apparently the contradiction that proves that you cannot transmit an $$L$$-length bit string using fewer than $$L$$ bits. And yet it seems to show that this actually can be done.

I understand the counting argument that says you cannot map $$2^L$$ bit-strings losslessly onto a range of $$2^L-1$$ outputs. What I need to understand for my class is why the given proof by contradiction is valid. If anyone can help me with the intuition concerning why the proof is valid, I would appreciate it

• This seems to be an issue about logic rather than computer science. – Yuval Filmus May 3 '18 at 12:11

If $0 > 1$ then $1 > 2$.
Proof: Starting with $0 > 1$, add $1$ to both sides.
Since it is not true that $1 > 2$, we can conclude that $0 > 1$ is also false.