Maximal Fragment of FOL Without Negation – Model Theory

lo.logicmodel-theory

Say that a logic $\mathcal{L}$ is nowhere-negative iff for every $\mathcal{L}$-theory $T$ there is a structure $\mathfrak{A}$ such that $$\mathit{Th}_\mathcal{L}(\mathfrak{A})=\mathit{Ded}_\mathcal{L}(T),$$ where $\mathit{Th}_\mathcal{L}(\mathfrak{A})=\{\varphi\in\mathcal{L}:\mathfrak{A}\models_\mathcal{L}\varphi\}$ is the $\mathcal{L}$-theory of the structure $\mathfrak{A}$ and $\mathit{Ded}_\mathcal{L}(T)=\{\varphi\in\mathcal{L}: T\models_\mathcal{L}\varphi\}$ is the $\mathcal{L}$-deductive-closure of $T$. Basically, $\mathcal{L}$ is nowhere-negative iff every deductively-closed theory is the full theory of some structure.

For example, first-order logic is unsurprisingly non-nowhere-negative: consider any incomplete but deductively closed theory. On the other hand, equational logic is nowhere-negative by the usual proof of the HSP theorem: given a class of structures $\mathbb{K}$ we construct a single structure $\mathcal{A}$ satisfying precisely those equations true in every element of $\mathbb{K}$, and if we apply this to $\mathbb{K}$ = the class of models of some equational theory $T$ then the resulting $\mathcal{A}$ will satisfy all and only the equational sentences provable from $T$.

Re: the name, note that if $\mathcal{L}$ contains sentences $\varphi,\psi$ with nonempty and exactly complementary model classes then $\mathcal{L}$ cannot be nowhere-negative: this is because any structure must satisfy exactly one of $\varphi$ and $\psi$ and neither $\varphi$ nor $\psi$ is in the deductive closure of $\emptyset$, so $\mathit{Ded}_\mathcal{L}(\emptyset)\not=\mathit{Th}_\mathcal{L}(\mathfrak{A})$ for any structure $\mathfrak{A}$.

My question is about the coarse structure of the nowhere-negative fragments of first-order logic:

Question: Is there a ("reasonably natural") maximal nowhere-negative sublogic of first-order logic?

(Actually, the question I'm really interested in is the broader "Is every nowhere-negative sublogic $\mathcal{L}\subseteq\mathsf{FOL}$ contained in a maximal nowhere-negative sublogic of $\mathsf{FOL}$?," but I think that's a bit ambitious.) Note that this is not immediately solved via Zorn's lemma, since the union of a chain of nowhere-negative logics could fail to be nowhere-negative. I'm separately interested in what nowhere-negativity is actually called, since I vaguely remember seeing the same notion with a different name before but I can't track it down at the moment.

Best Answer

There is a simple characterization that $\def\LL{\mathcal L}\LL$ is nowhere negative iff all $\LL$-theories have the disjunction property:

Proposition. For any $\LL\subseteq\mathrm{FO}$, the following are equivalent:

  1. $\LL$ is nowhere negative.
  2. For every $\LL$-theory $T$ and every finite set of $\LL$-formulas $\{\phi_i:i\in I\}$, $$T\models\bigvee_{i\in I}\phi_i\implies\exists i\in I\:T\models\phi_i.$$ Note that this is equivalent to the special cases where $|I|$ is either $0$ (which amount to the consistency of $T$) or $2$.
  3. The same for finite theories $T$.

Proof.

$1\to2$: Let $A$ be a model whose theory is $T$. Then $A\models\bigvee_{i\in I}\phi_i$ implies $A\models\phi_i$ for some $i\in I$ by the definition of satisfaction of disjunctions.

$2\to3$ is trivial.

$3\to1$: For any $\LL$-theory $T$, the $\mathrm{FO}$-theory $$T^*=T+\{\neg\phi:\phi\in\LL,T\not\models\phi\}$$ is consistent: if it were not, there would be a finite $T'\subseteq T$ and a finite set $\{\phi_i:i\in I\}$ of $\LL$-sentences such that $T\not\models\phi_i$ (hence $T'\not\models\phi_i$) for each $i\in I$, and $T'\cup\{\neg\phi_i:i\in I\}$ is inconsistent. But then $T'\models\bigvee_{i\in I}\phi_i$, contradicting the disjunction property of $T'$.

Then any model of $T^*$ has the property that its $\LL$-theory consists exactly of the $\LL$-consequences of $T$. QED

Note that the only properties of FO we used here is that it is closed under Boolean connectives, and obeys the compactness theorem.

It follows immediately from the Proposition that the property of being nowhere negative is stable under unions of chains after all, hence by Zorn’s lemma, maximal nowhere negative sublogics of FO exist (as long as we fix the language so that the class of all FO sentences is a set).

While it is neither here nor there, let me mention another fact from the comments: the equational logic example generalizes to the logic $\LL\subseteq\mathrm{FO}$ of sentences built from atomic formulas by means of $\exists$, $\forall$, and $\land$. The fact that all $\LL$-theories have the disjunction property, hence $\LL$ is nowhere negative, is a consequence of the property that for every family of models $\{A_i:i\in I\}$ (where $I$ may be empty) and every $\LL$-sentence $\phi$, $$\prod_{i\in I}A_i\models\phi\iff\forall i\in I\:A_i\models\phi.$$ The left-to-right implication follows from the fact that all $\LL$-sentences are positive (monotone), hence preserved under surjective homomorphisms (incuding projections from products); the right-to-left implication follows from the fact that $\LL$-sentences are strict Horn sentences. I do not know whether $\LL$ is maximal.