13 problems

A universal proposition is a statement asserting a property for every integer; a general proof is a proof establishing that proposition for all integers. Gödel's conjecture. One ma…

Let ${\sf PA}_n$ denote the set of theorems of Peano Arithmetic of complexity at most $\Pi_n$. A completion of ${\sf PA}_{n+2}$ is a complete consistent extension of this theory, a…

Let $R$ be the set of Kolmogorov-random binary strings defined using the fixed universal Turing machine $U$, and let $k$ be the threshold supplied by Chaitin's incompleteness theor…

Consider theories such as ZFC and an isomorphism between sentences that are impossible to prove and families of sentences that are hard to prove efficiently. True-unprovable-senten…

Let $\mathcal{S}$ and $\mathcal{T}$ be consistent theories, with $\mathcal{T}$ strictly stronger than $\mathcal{S}$, and let $\mathfrak{I}$ be a collection of sentences unprovable…

Let $R$ be the set of Kolmogorov-random binary strings, where $x\in R$ means that no program of length at most $|x|/2$ outputs $x$. Let $\mathcal{S}$ and $\mathcal{T}$ be consisten…

Let $Q$ be a propositional proof system. A theory $\mathcal{T}$ is a conservative extension of a base theory when it extends that theory without proving any new sentences in the ba…

Let $\mathcal{T}$ be the theory used to define $H'$, and let $H'$ be the collection of dense sets of true $\mathcal{T}$-unprovable sentences described in the source. Given a nondet…

Let $H'$ be the set comprising $H$ and other dense sets of true sentences unprovable in $\mathcal{T}$, including the specified sets associated with universal Turing machines and Tu…

Cieśliński–Urbaniak's conjecture. Any two distinct instances $Y^R(\overline{m})$ and $Y^R(\overline{n})$ are not provably equivalent.

Let $\sf G1$ denote Gödel's first incompleteness property, and order recursively enumerable theories by interpretability, written $\lhd$. A theory is minimal for $\sf G1$ when it s…

Let $\mathcal T$ be the class of theories under consideration, and let $Con_S$ mean that $S$ is consistent. Consistency-provability strengthening conjecture. For every…

Let $\mathcal T$ be the class of theories under consideration, and let $Con_T(\bar n)$ denote the finite consistency statement for $T$ at parameter $n$. Finite consistency incomple…