No single algorithm can compress all possible files

You can make that more concise too. An ideal compressor would be able to map every string of length n to a string of length m<n and back. Since a bijection requires that its source and target sets are of the same cardinality, and there are more strings of length m than length n, this compressor cannot be a bijection. Or even more concisely: you can't fit 10 pigeons into 9 pigeonholes unless one pigeon shares.

Um, yeah. Pigeonhole principle. Not exactly news...

http://en.wikipedia.org/wiki/Pigeonhole_principle

Any programmer who does not know this near-instinctively (and also related things like the impossibility of having distinct hash values for all strings) should be ashamed of himself and brush up on basic math.

Technically, this proof is slightly flawed. Why?

Take the set of all files of 10 bits. There are 1024 possibilities.

You can compress these files to 9 bits. But you could also compress them to 8, 7, 6, 5, 4, 3, 2, 1, or even 0 bits. In total, that gives you: 1024 possibilities!

Of course, the issue is the initial assumption that the files all contain exactly 10 bits. If we had started with the problem of compressing files between 0 and 10 bits to files with at most 9 bits, the proof is trivial.

Obviously, since there are are files that no algorithm can compress.

http://en.wikipedia.org/wiki/Kolmogorov_complexity

http://www.cs.auckland.ac.nz/CDMTCS/chaitin/ns.html

I did not understand how this proves that no single algorithm can compress all files. Why does he assume that the compression generates less files?