AFTD Auto-Formalizing Theoretical Domains

nat_le_sixty_three_in_span_powers_of_two

theoremverified

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.

  1. 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.

    lines 3–5

      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
  2. 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.

    lines 6–9

      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
  3. 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.

    lines 10–17

      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
  4. 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.

    lines 18–33

      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
  5. 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.

    lines 34–65

      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
  6. 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).

    line 66

      interval_cases g <;> assumption

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

/-- 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
See it in the graphDiscuss this resultChallenge it