nat_mex_list_append_comm
For any two lists of natural numbers l1 and l2, nat_mex_list (l1 ++ l2) = nat_mex_list (l2 ++ l1).
Statement
theorem nat_mex_list_append_comm (l1 l2 : List ℕ) :
nat_mex_list (l1 ++ l2) = nat_mex_list (l2 ++ l1)- Source
- step towards spider_blocked_incoming_one_inward
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- nat_mex_listThe minimum excluded value (mex) of a finite list of natural numbers is the least non-negative integer not in the list.
- nat_mex_list_not_mem_and_ltFor a list l of naturals, nat_mex_list l is not a member of l, and every natural number below nat_mex_list l is a member of l.
- Used by 2
- spider_gamma_rotate_three_short_legsFor any leg p, centre status and fuel, the value of (s;{p,1^in,1^out}) equals the value of (s;{1^in,1^out,p}): the leg p may be moved from…
- spider_gamma_swap_twoThe Grundy value of a two-legged spider state is invariant under swapping the two legs in the list.
The proof, explained
The proof shows that the minimum excluded value (mex) of a list depends only on the set of elements in the list. Since list concatenation is set-theoretically commutative, l1 ++ l2 and l2 ++ l1 contain exactly the same elements. By trichotomy, if one mex were strictly less than the other, it would have to belong to the other list by the definition of mex and therefore to its own list by element equivalence, contradicting that a mex never belongs to its list. Thus, the two mex values must be equal.
The minimum excluded value of l1 ++ l2 does not belong to l1 ++ l2 while every smaller natural number does, and symmetrically for l2 ++ l1.
Applying nat_mex_list_not_mem_and_lt to l1 ++ l2 gives hypothesis h1, and applying it to l2 ++ l1 gives hypothesis h2. Together, these establish the characteristic properties of the mex for each concatenated list.
uses
nat_mex_list_not_mem_and_lthave h1 := nat_mex_list_not_mem_and_lt (l1 ++ l2) have h2 := nat_mex_list_not_mem_and_lt (l2 ++ l1)
For any natural number k, k ∈ l1 ++ l2 ↔ k ∈ l2 ++ l1.
Membership in a concatenated list s ++ t means membership in s or in t (by List.mem_append). Since disjunction is commutative (by or_comm), k ∈ l1 ∨ k ∈ l2 is equivalent to k ∈ l2 ∨ k ∈ l1, so the two concatenations contain exactly the same elements.
uses
List.mem_append,or_commhave h_iff (k : ℕ) : k ∈ l1 ++ l2 ↔ k ∈ l2 ++ l1 := by simp [List.mem_append, or_comm]
It suffices to consider the three trichotomy cases: nat_mex_list (l1 ++ l2) < nat_mex_list (l2 ++ l1), equality, and nat_mex_list (l2 ++ l1) < nat_mex_list (l1 ++ l2).
By trichotomy of the strict linear order on natural numbers (lt_trichotomy), exactly one of these three relations must hold between the two values.
uses
lt_trichotomyrcases lt_trichotomy (nat_mex_list (l1 ++ l2)) (nat_mex_list (l2 ++ l1)) with hlt | heq | hgt
The strict inequality nat_mex_list (l1 ++ l2) < nat_mex_list (l2 ++ l1) leads to a contradiction.
If nat_mex_list (l1 ++ l2) were strictly less than nat_mex_list (l2 ++ l1), the defining property h2 would force nat_mex_list (l1 ++ l2) to be an element of l2 ++ l1. By the equivalence of list membership (h_iff), it would also belong to l1 ++ l2, which directly contradicts h1 (that the mex of a list cannot be an element of that list).
· have := h2.2 (nat_mex_list (l1 ++ l2)) hlt rw [← h_iff] at this exact (h1.1 this).elim
When nat_mex_list (l1 ++ l2) = nat_mex_list (l2 ++ l1), the theorem holds directly.
The equality goal is identical to the assumption heq in this branch.
· exact heqThe strict inequality nat_mex_list (l2 ++ l1) < nat_mex_list (l1 ++ l2) leads to a contradiction.
Symmetrically, if nat_mex_list (l2 ++ l1) were strictly less than nat_mex_list (l1 ++ l2), then by h1 it would belong to l1 ++ l2. Using the membership equivalence (h_iff), it would belong to l2 ++ l1, contradicting h2.
· have := h1.2 (nat_mex_list (l2 ++ l1)) hgt rw [h_iff] at this exact (h2.1 this).elim
nat_mex_list_not_mem_and_lt- For any list of natural numbers l, the minimum excluded value nat_mex_list l does not belong to l, and every natural number strictly less than nat_mex_list l belongs to l.
List.mem_append- An element belongs to the concatenation of two lists if and only if it belongs to the first list or to the second list.
or_comm- Logical disjunction is commutative: a ∨ b is equivalent to b ∨ a.
lt_trichotomy- For any two elements a and b in a linear order, either a < b, a = b, or b < a.
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 the concatenation of two lists does not depend on the order of concatenation. -/theorem nat_mex_list_append_comm (l1 l2 : List ℕ) : nat_mex_list (l1 ++ l2) = nat_mex_list (l2 ++ l1) := by have h1 := nat_mex_list_not_mem_and_lt (l1 ++ l2) have h2 := nat_mex_list_not_mem_and_lt (l2 ++ l1) have h_iff (k : ℕ) : k ∈ l1 ++ l2 ↔ k ∈ l2 ++ l1 := by simp [List.mem_append, or_comm] rcases lt_trichotomy (nat_mex_list (l1 ++ l2)) (nat_mex_list (l2 ++ l1)) with hlt | heq | hgt · have := h2.2 (nat_mex_list (l1 ++ l2)) hlt rw [← h_iff] at this exact (h1.1 this).elim · exact heq · have := h1.2 (nat_mex_list (l2 ++ l1)) hgt rw [h_iff] at this exact (h2.1 this).elim