66
$\begingroup$

In the past, first-order logic and its completeness and whether arithmetic is complete was a major unsolved issues in logic . All of these problems were solved by Godel. Later on, independence of main controversial axioms were established by forcing method.

I wonder if there still exist some "natural" questions in mathematical logic that are still unsolved? Or is it the case that most of the major questions have been already answered?

I'd love to know about some important, but still unsolved problems that puzzle logicians and why would the young logician\mathematician care about those? (that is, Whey they are important?)

I'm not an expert in logic (nor in any other mathematical field, I'm undergraduate) but I'm interested in logic so I would like to know about the current problems that logicians face and what are the trends of research in the discipline nowdays and what type of problems people are trying to solve.

I know that logic is a vast term which includes many sub-disciplines: model theory, proof theory, set theory, recursion theory, higher-order logics , non-classical logics, modal logics, algebraic logic and many others. So feel free to tell us about problems form whichever topic you would love to.

$\endgroup$
7
  • 4
    $\begingroup$ You might want to look at Saharon Shelah's "Logical dreams," although this is more about set theory than logic. arxiv.org/abs/math/0211398 He also wrote a sequel, "Reflecting on logical dreams," in the book Interpreting Goedel (ed. Juliette Kennedy). $\endgroup$ Dec 27, 2015 at 19:53
  • 17
    $\begingroup$ I believe that this question may be much too broad to answer sensibly. The field of mathematical logic is sweepingly broad, and even small parts of it, say, large cardinal set theory, have a dozen or more huge research programs going on, each with dozens or more open questions that are framing current work. And it is the same with most other topics in logic that you mention. Every one of them has numerous major and minor open questions on which people are hard at work, hundreds of questions altogether. A proper answer to the question will fill a book! $\endgroup$ Dec 27, 2015 at 20:30
  • 2
    $\begingroup$ @JoelDavidHamkins, I agree but I think that dividing the question to many sub-questions posting each one in a new thread will be annoying to the community so I preferred to post it in one thread here. Do you think that If I want more details on a particular topic (say higher order logics), then should I post a new question? $\endgroup$
    – FNH
    Dec 28, 2015 at 22:36
  • 8
    $\begingroup$ The current question is hopelessly broad. I think that much more focussed questions would get more useful and illuminating answers: What are the main open questions guiding research in the Turing degrees? What are the main open questions for cardinal characteristics of the continuum? For forcing axioms? Concerning the very largest large cardinals? What are the main open questions in o-minimality? In models of arithmetic? And so on. Let me add that the suggestion in the current post that perhaps "all the major open questions [in mathematical logic] have been already answered" is frankly absurd. $\endgroup$ Dec 28, 2015 at 22:53
  • 4
    $\begingroup$ @Thomas That doesn't really seem relevant - amongst the Millenium Problems, only P vs. NP is conceivably a logic problem, and it's already listed in none's answer below. $\endgroup$ Dec 30, 2015 at 19:12

9 Answers 9

77
$\begingroup$

Yes, there are several. Here's a few which I personally care about (described in varying amounts of precision). This is not meant to be an exhaustive list, and reflects my own biases and interests.

I am focusing here on questions which have been open for a long amount of time, rather than questions which have only recently been raised, in the hopes that these are more easily understood.


MODEL THEORY

The compactness and Lowenheim-Skolem theories let us completely classify those sets of cardinalities of models of a first-order theory; that is, sets of the form $$\{\kappa: \exists \mathcal{M}(\vert\mathcal{M}\vert=\kappa, \mathcal{M}\models T)\}.$$ A natural next question is to count the number of models of a theory of a given cardinality. For instance, Morley's Theorem shows that if $T$ is a countable first-order theory which has a unique model in some uncountable cardinality, then $T$ has a unique model of every uncountable cardinality (this is all up to isomorphism of course).

