AFTD Auto-Formalizing Theoretical Domains

nat_mex_list_append_comm

theoremverified

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.

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

    lines 4–5

    uses nat_mex_list_not_mem_and_lt

      have h1 := nat_mex_list_not_mem_and_lt (l1 ++ l2)
      have h2 := nat_mex_list_not_mem_and_lt (l2 ++ l1)
  2. 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.

    lines 6–7

    uses List.mem_append, or_comm

      have h_iff (k : ℕ) : k ∈ l1 ++ l2 ↔ k ∈ l2 ++ l1 := by
        simp [List.mem_append, or_comm]
  3. 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.

    line 8

    uses lt_trichotomy

      rcases lt_trichotomy (nat_mex_list (l1 ++ l2)) (nat_mex_list (l2 ++ l1)) with hlt | heq | hgt
  4. 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).

    lines 9–11

      · have := h2.2 (nat_mex_list (l1 ++ l2)) hlt
        rw [← h_iff] at this
        exact (h1.1 this).elim
  5. 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.

    line 12

      · exact heq
  6. The 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.

    lines 13–15

      · 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

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