Negation makes emptiness undecidable

Negation turns the containment question into an emptiness one. Collect everything in a but not in b:

diff(X) :- a(X), not b(X).

Then a ⊆ b holds exactly when diff is empty.

Deciding emptiness of diff would decide containment, which we just saw is undecidable. So once negation enters the language, emptiness is undecidable too.