I am given the following definition of L-formulas:

"Positive formulas are defined with the following properties:

(i) Every atomic formula is positive.

(ii) If $\phi,\psi$ are positive that $\phi\land\psi$ and $\phi\lor\psi$ are positive.

(iii) If $\phi$ is positive and $x$ is a variable, then $\forall x \phi$ and $\exists x\phi $ are positive."

How should I approach this question? My strategy now is to assume that $\Sigma$ is the set of positive formula and that it is inconsistent, i.e. $\Sigma \vdash \phi \land \lnot\phi$, and go case by case (the type of formula $\phi$ can be) to show that $\Sigma$ must contain non-positive formula. It's been difficult to write down the proof and I'm not sure if I'm right in arguing it this way. Is there another method I can try?

  • $\begingroup$ Can you use compacity? What are your inference rules? $\endgroup$ Nov 10 '14 at 19:15
  • $\begingroup$ Haven't heard of compacity. Not sure what you mean by inference rules either. My textbook states only that $\Sigma$ is consistent iff there does not exist $\phi$ such that $\Sigma \vdash \phi \land \lnot \phi$ $\endgroup$
    – jh4
    Nov 10 '14 at 19:38
  • 2
    $\begingroup$ If $\Sigma$ is not consistent, then $\Sigma \vdash \phi$ for every $\phi$. In particular, $\Sigma \vdash \lnot \sigma$ for an atomic formula $\sigma$. But $\lnot \sigma \not\in \Sigma$, (using complexity). $\endgroup$ Nov 10 '14 at 19:40
  • $\begingroup$ Let me see if I'm understanding this right: By definition of $\Sigma \vdash \phi$, there exists a finite sequence $(\phi_1,...,\phi_n)$ of L-formulas such that for each $k \in {1,..,n}$, $\phi_k$ is either an axiom, or $\phi_k \in \Sigma$, or there are $i,j < k$ such that $\phi_j$ is the formula $\phi_i \to \phi_k$. $\sigma$ is atomic so $\lnot \sigma$ cannot be axiom. It also doesn't fulfil any of the three properties, so $\sigma \not\in \Sigma$. But what about the last case? The modus ponens. I'm not sure how to find a contradiction in that. $\endgroup$
    – jh4
    Nov 10 '14 at 21:09
  • 3
    $\begingroup$ @Jonas Gomes: one does not need to prove that no negative formulas appear. Indeed, the set of positive formulas is not complete, because $\phi \vdash \lnot\lnot \phi$, so it would be impossible to prove that no negative formula is the consequence of the set of positive formulas. Instead, one can just make an interpretation satisfying all the positive formulas (e.g. an interpretation in which all relation symbols are identically true and all functions symbols are the constant function). $\endgroup$ Nov 14 '14 at 11:52

Show that the set of all positive formulas is consistent by giving an example of an interpretation in which all positive formulas are satisfied.

Hint: consider a one-element universe. If you can figure out how to interpret the relation symbols of $L$ so that all atomic formulas are satisfied, the rest will be an easy induction.

  • $\begingroup$ On the side: it must be that we are assuming $\bot$ is not part of our language, because otherwise the definition above would make that a positive formula. But that is the only atomic formula that is not satisfied by the model described in this answer. $\endgroup$ Nov 14 '14 at 12:01
  • $\begingroup$ @Carl Mummert: Depends how you define atomic formula. If an atomic formula is a formula containing no connectives, and if $\bot$ is a $0$-ary connective, we don't have a problem. Are $\bot$ and $\top$ usually considered atomic formulae? $\endgroup$
    – bof
    Nov 14 '14 at 12:27
  • $\begingroup$ There is quite a bit of variation on that point; it seems to have been discussed at math.stackexchange.com/questions/658262/… already. $\endgroup$ Nov 14 '14 at 12:58

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.