AFTD Auto-Formalizing Theoretical Domains

nat_mex_list_eq_of_all_eq_bit

theoremverified

For any list of natural numbers whose elements all equal a single bit b ∈ {0, 1}, if the list is non-empty, its nat_mex_list is 1 - b.

Statement

theorem nat_mex_list_eq_of_all_eq_bit {l : List ℕ} (b : ℕ) (hb : b = 0 ∨ b = 1)
    (h_all : ∀ x ∈ l, x = b) (h_nonempty : l ≠ []) :
    nat_mex_list l = 1 - b
Source
step towards spider_blocked_incoming_one_inward
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • nat_mex_list_eq_zeroIf a list of naturals does not contain 0, then its mex (minimum excluded value) is 0.
  • nat_mex_list_eq_oneIf a list of naturals contains 0 but not 1, then its mex is 1.
  • nat_mex_listThe minimum excluded value (mex) of a finite list of natural numbers is the least non-negative integer not in the list.

The proof, explained

The proof proceeds by case analysis on whether the bit b is 0 or 1. If b = 0, the non-empty list contains only zeros, so it contains 0 and does not contain 1, making its minimum excluded value (mex) equal to 1 = 1 - 0. If b = 1, the list contains only ones and therefore lacks 0, making its mex equal to 0 = 1 - 1.

  1. Consider separately the cases b = 0 and b = 1.

    The hypothesis hb provides the disjunction b = 0 ∨ b = 1, so we split into two cases.

    line 5

      rcases hb with rfl | rfl
  2. In the case b = 0, it suffices to prove that 0 ∈ l and 1 ∉ l.

    Since 1 - 0 = 1 by Nat.sub_zero, the goal simplifies to nat_mex_list l = 1. By nat_mex_list_eq_one, this equality holds if 0 is an element of l and 1 is not.

    lines 6–7

    uses Nat.sub_zero, nat_mex_list_eq_one

      · rw [Nat.sub_zero]
        apply nat_mex_list_eq_one
  3. 0 ∈ l.

    Because l is non-empty, List.exists_mem_of_ne_nil guarantees an element x ∈ l. Since every element of l equals 0, we have x = 0, and hence 0 ∈ l.

    lines 8–11

    uses List.exists_mem_of_ne_nil

        · obtain ⟨x, hx⟩ : ∃ x, x ∈ l := List.exists_mem_of_ne_nil l h_nonempty
          have hx0 := h_all x hx
          subst hx0
          exact hx
  4. 1 ∉ l.

    Assuming for contradiction that 1 ∈ l, the assumption that all elements are 0 implies 1 = 0, which is false by direct evaluation.

    lines 12–15

        · intro h1
          have h10 := h_all 1 h1
          revert h10
          decide
  5. In the case b = 1, it suffices to prove that 0 ∉ l.

    Since 1 - 1 = 0 by Nat.sub_self, the goal becomes nat_mex_list l = 0. By nat_mex_list_eq_zero, this follows once we show that 0 is not in l.

    lines 16–17

    uses Nat.sub_self, nat_mex_list_eq_zero

      · rw [Nat.sub_self]
        apply nat_mex_list_eq_zero
  6. 0 ∉ l.

    Assuming for contradiction that 0 ∈ l, the assumption that all elements of l are 1 implies 0 = 1, which is false by direct evaluation.

    lines 18–21

        intro h0
        have h01 := h_all 0 h0
        revert h01
        decide
Nat.sub_zero
Subtracting zero from any natural number leaves it unchanged: n - 0 = n.
nat_mex_list_eq_one
If a list of natural numbers contains 0 and does not contain 1, its minimum excluded value (mex) is 1.
List.exists_mem_of_ne_nil
Any non-empty list contains at least one element.
Nat.sub_self
Subtracting any natural number from itself yields zero: n - n = 0.
nat_mex_list_eq_zero
If a list of natural numbers does not contain 0, its minimum excluded value (mex) is 0.

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

/-- The mex of a non-empty list of natural numbers whose elements all equal a bit b in {0, 1} is 1 - b. -/theorem nat_mex_list_eq_of_all_eq_bit {l : List ℕ} (b : ℕ) (hb : b = 0 ∨ b = 1)    (h_all : ∀ x ∈ l, x = b) (h_nonempty : l ≠ []) :    nat_mex_list l = 1 - b := by  rcases hb with rfl | rfl  · rw [Nat.sub_zero]    apply nat_mex_list_eq_one    · obtain ⟨x, hx⟩ : ∃ x, x ∈ l := List.exists_mem_of_ne_nil l h_nonempty      have hx0 := h_all x hx      subst hx0      exact hx    · intro h1      have h10 := h_all 1 h1      revert h10      decide  · rw [Nat.sub_self]    apply nat_mex_list_eq_zero    intro h0    have h01 := h_all 0 h0    revert h01    decide
See it in the graphDiscuss this resultChallenge it