Alphabeta MathEffective Numberings, Reductions, Resources, and Randomness
About this page
Pipeline-generated
How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
1 · Prerequisites
Abstract Algebra
- Binary Operations, Monoids, Groups and Subgroups
- Cosets, Index and Lagrange's Theorem
- Divisibility, Euclidean Domains, Principal Ideal Domains and Unique Factorisation
- Ideals, Quotient Rings and the Isomorphism Theorems for Rings
- Normal Subgroups and Quotient Groups
- Polynomial Rings, the Division Algorithm and Roots
- Rings, Subrings, Integral Domains and Fields
- Simple Field Extensions and the Construction of the Complex Numbers
Combinatorics
Computability Theory
Linear Algebra
Measure Theory
Probability
Real Analysis
- Absolute and Conditional Convergence; Rearrangement; Products
- Construction of the Real Numbers via Cauchy Sequences
- Construction of the Real Numbers via Dedekind Cuts
- Continuity, IVT, EVT, and Uniform Continuity
- Countability and Uncountability
- Foundations of the Real Numbers for Analysis
- Limits of Real Functions
- limsup, liminf, and Subsequential Limits
- Monotone Functions, Discontinuities, and Continuity Sets
- Monotone Sequences, Bolzano-Weierstrass, and Cauchy Completeness
- Power Series and Real-Analytic Functions
- Properties of the Integral and the Working FTC
- Roots, Rational Powers, and Classical Inequalities
- Sequences and Limits
- Sequences and Series of Functions; Uniform Convergence
- Series: Convergence and the Nonnegative Tests
- Suprema and Infima
- The Derivative and the Mean Value Theorems
- The Exponential Function
- The Logarithm and General Powers
- The Riemann Integral: Definition and Integrability
- Topology of ℝ
Set Theory
2 · Logical flowchart
3 · Items
Definition
Uniform asymptotic time space comparison
Definition
Machine time and space constructibility
Theorem
Clocked universal simulation with time and space bounds
Definition
Primitive recursive functions by initial functions and schemes
Lemma
Fixed coding primitive recursive arithmetic and sequences
Definition
Kleene computation predicate and output map
Lemma
Fixed machine history predicate is primitive recursive
Theorem
Kleene normal form for the fixed machine coding
Definition
Computable many one reducibility interface
Definition
Oracle turing reducibility interface
Definition
Acceptable numbering with universal evaluation
Theorem
Smn for the fixed acceptable numbering
Theorem
Kleene fixed point theorem for program indices
Definition
Polynomial time verifier and reduction interface
Definition
Probabilistic polynomial time machine interface
Definition
Rp corp zpp bpp and pp classes
Definition
Pairwise independent hash family interface
Lemma
Chernoff bound for independent bernoulli trials
Theorem
Schwartz zippel over finite fields
Sources
- Arora–Barak §§1.2–1.3; local explicit uniform-constant and small-input conventions
- Arora–Barak Chapter 3 constructibility conventions, adapted contract; complete source reading pending
- Arora–Barak, Appendix 1.A, printed35–38, time-buffer route; integral reset counting, lazy initialization and separate space construction supplied locally
- Gallier §1.7–§1.8 (recovery edition); local parameter-recursion construction
- Gallier §§1.7–1.8, Proposition 1.5–1.8 and §2.1 coding; local cons coding replaces prime-sequence coding
- Gallier §2.3, adapted from register configurations to the published machine syntax
- Gallier §2.3, Comp and End construction; explicit local Turing-history adaptation
- Gallier §2.3, Proposition 2.5 and §1.9; machine-specific proof supplied locally
- Patey chapter 5, Definitions 4.1 and 5.2, pp.87–89 (design locator, independently unread)
- Patey chapter 5, relative-computability interfaces; full text pending
- Gallier §3.1, acceptable indexing and universal/composition interfaces
- Gallier Theorem 3.1 and its complete composition argument, pp.68–69 of recovery edition
- Gallier §5.1, Theorem 5.1; specialization proof route
- Arora–Barak §§2.1–2.2 verifier/reduction definitions; source reading incomplete
- Arora–Barak §7.1, Definitions 7.1 and 7.4
- Arora–Barak §7.3; local finite-prefix expectation convention
- Aspnes pairwise-independence/hash-family treatment, complete locator/reading pending; explicit local affine proof
- Aspnes §§5.2.1–5.2.4 and H.2.2; additive centered-mgf argument is local
- Arora–Barak Appendix A, Lemma A.25, PDF p.475; nonempty-subset extension by the same counting proof