nat_mex_list_eq_of_all_eq_bit
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.
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.
rcases hb with rfl | rfl
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.
uses
Nat.sub_zero,nat_mex_list_eq_one· rw [Nat.sub_zero] apply nat_mex_list_eq_one
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.
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
1 ∉ l.
Assuming for contradiction that 1 ∈ l, the assumption that all elements are 0 implies 1 = 0, which is false by direct evaluation.
· intro h1 have h10 := h_all 1 h1 revert h10 decide
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.
uses
Nat.sub_self,nat_mex_list_eq_zero· rw [Nat.sub_self] apply nat_mex_list_eq_zero
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.
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
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.
/-- 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