Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Mathematical Logic

78 missions · 48 completed

Missions

Open30Completed48All78
🏆Completed
Formal VerificationTheoretical Computer Science·Captain: Rizwan G Mir

The Cook-Levin Theorem: NP-Completeness of Boolean Satisfiability in Lean 4Research Paper

The Cook-Levin theorem states that CNF SAT is NP-complete. This mission formalizes the theorem over a multi-tape Turing machine model in Lean 4.

175 thms9 active usersReviewed
🏆Completed
OptimizationTheoretical Computer Science·Captain: Shuze Chen

Horn Maximum Satisfiability: Reductions, Algorithms and Applications: SAT reduces to Horn MaxSAT by dual-rail encodingResearch Paper

Boolean satisfiability asks whether a collection of logical requirements can hold simultaneously. Maximum satisfiability instead asks how many requirements can hold, while sometimes retaining a separate collection that must hold. Restricting the syntax of each requirement can substantially change the decision problem without removing the expressive power of…

19 thms6 active usersReviewed
🏆Completed
Formal VerificationTheoretical Computer ScienceTopology·Captain: Shuze Chen

Distributed LTL Synthesis under Arbitrary Message AdversariesResearch Paper

Reactive synthesis asks for a program whose outputs satisfy a logical specification against every input stream. For a single process and specifications in linear temporal logic (LTL) it is decidable (Pnueli–Rosner 1989); for several processes with partial information it is undecidable in general (Pnueli–Rosner 1990), and decidable cases rely on a hierarchy…

31 thms5 active usersReviewed
🏆Completed
Theory of Computation·Captain: mikedeng1

On the (Im)possibility of Obfuscating Programs 2: Without the Size 1^|M| a Simulator with Oracle Access to ⟨M⟩ Cannot Decide Every Decidable Promise Problem Closed under Functional EquivalenceResearch Paper

Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan and Yang (J. ACM 59(2), 2012) proved that virtual-black-box obfuscation is impossible in general: there are programs from which any obfuscated copy leaks something that oracle access to the program does not. The definition being refuted asks that whatever can be computed from the obfuscated code can also…

11 thms4 active usersReviewed
🏆Completed
Category TheoryTheoretical Computer ScienceType Theory·Captain: kmehltretter82

The Groupoid Model Refutes Uniqueness of Identity ProofsResearch Paper

In dependent type theory, a proof of equality is itself a mathematical object. If two objects a,b:Aa,b:Aa,b:A are equal, the identity type IdA(a,b)\mathrm{Id}_A(a,b)IdA​(a,b) contains the evidence for that equality. A further identity type can express equality between two such proofs. The uniqueness of identity proofs principle, abbreviated UIP, says that any two proofs of the same…

7 thms3 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: kmehltretter82

Multivariate Amortised Resource Analysis for Term Rewrite SystemsResearch Paper

Static resource analysis aims to derive machine-checkable upper bounds on the computational cost of a program without executing it on every input. In Tarjan's potential method (1985), each program state is assigned a nonnegative potential so that the drop in potential across a step pays for both its immediate cost and the potential required by subsequent…

10 thms3 active usersReviewed
🏆Completed
Model Theory·Captain: LG

Continuum Hypothesis: Independence from ZFCTextbook

The continuum hypothesis (CH) asks how large the set of real numbers is. Cantor proved that ∣Z∣=∣Q∣<∣R∣|\mathbb Z|=|\mathbb Q|<|\mathbb R|∣Z∣=∣Q∣<∣R∣, and in 1878 he conjectured that no set has cardinality strictly between that of the integers and that of the reals. Settling CH was the first of Hilbert's problems at the 1900 International Congress of Mathematicians. The question…

33 thms3 active usersReviewed
🏆Completed
Captain: LG

Singular Cardinals Hypothesis: Silver's reduction to countable cofinalityTextbook

Cantor's continuum problem asks for the value of 2κ2^\kappa2κ, the cardinality of the power set of an infinite cardinal κ\kappaκ. For regular cardinals ZFC says almost nothing: by Easton's theorem (1970) the function κ↦2κ\kappa\mapsto 2^\kappaκ↦2κ on regular cardinals can be essentially any non-decreasing function with cf⁡(2κ)>κ\operatorname{cf}(2^\kappa)>\kappacf(2κ)>κ. For singular card…

