Return to Answer

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.

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?

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.

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.

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.

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}$?"

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.

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.

The compactness and Löwenheim–Skolem theorems 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?

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 $\mathrm{PA}$ is $$\epsilon_0=\omega^{\omega^{\scriptstyle\omega^{\scriptstyle\cdot^{\scriptstyle.{\cdot}}}}}.$$ Proof-theoretic ordinals have been calculated for a variety of systems reaching up to (something around) $\Pi^1_2$-$\mathrm{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.

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 $\operatorname{Aut}(\mathcal{D})$ is at most countable. The automorphism problem is exactly the question of determining $\operatorname{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.

An important theme in set theory is the development of canonical models for extensions of ZFC. The first example is Gödel’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.

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-Tóth, A partial solution of the finite spectrum problem).

There is a complexity theory connection here: a set is a spectrum iff it is in NE. So the finite spectrum problem asks, “Does $\mathrm{NE}=\mathrm{coNE}$?”

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 Lindström’s Theorem, which showed that there is no “reasonable” logic stronger than first-order logic which satisfies both the Compactness and Löwenheim–Skolem properties.

Shortly after Lindström’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 Lindström, 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.

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

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

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

FINITE MODEL THEORY