Question

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:

  1. Atomic formulas, $x=y$ and $R(x_1,...,x_n)$, are guarded formulas.
  2. If $\phi,\psi$ are guarded formulas, so are $\neg \phi$ and $\phi \wedge \psi$.
  3. 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))) $$

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top