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

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

Consider the following argument:

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.

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.

  • $\begingroup$ Ahhhhhh... I see it now. Thank you! $\endgroup$ – Rebecca Schley May 3 '18 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.