cycle_cut_split_link_crosses
For integers i, j, a, b, m satisfying a ≤ m < b, if candidate link (i, j) crosses cycle cut [a, b] (meaning (a ≤ i ∧ i ≤ b) ↔ ¬(a ≤ j ∧ j ≤ b)), then it crosses exactly one of the two sub-cuts [a, m] and [m + 1, b].
Statement
theorem cycle_cut_split_link_crosses (i j a b m : ℤ)
(h_ab : a ≤ m ∧ m < b)
(h_cross : (a ≤ i ∧ i ≤ b) ↔ ¬(a ≤ j ∧ j ≤ b)) :
(((a ≤ i ∧ i ≤ m) ↔ ¬(a ≤ j ∧ j ≤ m)) ∨
((m + 1 ≤ i ∧ i ≤ b) ↔ ¬(m + 1 ≤ j ∧ j ≤ b))) ∧
¬ (((a ≤ i ∧ i ≤ m) ↔ ¬(a ≤ j ∧ j ≤ m)) ∧
((m + 1 ≤ i ∧ i ≤ b) ↔ ¬(m + 1 ≤ j ∧ j ≤ b)))- Source
- arXiv:2611.08570, Theorem 5.4
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
For all integers $i, j, a, b, m$, assuming: 1. $a \le m$ and $m < b$, and 2. $a \le i \le b$ holds if and only if $a \le j \le b$ does not hold (i.e., exactly one of $i, j$ is in the closed interval $[a, b]$), it holds that: either ($a \le i \le m$ holds if and only if $a \le j \le m$ does not hold) or ($m + 1 \le i \le b$ holds if and only if $m + 1 \le j \le b$ does not hold), and not both (i.e., exactly one of those two equivalence conditions holds).
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 asserts that splitting a cut interval [a, b] at m into two subintervals [a, m] and [m + 1, b] causes any crossing link to cross exactly one of the two halves. Since the two subintervals form a disjoint partition of [a, b], the single endpoint located inside [a, b] must lie in exactly one of the two halves while the other endpoint lies in neither. The entire claim is phrased in terms of linear inequalities over integers and is proved automatically by Presburger arithmetic.
The link (i, j) crosses exactly one of the two sub-cuts [a, m] and [m + 1, b]. automation
The crossing condition for an interval [x, y] is the exclusive-or relation (x ≤ i ∧ i ≤ y) ↔ ¬(x ≤ j ∧ j ≤ y), meaning exactly one endpoint belongs to the interval. Since a ≤ m < b, the integer interval [a, b] is partitioned into the two disjoint subintervals [a, m] and [m + 1, b]. By hypothesis, exactly one of i or j lies in [a, b] and the other lies outside. The endpoint inside [a, b] must lie in either [a, m] or [m + 1, b], but not both, while the endpoint outside [a, b] lies in neither. Consequently, exactly one endpoint is in one subinterval, and neither endpoint is in the other subinterval, which means the link crosses exactly one of the two halves. The `omega` tactic discharges this goal automatically by linear integer arithmetic.
omega
- The proof consists of a single invocation of the `omega` decision procedure, which discharges the goal through automated linear integer arithmetic reasoning.
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.
/-- A link crossing cut [a, b] crosses exactly one of the halves [a, m] or [m + 1, b]. -/theorem cycle_cut_split_link_crosses (i j a b m : ℤ) (h_ab : a ≤ m ∧ m < b) (h_cross : (a ≤ i ∧ i ≤ b) ↔ ¬(a ≤ j ∧ j ≤ b)) : (((a ≤ i ∧ i ≤ m) ↔ ¬(a ≤ j ∧ j ≤ m)) ∨ ((m + 1 ≤ i ∧ i ≤ b) ↔ ¬(m + 1 ≤ j ∧ j ≤ b))) ∧ ¬ (((a ≤ i ∧ i ≤ m) ↔ ¬(a ≤ j ∧ j ≤ m)) ∧ ((m + 1 ≤ i ∧ i ≤ b) ↔ ¬(m + 1 ≤ j ∧ j ≤ b))) := by omega