AFTD Auto-Formalizing Theoretical Domains

cycle_cut_split_link_crosses

theoremverified

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.

  1. 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.

    line 9

      omega

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

/-- 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
See it in the graphDiscuss this resultChallenge it