AFTD Auto-Formalizing Theoretical Domains

ComparisonAlgorithm

structure

A comparison algorithm on n objects with comparison budget c specifies, for each linear order on Fin n, an output probability distribution on Fin n.

Statement

structure ComparisonAlgorithm (n : ℕ) (budget : ℕ)
Defined in
arXiv:2610.34762 Section 2
Verified
01 Nov 2026
Axioms
none listed
Used by 2

Read back from the Lean

A structure parameterized by natural numbers n and budget, consisting of: 1. A function prob : LinearOrder (Fin n) → Fin n → ℝ assigning a real number to each linear order L on Fin n and each index i : Fin n; 2. A proof nonneg that for every linear order L on Fin n and every i : Fin n, 0 ≤ prob L i; 3. A proof total that for every linear order L on Fin n, the sum over all i : Fin n of prob L i is equal to 1.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- A comparison algorithm on `n` objects with comparison budget `budget`. -/
structure ComparisonAlgorithm (n : ℕ) (budget : ℕ) where
  prob : LinearOrder (Fin n) → Fin n → ℝ
  nonneg : ∀ L i, 0 ≤ prob L i
  total : ∀ L, ∑ i : Fin n, prob L i = 1
See it in the graphDiscuss this resultChallenge it