What we need is a construction that is as secure as the strongest underlying primitive. For instance, for symmetric encryption: Let M be the secret message, C1 the first cypher, C2 the second cypher, K1 and K2 two randomly generated, independent keys. Oh, and a nonce, but let's ignore that for now.

I Think it is easy to prove that C1(K1, C2(K2, M)) is at least as hard to break as either C1(K1, M) or C2(K2, M). Because if one of the cypher is easy to crack, the other can still work.

Hashes are different, because they're not reversible. In this case, a bad hash could indeed project the input space into a smaller output space than expected, and previous or subsequent hashes cannot reverse this mistake.