I am interested in how one proves that a sentence relativizes. Of course, proving that a sentence does not relativize is simple, as seen in the Baker-Gill-Solovay result; but how does one prove that a sentence does relativize, i.e., that it is true relative to any oracle? Are there known techniques for achieving this for arbitrary sentences?
If you know of any references that address this question, I would like to hear of them. Thanks.
Normally, the way people prove that a complexity theorem relativizes is using the following two-step procedure:
Prove the theorem.
Observe that your proof relativizes! In other words, that nothing in the proof changes at all if all the machines mentioned in the proof get access to the same oracle A.
Yes, it's really as simple as that. To make it rigorous, you should rewrite the whole proof adding superscripts of "A" all over the place. In practice, though, if people notice this issue at all, they'll usually just add a remark like "this result is easily seen to relativize."
If people seem cavalier about this, it's because they've learned, from experience, that only certain techniques (such as arithmetization) can possibly cause a proof not to relativize. So if your proof doesn't use those techniques, then it relativizes.
(A close analogy: suppose you prove a theorem about real numbers, but your proof never uses anything about the reals other than the fact that they're a field. Then it suffices to note that fact, to show that an analogous theorem must hold for complex numbers, p-adics, etc. There's no need to redo the proof.)
The one situation where more discussion is necessary, is where it's not even obvious what it means to relativize your theorem. (E.g., what's the oracle access mechanism?) As Kaveh pointed out above, there's no well-defined mathematical operation of "relativizing" a complexity theorem, just like there's no well-defined mathematical operation of "complexifying" a theorem about real numbers. Notice that, in the latter case, it's not enough to replace every occurrence of R by C: you probably also need to replace x2 by |x|2 (in some places, not others!), and make other changes that are "obvious" to a mathematician but hard to list formally. Likewise, in complexity theory, it's usually obvious what it means to "relativize" a theorem (i.e., who should get access to A, and what does it mean for them to access it?), but in some cases it can be quite subtle. See here for more about this issue.
Turning your question on its head, one could ask:
Is there any example of a relativizing complexity theorem, for which it's significantly harder to prove that the theorem relativizes than that the theorem is true?
Interestingly, I can't come up with a single indisputable example (though maybe someone else can)! Here's the best I can do:
Recent work on blind and authenticated quantum computing (by Broadbent-Fitzsimons-Kashefi, Reichardt-Unger-Vazirani, and others) might lead to examples. In those cases, the situation is that we don't know whether the theorems relativize or not---but if they do relativize, then certainly a new idea will be needed beyond what's in the existing proofs.
Arguably, another example might be the random self-reducibility of #P. If you asked most complexity theorists why that was true, they'd probably say it's because the permanent is both #P-complete and random self-reducible. That's true, but it doesn't answer the question of whether #P is rsr relative to any oracle. Well, it turns out that #P is rsr relative to any oracle, and it's not even hard to prove it---but you need to give a direct argument using polynomials, rather than appealing to properties of the permanent.
In Section 8 of my and Avi Wigderson's algebrization paper, we showed that the GMW theorem (that NP has computational zero-knowledge proofs) is algebrizing. And that really did take new ideas: not "dramatically" new, but certainly nowhere to be found in the usual proofs of the GMW theorem. Of course, this is for algebrization rather than for relativization.
Addendum: In answer to a further question of the OP, I don't know of any techniques whatsoever for showing that, if you could prove a certain complexity conjecture (which you haven't yet), then your proof would necessarily relativize. Yes, as long as you restrict your "search for a proof" to relativizing techniques only, you can be sure that, if you ever succeed in finding a proof, then your proof will necessarily relativize. And in practice, that's often what people do (e.g., because they have certain ideas about what a proof would look like, and those ideas relativize). But I don't know of any way to guarantee, a priori, that by broadening your search to include non-relativizing techniques, you couldn't find a proof that had eluded you before.
