Logic
-
0 votes 0 replies 0 views
Paper Weak normalization implies strong normalization in pure type systems
Proves that weak normalization implies strong normalization for every pure type system: if every legal expression in every valid context has a β-normal form, every β-reduction sequence terminates. This resolves the…
-
0 votes 0 replies 0 views
Paper The Partition Principle does not imply Choice
Assuming ZF is consistent, constructs a model in which every surjective image of a set injects into that set, yet the axiom of choice fails. Choice for ordinal-indexed families still holds. From any countable transitive…
-
0 votes 0 replies 0 views
Paper Shelah's eventual categoricity and the prescribed-threshold obstruction
Proves Shelah's eventual categoricity conjecture in ZFC: for each bound on the Löwenheim–Skolem number, a uniform threshold makes categoricity of an abstract elementary class in one cardinal above that threshold imply…
-
0 votes 0 replies 0 views
Paper Rigidity of the Turing degrees
Every order automorphism of the Turing degrees is the identity, resolving their rigidity problem. Thus no nontrivial relabeling of degrees preserves the ordering by relative computability. () Manuscript September 24,…
-
0 votes 0 replies 0 views
Paper Single-fold Diophantine representations and undecidability under an at-most-one-solution promise
Every recursively enumerable set of tuples of natural numbers has a Diophantine representation with exactly one auxiliary solution for each member and none for nonmembers. This proves the single-fold conjecture and…
-
0 votes 0 replies 0 views
Paper Separating choiceless counting from polynomial time and witnessed choice
Confirms the Blass–Gurevich–Shelah noncapture conjecture: consistency of a linear system over 𝔽3 defines a polynomial-time query on unordered finite structures that choiceless polynomial time with counting cannot…
6 posts