AFTD Auto-Formalizing Theoretical Domains

op1525_flip_neighborhood_injective

theoremverified

On an index set with at least three points, a Boolean vector is determined by the set of its single-coordinate flips, even if only containment of that flip set in another vector’s flip set is assumed.

Statement

theorem op1525_flip_neighborhood_injective {I : Type*} [DecidableEq I]
    (a b c : I) (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c)
    (f g : I → Bool)
    (h : ∀ i : I, ∃ j : I, ∀ k : I,
      xor (f k) (decide (k = i)) = xor (g k) (decide (k = j))) : f = g
Source
A bit-flip status lemma for the invariant-pair-orbit route to OP-1525.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The proof proceeds by contradiction, assuming $f \neq g$, which provides a coordinate $x$ where $f(x) \neq g(x)$. Since the index set contains at least three distinct elements, there exist two distinct indices $p, q$ different from $x$. By hypothesis, single flips of $f$ at $p$ and $q$ must match flips of $g$ at some coordinates $j_p$ and $j_q$, respectively; evaluating both equalities at $x$ forces $j_p = x$ and $j_q = x$. Evaluating the equality for $p$ at coordinate $q$ then forces $f(q) = g(q)$, while evaluating the equality for $q$ at coordinate $q$ forces $g(q) = \neg f(q)$, producing the impossible identity $f(q) = \neg f(q)$.

  1. There exists an index $x \in I$ at which $f(x) \neq g(x)$.

    We assume for contradiction that $f \neq g$. If no coordinate differed, then $f(x) = g(x)$ for all $x$, which by function extensionality would force $f = g$, a contradiction. Thus, there is some coordinate $x$ where $f(x) \neq g(x)$.

    lines 6–13

      by_contra hne
      have hx : ∃ x, f x ≠ g x := by
        by_contra hx
        apply hne
        funext x
        by_contra hfxg
        exact hx ⟨x, hfxg⟩
      rcases hx with ⟨x, hxfg⟩
  2. There exist two distinct indices $p, q \in I$ that are both different from $x$.

    The index set contains three distinct elements $a, b, c$. By case analysis on whether $a = x$, and if not, whether $b = x$: if $a = x$, then $b \neq x$ and $c \neq x$, so $(b, c)$ works; if $b = x$, then $a \neq x$ and $c \neq x$, so $(a, c)$ works; otherwise, neither $a$ nor $b$ equals $x$, so $(a, b)$ works. In every branch, we obtain distinct indices $p, q$ different from $x$.

    lines 14–29

      have hpair : ∃ p q : I, p ≠ q ∧ p ≠ x ∧ q ≠ x := by
        by_cases hax : a = x
        · have hbx : b ≠ x := by
            intro hb
            exact hab (hax.trans hb.symm)
          have hcx : c ≠ x := by
            intro hc
            exact hac (hax.trans hc.symm)
          exact ⟨b, c, hbc, hbx, hcx⟩
        · by_cases hbx : b = x
          · have hcx : c ≠ x := by
              intro hc
              exact hbc (hbx.trans hc.symm)
            exact ⟨a, c, hac, hax, hcx⟩
          · exact ⟨a, b, hab, hax, hbx⟩
      rcases hpair with ⟨p, q, hpq, hpx, hqx⟩
  3. Specializing the assumption to $p$ and $q$ yields flip indices $j_p, j_q \in I$.

    Applying the assumption to $i = p$ provides an index $j_p$ such that flipping coordinate $p$ in $f$ matches flipping coordinate $j_p$ in $g$. Symmetrically, applying it to $i = q$ yields $j_q$. We also note by symmetry of inequality that $x \neq p$ and $x \neq q$.

    lines 30–33

      rcases h p with ⟨jp, hp⟩
      rcases h q with ⟨jq, hq⟩
      have hxp : x ≠ p := fun h' => hpx h'.symm
      have hxq : x ≠ q := fun h' => hqx h'.symm
  4. The flip index $j_p$ associated with $p$ must be $x$.

    Assume for contradiction that $x \neq j_p$. Evaluating the equality for $p$ at coordinate $x$, both $\text{decide}(x = p)$ and $\text{decide}(x = j_p)$ are $\text{false}$ because $x \neq p$ and $x \neq j_p$. Simplifying with `Bool.xor_false` leaves $f(x) = g(x)$, directly contradicting $f(x) \neq g(x)$. Therefore, $j_p = x$.

    lines 34–40

    uses Bool.xor_false

      have hxjp : x = jp := by
        by_contra hxne
        have hdecp : decide (x = p) = false := by simp [hxp]
        have hdecj : decide (x = jp) = false := by simp [hxne]
        have := hp x
        simp only [hdecp, hdecj, Bool.xor_false] at this
        exact hxfg this
  5. The flip index $j_q$ associated with $q$ must be $x$.

    Similarly, if $x \neq j_q$, evaluating the equality for $q$ at coordinate $x$ simplifies via `Bool.xor_false` to $f(x) = g(x)$ because neither flip affects coordinate $x$. This contradicts $f(x) \neq g(x)$, so $j_q = x$.

    lines 41–47

    uses Bool.xor_false

      have hxjq : x = jq := by
        by_contra hxne
        have hdecq : decide (x = q) = false := by simp [hxq]
        have hdecj : decide (x = jq) = false := by simp [hxne]
        have := hq x
        simp only [hdecq, hdecj, Bool.xor_false] at this
        exact hxfg this
  6. The values of $f$ and $g$ coincide at coordinate $q$: $f(q) = g(q)$.

    We evaluate the equality for $p$ at coordinate $q$. Since $q \neq p$ and $q \neq j_p$ (as $j_p = x$ and $q \neq x$), the flip indicators $\text{decide}(q = p)$ and $\text{decide}(q = j_p)$ both evaluate to $\text{false}$. Simplifying with `Bool.xor_false` yields $f(q) = g(q)$.

    lines 48–57

    uses Bool.xor_false

      have hqp : q ≠ p := fun h' => hpq h'.symm
      have hqjp : q ≠ jp := by
        intro h'
        exact hqx (h'.trans hxjp.symm)
      have hpq_eq : f q = g q := by
        have := hp q
        have hdecqp : decide (q = p) = false := by simp [hqp]
        have hdecqjp : decide (q = jp) = false := by simp [hqjp]
        simp only [hdecqp, hdecqjp, Bool.xor_false] at this
        exact this
  7. The values of $f$ and $g$ differ at coordinate $q$: $g(q) = \neg f(q)$.

    We evaluate the equality for $q$ at coordinate $q$. The left-hand indicator $\text{decide}(q = q)$ evaluates to $\text{true}$ by `decide_true`, while the right-hand indicator $\text{decide}(q = j_q)$ is $\text{false}$ because $j_q = x$ and $q \neq x$. Simplifying with `Bool.xor_true` and `Bool.xor_false` yields $\neg f(q) = g(q)$, or $g(q) = \neg f(q)$.

    lines 58–66

    uses Bool.xor_false, decide_true, Bool.xor_true

      have hq_neg : g q = ! f q := by
        have := hq q
        have hdecqjq : decide (q = jq) = false := by
          have hqjq : q ≠ jq := by
            intro h'
            exact hqx (hxjq.trans h'.symm).symm
          simp [hqjq]
        simp only [hdecqjq, Bool.xor_false, decide_true, Bool.xor_true] at this
        exact this.symm
  8. A contradiction is derived, concluding $f = g$.

    Transitivity of equality between $f(q) = g(q)$ and $g(q) = \neg f(q)$ produces $f(q) = \neg f(q)$. Case analysis on whether $f(q)$ is $\text{false}$ or $\text{true}$ reveals this equation to be impossible in both cases, which closes the proof by contradiction.

    lines 67–68

      have hcontra : f q = ! f q := hpq_eq.trans hq_neg
      cases hfq : f q <;> simp [hfq] at hcontra
Bool.xor_false
Exclusive-or with `false` is the identity: for any Boolean $x$, $x \oplus \text{false} = x$.
decide_true
The truth value `True` evaluates to the Boolean `true` under `decide`.
Bool.xor_true
Exclusive-or with `true` negates a Boolean: for any Boolean $x$, $x \oplus \text{true} = \neg x$.

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

theorem op1525_flip_neighborhood_injective {I : Type*} [DecidableEq I]    (a b c : I) (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c)    (f g : I → Bool)    (h : ∀ i : I, ∃ j : I, ∀ k : I,      xor (f k) (decide (k = i)) = xor (g k) (decide (k = j))) : f = g := by  by_contra hne  have hx : ∃ x, f x ≠ g x := by    by_contra hx    apply hne    funext x    by_contra hfxg    exact hx ⟨x, hfxg⟩  rcases hx with ⟨x, hxfg⟩  have hpair : ∃ p q : I, p ≠ q ∧ p ≠ x ∧ q ≠ x := by    by_cases hax : a = x    · have hbx : b ≠ x := by        intro hb        exact hab (hax.trans hb.symm)      have hcx : c ≠ x := by        intro hc        exact hac (hax.trans hc.symm)      exact ⟨b, c, hbc, hbx, hcx⟩    · by_cases hbx : b = x      · have hcx : c ≠ x := by          intro hc          exact hbc (hbx.trans hc.symm)        exact ⟨a, c, hac, hax, hcx⟩      · exact ⟨a, b, hab, hax, hbx⟩  rcases hpair with ⟨p, q, hpq, hpx, hqx⟩  rcases h p with ⟨jp, hp⟩  rcases h q with ⟨jq, hq⟩  have hxp : x ≠ p := fun h' => hpx h'.symm  have hxq : x ≠ q := fun h' => hqx h'.symm  have hxjp : x = jp := by    by_contra hxne    have hdecp : decide (x = p) = false := by simp [hxp]    have hdecj : decide (x = jp) = false := by simp [hxne]    have := hp x    simp only [hdecp, hdecj, Bool.xor_false] at this    exact hxfg this  have hxjq : x = jq := by    by_contra hxne    have hdecq : decide (x = q) = false := by simp [hxq]    have hdecj : decide (x = jq) = false := by simp [hxne]    have := hq x    simp only [hdecq, hdecj, Bool.xor_false] at this    exact hxfg this  have hqp : q ≠ p := fun h' => hpq h'.symm  have hqjp : q ≠ jp := by    intro h'    exact hqx (h'.trans hxjp.symm)  have hpq_eq : f q = g q := by    have := hp q    have hdecqp : decide (q = p) = false := by simp [hqp]    have hdecqjp : decide (q = jp) = false := by simp [hqjp]    simp only [hdecqp, hdecqjp, Bool.xor_false] at this    exact this  have hq_neg : g q = ! f q := by    have := hq q    have hdecqjq : decide (q = jq) = false := by      have hqjq : q ≠ jq := by        intro h'        exact hqx (hxjq.trans h'.symm).symm      simp [hqjq]    simp only [hdecqjq, Bool.xor_false, decide_true, Bool.xor_true] at this    exact this.symm  have hcontra : f q = ! f q := hpq_eq.trans hq_neg  cases hfq : f q <;> simp [hfq] at hcontra
See it in the graphDiscuss this resultChallenge it