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.