1

Find to which $( \forall x) $, each occurrence of x belongs to.

$$ (\forall x)((\forall x)(\forall y)\ x < y \lor x > z ) \rightarrow (\forall y)\ y=x $$

Is it right that the third and fourth occurrence of x belongs to the second occurrence of $ \forall x $ and the last occurrence of x belongs to the first occurrence of $\forall x $ ? ( I count the occurrences from left to right)

Is the following formula calculation right ?

$$ y=x,(\forall y\ y=x),x<y,\ x>z,\ x<y\ \lor x>z,\ ((\forall y)\ x<y\ \lor\ x>z), ((\forall x)(\forall y)\ x<y\ \lor\ x>z), ((\forall x)((\forall x)(\forall y)\ x < y \lor x > z ) \rightarrow (\forall y)\ y=x )$$

Out Of Bounds
  • 1,531

1 Answers1

0

With this particular notation, there are two conventions (let the example be $(\forall x)\phi \star \psi$)

  • quantifier binds as far as it can (the example becomes $(\forall x)(\phi \star \psi)$),
  • quantifier binds only the closest subexpression (while here it is $\big((\forall x)\phi\big) \star \psi$).

You are correct in the first, but wrong in the second. You should check the notes on which one you need to use. One nice way to match variables with quantifiers it to number them, e.g.

$$(\forall x_1)\big((\forall x_2)(\forall y_3)\ x_2 < y_3 \lor x_2 > z_4 \big) \rightarrow (\forall y_5)\ y_5=x_1, \tag{1}$$ $$(\forall x_1)\big((\forall x_2)(\forall y_3)\ x_2 < y_3 \lor x_{\color{red}{1}} > z_4 \big) \rightarrow (\forall y_5)\ y_5=x_{\color{red}{6}}. \tag{2}$$

As for the second part, I would recommend drawing a tree, perhaps like this:

  • $(\forall x)\big((\forall x)(\forall y)\ x < y \lor x > z \big) \rightarrow (\forall y)\ y=x$
    • $(\forall x)(\forall y)\ x < y \lor x > z$
      • $(\forall y)\ x < y \lor x > z$
        • $x < y \lor x > z$
          • $x < y$
          • $x > z$
    • $(\forall y)\ y=x$
      • $y = x$

Going back bottom-up you will get the sequence of terms from your post. Also, with this particular notation you need to be careful with parentheses, e.g. you have a term $(\forall y\ y = x)$, which is confusing because now the reader does not know which convention you try to follow.

I hope this helps $\ddot\smile$

Edit: Some clarification after the comments.

dtldarek
  • 37,381
  • Thank you :). I have another question. $ (\forall z)((\forall z)\ z<y\ \land\ z=w) $. This was in the lecture notes and it says that the fourth occurrence of z belongs to the first occurrence of $ (\forall z) $. Why it doesn't belong to the second one like in the question? – Out Of Bounds Mar 10 '14 at 02:02
  • @Tennisman This is why I particularly dislike this notation (i.e. one with parentheses for quantifiers): you are never sure whether $(\forall x)P(x) \star Q(x)$ means $(\forall x)(P(x) \star Q(x))$ or $((\forall x)P(x)) \star Q(x)$. Try to check with your notes or lecture, but there are two conventions, one where the quantifier binds only the closest formula (the question is where it ends?), and the second where it binds as far as it can (e.g. end of formula or closing parenthesis). Here it seems that it is the former (and that I need to fix the answer). – dtldarek Mar 10 '14 at 02:10