I don't think Gödel is necessarily what is meant here, there are very good information theoretical(and other) reasons you can never describe a system with truly perfect accuracy. The map has to be become the territory for genuinely perfect accuracy.
Why couldn't the territory be losslessly compressible?
If reality has irreducible randomness (an open question afaik), and we're talking about theories and explanations (so we're not necessarily trying to describe the actual state of every particle in the universe, but only the rules governing their interactions), couldn't we have a complete, correct theory that was much smaller than the universe and contained terms for the random elements?
There would always be the possibility that it would turn out to be wrong, but it could be complete and correct, so it seems like the original claim must depend heavily on the word 'provable' and not on the impossibility of describing a system via a map smaller than the territory.
edit: but also, surely 'the territory is randomized' is a contingent physical fact, and not a necessary truth of information theory. Until we know for sure that there is irreducible randomness, we can't know that the information content of the universe (including the actual state of all particles at all times) isn't losslessly compressible, right?
We know with a high degree of certainty the universe contains things we can’t predict or observe, see Bell’s Theorem.
“Truth” doesn’t exist outside reality. There’s no substrate to hang it in. Information theory is likewise a subset of the territory, part of the universe, not apart from it. For these things to exist independently, you need something other than or bigger than the universe to put them in. If such a thing existed, sure, from that perspective maybe a lossless compression could exist. But that’s a metaphysical argument.