Mathematics Problem Archive

Problem Find a constant $k$ such that for any $d$ there is a sequence of tautologies of depth $k$ that have polynomial (or quasi-polynomial) size proo...

Conjecture Is the theory of the real numbers with the exponential function decidable?...

Question How many steps does it take the sixth Goodstein sequence to terminate?...

Question Can either of the following be expressed in fixed-point logic plus counting: - Given a graph, does it have a perfect matching, i.e., a set $...

Question - Does ${<}\text{-invariant\:FO} = \text{FO}$ hold over graphs of bounded tree-width? - Is ${<}\text{-invariant\:FO}$ included in $\text{MSO...

The problem concerns the extension of Monadic Second Order Logic (over a binary relation representing the edge relation) with the following atomic for...

Let $C$ be a class of finite relational structures. We denote by $f_C(n)$ the number of structures in $C$ over the labeled set $\{0, \dots, n-1 \}$. F...

Question Is the MSO-alternation hierarchy strict for pictures that are balanced, in the sense that the width and the length are polynomially (or linea...

Question Positive Horn logic (pH) is the fragment of FO involving exactly $\exists, \forall, \wedge, =$. Does the fragment $pH \wedge \neg pH$ have th...

Conjecture For every $\varepsilon > 0$ there is $\delta > 0$ such that, for every large $n$, there are $n$-vertex graphs $G$ and $H$ such that $G \equ...

Is the complement of the finite spectrum of every first-order sentence also a finite spectrum? Equivalently, is $\mathrm{NE}=\mathrm{coNE}$?...

Does there exist a reasonable logic strictly stronger than first-order logic that has both compactness and Craig's interpolation property?...

Prove a superpolynomial lower bound on the size of Frege proofs; in particular, do some tautologies require exponentially large Frege proofs?...

For any finite sets $X$ and $Y$ of published mathematical theorems expressible in second-order arithmetic, is either $\mathsf{RCA}_0+X$ interpretable ...

Are the following statements equivalent to $\Pi^1_1\text{-}\mathsf{CA}_0$? (i) If countable torsion abelian groups $G,H$ satisfy $G\oplus G\cong H\opl...

Determine the reverse-mathematical strength of Alexandroff's one-point compactification theorem for countably based MF spaces....

Determine the reverse-mathematical strength of the assertion that a proper MF space is metrizable if and only if it is regular....

Over $\mathsf{RCA}_0$, does the Furstenberg–Zimmer structure theorem imply $\Pi^1_1\text{-}\mathsf{CA}_0$?...

For an ordinal $\alpha$, determine the length (maximal order type) of the well-quasi-order $L_\alpha$ of countable linear orders of Hausdorff rank bel...

Determine the reverse-mathematical strengths of Laver's labeled-linear-order theorem $\mathsf{LAV}$ and the Nash–Williams bqo transfinite-sequence the...

Is weak-$L_{\omega_1,\omega}$-$\mathsf{CA}$ equivalent to weak-$\Sigma^1_1$-$\mathsf{AC}_0$?...

Is the open mapping theorem for separable Banach spaces provable in $\mathsf{RCA}_0$, or at least in $\mathsf{WKL}_0$?...

Determine the exact reverse-mathematical strength of the Krein–Šmulian theorem for separable Banach spaces....

Is Szemerédi's theorem provable in $\mathsf{ACA}_0$? More generally, determine its reverse-mathematical strength....

Determine the reverse-mathematical strength of Kříž's labeled-tree generalization of Kruskal's theorem....

The universality spectrum problem: Is there a first-order theory whose universality spectrum is minimum?...

Does a finitely presented homogeneous structure for a finite relational language have finitely many reducts?...

Is the theory of the field of Laurent series over $\mathbb{Z}_p$ decidable? of the field of polynomials over $\mathbb{C}$?...

Is there a logic L which satisfies both the Beth property and Δ-interpolation, is compact but does not satisfy the interpolation property?...

What is the nature of the proof-theoretic ordinal (the smallest ordinal a theory cannot prove well-founded) for second-order arithmetic, ZFC, or stron...