We got the class LT by taking the class SL and closing it under Boolean operations. We have observed that LT ⊆ Recog, so certainly any Boolean combination of LT languages will also be recognizable. But what about the class of recognizable languages as a whole? Are Boolean combinations of recognizable (not just LT) languages also recognizable. In answering we can use the same methodology we use to show that any language is recognizable: consider what we need to keep track of in scanning a string in order to determine if it belongs to the language or not and then use that information to build our state set.

Suppose, then, that L = L₁ ∩ L₂, where L₁ and L₂ are both recognizable. A string w will be in L iff it is in both L₁ and L₂. Since they are recognizable there exist DFAs A₁ and A₂ for which L₁ = L(A₁) and L₂ = L(A₂). We can tell if the string is in L₁ or L₂ simply by keeping track of the state of the corresponding automaton. We can tell if it is in both by keeping track of both states simultaneously.