2

Can you help me determine how to know if a formula is preserved? My book has 3 sentences about it that being

  1. variables and named variables get the same value in the model and sub model
  2. "Exist" Quantifier formulas are preserved up
  3. "For all" Quantifier formulas are preserved down

That is all good and nice, but that still doesnt explain to me how to determine if a formula is preserved up, down or not at all

I have 3 examples: (excuse me i'm new here, and i dont know how to write formulas)

I had 3 formulas, and i turned them into pernex normal form, and now these are my examples

1.∀x∀y∀z(¬P(y)∨(P(x)∧Q(z)))

this one i determined that it preserves down because it only has forall quantifiers am i correct?

2.∃x∃y∀z(P(y)∨(P(x)∧Q(z)))

this one i dont know how to determine, because it has both exist and forall quantifiers and they are all related to a variable

3.∃x∀y∃z(P(y)∨(¬P(z)∨Q(x)))

this one i also dont know how to determine because it has both exist and forall quantifiers

can you explain to me how to determine if it is preserved up down or not at all ?

Lena Bru
  • 173

1 Answers1

1

For 1., you are right. The formula has only universal quantifiers; thus it is preserved under substructures (i.e.downward).

Intuitively if all objects in the domain $D$ of my interpretation have some "property" $P$ than if I "restrict" the interpretation to a subset of $D$, it still holds that all objects "are $P$" (if all the balls in the box are black, if I pick up half of them to move into another box, the new one will have only black balls inside).

Formula 2. is not preserved up because it is not quantified by only existential quantifiers. If there is $x$ and $y$ such that for all $z$ ..., it is not sure that when I add to the domain of interpretation more objects, it still holds that ...

Consider the set of numbers $A= \{ 0, 1, 2, 3 \}$; in this domain it is true that exists $x$ for all $y$ such that $(y \le x)$ : it is $3$. But if I "expand" the domain to include all the set $\mathbb N$ of natural numbers, it is nor more true that : $\exists x \forall y(y \le x)$.

Mauro ALLEGRANZA
  • 94,169