Surprisingly, the countable models are much harder to count! Vaught showed that if $T$ is a (countable complete) first-order theory, then - up to isomorphism - $T$ has either $\aleph_0$, $\aleph_1$, or $2^{\aleph_0}$-many countable models. Vaught's Conjecture states that we can get rid of the weird middle case: it's either $\aleph_0$ or $2^{\aleph_0}$. In case the continuum hypothesis holds, VC is vacuously true; but in the absence of CH, very little is known. VC is known for certain special kinds of theories (see e.g. Vaught's conjecture for partial orders and http://link.springer.com/article/10.1007%2FBF02760651) and a counterexample to VC is known to have some odd properties, including odd computability-theoretic properties (https://math.berkeley.edu/~antonio/papers/VaughtEquiv.pdf), but the conjecture is wide open.

NOTE: VC can be rephrased as a "countable/perfect" dichotomy, in which case it is not trivially true if CH holds and is in fact forcing invariant; see e.g. How do we know if Vaught's Conjecture is Absolute?


PROOF THEORY

If $T$ is a strong enough reasonable theory, we can define the proof-theoretic ordinal of $T$; roughly, how much induction is necessary to prove that $T$ is consistent. For instance, the proof-theoretic ordinal of $PA$ is $$\epsilon_0=\omega^{\omega^{\omega^{...}}}.$$ Proof-theoretic ordinals have been calculated for a variety of systems reaching up to (something around) $\Pi^1_2$-$CA_0$, a reasonably strong fragment of second-order arithmetic which is in turn a very very small part of ZFC. It seems unfair, based on this, to list "finding the proof-theoretic ordinal of ZFC" as one of these problems, based on how far away it is; but "find ordinals for stronger theories" is an important program.

See e.g. Proof-Theoretic Ordinal of ZFC or Consistent ZFC Extensions?


COMPUTABILITY THEORY

I believe the oldest open problem in computability theory is the automorphism problem. In Turing's 1936 paper, he introduced - in addition to the usual Turing machine - the oracle Turing machine (or o-machine). This is a Turing machine which is equipped with "extra information" in the form of a (fixed arbitrary) infinite binary string. Oracle machines allow us to compare the non-computability of sets of natural numbers: we write $A\le_T B$ if an oracle machine equipped with $B$ can compute $A$. This yields a partial ordering $\mathcal{D}$, the Turing degrees. Initially the Turing degrees were thought to be structurally simple; for instance, it was conjectured (I believe by Shoenfield) that the partial order is "very homogeneous" (there were many different conjectures).

As it turned out, however, the exact opposite happens: the Turing degrees have surprisingly rich structure. See e.g. http://www.jstor.org/stable/2270693?seq=1#page_scan_tab_contents for an early example of this by Feiner, and http://www.pnas.org/content/76/9/4218.full.pdf for a later one by Shore. Indeed, currently the general belief is that $\mathcal{D}$ is rigid, and it has been shown (see e.g. https://math.berkeley.edu/~slaman/papers/IMS_slaman.pdf, Theorem 4.30) that $Aut(\mathcal{D})$ is at most countable. The automorphism problem is exactly the question of determining $Aut(\mathcal{D})$; I don't have a reference as to when it was first stated, but I vaguely recall the date 1955.

We can also ask about "local" degree structures - e.g., the partial order of the c.e. degrees, or the degrees below $0'$ - and there are interesting connections between the local and global pictures.

Another structural question about the Turing degrees is what sort of natural operations on Turing degrees exist. For instance, there is the Turing jump, and its iterates; but these seem to be the only natural ones. Martin's conjecture states that indeed, every "reasonable" increasing function on the Turing degrees is "basically" an iterate of the Turing jump; MC has a few different forms, for instance "all Borel functions . . ." or "In $L(\mathbb{R})$ . . .". See e.g. https://math.berkeley.edu/~slaman/talks/vegas.pdf.


SET THEORY

An important theme in set theory is the development of canonical models for extensions of ZFC. The first example is Goedel's $L$, which has a number of nice properties: a well-understood structure, a "minimality" property, and a canonical (in particular, foring-invariant) definition. We can ask whether similar models exist for ZFC + large cardinals: e.g. is there a "core" model for ZFC + "There is a measurable cardinal"? This is the inner model program, and has been developed extensively. Surprisingly, there is an end in sight: in an appropriate sense, if a canonical inner model for ZFC + "There is a supercompact cardinal" can be constructed, then this inner model will in fact capture all the large cardinal properties of the universe.

I am breezing past a truly gargantuan amount of detail here, but the picture is roughly accurate. See e.g. http://www.math.uni-bonn.de/ag/logik/events/young-set-theory-2011/Slides/Grigor_Sargsyan_slides.pdf for more details, as well as the recent presentation https://www.youtube.com/watch?v=MFDVN7UEUSg&list=PLTn74Qx5mPsQlRpBE5OnxMdN3R1d3DLUO&index=4 by Woodin.


SET THEORIES

When someone says "set theory," they usually mean ZFC-style set theory. But this isn't necessarily so; there are alternative set theories. As far as I know, the oldest open consistency problem here is whether Quine's NF - an alternative to ZFC - is consistent. Seemingly small variations of NF are known to be consistent, relative to very weak theories, but these proofs dramatically fail to establish the consistency of NF. Recently Gabbay (http://arxiv.org/abs/1406.4060) and Holmes (http://math.boisestate.edu/~holmes/holmes/basicfm.pdf) proposed proofs of Con(NF); my understanding is that Gabbay has withdrawn his proof, and Holmes' proof has not been evaluated by the community (it is quite long and intricate).


FINITE MODEL THEORY

For a first-order sentence $\varphi$, let the spectrum of $\varphi$ be the set of sizes of finite models of $\varphi$: $$\operatorname{Spec}(\varphi)=\{n: \exists\mathcal{M}(\vert\mathcal{M}\vert=n, \mathcal{M}\models\varphi)\}.$$ We can ask what sets of natural numbers are spectra of sentences; in particular, the finite spectrum problem (see the really lovely paper Durand/Jones/Makowsky/More, Fifty years of the spectrum problem) asks whether the complement of a spectrum is also a spectrum. It is known, for example, that the complement of the spectrum of a sentence not using "$=$" is a spectrum (Ecsedi-Toth, A partial solution of the finite spectrum problem).

There is a complexity theory connection here: a set is a spectrum iff it is in NEXP. So the finite spectrum problem asks, "Does $\text{NEXP}=\text{coNEXP}$?"

We can also ask about spectra for non-first-order sentences.


ABSTRACT MODEL THEORY

Abstract model theory is the study of logics other than first-order. The classic text is "Model-theoretic logics" edited by Barwise and Feferman; see (freely available!) https://projecteuclid.org/euclid.pl/1235417263. The field began (arguably) with Lindstrom's Theorem, which showed that there is no "reasonable" logic stronger than first-order logic which satisfies both the Compactness and Lowenheim-Skolem properties.

Shortly after Lindstrom's result, attention turned towards Craig's interpolation theorem, a powerful result in proof theory (see https://math.stanford.edu/~feferman/papers/Harmonious%20Logic.pdf). Feferman, following Lindstrom, asked whether there is a reasonable logic stonger than first-order which satisfies compactness and the interpolation property. As far as I know, this question - and many weaker versions! - are still completely open.

I believe this is by far the youngest question in this answer.

$\endgroup$
15
  • 1
    $\begingroup$ I was planning to write this as a separate post but since your answer already mentions Turing degrees, maybe I should not. May I suggest Martin's conjecture as an important open problem relevant to your list? $\endgroup$
    – Burak
    Dec 27, 2015 at 19:58
  • $\begingroup$ @Burak I completely forgot Martin's conjecture! I've added a little bit on it; feel free to make a more detailed answer. $\endgroup$ Dec 27, 2015 at 20:01
  • $\begingroup$ If you're bringing up inner model theory, why not link to Woodin's notes (and lecture videos) from the recent YST in Jerusalem? $\endgroup$
    – Asaf Karagila
    Dec 27, 2015 at 22:25
  • 1
    $\begingroup$ @AsafKaragila Because I didn't know about them. $\endgroup$ Dec 27, 2015 at 22:43
  • $\begingroup$ @NoahSchweber Thank you very much for the extensive well-written answer! I appreciate your effort very much. If you know something about the open problems on higher order logics or non classical logics, I would love to know about them. $\endgroup$
    – FNH
    Dec 28, 2015 at 19:13
26
$\begingroup$

The modern logic (and foundational mathematics in general) of the 20th century gave us many important things: Russell's type theory, Zermelo-Fraenkel's set theory, meta-theorems about first order logic, including completeness and incompletness phenomena, model theory, and computability theory. Logic expanded into and around mathematics.

In the summer of 2014 at the Vienna Summer of Logic a thousand logicians, if not more, attended a plethora of events that were divided into two parts:

  1. Mathematical Logic hosted 4 conferences, 2 workshops, and one competition.

  2. Logic in Computer Science hosted 8 conferences, $\aleph_0$ workshops, Computer Logic Olympic Games, and a summer school.

It is safe to say that computer science logic has grown bigger than its older sister.

If you are looking for exciting new developments and challenges in logic, turn attention to computer science. But the challenges there are rarely hard mathematical nuts to be cracked. Instead, they are about development of new and strange kinds of logic, about algorithms and decision procedures that serve the needs of computer science, about design of formal systems that is suitable for computer implementation, and so on.

Logic of the early 20th century was a reaction to a conceptual and methodological crisis in mathematics. Logic of the early 21st century is the tool for conquering the newly discovered land of computer science. Now is a good time to be an Edison or a Tesla of logic, and a little less a Cantor or a Russell. (It's always good to be a Gödel or a Turing, of course.)

$\endgroup$
22
$\begingroup$

I do not know whether it is logic or number theory, but Hilbert's 10th problem over rationals ("is there an algorithm to decide whether a given polynomial equation $f(x_1,\dots,x_n)=0$ with rational coefficients have a rational solution?") is still open, on the contrast with negative solution to equations over integers (DPRM theorem.)

$\endgroup$
2
  • $\begingroup$ I think it's definitely in both; see qcpages.qc.cuny.edu/~rmiller/slides/IMS2015.pdf and math.wisc.edu/~lempp/conf/ams15/rmiller.pdf. In particular, it's a question about decidability (so definitely part of logic), and number theory seems deeply relevant (this is actually the first context I saw Bunyakovsky's Conjecture!). $\endgroup$ Dec 27, 2015 at 21:11
  • $\begingroup$ Positive answer would probably have nothing to do with logic (as positive answers for degrees 1 and 2 do not have), but the answer is believed to be negative. $\endgroup$ Dec 28, 2015 at 10:17
21
$\begingroup$

If we're going to include computer science, the big kahuna is of course P vs NP, first proposed by Gödel in a now-famous letter to von Neumann in the 1950s. A fair amount of the existing progress on it has been made by logicians.

Furthermore, the problem can be stated in a particularly logical way: "Is existential second-order logic able to describe languages (of finite linearly ordered structures with nontrivial signature) that first-order logic with least fixed point cannot?"

$\endgroup$
12
$\begingroup$

A recent list of open problems in Reverse Mathematics is:

Antonio Montalbán, Open questions in reverse mathematics, Bulletin of Symbolic Logic 17:3 (2011), 431-454. Preprint

A slightly older list is from Steve Simpson: Open problems in Reverse Mathematics (1999)

I will mention one specific and tantalizing problem: the strength of Hindman's theorem. Upper and lower bounds for this theorem were first established by Blass, Hirst, and Simpson in a joint paper from 1987. Since then, there have been several papers on the ultrafilters that are relevant to the proof, but the overall bounds have been only slightly improved, for example by

Henry Towsner, A Simple Proof and Some Difficult Examples for Hindman’s Theorem, Notre Dame Journal of Formal Logic, 53(1): 53-65. 2012. Preprint

Hindman's theorem is of interest as a purely combinatorial result, but also because it is so closely related to results of topological dynamics such as the Auslander--Ellis theorem.

$\endgroup$
12
$\begingroup$

One of the very interesting open problems in Logic (and CS) I think:

Is the field of constructible numbers known to be decidable?

$\endgroup$
3
  • $\begingroup$ I have an admittedly very naive question: How is the real number whose constructibility is of interest defined? $\endgroup$
    – Joel Adler
    Sep 12, 2018 at 8:37
  • 2
    $\begingroup$ @JoelAdler What do you mean? The problem asks if there exists an algorithm that can tell whether any given first-order sentence in the language of rings is true when interpreted in the field of all constructible numbers. It does not involve any specific real number. $\endgroup$ Sep 12, 2018 at 8:59
  • 1
    $\begingroup$ @EmilJerabek Thanks a lot for your comment, this settles my confusion. I thought it was about deciding whether there was an algorithm deciding the constructibility of a real number, which is decidable. $\endgroup$
    – Joel Adler
    Sep 12, 2018 at 21:53
12
$\begingroup$

The paper “One Hundred and Two Problems in Mathematical Logic” by Harvey Friedman is an article that lists 102 problems in mathematical logic.

These problems were selected in the form of statements "at least as likely as their negations". The problems were open as of 1973, and the article has a postscript from September 1974 with news of three of the problems being solved.

$\endgroup$
4
  • $\begingroup$ Obviously a lot has changed since then; in a once-over, I noted two problems with positive solutions since publication: #25 ("the first-order theory of any nonabelian free group is decidable", by Kharlampovich and Myasnikov), and #38 ("$HA^\omega$ with extensionality and the full axiom of choice is a conservative extension of $HA$", by Beeson and others). I'm sure others would note many other solved problems on the list. $\endgroup$
    – user44143
    Jan 11, 2019 at 3:32
  • 2
    $\begingroup$ The absence of $P=NP$ from the list is interesting. The problem had been formulated by Cook as of 1971, but perhaps was not obviously a problem "in mathematical logic" as of the first draft of Friedman's article in July 1973. The logical description of NP in terms of existential second-order logic had only just been proved, in Ronald Fagin's thesis, submitted at Berkeley in June 1973. $\endgroup$
    – user44143
    Jan 11, 2019 at 3:36
  • 1
    $\begingroup$ The absence of P=NP is due to how everyone knows in their hearts that $P\neq NP$ though no one can prove it. Friedman was looking for problems that are likely to be solved in either direction. $\endgroup$ Mar 18, 2019 at 22:38
  • $\begingroup$ that’s not what Friedman said in the paper, which is why I edited the answer. $\endgroup$
    – user44143
    Mar 19, 2019 at 2:23
11
$\begingroup$

Woodin's omega conjecture. See this pdf

$\endgroup$
11
$\begingroup$

This is perhaps closer to computational complexity than to logic, but there are many open problems in propositional proof complexity that are analogous to, and have close connections to, well-known open problems in computational complexity. For example, it is widely believed that there are tautologies whose proof in a Frege system is necessarily exponential in size; however, so far, no superpolynomial lower bounds have been proven.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.