No compressor can shrink every file, and the proof takes one paragraph
Every few years someone announces an algorithm that compresses any file by 50%. Applied twice it would compress any file to a quarter, and applied enough times to a single bit.
Consider every possible file of exactly 1,000 bits. There are 2¹⁰⁰⁰ of them. Now consider every possible file shorter than that: 999 bits, 998, and so on down to nothing. Add those up and you get 2¹⁰⁰⁰ − 1 files, one fewer than you started with.
A lossless compressor must map distinct inputs to distinct outputs, or it could not reverse itself. But you cannot fit 2¹⁰⁰⁰ things into 2¹⁰⁰⁰ − 1 boxes without putting two in one box. So no lossless compressor shrinks every input. If it shrinks some, it must expand others.
No assumptions about the algorithm were needed, so no cleverness can evade it. It is the pigeonhole principle, and it is why every real compressor has a worst case where the output is slightly larger than the input: the original plus a few bytes of header.
So what is actually being exploited
Structure. Compression does not remove "redundancy" in some vague sense; it reassigns the short codes to the things that happen often.
English text is enormously predictable. After "th" the next letter is overwhelmingly "e". Spaces are the most common character. A picture of a wall has long runs of nearly identical pixels. In each case the file, considered as a random variable, has low entropy — the average surprise per symbol is small — and Shannon showed in 1948 that this quantity is the exact floor. You cannot encode a source in fewer bits per symbol than its entropy, and you can always get arbitrarily close to it.
Which turns compression into a competition about prediction. A compressor that models the source well assigns short codes accurately and lands near the entropy. A compressor that models it badly wastes bits. This is why the state of the art in text compression looks increasingly like a language model: predicting the next symbol well and compressing well are the same problem wearing different clothes.
You can watch the floor being approached in the Entropy Coding tool, and see the code assignment itself in Huffman Encoding.
Why zipping a zip does nothing
A well-compressed file has had its structure removed. What is left looks, statistically, like noise: every symbol about equally likely, no useful correlations between neighbours. Its entropy per bit is close to 1, so there is nothing left to exploit, and a second pass will typically make it very slightly larger: the header, plus the compressor's failure to find any pattern worth encoding.
The same explains why a JPEG inside a ZIP archive barely shrinks, why encrypted data is incompressible (good encryption is specifically designed to look like noise), and why compressing before encrypting is the correct order — afterwards there is nothing to compress.
The honest version of "50% smaller"
Every truthful compression claim is a claim about a class of inputs. "Halves the size of English prose" is a real and useful statement. "Halves the size of any file" is provably false, and the proof is the paragraph at the top.
Where lossy is a different beast entirely
None of this constrains lossy compression, because it does not have to be reversible. JPEG, MP3 and every video codec discard information deliberately, choosing what to lose using models of what human eyes and ears fail to notice.
That changes the question from "how much structure is there" to "how much can be thrown away before anyone complains", which is a question about perception rather than mathematics. It is also why the lossy trade-off has a knob and the lossless one does not: the entropy is a fact about the data, but the acceptable distortion is a judgement about the audience.
The one thing both share is that the honest specification is always conditional. A lossless compressor is good for a class of inputs. A lossy one is good at a given distortion.