nat_le_sixty_three_in_span_powers_of_two
If a set $S$ of natural numbers contains $0$ and the powers of two $2^i$ for all $0 \le i \le 5$, and is closed under bitwise XOR, then every natural number $g \le 63$ belongs to $S$.
Statement
theorem nat_le_sixty_three_in_span_powers_of_two (S : Set ℕ) (h0 : 0 ∈ S) (hp : ∀ i : ℕ, i ≤ 5 → 2^i ∈ S) (hxor : ∀ a ∈ S, ∀ b ∈ S, a ^^^ b ∈ S) (g : ℕ) (hg : g ≤ 63) : g ∈ S- Source
- arXiv:2610.15145 Theorem 7.3 proof
- Verified
- 24 Oct 2026
- Axioms
Quot.soundpropext
Read back from the Lean
For any set of natural numbers $S$, if $0 \in S$, $2^i \in S$ for all natural numbers $i \le 5$, and $S$ is closed under bitwise XOR (for all $a, b \in S$, $a \oplus b \in S$), then every natural number $g \le 63$ belongs to $S$.
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
The theorem is proved by explicitly constructing every integer from 1 to 63 in S using the powers of two and closure under bitwise XOR. Each power of two 2ᵏ (for k from 0 to 5) is introduced from the hypothesis, and XORing 2ᵏ with all previously derived integers in [1, 2ᵏ - 1] produces all values up to 2ᵏ⁺¹ - 1. Finally, exhaustive case analysis on the natural number g ≤ 63 dispatches all 64 cases against 0 ∈ S and the 63 derived membership facts.
The numbers 1, 2, and 3 belong to S.
Instantiating the power-of-two hypothesis with exponent 0 gives 2⁰ = 1 ∈ S, and with exponent 1 gives 2¹ = 2 ∈ S (with exponents verified to be ≤ 5 by linear integer arithmetic). Because S is closed under bitwise XOR, taking the XOR of 2 and 1 yields 3 ∈ S.
have h1 : (1 : ℕ) ∈ S := hp 0 (by omega) have h2 : (2 : ℕ) ∈ S := hp 1 (by omega) have h3 : (3 : ℕ) ∈ S := hxor 2 h2 1 h1
The numbers 4, 5, 6, and 7 belong to S.
Instantiating the power-of-two hypothesis with exponent 2 gives 2² = 4 ∈ S. Taking the bitwise XOR of 4 with each of the earlier elements 1, 2, and 3 produces 5, 6, and 7, so they all belong to S.
have h4 : (4 : ℕ) ∈ S := hp 2 (by omega) have h5 : (5 : ℕ) ∈ S := hxor 4 h4 1 h1 have h6 : (6 : ℕ) ∈ S := hxor 4 h4 2 h2 have h7 : (7 : ℕ) ∈ S := hxor 4 h4 3 h3
The numbers 8 through 15 belong to S.
The power-of-two hypothesis at exponent 3 gives 2³ = 8 ∈ S. XORing 8 with each of the numbers 1 through 7, all established in previous steps, yields the integers 9 through 15 in S.
have h8 : (8 : ℕ) ∈ S := hp 3 (by omega) have h9 : (9 : ℕ) ∈ S := hxor 8 h8 1 h1 have h10 : (10 : ℕ) ∈ S := hxor 8 h8 2 h2 have h11 : (11 : ℕ) ∈ S := hxor 8 h8 3 h3 have h12 : (12 : ℕ) ∈ S := hxor 8 h8 4 h4 have h13 : (13 : ℕ) ∈ S := hxor 8 h8 5 h5 have h14 : (14 : ℕ) ∈ S := hxor 8 h8 6 h6 have h15 : (15 : ℕ) ∈ S := hxor 8 h8 7 h7
The numbers 16 through 31 belong to S.
The power-of-two hypothesis at exponent 4 gives 2⁴ = 16 ∈ S. XORing 16 with each integer from 1 through 15 yields the numbers 17 through 31 in S.
have h16 : (16 : ℕ) ∈ S := hp 4 (by omega) have h17 : (17 : ℕ) ∈ S := hxor 16 h16 1 h1 have h18 : (18 : ℕ) ∈ S := hxor 16 h16 2 h2 have h19 : (19 : ℕ) ∈ S := hxor 16 h16 3 h3 have h20 : (20 : ℕ) ∈ S := hxor 16 h16 4 h4 have h21 : (21 : ℕ) ∈ S := hxor 16 h16 5 h5 have h22 : (22 : ℕ) ∈ S := hxor 16 h16 6 h6 have h23 : (23 : ℕ) ∈ S := hxor 16 h16 7 h7 have h24 : (24 : ℕ) ∈ S := hxor 16 h16 8 h8 have h25 : (25 : ℕ) ∈ S := hxor 16 h16 9 h9 have h26 : (26 : ℕ) ∈ S := hxor 16 h16 10 h10 have h27 : (27 : ℕ) ∈ S := hxor 16 h16 11 h11 have h28 : (28 : ℕ) ∈ S := hxor 16 h16 12 h12 have h29 : (29 : ℕ) ∈ S := hxor 16 h16 13 h13 have h30 : (30 : ℕ) ∈ S := hxor 16 h16 14 h14 have h31 : (31 : ℕ) ∈ S := hxor 16 h16 15 h15
The numbers 32 through 63 belong to S.
The power-of-two hypothesis at exponent 5 gives 2⁵ = 32 ∈ S. XORing 32 with each integer from 1 through 31 yields the numbers 33 through 63 in S.
have h32 : (32 : ℕ) ∈ S := hp 5 (by omega) have h33 : (33 : ℕ) ∈ S := hxor 32 h32 1 h1 have h34 : (34 : ℕ) ∈ S := hxor 32 h32 2 h2 have h35 : (35 : ℕ) ∈ S := hxor 32 h32 3 h3 have h36 : (36 : ℕ) ∈ S := hxor 32 h32 4 h4 have h37 : (37 : ℕ) ∈ S := hxor 32 h32 5 h5 have h38 : (38 : ℕ) ∈ S := hxor 32 h32 6 h6 have h39 : (39 : ℕ) ∈ S := hxor 32 h32 7 h7 have h40 : (40 : ℕ) ∈ S := hxor 32 h32 8 h8 have h41 : (41 : ℕ) ∈ S := hxor 32 h32 9 h9 have h42 : (42 : ℕ) ∈ S := hxor 32 h32 10 h10 have h43 : (43 : ℕ) ∈ S := hxor 32 h32 11 h11 have h44 : (44 : ℕ) ∈ S := hxor 32 h32 12 h12 have h45 : (45 : ℕ) ∈ S := hxor 32 h32 13 h13 have h46 : (46 : ℕ) ∈ S := hxor 32 h32 14 h14 have h47 : (47 : ℕ) ∈ S := hxor 32 h32 15 h15 have h48 : (48 : ℕ) ∈ S := hxor 32 h32 16 h16 have h49 : (49 : ℕ) ∈ S := hxor 32 h32 17 h17 have h50 : (50 : ℕ) ∈ S := hxor 32 h32 18 h18 have h51 : (51 : ℕ) ∈ S := hxor 32 h32 19 h19 have h52 : (52 : ℕ) ∈ S := hxor 32 h32 20 h20 have h53 : (53 : ℕ) ∈ S := hxor 32 h32 21 h21 have h54 : (54 : ℕ) ∈ S := hxor 32 h32 22 h22 have h55 : (55 : ℕ) ∈ S := hxor 32 h32 23 h23 have h56 : (56 : ℕ) ∈ S := hxor 32 h32 24 h24 have h57 : (57 : ℕ) ∈ S := hxor 32 h32 25 h25 have h58 : (58 : ℕ) ∈ S := hxor 32 h32 26 h26 have h59 : (59 : ℕ) ∈ S := hxor 32 h32 27 h27 have h60 : (60 : ℕ) ∈ S := hxor 32 h32 28 h28 have h61 : (61 : ℕ) ∈ S := hxor 32 h32 29 h29 have h62 : (62 : ℕ) ∈ S := hxor 32 h32 30 h30 have h63 : (63 : ℕ) ∈ S := hxor 32 h32 31 h31
Every natural number g ≤ 63 belongs to S. automation
Because g is a natural number bounded by 63, interval_cases performs exhaustive case analysis, generating 64 cases: g = 0 through g = 63. Each case is closed by matching the goal with the corresponding membership hypothesis (h0 for 0, and h1 through h63 for 1 through 63).
interval_cases g <;> assumption
- In Lean, bitwise XOR (`^^^`) and powers of two on numeral literals reduce definitionally (e.g. `2^2 = 4` and `4 ^^^ 1 = 5`), so applications of `hp` and `hxor` prove membership of the resulting numbers directly without requiring arithmetic rewrite lemmas.
- The tactic `interval_cases g` automatically splits the goal into 64 cases corresponding to the integers 0 through 63, each of which is immediately closed by the corresponding hypothesis in scope.
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.
/-- Any subset of natural numbers containing 0 and the first six powers of 2 and closed under XOR contains all integers up to 63. -/theorem nat_le_sixty_three_in_span_powers_of_two (S : Set ℕ) (h0 : 0 ∈ S) (hp : ∀ i : ℕ, i ≤ 5 → 2^i ∈ S) (hxor : ∀ a ∈ S, ∀ b ∈ S, a ^^^ b ∈ S) (g : ℕ) (hg : g ≤ 63) : g ∈ S := by have h1 : (1 : ℕ) ∈ S := hp 0 (by omega) have h2 : (2 : ℕ) ∈ S := hp 1 (by omega) have h3 : (3 : ℕ) ∈ S := hxor 2 h2 1 h1 have h4 : (4 : ℕ) ∈ S := hp 2 (by omega) have h5 : (5 : ℕ) ∈ S := hxor 4 h4 1 h1 have h6 : (6 : ℕ) ∈ S := hxor 4 h4 2 h2 have h7 : (7 : ℕ) ∈ S := hxor 4 h4 3 h3 have h8 : (8 : ℕ) ∈ S := hp 3 (by omega) have h9 : (9 : ℕ) ∈ S := hxor 8 h8 1 h1 have h10 : (10 : ℕ) ∈ S := hxor 8 h8 2 h2 have h11 : (11 : ℕ) ∈ S := hxor 8 h8 3 h3 have h12 : (12 : ℕ) ∈ S := hxor 8 h8 4 h4 have h13 : (13 : ℕ) ∈ S := hxor 8 h8 5 h5 have h14 : (14 : ℕ) ∈ S := hxor 8 h8 6 h6 have h15 : (15 : ℕ) ∈ S := hxor 8 h8 7 h7 have h16 : (16 : ℕ) ∈ S := hp 4 (by omega) have h17 : (17 : ℕ) ∈ S := hxor 16 h16 1 h1 have h18 : (18 : ℕ) ∈ S := hxor 16 h16 2 h2 have h19 : (19 : ℕ) ∈ S := hxor 16 h16 3 h3 have h20 : (20 : ℕ) ∈ S := hxor 16 h16 4 h4 have h21 : (21 : ℕ) ∈ S := hxor 16 h16 5 h5 have h22 : (22 : ℕ) ∈ S := hxor 16 h16 6 h6 have h23 : (23 : ℕ) ∈ S := hxor 16 h16 7 h7 have h24 : (24 : ℕ) ∈ S := hxor 16 h16 8 h8 have h25 : (25 : ℕ) ∈ S := hxor 16 h16 9 h9 have h26 : (26 : ℕ) ∈ S := hxor 16 h16 10 h10 have h27 : (27 : ℕ) ∈ S := hxor 16 h16 11 h11 have h28 : (28 : ℕ) ∈ S := hxor 16 h16 12 h12 have h29 : (29 : ℕ) ∈ S := hxor 16 h16 13 h13 have h30 : (30 : ℕ) ∈ S := hxor 16 h16 14 h14 have h31 : (31 : ℕ) ∈ S := hxor 16 h16 15 h15 have h32 : (32 : ℕ) ∈ S := hp 5 (by omega) have h33 : (33 : ℕ) ∈ S := hxor 32 h32 1 h1 have h34 : (34 : ℕ) ∈ S := hxor 32 h32 2 h2 have h35 : (35 : ℕ) ∈ S := hxor 32 h32 3 h3 have h36 : (36 : ℕ) ∈ S := hxor 32 h32 4 h4 have h37 : (37 : ℕ) ∈ S := hxor 32 h32 5 h5 have h38 : (38 : ℕ) ∈ S := hxor 32 h32 6 h6 have h39 : (39 : ℕ) ∈ S := hxor 32 h32 7 h7 have h40 : (40 : ℕ) ∈ S := hxor 32 h32 8 h8 have h41 : (41 : ℕ) ∈ S := hxor 32 h32 9 h9 have h42 : (42 : ℕ) ∈ S := hxor 32 h32 10 h10 have h43 : (43 : ℕ) ∈ S := hxor 32 h32 11 h11 have h44 : (44 : ℕ) ∈ S := hxor 32 h32 12 h12 have h45 : (45 : ℕ) ∈ S := hxor 32 h32 13 h13 have h46 : (46 : ℕ) ∈ S := hxor 32 h32 14 h14 have h47 : (47 : ℕ) ∈ S := hxor 32 h32 15 h15 have h48 : (48 : ℕ) ∈ S := hxor 32 h32 16 h16 have h49 : (49 : ℕ) ∈ S := hxor 32 h32 17 h17 have h50 : (50 : ℕ) ∈ S := hxor 32 h32 18 h18 have h51 : (51 : ℕ) ∈ S := hxor 32 h32 19 h19 have h52 : (52 : ℕ) ∈ S := hxor 32 h32 20 h20 have h53 : (53 : ℕ) ∈ S := hxor 32 h32 21 h21 have h54 : (54 : ℕ) ∈ S := hxor 32 h32 22 h22 have h55 : (55 : ℕ) ∈ S := hxor 32 h32 23 h23 have h56 : (56 : ℕ) ∈ S := hxor 32 h32 24 h24 have h57 : (57 : ℕ) ∈ S := hxor 32 h32 25 h25 have h58 : (58 : ℕ) ∈ S := hxor 32 h32 26 h26 have h59 : (59 : ℕ) ∈ S := hxor 32 h32 27 h27 have h60 : (60 : ℕ) ∈ S := hxor 32 h32 28 h28 have h61 : (61 : ℕ) ∈ S := hxor 32 h32 29 h29 have h62 : (62 : ℕ) ∈ S := hxor 32 h32 30 h30 have h63 : (63 : ℕ) ∈ S := hxor 32 h32 31 h31 interval_cases g <;> assumption