14 thms3 active usersReviewed
🏆Completed
Theory of Computation·Captain: mikedeng1

On the (Im)possibility of Obfuscating Programs 1: A Decidable Promise Problem Closed under Functional Equivalence Is Decided by a Simulator Given Only Oracle Access to ⟨M⟩ and the Size 1^|M|Research Paper

Program obfuscation asks for a compiler that turns a program into one computing the same function while revealing nothing beyond what black-box access to the function reveals. Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan and Yang (J. ACM 59(2), 2012; conference version CRYPTO 2001) showed that this "virtual black box" notion cannot be achieved in…

8 thms3 active usersReviewed
🏆Completed
Number Theory·Captain: marwahaha

Single-fold Diophantine representationsOpen Problem

A Diophantine representation translates membership in a computably enumerable set into solvability of one polynomial equation. The source asks whether the entire auxiliary witness can always be made unique. The source is OpenAI's September 2026 manuscript.

48 thms3 active usersReviewed
🏆Completed
Model Theory·Captain: wurtle

A CH obstruction to a prescribed categoricity thresholdResearch Paper

A class of structures is categorical in a cardinal λ\lambdaλ if it has exactly one model of size λ\lambdaλ up to isomorphism. Morley's theorem (1965) says that a complete first-order theory in a countable language categorical in one uncountable cardinal is categorical in all of them. Abstract elementary classes (AECs), introduced by Shelah in the 1970s,…

26 thms3 active usersReviewed
🏆Completed
Formal VerificationTheoretical Computer Science·Captain: mikedeng1

Compositional Shape Analysis by Means of Bi-Abduction 1: The Best Abductive Solution for Points-To Symbolic Heaps Is a Computable Disjunction of Symbolic HeapsResearch Paper

Automatic verification of programs that manipulate pointers needs procedure specifications: preconditions saying which part of the heap a procedure touches and postconditions saying what it leaves behind. Writing them by hand does not scale to millions of lines of code. Calcagno, Distefano, O'Hearn and Yang (J. ACM 58(6), 2011) infer them compositionally…

13 thms3 active usersReviewed
🏆Completed
Topology·Captain: LG

Acharjee–Gogoi: Cognitive-Consequence Spaces and the Limit of Human IntelligenceResearch Paper

In 1998 Smale listed eighteen problems for the twenty-first century; the eighteenth asks: What are the limits of intelligence, both artificial and human? (Smale 1998). The paper of Acharjee and Gogoi (arXiv:2310.10792) proposes a mathematical model of a mind, the cognitive-consequence space, built from a Tarski consequence operator, and claims that two…

14 thms3 active usersReviewed
🏆Completed
Captain: LG

Jech Set Theory I: Silver's Theorem on Singular CardinalsTextbook

How large can the power set of an infinite set be? For a regular cardinal κ\kappaκ (one that is not the supremum of fewer than κ\kappaκ smaller ordinals) the answer is: almost anything. Easton's theorem (1970) shows that the function κ↦2κ\kappa \mapsto 2^{\kappa}κ↦2κ on regular cardinals can be prescribed arbitrarily in any model of ZFC, subject only to monotonicity…

7 thms3 active usersReviewed
🏆Completed
Formal VerificationTheoretical Computer Science·Captain: mikedeng1

Tree Equivalence of Higher-Order Recursion Schemes Is UndecidableResearch Paper

A higher-order recursion scheme (HORS) is a finite, simply typed recursive program whose terminal symbols act as tree constructors. Unfolding it from its start symbol generates a possibly infinite ordered, labelled tree. Schemes are a standard model of higher-order functional programs: Ong proved that monadic second-order properties of the generated tree…

30 thms2 active usersReviewed
🏆Completed
Complexity TheoryTheoretical Computer Science·Captain: iris

Hard Instances for Strong Semantic Proof Systems: CNFs for Depth-Four PC and Deep Instances for AC0[2]\mathsf{AC}^0[2]AC0[2]-FregeResearch Paper

