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
Consider the following argument:


  If $0 &gt; 1$ then $1 &gt; 2$.


Proof: Starting with $0 &gt; 1$, add $1$ to both sides.

Since it is not true that $1 &gt; 2$, we can conclude that $0 &gt; 1$ is also false.

The same is true in your example. Starting with some assumption A, you prove property B. However, property B is clearly false, so assumption A must have been false as well. Don't forget that you can derive everything from False.