8
$\begingroup$

I mean here a logic in the sense of a language and semantics. By strongly axiomatizable I mean strongly sound and strongly complete. So I'm basically asking if there is a particular deductive system for which strong completeness and soundness hold, but compactness fails.

Obviously the deductive system cannot be finitary, for if it were then compactness would follow from completeness. But does it follow immediately that a deductive system containing an infinitary rule prevents compactness? I can see that it must but don't see how to 'prove' it, without using induction up to at least the ordinal associated with the infinitary rule.

Hence, a sub-question: Is there a standard way to 'prove' such a result?

For motivation, I know for example that infinitary logics are weakly complete and not compact.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Doesn't strong completeness imply strong compactness? $\endgroup$ – Apostolos May 25 '11 at 9:20
  • $\begingroup$ @Apostolos Yes trivially if deductions have to be finite. My question is whether this implication can be violated if we allow non-finitary deductions by e.g. adding an infinitary rule. Maybe I should have put the second paragraph first because people seem to answer after only reading the first paragraph $\endgroup$ – Chuck May 25 '11 at 20:58
  • $\begingroup$ Can you please provide the definitions of strong completeness and compactness? $\endgroup$ – Apostolos May 25 '11 at 21:20
  • 1
    $\begingroup$ Strong Completeness is the following property $$\Gamma \models_{L} \phi \Rightarrow \Gamma \vdash_{D} \phi$$ for a given deductive system $D$ and semantics $L$. Strong soundness is the other way around. And strong axiomatizability is the biconditional, i.e. str. comp. and strong. soundness. As for compactness it cannot (as far as I know) be strong in any meaningful sense - it just means that there are no essentially infinite relations of logical consequence, i.e. that if $$\Gamma \models \phi$$ then there exists a finite subset $\Delta$ of $\Gamma$ such that $$\Delta \models \phi$$ $\endgroup$ – Chuck May 25 '11 at 22:32
  • $\begingroup$ Oh I see. I thought you were referring to infinitary languages. Then the general answer to your question is: If there are theorems whose every proof has infinite size (and only then) compactness fails while soundeness and completeness hold. $\endgroup$ – Apostolos May 26 '11 at 13:22
3
$\begingroup$

First, I think we can always define a semantics for any deduction system such that the strong completeness and soundness will hold by taking the Lindenbaum algebra (models are made of constant and semantics is defined over the corresponding algebra of provably equivalent classes of formulas). And there are deduction systems which are not compact so that would answer the question.

An interesting case would be the $\omega$-logic with the infinitary $\omega$ rule:

$$\{\varphi(n)\}_{n\in\omega} \vdash \forall x \ \varphi(x) $$

| cite | improve this answer | |
$\endgroup$

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.