On Aug 31, 2004, at 14:50, Victor Duchovni wrote:
This is a question in elementary finite set theory, not computer science
(whatever that is :-). All proofs will involve some mathematics. The
above is I think simpler than your original argument and is the simplest
I can come up with...
I think Hadmut was looking for an authority that would be respected by the CS department he is dealing with. It's a sad state of affairs when they will accept authority over proof. However, I can give what I think is a simpler proof, using only high school math.
Assume that some invertible function f() turns no input message into a longer output message.
We can prove that it also does not make any message *shorter*, and hence is not a "compression" function after all.
In particular, f() turns every one-bit message into a one-bit message.
Suppose f() preserves the length of all n-bit messages, for 1 <= n <= N. (This is already the case for N=1.) What does f() do to a message M of N+1 bits length? By assumption, f(M) is not N+2 bits or longer. But all output messages of N bits or less are the result of some input of N bits or less and hence cannot be f(M). So by elimination, f(M) is N+1 bits long.
By mathematical induction, f() preserves the length of every message.
--------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
