AFTD Auto-Formalizing Theoretical Domains

cycle_power_no_island_of_half_monotone

theoremverified

A Boolean class which is monotone toward the left endpoint on the left half and toward the right endpoint on the right half has no selected island between two missing offsets.

Statement

theorem cycle_power_no_island_of_half_monotone
    (H D : ℕ) (x : ℤ → ℕ → Bool)
    (hmono : ∀ p : ℤ,
      (∀ a b : ℕ, a ≤ b → b < H → x p b = true → x p a = true) ∧
      (∀ a b : ℕ, H ≤ a → a ≤ b → b < D → x p a = true → x p b = true)) :
    ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < D →
      x p a = false → x p b = true → x p c = true
Source
Uniform conditional structural helper for OP-205 / RT-1 following arXiv:2610.15635 Section 3. The middle-bit fullness assumptions and smaller-quarter monotonicity are explicit when used; no optimal-count classification, graph covering value or research advance is claimed.
Verified
27 Oct 2026
Axioms
Quot.soundpropext
Used by 2

The proof, explained

The proof proceeds by case analysis on whether the middle offset $b$ lies in the left half $[0, H)$. If $b < H$, then since $a < b$, left-monotonicity forces $x(p, a) = \text{true}$, contradicting the hypothesis that $x(p, a) = \text{false}$. Otherwise $b \ge H$, and right-monotonicity on $[H, D)$ propagates the truth value from $b$ to $c$, yielding $x(p, c) = \text{true}$.

  1. Fix an integer $p$, offsets $a < b < c < D$, and assume $x(p, a) = \text{false}$ and $x(p, b) = \text{true}$.

    We introduce the arbitrary integer $p$, the offsets $a, b, c$ satisfying $a < b$, $b < c$, and $c < D$, and the assumptions that $x(p, a) = \text{false}$ and $x(p, b) = \text{true}$. The goal is to deduce that $x(p, c) = \text{true}$.

    line 10

      intro p a b c hab hbc hc ha hb
  2. The case $b < H$ cannot occur.

    We perform a case split on whether $b < H$. In the branch where $b < H$, since $a < b$, the left-half monotonicity condition applies to $a \le b < H$. Because $x(p, b) = \text{true}$, this forces $x(p, a) = \text{true}$. However, rewriting with the assumption $x(p, a) = \text{false}$ produces the contradiction $\text{false} = \text{true}$.

    lines 11–14

      by_cases hbl : b < H
      · have hh := (hmono p).1 a b (by omega) hbl hb
        rw [ha] at hh
        contradiction
  3. In the remaining case $b \ge H$, $x(p, c) = \text{true}$.

    In the case where $b \ge H$, the inequalities $H \le b \le c < D$ hold by linear arithmetic. The right-half monotonicity condition on $[H, D)$ then applies to $b \le c$. Because $x(p, b) = \text{true}$, it directly implies that $x(p, c) = \text{true}$, completing the proof.

    line 15

      · exact (hmono p).2 b c (by omega) (by omega) hc hb

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

open Finsettheorem cycle_power_no_island_of_half_monotone    (H D : ℕ) (x : ℤ → ℕ → Bool)    (hmono : ∀ p : ℤ,      (∀ a b : ℕ, a ≤ b → b < H → x p b = true → x p a = true) ∧      (∀ a b : ℕ, H ≤ a → a ≤ b → b < D → x p a = true → x p b = true)) :    ∀ (p : ℤ) (a b c : ℕ), a < b → b < c → c < D →      x p a = false → x p b = true → x p c = true := by  intro p a b c hab hbc hc ha hb  by_cases hbl : b < H  · have hh := (hmono p).1 a b (by omega) hbl hb    rw [ha] at hh    contradiction  · exact (hmono p).2 b c (by omega) (by omega) hc hb
See it in the graphDiscuss this resultChallenge it