Prova del limite inferiore per algoritmo di elementi distinti deterministici

Question

C'è una prova in questo documento (pagina 8, sezione 4, Lemma 3: https://inst.eecs.berkeley.edu/~cs170/fa16/lecture-11-29.pdf) che rispecchia una prova che il mio professore ha dato nella mia classe di algoritmi. Il lemma afferma:

Supponiamo che esista un algoritmo esatto deterministico per il conteggio di elementi distinti che utilizza O (min {| $ Sigma $ |, $ n $}) bit di memoria per elaborare un flusso di $ n $ elementi di $ Sigma $.

Quindi c'è un algoritmo di compressione che mappa $ l $ -bit stringhe a bit stringhe di lunghezza O ($ l $).

La conclusione è falsa, quindi la premessa è falsa. La prova è per contraddizione. Ciò è dimostrato costruendo un algoritmo di compressione che codifica una stringa di bit di lunghezza di $ L $ in meno di $ L $ bit. Viene quindi fornito un metodo di decodifica per ricostruire la stringa di bit di lunghezza di $ L $.

Ciò che mi confonde è che il paragrafo sopra è apparentemente la contraddizione che dimostra che non è possibile trasmettere una stringa di bit di lunghezza di $ l $ usando meno di $ l $ bit. Eppure sembra dimostrare che questo in realtà può essere fatto.

Comprendo l'argomento di conteggio che dice che non puoi mappare $ 2^l $ bit strings senza perdite su un intervallo di output $ 2^l-1 $. Quello che devo capire per la mia classe è il motivo per cui la prova data per contraddizione è valida. Se qualcuno può aiutarmi con l'intuizione riguardo al motivo per cui la prova è valida, lo apprezzerei