4

Are there major theorems that logicians have yet to tackle? And I don't mean any problems that pertain to the philosophy of logic (i.e. logical pluralism, the nature of logical consequence, etc), but straight up meta-logical theorems about particular logics.

alghazali
  • 41
  • 1
  • 2
    See [What are some important but still unsolved problems in mathematical logic? on MO](https://mathoverflow.net/q/227083/51484) and an existing [analog on PhilSE](https://philosophy.stackexchange.com/q/51372/9148). Wikipedia has [another list](https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_mathematics#Model_theory_and_formal_languages). One of them is one of the Millenium problems: is [Boolean satisfiability](https://en.wikipedia.org/wiki/Boolean_satisfiability_problem) solvable in polynomial time, i.e. does NP=P? – Conifold Jul 08 '20 at 07:43

1 Answers1

1

Mathematical logic is definitely still an active field. Exactly what constitutes "meta-logical theorems about particular logics" is a bit unclear, but according to any reasonable interpretation I can think of there are plenty of major open questions under this heading. Here are just a couple:

  • Vaught's conjecture about the number of (countable) models (up to isomorphism) of a (countable, consistent, complete, first order) theory is perhaps the oldest "major" open question in mathematical logic. It's a question about the basic set-theoretic properties of the semantics of first-order logic, so I'd think it would qualify.

  • The subfield of abstract model theory is full of questions about logics stronger than first-order, including general existence questions (e.g. "Is there a logic, appropriately defined, which has the compactness and interpolation properties?"). Abstract model theory is no longer as active as it once was, but that's not because all the questions got answered - rather, it's because the questions turned out to be really really hard.

  • Fragments of first-order logic, and nonclassical propositional logics, play important roles in theoretical computer science and complexity theory, and there are plenty of open questions around their combinatorial properties (e.g. about the lengths of proofs in propositional systems of various kinds).

  • Finally, via finite model theory we can often reformulate complexity-theoretic questions like P vs. NP as questions about the relationship between different logics on finite structures; this is called descriptive complexity theory. And again, there are plenty of open questions here (including a rephrasing of P vs. NP as hinted at in the previous sentence).

More generally, this MO thread which Conifold's comment above mentioned has a lot of relevant information.

Noah Schweber
  • 3,220
  • 1
  • 15
  • 19