What can't guarded fragment of FO express?
-
05-11-2019 - |
题
I have some basic confusions about the definition of the guarded fragment of first-order logic. Hopefully someone can tell me where I'm wrong.
GF in FO is defined by:
- Atomic formulas, $x=y$ and $R(x_1,...,x_n)$, are guarded formulas.
- If $\phi,\psi$ are guarded formulas, so are $\neg \phi$ and $\phi \wedge \psi$.
- For variables $\{x_j,...,x_m\} \subseteq \{x_i,...,x_n\}$ and guarded fomula $\phi$ and atomic formula $A$, $\exists x_j\ A(x_i,...,x_n) \wedge \phi(x_j,...,x_m)$ is a guarded formula.
My reasoning is: for arbitrary FO formula of form $\exists x\ \phi$, I can just pick some relation $T$ that's always true and over all variables, and it's then equivalent to $\exists x \ T \wedge \phi$, a guarded formula. Other forms follow from this. So FO reduces to GF.
But that's obviously not true. I can't figure out where my mistake is. Could someone let me know where I got it wrong?
For example, isn't $$ \forall x\ \exists y\ \forall z\ \phi $$ equivalent to $$ \forall x\ (T \to \exists y\ (T \wedge \forall z\ (T \to \phi))) $$
没有正确的解决方案
不隶属于 cs.stackexchange