定理：
いかなるプログラムも長さが N ビット以上の「全ての」ファイルを
ロスなしに圧縮することはできない。なお、N はゼロ以上の整数とする。

証明：
仮にあるプログラムが N ビット以上の全てのファイルを圧縮できるとする。
このプログラムによる圧縮では、丁度 N ビットの長さを持った、
全部で 2^N 通りのファイルを圧縮する。圧縮されたファイルのサイズは
高々 N-1 ビットであり、従ってそれらは高々 (2^N)-1 通りの異なる
圧縮済みファイルとなる(N-1ビットのファイルが 2^(N-1) 通り、
N-2 ビットのファイルが 2^(N-2) 通り・・・と言う風に
サイズ０の１通りのファイルまでを合計した)。
従って、少なくとも２つの異なる入力ファイルが、
同一の圧縮結果ファイルとならざるをえない。
故に、圧縮プログラムはロスレスではありえない。