Prove or disprove: If $A$ is regular and $B$ is not regular, then $A ∩ B$ is not regular.

Question

I suspect the Myhill–Nerode theorem may come into play, but not certain. If this was a union instead of an intersect, I'm certain it's true. I'm relatively confident that this statement is false and thus, is to be disproven, but not certain how to formally prove it. I was thinking that, if my intuition is correct, a counterexample would be optimal. I know that the empty language is a regular subset of all non-regular languages (or any language), so I was thinking of doing a proof that is essentially a reordering of this post (Prove or disprove: If $A$ and $A ∩ B$ are regular, then $B$ is regular). Of course, I could be wrong and it's true. I just want to be fully confident – anything to help me better understand this would be greatly appreciated.

Answer 1

The proof is the same as suggested in the answer of your post (Prove or disprove: If $A$ and $A \cap B$ are regular, then $B$ is regular). You can choose $A = \emptyset$ and $B$ to be any non-regular language, then $A \cap B = \emptyset$ is regular.

The reason why the answers are the same is because the two statements are logically equivalent, i.e. Let $p = A$ is regular, $q = B$ is regular, $r = A\cap B$ is regular. Your previous question is $(p \land r)\to q$, and your current question is $(p \land \neg q) \to \neg r$. We can show that $((p \land r)\to q) \equiv ((p \land \neg q) \to \neg r)$ by proof tree, or by natural deduction:

\begin{align} &\quad((p\land r)\to q) \\&\equiv (\neg (p \land r)\lor q) \\&\equiv (\neg p \lor \neg r \lor q)\\&\equiv (\neg p \lor q \lor \neg r) \\&\equiv (\neg(p\land \neg q)\lor \neg r)\\&\equiv((p\land \neg q)\to \neg r)\end{align}