nat_xor_mod_two
For any natural numbers a and b, (a ^^^ b) % 2 = (a + b) % 2.
Statement
theorem nat_xor_mod_two (a b : ℕ) : (a ^^^ b) % 2 = (a + b) % 2- Source
- step towards spider_two_leg_one_free
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- spider_mex_two_leg_one_freeGiven an explicit options list where every element has parity k % 2, the minimum excluded value is 1 - k % 2 (which is 1 when k is even,…
The proof, explained
The statement asserts that for any natural numbers $a$ and $b$, bitwise XOR modulo 2 agrees with addition modulo 2. This is identical to the Mathlib lemma `Nat.xor_mod_two_eq`, so the theorem is proved by applying that lemma directly.
For any natural numbers $a$ and $b$, $(a \oplus b) \pmod 2 = (a + b) \pmod 2$.
This is a direct application of the library lemma `Nat.xor_mod_two_eq`, which establishes that bitwise XOR modulo 2 coincides with addition modulo 2 for all natural numbers.
uses
Nat.xor_mod_two_eqtheorem nat_xor_mod_two (a b : ℕ) : (a ^^^ b) % 2 = (a + b) % 2 := Nat.xor_mod_two_eq
Nat.xor_mod_two_eq- For any two natural numbers $m$ and $n$, the bitwise XOR $(m \oplus n) \pmod 2$ is equal to $(m + n) \pmod 2$.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
/-- The bitwise XOR of natural numbers modulo 2 equals their sum modulo 2. -/theorem nat_xor_mod_two (a b : ℕ) : (a ^^^ b) % 2 = (a + b) % 2 := Nat.xor_mod_two_eq