# Definition nested and unnested first order formulas

What's the definition of nested and unnested formulas in a first order language? I came across the term in a model theory book i'm reading, and I can't seem to find it defined there, or in my brief internet searches. Thanks!

• Usually, we speak of "nested" quantifiers in a formula like this one : $∃z∀x∀yP(x,y,z)$; there is nothing "strange" in it. May you provide us with reference to your book with page number, please ? – Mauro ALLEGRANZA Apr 13 '14 at 8:08

Is in the scope of can be defined by induction on the structure of the expressions. Mauro pointed out the interesting case: if φ is of the form $\forall x_1...x_k~\psi$, then ψ is said to be in the scope of φ. When ψ too starts with a quantifier, we speak of the two quantifiers being nested. Alternatively, you can make use of the parse trees associated with the expressions. The definition is straightforward:
Thanks for the answers everyone. I think i've found the answer: Let $L$ be a signature. An unnested atomic formula is an atomic formula of one of the following forms: \begin{align} x=y\\ c=y\\ F(\overline(x))=y\\ R\overline{x} \end{align} where $c,F,R$ are respectively some constant, function, and relation symbols of $L$. (Wilfrid Hodges' "A Shorter Model Theory", section 2.6, page 51)Apparently, using unnested atomic formulas is useful for building up induction on the complexity of formulas - one place I'm finding this is the induction building up to a proof of Los's ultraproduct theorem.(section 8.5)
• Yes, you are right. An atomic formula [see page 12] is without conncetives and without quantifiers; but it can be of the "form" $s=t$, where $s,t$ are terms. Terms, in turn, can be "complex, i.e. of the "form" $t=F(t_1, ...,t_n)$, where possibly : $t_1=f(x)$. In this case, we have "inner" variables (the $x$) "nested" into the term $t_1$ that in turn is into $t$. With unnested atomic formula, Hodges means an atomic one of the form yuo have listed, where there are no variables "inside" terms, but only terms of "$0$-level" complexity : variables or constants. – Mauro ALLEGRANZA Apr 14 '14 at 11:49