AC0[2]-Frege is the propositional proof system whose lines are constant-depth Boolean formulas with AND, OR and parity (XOR) gates. Superpolynomial lower bounds for the corresponding circuit class have been known since Razborov and Smolensky (1987) (Razborov 1987, Smolensky 1987), but carrying these techniques over to proofs has been open since the 1990s (Be…

64 thms2 active usersReviewed
🏆Completed
AlgebraModel TheoryPure Mathematics·Captain: Alien60

Barto-Kozik: Absorbing Subalgebras and Cyclic TermsResearch Paper

A constraint satisfaction problem CSP(A)\mathrm{CSP}(\mathbb A)CSP(A) asks whether a given conjunction of constraints, each a relation of a fixed finite structure A\mathbb AA, has a solution. The algebraic approach to its complexity studies the polymorphisms of A\mathbb AA, the operations preserving all of its relations. Bulatov, Jeavons and Krokhin (SIAM J. Comput. 2005)…

13 thms2 active usersReviewed
🏆Completed
AlgebraPure Mathematics·Captain: Alien60

Function Algebras on Finite Sets I: Pol-Inv Galois Connection and the Baker-Pixley TheoremTextbook

A clone on a set AAA is a set of finitary operations that contains all projections and is closed under composition; the term operations of any algebra form a clone. Relations give a dual description: an operation fff preserves an hhh-ary relation R⊆AhR\subseteq A^hR⊆Ah if applying fff coordinatewise to tuples of RRR always lands in RRR. The maps Pol\mathrm{Pol}Pol (operations…

9 thms2 active usersReviewed
🏆Completed
Complexity TheoryTheoretical Computer Science·Captain: iris

Progress on AC0[2]-Frege Lower BoundsResearch Paper

AC0[2]-Frege is the propositional proof system whose lines are constant-depth Boolean formulas with AND, OR, NOT and parity (MOD 2) gates. Proving superpolynomial lower bounds on the size of AC0[2]-Frege refutations of explicit unsatisfiable CNFs is one of the central open problems of proof complexity: the corresponding question for circuits was settled by…

36 thms2 active usersReviewed
🏆Completed
Theoretical Computer ScienceType Theory·Captain: kmehltretter82

Type-Based Termination Checking in AgdaResearch Paper

A proof assistant based on type theory has to reject non-terminating definitions: a function that loops can inhabit any type, including the empty one, and so proves everything. Agda therefore checks every recursive definition for termination before accepting it. Purely syntactic checks, which require some argument to become structurally smaller at each…

30 thms2 active users
🏆Completed
Formal VerificationTheory of Computation·Captain: mikedeng1

Monitoring Metric First-Order Temporal Properties: The Monitor M_Φ Outputs Exactly the Violations (¬Φ)^(D̄,τ̄,i) of a Bounded MFOTL Formula Φ, as Regular Sets, at Every Time Point iResearch Paper

Runtime monitoring checks a running system against a specification by inspecting its trace of events as it is produced. Policies on data, such as "every published report was approved within the last 10 days" or "each value stored in in reaches out within 5 time units", quantify over data values and constrain the time between events. Metric first-order…

14 thms2 active usersReviewed
🏆Completed
Functional Analysis·Captain: marwahaha

Relative independence of the separable quotient problemOpen Problem

The separable quotient problem asks whether every infinite-dimensional Banach space admits a separable infinite-dimensional quotient. The selected statement isolates a negative result under the continuum hypothesis. The pinned manuscript supplies the research context.

5 thms2 active usersReviewed
🏆Completed
Functional Analysis·Captain: marwahaha

A counterexample to Naimark's problem in ZFCOpen Problem

Uniqueness of irreducible representations is a strong condition on a C*-algebra. The target asks for a counterexample to the expected compact-operator characterization without added set-theoretic hypotheses. The pinned manuscript supplies the research context.

3 thms2 active usersReviewed
🏆Completed
Captain: marwahaha

The Partition Principle does not imply ChoiceOpen Problem

The Partition Principle reverses the cardinal comparison provided by a surjection without requiring a section. The source studies whether this weaker form of comparison can hold while full Choice fails. The source is OpenAI's September 2026 manuscript.

24 thms2 active usersReviewed
🏆Completed
Algebra·Captain: marwahaha

Finite congruence lattices: characterization and undecidabilityOpen Problem

A finite algebra has a lattice of congruences, ordered by inclusion. The source studies which finite lattices arise in this way, and the available goal captures its colored-graph characterization. The source is OpenAI's September 2026 manuscript.

4 thms2 active usersReviewed
PreviousPage 1 of 2Next

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me