3
$\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$
7
  • $\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$ Commented May 4, 2016 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$ Commented May 4, 2016 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
    Commented May 4, 2016 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$ Commented May 4, 2016 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$ Commented May 4, 2016 at 21:02

2 Answers 2

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$
2
  • $\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
    Commented May 4, 2016 at 11:25
  • $\begingroup$ I added a counterexample showing that the notion of compactness from the question is not sufficient. $\endgroup$ Commented May 4, 2016 at 12:03
0
$\begingroup$

Let a logic $L$ has the following properties:

  1. It is weak complete
  2. It is compact
  3. If $\Gamma\nvdash\varphi$ then $\Gamma\cup\{\neg\varphi\}$ is satisfiable.

Hence, to prove strong completeness for $L$, we assume $\Gamma\cup\{\neg\varphi\}$ is satisfiable and show that $\Gamma\nvDash\varphi$.

Now, suppose that $\Gamma\cup\{\neg\varphi\}$ is satisfiable. Thus for every finite subset of $\Gamma$, such as $\{\varphi_1,\ldots,\varphi_n\}\subseteq\Gamma$, we have $\nvdash\neg(\varphi_1\wedge\ldots\wedge\varphi_n)$. But $\nvDash\neg(\varphi_1\wedge\ldots\wedge\varphi_n)$ due to weak completeness. So there is a model $M$ such that $M\vDash\{\varphi_1,\ldots,\varphi_n\}$. Therefore, each finite subset of $\Gamma\cup\{\neg\varphi\}$ is satisfiable and, by compactness, $\Gamma\cup\{\neg\varphi\}$ is itself satisfiable which means $\Gamma\nvDash\varphi$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .