cycle_link_crosses_cut_iff_tl_rect
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
- online_cycle_augmentation_reduction_to_tl_hitting_setLet n be a natural number, L a finite set of pairs (i, j) of integers satisfying 0 ≤ i < j < n, w a real cost function on pairs, and α a…
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.
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.
((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)
- The proof uses a tactic cascade `first | (simp_all; done) | omega | ...`. The initial attempt `simp_all` simplifies the logical structure but cannot close the goal; Lean then passes the goal to `omega`, which completes the proof automatically.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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)