Theorem:
No program can compress without loss *all* files of size >= N bits, for any given integer N >= 0.

Proof:
Assume that the program can compress without loss all files of size >= N bits. Compress with this program all the 2^N files which have exactly N bits. All compressed files have at most N-1 bits, so there are at most (2^N)-1 different compressed files [2^(N-1) files of size N-1, 2^(N-2) of size N-2, and so on, down to 1 file of size 0]. So at least two different input files must compress to the same output file. Hence the compression program cannot be lossless.

Aus dem comp.compression FAQ.

Das Problem ist uralt, um genau zu sein, in Bayreuth ist es in diesem Jahr 20 Jahre alt: Übungen in Mathematik. Die Rechnungen sind meist kein Problem, jedoch Beweise zu führen ist schon schwieriger [...] Eigentlich aber sind sie die Quintessenz eines Studiums der Mathematik. Deshalb: Making Proof.
Der Artikel beschäftigt sich mit Beweisführung für Leute, die noch nicht so geübt darin sind (Psychologie des Beweises, Häufige Satzstrukturen, Häufige Beweisstrukturen). Vor allem gut lesbar, weil der Autor seinen Gedanken zur Mathematik teilweise freien Lauf lässt (Wie würde Mathematik ohne Zeit aussehen, nur aus Faulheit entstanden, ...). Deshalb: Making Proof.

Sehr lesenswerter Artikel! Gibt es als html oder pdf .

Das vielleicht verblüffendste Ergebnis der modernen, auf der Mengenlehre basierenden Mathematik ist das Paradoxon von Banach-Tarski. Es erklärt, wie eine Kugel in Teile zerlegt werden kann, welche - anders zusammengesetzt - zwei volle Kugeln ergeben, jede gleich groß wie die ursprüngliche.

Der scheinbare Widerspruch zur Tatsache, dass durch Bewegungen keine Volumina verändert werden können, löst sich auf, wenn man die Konsequenz zieht, dass die Teile in der Zerlegung so kompliziert sind, dass ihnen gar kein Volumen zugeordnet werden kann.

In diesem Artikel wird ein Beweis des Paradoxons von Banach-Tarski gebracht, der sich zwar an Wagon's Monographie [Wa 2] anlehnt, der aber kein mathematisches Wissen voraussetzt, das über den Schulstoff noch vor der Infinitesimalrechnung hinausgeht. Dementsprechend werden fundamentale Eigenschaften abzählbarer und überabzählbarer Mengen, soweit sie für den Beweis notwendig sind, im Text ausführlich besprochen. Die bei der Konstruktion der paradoxen Zerlegung involvierten Drehungen werden ohne Verwendung des Matrizenkalküls behandelt. Lediglich mit linearen Gleichungssystemen wird umgegangen, deren Interpretation als Drehungen explizit erläutert wird. Der Grenzwertbegriff kommt nur implizit über die Zifferndarstellung reeller Zahlen vor.

Anschließend an den Beweis wird noch die Bedeutung des Paradoxons in etwas größerem Kontext diskutiert.