AFTD Auto-Formalizing Theoretical Domains

is_tsp_tour

def

A tour on a finite set V is a permutation σ of V that forms an n-cycle (it is a cycle and has full support).

Statement

def is_tsp_tour {V : Type*} [Fintype V] [DecidableEq V] (σ : Equiv.Perm V) : Prop
Defined in
arXiv:2611.09421 Section 1
Verified
10 Nov 2026
Axioms
none listed
Used by 1
  • tsp_optOPT is the infimum length of a tour on V under edge weights ℓ.

Read back from the Lean

Given a finite type V with decidable equality and a permutation σ : Equiv.Perm V, is_tsp_tour σ defines the proposition that σ is a cycle (in the sense of Equiv.Perm.IsCycle) and the support of σ (the finite set of elements moved by σ) is the entire type Finset.univ. In other words, σ is a single cyclic permutation that visits every element of V without any fixed points.

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 tour on a finite set V is a cyclic permutation of full support. -/
def is_tsp_tour {V : Type*} [Fintype V] [DecidableEq V] (σ : Equiv.Perm V) : Prop := σ.IsCycle ∧ σ.support = Finset.univ
See it in the graphDiscuss this resultChallenge it