AFTD Auto-Formalizing Theoretical Domains

cycle_link_crosses_cut_iff_tl_rect

theoremverifiedformalization

For integers i, j, a, b, n satisfying 0 ≤ i < j < n and 1 ≤ a ≤ b < n, candidate link (i, j) crosses cycle cut [a, b] (meaning (a ≤ i ∧ i ≤ b) ↔ ¬(a ≤ j ∧ j ≤ b)) if and only if (i, j) lies in the union of the leftless rectangle (i ≤ a - 1 ∧ a ≤ j ≤ b) and the topless rectangle (a ≤ i ≤ b ∧ b + 1 ≤ j).

Statement

theorem cycle_link_crosses_cut_iff_tl_rect (i j a b n : ℤ)
    (h_ij : 0 ≤ i ∧ i < j ∧ j < n) (h_ab : 1 ≤ a ∧ a ≤ b ∧ b < n) :
    ((a ≤ i ∧ i ≤ b) ↔ ¬(a ≤ j ∧ j ≤ b)) ↔
      ((i ≤ a - 1 ∧ a ≤ j ∧ j ≤ b) ∨ (a ≤ i ∧ i ≤ b ∧ b + 1 ≤ j))
Formalizes
arXiv:2611.08570 Proposition 3.2
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

Read back from the Lean

For all integers $i, j, a, b, n$, given the hypotheses that $0 \le i$, $i < j$, $j < n$, and that $1 \le a$, $a \le b$, $b < n$: The condition that $(a \le i \wedge i \le b)$ holds if and only if $\neg(a \le j \wedge j \le b)$ (that is, exactly one of $i$ or $j$ lies in the closed interval $[a, b]$) is logically equivalent to the disjunction: - $(i \le a - 1 \wedge a \le j \wedge j \le b)$ or - $(a \le i \wedge i \le b \wedge b + 1 \le j)$.

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

The proof, explained

The theorem establishes that a candidate link (i, j) with i < j crosses the cycle cut [a, b]—meaning exactly one of i or j lies in [a, b]—if and only if (i, j) belongs to either the leftless rectangle (i ≤ a - 1 and a ≤ j ≤ b) or the topless rectangle (a ≤ i ≤ b and b + 1 ≤ j). The constraint i < j prevents i from exceeding b when j ≤ b, and prevents j from falling below a when i ≥ a. Since all constraints are quantifier-free linear integer inequalities, Lean's `omega` decision procedure resolves the equivalence automatically.

  1. A link (i, j) with i < j has exactly one endpoint in [a, b] if and only if either i ≤ a - 1 and a ≤ j ≤ b, or a ≤ i ≤ b and b + 1 ≤ j. automation

    The equivalence asserts that exactly one endpoint of the link (i, j) falls in the interval [a, b]. Because i < j, if j ∈ [a, b] then i < j ≤ b, so i ∉ [a, b] forces i ≤ a - 1 (the leftless rectangle). Similarly, if i ∈ [a, b] then j > i ≥ a, so j ∉ [a, b] forces j ≥ b + 1 (the topless rectangle). The tactic cascade executes `omega`, which decides the Presburger arithmetic problem over the integers and closes the goal.

    line 5

          ((i ≤ a - 1 ∧ a ≤ j ∧ j ≤ b) ∨ (a ≤ i ∧ i ≤ b ∧ b + 1 ≤ j)) := by first | (simp_all; done) | omega | decide | linarith | positivity | (aesop; done)

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Proposition 3.2: A candidate link crosses cycle cut [a, b] if and only if it belongs to the TL-rectangle shape. -/theorem cycle_link_crosses_cut_iff_tl_rect (i j a b n : ℤ)    (h_ij : 0 ≤ i ∧ i < j ∧ j < n) (h_ab : 1 ≤ a ∧ a ≤ b ∧ b < n) :    ((a ≤ i ∧ i ≤ b) ↔ ¬(a ≤ j ∧ j ≤ b)) ↔      ((i ≤ a - 1 ∧ a ≤ j ∧ j ≤ b) ∨ (a ≤ i ∧ i ≤ b ∧ b + 1 ≤ j)) := by first | (simp_all; done) | omega | decide | linarith | positivity | (aesop; done)
See it in the graphDiscuss this resultChallenge it