1
$\begingroup$

I have heard it said from reputable sources that one of the differences between a compact and a non-compact logic is that in a compact logic, strong completeness follows from weak completeness. However, I have not been able to prove this myself. Can anyone help me prove this?

For clarity's sake, here are some definitions.

Definition 1 A logic $\mathcal{L}$ is compact if for any $\Phi \subseteq \mathcal{L}$, whenever $\Phi' \models \varphi$ for some $\varphi \in \mathcal L$ and for all finite $\Phi' \subseteq \Phi$, then also $\Phi \models \varphi$.

Definition 1 A logic $\mathcal L$ is compact if for any $\Phi \subseteq \mathcal L$, if every finite subset of $\Phi$ is satisfiable, then also $\Phi$ is satisfiable.

Definition 2 A logic $\mathcal{L}$ is weak-complete if for all $\varphi \in \mathcal L$ we have $\models \varphi$ implies $\vdash \varphi$.

Definition 3 A logic $\mathcal L$ is strong-complete if for all $\varphi \in \mathcal{L}$ and $\Phi \subseteq \mathcal L$ we have $\Phi \models \varphi$ implies $\Phi \vdash \varphi$.

I assume the idea is to get the hypotheses $\Phi$ to the right side of $\models$ and then use the weak completeness. However, I am not sure how to actually do this, or what to do from there.

$\endgroup$
  • $\begingroup$ How about using this? If $\Phi' = \{\phi_1, ..., \phi_n\}$ and $\psi = \phi_1 \land ... \land \phi_n$, then $\Phi' \models \phi$ if and only if $\models \psi \to \phi$. $\endgroup$ – Levon Haykazyan May 4 '16 at 9:54
  • $\begingroup$ I think that the statement of Definition 1 is not quite what you meant. Did you mean that, for all $\Phi \subseteq L$, if $\Phi' \vDash \phi$ for some finite $\Phi' \subseteq \Phi$ then $\Phi \vDash \phi$? I would imagine that compactness might be more useful if stated differently: if $\Phi \vDash \phi$ then there is some finite $\Phi' \subseteq \Phi$ with $\Phi' \vDash \phi$. $\endgroup$ – Carl Mummert May 4 '16 at 11:03
  • $\begingroup$ @Carl Mummert No, the compactness definition is definitely right. It's a kind of limit property: if every finite subset of an infinite set proves $\varphi$, then the infinite set itself must also prove $\varphi$. $\endgroup$ – mrp May 4 '16 at 11:16
  • $\begingroup$ @mrp: the problem is that if we do not have $\emptyset \vdash \phi$ then the axiom just stated has no bearing on $\phi$. In general, we can't expect that every finite subset of will prove $\phi$. Put another way, if every finite subset of $\Phi$ proves $\phi$ then $\emptyset$ proves $\phi$, so $\Phi$ proves $\phi$ by monotonicity. So, unless every monotonic logic is compact we need a different form of compactness. $\endgroup$ – Carl Mummert May 4 '16 at 11:18
  • $\begingroup$ @mrp Your Definition 1 is not compactness! Compactness states that if $\Phi\models\varphi$, then there is some finite subset $\Phi'\subseteq \Phi$ such that $\Phi'\models \varphi$. Taking the contrapositive, we have that if $\Phi'\not\models \varphi$ for every finite subset $\Phi'\subseteq \Phi$, then $\Phi\not\models \varphi$. This is the same as your statement, but with $\not\models$ in place of $\models$ - an important distinction! $\endgroup$ – Alex Kruckman May 4 '16 at 21:02
3
$\begingroup$

You will need a few more properties of the logic, in addition to the ones stated. Perhaps the author you were reading included these properties as part of the definition of a "logic". Also, the form of compactness stated in the question is not the ideal one for this purpose.

Suppose that we replace compactness with the following:

  • $\Phi \vDash \phi$ if and only if there is a finite $\Phi' \subseteq \Phi$ with $\Phi' \vDash \phi$

