AFTD Auto-Formalizing Theoretical Domains

carpool_edge_crosses

def

An edge between vertices u and v in Fin n crosses a finite vertex subset S : Finset (Fin n) if either u ∈ S and v ∉ S, or v ∈ S and u ∉ S.

Statement

def carpool_edge_crosses {n : ℕ} (u v : Fin n) (S : Finset (Fin n)) : Prop
Defined in
arXiv:2611.00388 Section 2
Verified
07 Nov 2026
Axioms
none listed
Used by 2
  • carpool_witness_familyFix n, T, an edge sequence (u_t, v_t) and D >= 300. From the edges alone one builds a family W of pairs (t, S) with |W| <= 2 T…
  • carpool_backward_step_slack_increaseFor natural numbers n and T, an integer D, trajectory d : ℕ → Fin n → ℤ, and receiver/sender functions a, b : ℕ → Fin n satisfying for all…

Read back from the Lean

Given a natural number n, two vertices u, v : Fin n, and a subset S : Finset (Fin n), carpool_edge_crosses u v S is defined to hold if and only if either u is in S and v is not in S, or v is in S and u is not in S (that is, exactly one of u or v belongs to S).

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

/-- An edge between u and v crosses subset S if exactly one endpoint belongs to S. -/
def carpool_edge_crosses {n : ℕ} (u v : Fin n) (S : Finset (Fin n)) : Prop := (u ∈ S ∧ v ∉ S) ∨ (v ∈ S ∧ u ∉ S)
See it in the graphDiscuss this resultChallenge it