I vaguely remember reading somewhere about a theorem which states that classical logic is the strongest logical system in some sense.

Unfortunately, after much search, I cannot find any reference. I’m not sure what notion of "strength" was involved here - perhaps something along the lines of "classical logic proves the greatest number of tautologies", or something similar.

I’m not even sure whether this concerned sentential or predicate logics specifically, or some other larger class.

Can anyone provide a reference to anything similar?

  • $\begingroup$ Would a system where every statement was provable (including all contradictions) be deemed strong? $\endgroup$ – Henry Jun 28 '18 at 14:54
  • $\begingroup$ Perhaps, but this would not be classical logic. What I am looking for is a concrete theorem or classification scheme for logical systems which specifically concerns classical logic. $\endgroup$ – Dawid K Jun 28 '18 at 15:01
  • $\begingroup$ I don't think the statement can be true in any reasonable sense : if you have a non contradictory non tautology $H$, then the system consisting in "classical first order logic" + the axiom $H$, then this system will be strictly stronger than classical first order logic but still consistent. (Replace "first order" by "propositional" if you like that better) $\endgroup$ – Max Jun 28 '18 at 15:12
  • $\begingroup$ There is no such thing that is "classical logic". "Classical" is a property of a logic. You can say "those two logics are classical". You cannot say "I have implemented classical logic in software". $\endgroup$ – DanielV Jul 1 '18 at 7:48

You are probably thinking of Lindstrom's theorem which says that, among a family of abstract logics, first-order logic is the strongest that satisfies the compactness theorem and the downward Lowenheim-Skolem theorem.

  • $\begingroup$ What does "strongest" mean in this context? $\endgroup$ – Théophile Jun 28 '18 at 15:46
  • 1
    $\begingroup$ @Théophile: in this sense, $A$ is a sublogic of $B$ if, for each formula $\phi$ in $L(A)$ there is a formula $\phi'$ in $L(B)$ so that $\text{Mod}^A(\phi) = \text{Mod}^B(\phi')$. So every finitely axiomatizable $A$-elementary class is also a finitely axiomatizable $B$-elementary class. See this PDF by Väänänen for formal details - math.helsinki.fi/logic/opetus/lt/lindstrom_theorem1.pdf . There is no easy way to summarize the entire abstract logic framework in just a couple sentences. $\endgroup$ – Carl Mummert Jun 28 '18 at 15:51
  • $\begingroup$ Quoting from the paper: "Loosely speaking Lindstrom’s Theorem tells us that any proper extension of first order logic has to detect something non-trivial about the set-theoretic universe." $\endgroup$ – Carl Mummert Jun 28 '18 at 15:53
  • $\begingroup$ This is it! Thank you Carl $\endgroup$ – Dawid K Jun 28 '18 at 16:25

I guess you are referring to the notion of Post-completeness (also known as maximal consistency): a formal system is Post-complete if and only if it is consistent and has no consistent proper extension (i.e. no unprovable sentence can be added to it without introducing an inconsistency). On Wikipedia this property is also called syntactical completeness.

Propositional classical logic is Post-complete. First-order classical logic and propositional intuitionistic logic are not Post-complete.

For some references, you can have a look here and here (and at their bibliography).

  • 1
    $\begingroup$ How can classical propositional logic be Post-complete ? What goes wrong when you add a noncontradictory non tautology as an axiom ? $\endgroup$ – Max Jun 28 '18 at 15:18
  • $\begingroup$ This wasnt it, but still very interesting. Thanks for the references! $\endgroup$ – Dawid K Jun 28 '18 at 16:27
  • 1
    $\begingroup$ @Max - I guess the original proof of Post-completeness of propositional classical logic is in Post's paper in 1921. Informally, if you add an axiom $p$ to your formal system (say Hilbert calculus for propositional classical logic) for some propositional variable $p$, then by substitution $p \mapsto A \land \lnot A$ you can prove the contradictory formula $A \land \lnot A$ in your extended system. Of course, you can add formulas to your formal system other that $p$, but the reasoning is analogue. $\endgroup$ – Taroccoesbrocco Jun 28 '18 at 17:21
  • $\begingroup$ Mhm on wikipedia it is said that propositional logic is not syntactically complete. Moreover, I wouldn't take substitution to be a deduction rule. But of course that depends on the system, but then if you have substitution it's not really "propositional logic" (if you have substitution, it means any interesting propositional theory is contradictory) $\endgroup$ – Max Jun 28 '18 at 17:29
  • $\begingroup$ @Max - I don't know any proof system that is not closed under substitutions (at least as an admissible rule). I don't understand what you mean by "if you have substitution, it means any interesting propositional theory is contradictory". For instance, the axioms of Hilbert's proof-system for propositional classical logic form a theory that is closed under substitution and not contradictory. $\endgroup$ – Taroccoesbrocco Jun 28 '18 at 17:37

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.