We have that a formula $\alpha(x_1,x_2,\dots, x_k)$ is existential if it is of the form $$\exists t_1\exists t_2\cdots \exists t_l\beta(x_1,\dots,x_k, t_1,\dots,t_l)$$ where the formula $\beta(x_1,\dots,x_k, t_1,\dots,t_l)$ is quantifier-free, i.e., it doesn't contain the quantifiers $\exists$ and $\forall$.

If the formula $\beta(x_1,\dots,x_k, t_1,\dots,t_l)$ doesn't contain negation, it is called positive existential.

Which is the definition of an (positive) existential sentence?

Is the (positive) existential theory the set of all the (positive) existential formulas or the set of all (positive) existential sentences? Or is the definition of the (positive) existential theory entire different?

P.S. I have posted this question also here.


Disclaimer: Definitions may vary from person to person, book to book or article to article. Thus if you are reading a book or taking a course, you should refer to that litterature for the definition they mean. The bellow explanations are based on what I percieve as the most common definition.

A sentence is a formula without free variables. Thus a (positive) existential sentence is just a sentence on the form:

$ \exists t_1...\exists t_l\beta(t_1,...,t_l) $ where $\beta$ is quantifier free.

There is no The (positive) existential theory, but rather we say that a theory is existensial if it is a set of (positive) existensial sentences (or possibly possible to axiomatize using such sentences). If we would take the set of all existential sentences it would include things such as $\exists x (P(x) \wedge \neg P(x))$ and thus would be inconsistent.

  • $\begingroup$ Which of the definitions, (positive) existential formula, (positive) existential sentence, (positive) existential theory, is closed under the union ($\lor$) and the intersection ($\land$) ? Or none of them? $\endgroup$
    – Mary Star
    Sep 10 '15 at 11:03
  • $\begingroup$ @MaryStar (positive) existential formulas and sentences are closed, up to equivalence, under $\vee$ and $\wedge$ and thus Theories are too. $\endgroup$
    – Ove Ahlman
    Sep 10 '15 at 13:18
  • $\begingroup$ What do you mean that they are closed up to equivalence ? $\endgroup$
    – Mary Star
    Sep 10 '15 at 13:58
  • $\begingroup$ @MaryStar The sentence $(\exists x\,\varphi(x))\land (\exists y\, \psi(y))$ is no longer existential, since it is not explicitly in the form given in Ove's answer. However, it is equivalent to the sentence $\exists x\, \exists y\, (\varphi(x)\land \varphi(y))$, which is existential. $\endgroup$ Sep 10 '15 at 17:12
  • $\begingroup$ We say that sentences $\theta$ and $\eta$ are equivalent if for all structures $M$, $M\models \theta$ if and only if $M\models\eta$. Equivalently, your favorite proof system for first-order logic can prove $\theta \leftrightarrow \eta$. Often it's useful to consider the notion of equivalence of sentences relative to a theory. So $\theta$ and $\eta$ are equivalent relative to $T$ if for all $M\models T$, $M\models \theta$ if and only if $M\models \eta$, equivalently $T\vdash \theta\leftrightarrow \eta$. The first definition I gave is then the special case that $T$ is the empty theory. $\endgroup$ Sep 10 '15 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.