Q:

Proving a language is not regular

If two languages L1 and L2 are regular than so is their intersection. 
If follows that, for two languages L1 and L2, if L1 intersection L2 is not regular and L1 IS regular than L2 is not regular.
I am having a hard time proving this. Since I am dealing with regular languages, I decided to build DFA's for them to help my proof. However, this does not help with my proof if I am supposed to prove the irregularity of a language. How do you prove a language is not regular if you cannot construct a DFA/NFA for them? Is pumping lemma the only way?

A:

The second statement logically follows from the first without any knowledge of how languages or sets work:
$$Regular(L_1) \wedge Regular(L_2) \to Regular (L_1 \cap L_2)$$
$$\lnot Regular (L_1 \cap L_2) \wedge Regular(L_1) \to \lnot Regular(L_2)$$
To prove that the first statement is true, show how you could construct a DFA for the intersection of two languages for which you already have DFAs.
Edit: Here is a slightly more detailed outline. Let $A = Regular(L_1)$, $B = Regular(L_2)$, $C = Regular(L_1 \cap L_2)$. The first 3 lines are given, and you want to show the last line ($\lnot B$).
Given:
$$(A \wedge B) \to C$$
$$\lnot C$$
$$A$$
From line 1:
$$\lnot C \to \lnot (A \wedge B)$$
From lines 2 and 4:
$$\lnot (A \wedge B)$$
From line 5:
$$\lnot A \lor \lnot B$$
From lines 3 and 6:
$$\lnot B$$
This isn't a formal proof--I haven't established a set of inference rules, and listed the rule used at each step. But it should give you a starting place. You'll have to look up which inference rules you're allowed to use in your course.