And suppose we assume the logic satisfies two more requirements:

  1. A form of the deduction theorem: $\psi \vDash \phi$ if and only if $\vDash \psi \to \phi$, and $\psi \vdash \phi$ and and only if $\vdash \psi \to \phi$

  2. A property of conjunction: if $\Psi$ is finite and $\psi$ is the conjunction of the axioms of $\Psi$ then $\Psi \vDash \phi$ if and only if $\psi \vDash \phi$, and $\Psi \vdash \phi$ if and only if $\psi \vdash \phi$.

Then we can prove that weak completeness implies strong completeness, following this outline:

  • Suppose $\Phi \vDash \phi$
  • By compactness, choose a finite $\Psi \subseteq \Phi$ with $\Psi \vDash \phi$
  • Let $\psi$ be the conjunction of $\Psi$. Then $\psi \vDash \phi$ by requirement 2
  • So $\vDash \psi \to \phi$ by requirement 1
  • So $\vdash \psi \to \phi$ by weak completeness
  • So $\psi \vdash \phi$ by requirement 1
  • So $\Psi \vdash \phi$ by requirement 2
  • So $\Phi \vdash \phi$ by compactness (this half of compactness is just the monotonicity of $\vdash$)

A counterexample

Here is a counterexample showing that the result does not work with the original version of compactness from the question. Begin with ordinary propositional logic with infinitely many propositional variables. For the deductive system, use any of the standard complete deductive systems for propositional logic.

For the semantics, first construct a collection $\mathcal{M}$ of models so that, for each sentence $\phi$ in the language, if $\phi$ is not a tautology then there is $M \in \mathcal{M}$ such that $M \not \vDash \phi$, but also each $M \in \mathcal{M}$ has infinitely many variables that evaluate to T and infinitely many that evaluate to F. This is possible because each formula only mentions finitely many variables, and we just need to choose one model $M$ for each non-tautology.

To finish our logic, we define $\Phi \vDash_\mathcal{M} \psi$ to mean that every model in our collection $\mathcal{M}$ which satisfies $\Phi$ also satisfies $\psi$.

  1. This logic has weak completeness. We have that a sentence $\phi$ is a tautology if and only if $\vdash \phi$, because we use the usual deductive system. But we defined $\mathcal{M}$ so that $\phi$ is true in every model of $\mathcal{M}$ if and only if $\phi$ is a tautology, and hence our logic has the property that $\vDash_\mathcal{M} \phi$ if and only if $\vdash \phi$.

  2. This logic has compactness in the form of the question. Assume that every finite subset $\Phi'$ of a set of axioms $\Phi$ satisfies $\Phi' \vDash_\mathcal{M} \phi$. Then in particular $\emptyset \vDash_\mathcal{M} \phi$, so $\phi$ holds in every model in $\mathcal{M}$, so $\Phi \vDash_\mathcal{M} \phi$.

  3. This logic also satisfies requirements 1 and 2 above. This is because, essentially, we chose enough models in $\mathcal{M}$ to ensure that the only logically valid sentences are the tautologies.

  4. This logic does not satisfy strong completeness. Let $\Phi$ be the set of axioms which states that every propositional variable has the value T. Then $\Phi$ is not satisfiable in $\mathcal{M}$, so we have $\Phi \vDash_\mathcal{M} \bot$. But $\Phi$ is syntactically consistent, because we are using the normal deductive system, so $\Phi \not \vdash \bot$.

This kind of example is a standard way to get (the usual version of) compactness to fail: take a logic that does have soundness, completeness, and compactness, and then restrict the semantics to use some appropriate subset of the interpretations of the original logic.

$\endgroup$
  • $\begingroup$ I definitely agree that we need some properties to hold, such as the deduction theorem; I should have mentioned this in my question. This seems interesting and much like the kind of proof I had imagined, but it is not the definition of compactness I had in mind. $\endgroup$ – mrp May 4 '16 at 11:25
  • $\begingroup$ I added a counterexample showing that the notion of compactness from the question is not sufficient. $\endgroup$ – Carl Mummert May 4 '16 at 12:03

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.