Theory of complexity – How to understand the notion of Boolean query via the definition of Immerman

Boolean queries are a special case of general queries. You can take $ tau $ to be a practical vocabulary and choose a pair of $ tau $-structures to represent "true" and "false".

For a concrete example, let's take a look at $ tau $ to be the vocabulary with a single symbol of nullary relation $ T $. Now, associate "true" with $ tau $-structure $ mathfrak {T} $ who has $ | mathfrak {T} | = emptyset $ and $ T ^ mathfrak {T} = { langle , rangle } $ (that is, the nullity relation that contains the empty tuple) and "false" with the structure $ mathfrak {F} $ who has $ | mathfrak {F} | = emptyset $ and $ T ^ mathfrak {F} = emptyset $ (the nullary relation that does not contain the empty tuple).

Empty universes are a little awkward because they mean that $ ( forall x , varphi) rightarrow exists x , varphi $ is not a tautology. If you do not like this and / or you do not like zero relationships, make sure that $ T $ unary and use a universe to an element.