0
$\begingroup$

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!

$\endgroup$
  • 2
    $\begingroup$ 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 ? $\endgroup$ – Mauro ALLEGRANZA Apr 13 '14 at 8:08
1
$\begingroup$

Not a very useful definition, but can be done. For example, in the following two ways.

Def 1. First-order expressions φ are ψ are nested iff either one is in the scope of the other.

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:

Def 2. First-order expressions φ and ψ are nested iff either the parse tree associated with φ is a branch of the parse tree associated with ψ, or the other way around.

$\endgroup$
0
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mauro ALLEGRANZA Apr 14 '14 at 11:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.