op1525_flip_neighborhood_injective
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)$.
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)$.
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⟩
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$.
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⟩
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$.
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
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$.
uses
Bool.xor_falsehave 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
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$.
uses
Bool.xor_falsehave 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
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)$.
uses
Bool.xor_falsehave 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
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)$.
uses
Bool.xor_false,decide_true,Bool.xor_truehave 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
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.
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
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.
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