Why there is no classification theorem for logics, if there are classification theorems for groups and algebras?

Solution 1:

As Max states, the notion of "logic" is much more complicated than that of "group" or "algebra" - there is no generally accepted notion of what a "logic" is (e.g. related to your previous question, do we consider second-order logic with the standard semantics a "logic"? reasonable people disagree on this point - certainly I personally don't have a constant position on the question) although there are a few very common ones.

(Incidentally, an interesting question is why "logic" has not developed a precise mathematical meaning over time, given the important role the concept plays in the foundations of mathematics. I have some opinions on that, but I think the question is too vague (and my opinions too unjustified and subjective) to be appropriate here.)


That said, there are indeed theorems which I would call "classification theorems of logics." For example:

  • Lindstrom showed that first-order logic is the maximal regular logic satisfying the Downward Lowenheim-Skolem and Compactness properties, and also the maximal regular logic satisfying the Downward Lowenheim-Skolem property which admits a reasonable (= effective, sound, and complete) proof system. (A regular logic is closely related to first-order logic: sentences are identified with the classes of structures which satisfy them, and we demand closure under Boolean operations and "relativization.") There are a number of other similar results inspired by this, included a Lindstrom-style characterization of modal logic due to Benthem.

  • Shelah showed that there are only four "nicely-definable" fragments of second-order logic: first-order logic, full second-order logic, monadic second-order logic (where we can quantify only over sets, that is, unary predicates), and "permutational" second-order logic (where we can quantify only over 1-1 functions).

  • Abstract elementary classes constitute a kind of generalization of first-order logic, and there are many classification results and conjectures for AECs.

These and other similar results - about logics generally thought of semantically, where the structures involved are (usually) sets with functions, relations, and constants indicated (that is, the same kind of structure as in first-order logic) - belong to abstract model theory, and the collection Model-Theoretic Logics is an invaluable source in this regard. There are also classification results for logics syntactically defined, but I'm less familiar with that side of the subject.