# $C_1 \subseteq C_2$ implies $C_1^A\subseteq C_2^A$?

$C_1 \subseteq C_2$ implies $C_1^A\subseteq C_2^A$?

I've given a caveat that one shouldn't make this implication blindly and it shall be justified.

I can think of examples such that $C_1^A \subsetneq C_2^A$ and examples such that $C_1^A = C_2^A$.

but could it be that $C_2^A \subset C_1^A$? I can't see how.

So what's the point of this caveat?

• The main point is that $C_2^A$ is not a strict subset of $C_1^A$ for any oracle. But it still can be a subset (equal). – rus9384 Sep 18 '17 at 13:38
• A proof of $C_1 \subseteq C_2$ relativizes if $C_1^A \subseteq C_2^A$ using essentially the same argument. Some proof techniques are non-relativizing. – Yuval Filmus Sep 18 '17 at 13:47

A proof technique is (informally) relativizing if the results it generates also hold relative to an oracle. Not all proof techniques are relativizing. Perhaps the best known example is $\mathsf{IP}=\mathsf{PSPACE}$, which uses the technique of algebraization. Although $\mathsf{PSPACE} \subseteq \mathsf{IP}$, there is an oracle $O$ such that $\mathsf{PSPACE}^O \not\subseteq \mathsf{IP}^O$ (see this question on cstheory).