AFTD Auto-Formalizing Theoretical Domains

cycle_link_zero_crosses_cut

theoremverified

For integers v, a, b, n satisfying 0 < v < n and 1 ≤ a ≤ v ≤ b < n, the candidate link (0, v) crosses the cycle cut [a, b], that is, (a ≤ 0 ∧ 0 ≤ b) ↔ ¬(a ≤ v ∧ v ≤ b).

Statement

theorem cycle_link_zero_crosses_cut (v a b n : ℤ)
    (h_v : 0 < v ∧ v < n) (h_c : 1 ≤ a ∧ a ≤ v ∧ v ≤ b ∧ b < n) :
    ((a ≤ 0 ∧ 0 ≤ b) ↔ ¬(a ≤ v ∧ v ≤ b))
Source
arXiv:2611.08570, Theorem 5.4
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…

Read back from the Lean

For all integers $v, a, b, n \in \mathbb{Z}$, if $0 < v$ and $v < n$, and if $1 \le a$, $a \le v$, $v \le b$, and $b < n$, then $(a \le 0 \land 0 \le b)$ holds if and only if $\neg(a \le v \land v \le b)$.

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

Under the hypothesis $1 \le a \le v \le b < n$, both sides of the equivalence are independently false. The forward direction assumes $a \le 0 \land 0 \le b$, which contradicts $1 \le a$ and is closed by linear arithmetic. The backward direction assumes $\neg(a \le v \land v \le b)$, which contradicts the established inequalities $a \le v \le b$, yielding a contradiction from which the goal follows by principle of explosion.

  1. It suffices to prove both implications of the equivalence, having extracted the bounds $1 \le a$, $a \le v$, and $v \le b$.

    Deconstruct the compound hypothesis $h_c$ ($1 \le a \le v \le b < n$) into the individual inequalities $1 \le a$, $a \le v$, and $v \le b$, and split the bi-implication into forward and backward implications.

    lines 5–6

      obtain ⟨ha, hav, hvb, -⟩ := h_c
      constructor
  2. If $a \le 0 \land 0 \le b$, then $\neg(a \le v \land v \le b)$.

    Assume $a \le 0 \land 0 \le b$ for the forward direction. The assumption gives $a \le 0$, which directly contradicts $1 \le a$. Linear arithmetic detects this impossibility ($1 \le a \le 0$) to close the goal.

    lines 7–8

      · rintro ⟨ha0, -⟩
        linarith
  3. If $\neg(a \le v \land v \le b)$, then $a \le 0 \land 0 \le b$.

    Assume $\neg(a \le v \land v \le b)$ for the backward direction. Pairing the known inequalities $a \le v$ and $v \le b$ provides a witness to $a \le v \land v \le b$, which directly contradicts the assumption. This produces False, closing the goal by explosion.

    lines 9–10

      · intro h
        exact (h ⟨hav, hvb⟩).elim

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 with endpoints 0 and v in [a, b] crosses the cycle cut [a, b]. -/theorem cycle_link_zero_crosses_cut (v a b n : ℤ)    (h_v : 0 < v ∧ v < n) (h_c : 1 ≤ a ∧ a ≤ v ∧ v ≤ b ∧ b < n) :    ((a ≤ 0 ∧ 0 ≤ b) ↔ ¬(a ≤ v ∧ v ≤ b)) := by  obtain ⟨ha, hav, hvb, -⟩ := h_c  constructor  · rintro ⟨ha0, -⟩    linarith  · intro h    exact (h ⟨hav, hvb⟩).elim
See it in the graphDiscuss this resultChallenge it