Proof (not by counterexample) that $A$ and $B$ being independent given $C$ does not imply independence given $C^c$

I know that it's not true that $$A$$ and $$B$$ being independent given $$C$$ implies $$A$$ and $$B$$ are independent given $$C^c$$. However, I can only show this is false using a counterexample (see here for one of many).

What key ideas should I keep in mind if I want to write a proof of this that doesn't resort to using a contradiction?

Alternatively, could someone tell me when exactly the implication holds?

• Why on earth wouldn't you want to use a counterexample? – TonyK Feb 19 at 22:38
• @TonyK Finding an alternative proof method might give me a deeper understanding as to how independence works, at least in this type of situation and at most in general. Also, it has good recreational value since (at least at my level) trying to formulate a contradiction proof is proving much more challenging than thinking up a counterexample – Tiwa Aina Feb 19 at 22:44
• Technically a counter-example is proof by contradiction. The proof goes "Assume S is always true. Then for example E, S(E) must be true. But S(E) is not true. Therefore S is not always true." – ConMan Feb 19 at 22:51
• @ConMan Good point! I guess I seek a more direct/constructive proof, then? Or perhaps a better question is when exactly is the implication true? – Tiwa Aina Feb 19 at 23:00

If you're looking for a better understanding of what's going on, the idea is that "Since $$C$$ and $$C'$$ are disjoint events, things that happen when you condition on one of them are completely unrelated to the things that happen when you condition on the other one."
To give some context, imagine that $$C$$ is the event "magic is not real". Then let $$A$$ be "you break a mirror" and $$B$$ be "you stub your toe". Conditioning on $$C$$, i.e. in a world where magic is not real, of course events $$A$$ and $$B$$ are independent, and if they both happen then it's just a coincidence. However, if you condition on $$C'$$, i.e. in a world where magic is real, it's possible for $$A$$ and $$B$$ to be closely connected. And all of this happens regardless of the individual probabilities involved.
To ask "When does the calculation hold?", then it can happen under many different circumstances. In particular, if $$A$$, $$B$$ and $$C$$ are unconditionally independent of each other, then it doesn't matter if $$C$$ is true or not, $$A$$ and $$B$$ will still be independent. 