What is difference between ϕ\phi and ∃xϕ\exists x \phi

where ϕ\phi is a first-order formula. What about satisfability?

=================

No difference; if xx is free in ϕ\phi, then ϕ\phi is satisfiable iff ∃xϕ\exists x \phi is.

– Mauro ALLEGRANZA

2 days ago

@MauroALLEGRANZA Don’t you mean “isn’t free”? To be exact, there is a difference. Just not in terms of satisfiability.

– Git Gud

2 days ago

If xx is not free : ϕ,∃xϕ\phi, \exists x \phi and ∀xϕ\forall x \phi are all “sematically” equivalent.

– Mauro ALLEGRANZA

2 days ago

=================

1 Answer

1

=================

When people write formulas such as (x+1)2=5,(x+1)^2 = 5\,, they often mean that the freely occuring variables (here: xx) are implicitly universally quantified (unless they occur in the context). In the above example, they mean ∀x: (x+1)2=5\forall\,x\colon\ (x+1)^2 = 5 (unless xx occurs in the context). This is different from ∃x: (x+1)2=5.\exists\,x\colon\ (x+1)^2 = 5\,.

Over the real numbers, the first formula is false, while the second one is true.

Sometimes the authors do not want to have implicit universal quantification. For example, the say something like “the formula (x+1)2=5(x+1)^2=5 has a solution over the real numbers”, which is the same as “the formula (x+1)2=5(x+1)^2=5 is satisfiable over the real numbers”, which is the same as “∃x∈R:(x+1)2=5\exists\,x{\in}\mathbb{R}\colon (x+1)^2=5.”

Speaking about the satisfiability of a formula without free variables such as ∃x∈R:(x+1)2=5\exists\,x{\in}\mathbb{R}\colon (x+1)^2=5 or ∀x∈R:(x+1)2=5\forall\,x{\in}\mathbb{R}\colon (x+1)^2=5 would be a bit obscure.