2

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?

Dawid K
  • 345
  • 1
    Would a system where every statement was provable (including all contradictions) be deemed strong? – Henry Jun 28 '18 at 14:54
  • 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. – Dawid K Jun 28 '18 at 15:01
  • 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) – Maxime Ramzi Jun 28 '18 at 15:12
  • 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". – DanielV Jul 01 '18 at 07:48
  • Classical Logic is a specific set of logics, namely Classical Propositional Logic, and Classical FOL. Other logics, like Modal Logic, can have classical fragments, but what makes a logic classical is whether or not it is truth-functional. Since not every logic with classical negation and implication is strictly truth-functional, it doesn’t make sense to say that “classical” is a property that any old logic with classical negation and implication has. – PW_246 Dec 18 '22 at 17:50

2 Answers2

5

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.

Carl Mummert
  • 81,604
  • What does "strongest" mean in this context? – Théophile Jun 28 '18 at 15:46
  • 1
    @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 - http://www.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. – Carl Mummert Jun 28 '18 at 15:51
  • 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." – Carl Mummert Jun 28 '18 at 15:53
  • This is it! Thank you Carl – Dawid K Jun 28 '18 at 16:25
3

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).

Taroccoesbrocco
  • 16,964
  • 1
    How can classical propositional logic be Post-complete ? What goes wrong when you add a noncontradictory non tautology as an axiom ? – Maxime Ramzi Jun 28 '18 at 15:18
  • This wasnt it, but still very interesting. Thanks for the references! – Dawid K Jun 28 '18 at 16:27
  • 1
    @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. – Taroccoesbrocco Jun 28 '18 at 17:21
  • 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) – Maxime Ramzi Jun 28 '18 at 17:29
  • @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. – Taroccoesbrocco Jun 28 '18 at 17:37
  • Substitution is an admissible rule, but not a rule. Hence adding as sole axiom the propositional variable $p$, you lose the admissibility of this rule (for instance $q$ is not provable, if $q$ is a different propositional variable). What I mean is a propositional theory, not a formal system (as in "first order theory"). For instance the theory ${p}$ would be contradictory and so the completeness theorem (if $T\models A$ then $T\vdash A$) wouldn't be interesting, as $T\vdash A$ would almost always be true) – Maxime Ramzi Jun 28 '18 at 17:44
  • In classical formal systems, substitution is an admissible rule intuitively because "propositional variables are treated the same as generic sentences", so any proof you can make with a $p$ in the end, you can make the same with an arbitrary sentence $\varphi$ (essentially it would be a proof by induction); this is no longer true if you add the axiom $p$ – Maxime Ramzi Jun 28 '18 at 17:47
  • @Max - Concerning your reference to Wikipedia, when it says that classical propositional logic it is not syntactically complete, it refers to the first definition of syntactical completeness, i.e. for every formula $A$ either $A$ or $\lnot A$ are derivable (the counterexample given there clearly refers to this notion of syntactical completeness). – Taroccoesbrocco Jun 28 '18 at 17:53
  • Well this is exactly equivalent to the fact that the logic is maximal: if there is $A$ which is neither provable nor refutable, then the logic + $A$ as an axiom is strictly stronger and consistent (an inconsistency would amount to a proof of $\neg A$) – Maxime Ramzi Jun 28 '18 at 17:56
  • @Max - But it is still possible to be syntactical complete in the sense of maximal consistency (see my answer) and not syntactical complete in the sense of negation completeness (for every formula $A$ either $A$ or $\lnot A$ is derivable). Clearly, negation completeness + consistency implies maximal consistency. – Taroccoesbrocco Jun 28 '18 at 18:00
  • @Max - I think we both agree that the only interesting theory in classical propositional logic is classical propositional logic. Other interesting theory either are not propositional or are not classical. Hilbert system contains the substitution rule by definition, since its "axioms" actually are axiom schemes. – Taroccoesbrocco Jun 28 '18 at 18:02
  • 1
    I challenge you to find a Hilbert proof of $A\land \neg A$ from the axiom $p$ (the substitution rule is admissible, not a rule; at least not according to wikipedia). And I think you don't understand what I mean by theory: I don't mean formal system, I actually mean theory, i.e. a set of sentences. Moreover I don't agree that you can be maximally consistent and not negation-complete (at least for sensible formal systems): again, if $A$ is neither provable nor refutable, you may simply add it as an axiom and this will be stronger and consistent. – Maxime Ramzi Jun 28 '18 at 18:27