32 problems

In logic, a true/false decision problem is decidable if there exists an effective method for deriving the correct answer. Logical systems are decidable if membership in their set o…

The Vaught conjecture is a conjecture in the mathematical field of model theory originally proposed by Robert Lawson Vaught in 1961. It states that the number of countable models o…

In model theory, Tarski's exponential function problem asks whether the theory of the real numbers together with the exponential function is decidable. Alfred Tarski had previously…

Hilbert's tenth problem is the tenth on the list of mathematical problems that the German mathematician David Hilbert posed in 1900. It is the challenge to provide a general algori…

The generalized star-height problem in formal language theory is the open question whether all regular languages can be expressed using generalized regular expressions with a limit…

In model theory, a stable group is a group that is stable in the sense of stability theory. An important class of examples is provided by groups of finite Morley rank (see below).

Innateness of multi-step planning. An apparatus enabling multi-step planning is among humans' innate functions.

Let $Q(X,Y)$ be a generalized quantifier, where $X$ and $Y$ denote its two domains. A sentence is $X$-restricted if all of its quantifiers range over $X$. Van Benthem's conjecture.…

In the inferentialist logical basis, base rules are defined for atoms of the form $\langle p,\mathfrak{b}\rangle$, where $p$ is a propositional or predicate atom and $\mathfrak{b}$…

The language and proof system of non-hypothetical logic are considered over the axioms of Peano Arithmetic, denoted by $\mathsf{PA}$, in a purely relational language. One may also…

Let $\Sigma_1$ and $\Sigma_2$ be disjoint signatures, and let ${\mathcal{T}}_1$ and ${\mathcal{T}}_2$ be decidable theories over them. Let ${\mathcal{T}}_1\oplus{\mathcal{T}}_2$ be…

Fast-growth conjecture. The number of arbitrary object systems containing $n$ arbitrary objects is described by a fast-growing function of $n$.

Inferentialist conjecture. The inferentialist view of meaning as being derived from use — in particular, from inference in P-tS — provides a fruitful perspective on the concept of…

Let $AC_*^{1,1}$ and $AC^{1,1}$ denote the indicated choice principles in Henkin predicate logic, and write “weaker” for implication in HPL: a principle $P$ is weaker than $Q$ if e…

Entailment-to-interpolant-existence conjecture. The IEP for $L$ is decidable whenever entailment in $L$ is decidable.

Let $X$ be a team, let $\Sigma$ be a set of $k$-anonymity atoms, and let $\Sigma\vdash x\mkern 2mu\bm{\Upsilon}\mkern -3mu_{k}\mkern 2mu y$ denote derivability from $\Sigma$ using…

A logical domain is a collection of elements with a binary pairing $D\times D\to \textsf{y/n}$ that detects whether elements are the same or not. Its powerset is the collection of…

The paper studies equational theories identifying formal derivations by rule permutations and naturality conditions. In particular, it considers the naturality condition referred t…

Let CL, IL, and ILL denote classical, intuitionistic, and intuitionistic linear logic, respectively. Let $\mathrm{LL}^-$ be linear logic without concurrency or polarization. The no…

Formula-to-variable translation conjecture. Among more expressive logics, there should be translations $(alT,f)$ such that $alT$ maps each entire formula $phi$ to the propositional…

Let ${{\mathsf{SPR}}}\xspace^+$ denote the behavioural formulation of the special principle of relativity, and let ${{\mathsf{SPR}_{{{\mathit{B}}}\xspace}}}\xspace$ denote the body…

Proof-theoretic semantics studies logical validity through the deductive use of logical constants, as expressed by their introduction and elimination rules. In a verificationist ap…

Woods's conjecture. Every parametric Presburger family exhibits eventual quasi-polynomial behavior.

Let $\mathbf A$ be a modeling, and for every first-order formula $\phi$ let $\langle\phi,\mathbf A\rangle$ denote its satisfaction probability in $\mathbf A$. Modeling-theory conje…

Da Costa's conjecture. All logics can be adapted in order to become paraconsistent.