PL 330, Advanced Symbolic Logic

Overview of the Relation between Logical Systems

H. Hamner Hill, Southeast Missouri State


D. Higher order logics
  • not (generally) consistent
  • not decidable
  • formal proof procedures generally not available


C. First order polyadic predicate logic
  • with or without identity
  • consistent, semantically complete
  • not fully decidable, syntactically complete, negation complete
  • Pure Existentials (when proper prenexing is possible), Main Method, Rigid Routine
B. First order monadic predicate logic
  • consistent, semantically complete, decidable
  • not syntactically complete, negation complete
  • not expressively complete
  • Venn diagrams, Boolean existential conditionals, Pure Existentials

A. Truth-functional propositional logic

  • consistent, semantically complete, syntactically complete, decidable

  • not negation complete

  • not expressively complete

  • truth tables, truth value analysis, truth trees, fell swoop, proofs

This "map" shows that these important systems of logic are related by subsumption, and that to "climb" to the next higher, more encompassing system, one must sacrifice some important metalogical properties.

In climbing from A to B, one gives up syntactic completeness and truth-functionality. In climbing from B to C, one gives up decidability; note that one must climb at least this high to have a "respectable" system of arithmetic. In climbing from C to D, one (generally) gives up consistency.