Difference between ∃\exists-rudimentary and generalised ∃\exists-rudimentary formulas

On Boolos’ Computability and Logic, chapter 16:

“A rudimentary formula [in the language of arithmetics] is a formula constructed from atomic formulas using only negation, disjunction, conjunction and bounded quantification. A ∃\exists-rudimentary formula is a a formula of the form ∃xϕ\exists x \phi, where ϕ\phi is rudimentary.”


“A generalised ∃\exists-rudimentary formula is any formula that can be obtained from a rudimentary formula by conjunction, disjunction, bounded quantification or unbounded existential quantification”

[Not exact words as my book is not in English]

By this definition, it seems that ∃\exists-rudimentary formulas are the same as generalised ∃\exists-rudimentary formulas. So I am believing that an extra “∃\exists” is missing on the second definition – i.e. “a generalised ∃\exists-rudimentary formula is any formula that can be obtained from a ∃\exists-rudimentary formula…”, making it so that the ∃\exists-rudimentary formulas are those with exactly one unbounded existential quantifier, and the generalised ones are those with any number of those (but no unbounded universal quantifiers of course), as that makes more sense, explains the omission of “negation” in the second definition and is consonant with Enderton’s definition of ∃n\exists_{n}-formulas.

Is this correct or am I misreading something?




Correct; see George Boolos & John Burgess & Richard Jeffrey, Computability and Logic (5th ed – 2007), page 204 : rudimentary, ∃\exists-rudimentary and ∀\forall-rudimentary.
2 days ago


1 Answer


I don’t have this book, but those definitions look OK to me; they are different from one another.

For a formula to be ∃\exists-rudimentary, it has to be literally of the form ∃xφ,\exists x\varphi, where ϕ\phi is rudimentary. (It’s not sufficient to be equivalent to such a formula over some theory, or even to be logically equivalent to such a formula.) For example, an ∃\exists-rudimentary formula can’t have two unbounded existential quantifiers; it can’t be a conjunction or disjunction of two ∃\exists-rudimentary formulas, or even a conjunction or disjunction of an ∃\exists-rudimentary formula with a rudimentary formula.

Formulas of all those forms are perfectly good examples of generalised ∃\exists-rudimentary formulas, according to the definition given. (And there are plenty of even more complex formulas that are generalised ∃\exists-rudimentary formulas but that aren’t ∃\exists-rudimentary formulas.)

By the way, the reason that negation isn’t included in either the definition of ∃\exists-rudimentary formulas or the definition of generalised ∃\exists-rudimentary formulas is that any negations can be moved into the rudimentary part (you don’t want to allow anything equivalent to the negation of an unbounded existential quantifier, and this approach avoids that issue completely).