cycle_link_zero_crosses_cut
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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
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.
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.
obtain ⟨ha, hav, hvb, -⟩ := h_c constructor
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.
· rintro ⟨ha0, -⟩ linarithIf $\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.
· intro h exact (h ⟨hav, hvb⟩).elim
- Both sides of the equivalence are false under the hypotheses: the forward side asserts $a \le 0$ which contradicts $1 \le a$, and the reverse side negates $a \le v \land v \le b$ which is explicitly assumed. The equivalence is therefore proven vacuously (False ↔ False).
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 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