spider_blocked_none_one_inward_one_outward_raw_opts_eq
For r ≥ 2 and φ ≠ free, the value of (none;{(1,inward),(1,outward),(r,φ)}) at fuel r+3 is the mex of the raw option list spider_none_one_inward_one_outward_raw_opts r φ.
Statement
theorem spider_blocked_none_one_inward_one_outward_raw_opts_eq (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) :
spider_gamma (r + 3) CentreStatus.none [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (r, φ)] =
nat_mex_list (spider_none_one_inward_one_outward_raw_opts r φ)- Source
- step towards spider_blocked_none_one_inward_one_outward
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 10
- spider_gammaThe function spider_gamma computes a natural number from a fuel parameter fuel : ℕ, a centre status s : CentreStatus, and a list of spider…
- spider_rho_zero_sameFor any non-free spider leg end φ, spider_rho 0 φ φ = 0.
- spider_none_one_inward_one_outward_raw_optsThe raw option list of the state (none;{(1,inward),(1,outward),(r,φ)}) after one unfolding step, in the exact order the recursion…
- spider_update_centreThe function spider_update_centre updates centre status s given leg transition delta: if delta is inward, none maps to incoming, incoming…
- 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…
- CentreStatusThe status of the central vertex in a spider state: none (no marked arcs incident), incoming (at least one incoming arc), outgoing (at…
- SpiderLegEndThe end condition of an attached leg in a spider state is either free (no arc on the leg), inward (pointing towards the centre), or…
- spider_rho_starThe function spider_rho_star takes h : ℕ and phi : SpiderLegEnd, returning h % 2 if phi = free, and h otherwise.
- spider_rhoThe function spider_rho takes h : ℕ and delta, phi : SpiderLegEnd, returning h if phi = free; if phi = inward, it returns h % 2 when delta…
- nat_mex_listThe minimum excluded value (mex) of a finite list of natural numbers is the least non-negative integer not in the list.
- Used by 1
- spider_blocked_none_one_inward_one_outwardFor the configuration κ₁ = (none;{(1,inward),(1,outward)}), the blocked family V^φ_κ₁(r) equals r for every r ≥ 1 and both φ.
The proof, explained
The theorem establishes that the Sprague-Grundy nim-value γ for a 3-legged spider with center status none and legs (1, inward), (1, outward), (r, φ) (where r ≥ 2 and φ ≠ free) is the mex of the raw option list spider_none_one_inward_one_outward_raw_opts r φ. The proof unfolds γ via its recursive definition and decomposes the flatMap of available moves across the three legs. Helper lemmas evaluate the moves on the two length-1 legs and partition the moves on the length-r leg into the initial length-1 cut, intermediate cuts of lengths 2 through r - 1, and the terminal cut of length r, directly assembling the full option list.
For any n, List.range (n + 2) decomposes as 0 followed by the shifted range of n and the terminal element n + 1
By induction on n. The base case n = 0 is a direct computation by reflexivity (rfl). In the inductive step n = k + 1, we rewrite k + 1 + 2 as (k + 2) + 1, expand List.range at successor values using List.range_succ, apply the induction hypothesis, and distribute List.map over append before normalizing list concatenation with simp.
uses
List.range_succ,List.map_append,List.cons_append,List.append_associnduction n with | zero => rfl | succ k ih => rw [show k + 1 + 2 = (k + 2) + 1 by ring, List.range_succ, ih] rw [show k + 1 + 1 = k + 2 by ring] rw [List.range_succ (n := k), List.map_append] simp [List.cons_append, List.append_assoc]
For r ≥ 2, List.range r splits into 0, the shifted range of r - 2, and r - 1
Rewriting r as (r - 2) + 2 via linear integer arithmetic (omega) allows us to apply the previous lemma spider_blocked_none_one_inward_one_outward_raw_opts_eq_range_succ_two with n = r - 2, and another arithmetic rewrite simplifies (r - 2) + 1 to r - 1.
uses
spider_blocked_none_one_inward_one_outward_raw_opts_eq_range_succ_twoconv => lhs; rw [show r = (r - 2) + 2 by omega] rw [spider_blocked_none_one_inward_one_outward_raw_opts_eq_range_succ_two] rw [show r - 2 + 1 = r - 1 by omega]
Playing on leg 0 of length 1 (inward) yields a single option updating the center status to incoming automation
Since the cut length is 1, the leg is exhausted and updates the center from none to incoming. Because the leg orientation is inward, any choice of move direction other than inward is discarded, leaving exactly one option. Lean's simplifier verifies this directly from definitions.
simp [spider_rho, spider_update_centre]Playing on leg 1 of length 1 (outward) yields a single option updating the center status to outgoing automation
Symmetric to leg 0: cutting the entire leg of length 1 forces the orientation to match outward and transitions the center status to outgoing, which simp checks definitionally.
simp [spider_rho, spider_update_centre]Cutting length 1 on leg 2 yields two options that update the center to incoming and outgoing
Since r ≥ 2, the cut length 0 + 1 = 1 does not equal r, so the equality check (0 + 1 == r) is false by beq_false_of_ne. Because the cut length 1 is less than 2, it does not leave a remainder leg but updates the center status according to the move direction delta ∈ {inward, outward}.
uses
beq_false_of_nehave : (0 + 1 == r) = false := beq_false_of_ne (by omega) simp [this, spider_update_centre]
Intermediate cuts of length a + 2 on leg 2 leave an interior leg of length a + 1
For a ∈ List.range (r - 2), we have a < r - 2, so the cut length satisfies 2 ≤ a + 2 < r. It does not cut the whole leg ((a + 2 == r) is false), leaving a shortened leg of length a + 1 and keeping the center status as none. The three short legs are rotated into canonical order using spider_gamma_rotate_three_short_legs.
uses
List.mem_range.mp,beq_false_of_ne,spider_gamma_rotate_three_short_legshave hlt : a < r - 2 := List.mem_range.mp ha have hne : (a + 1 + 1 == r) = false := beq_false_of_ne (by omega) have hge : 2 ≤ a + 1 + 1 := by omega have harith1 : r - (a + 1 + 1) = r - 2 - a := by omega have harith2 : a + 1 + 1 - 1 = a + 1 := by omega simp [hne, hge, harith1, harith2, spider_gamma_rotate_three_short_legs]
A cut of the full length r on leg 2 leaves a leg of length r - 1 with orientation φ
Here the cut length equals r, so the check (r - 1 + 1 == r) is true by beq_iff_eq. Since φ ≠ free, the condition delta ≠ φ filters out the opposite direction, leaving only delta = φ. Case analysis on φ dismisses the free case by contradiction and simplifies the remaining cases using leg rotation.
uses
beq_iff_eq,spider_gamma_rotate_three_short_legshave heq : (r - 1 + 1 == r) = true := by rw [beq_iff_eq]; omega have hge : 2 ≤ r - 1 + 1 := by omega have hsub1 : r - (r - 1 + 1) = 0 := by omega have hsub2 : r - 1 + 1 - 1 = r - 1 := by omega cases φ with | free => contradiction | inward => simp [heq, hge, hsub1, hsub2, spider_gamma_rotate_three_short_legs] | outward => simp [heq, hge, hsub1, hsub2, spider_gamma_rotate_three_short_legs]
Unfolding the game value at fuel r + 3 reduces the theorem to equality of the option lists and evaluates moves on legs 0 and 1
We unfold spider_gamma at fuel r + 3 via spider_gamma.eq_def. Applying congr_arg nat_mex_list reduces the equality of nim-values to equality of the underlying option lists. Expanding List.flatMap across the three legs [(1, inward), (1, outward), (r, φ)] and evaluating List.range 1 = [0] expands the moves on the first two legs.
uses
spider_gamma.eq_def,congr_arg,List.flatMap_cons,List.flatMap_nil,List.append_nilrw [spider_gamma.eq_def] dsimp only apply congr_arg nat_mex_list change List.flatMap _ [((1, SpiderLegEnd.inward), 0), ((1, SpiderLegEnd.outward), 1), ((r, φ), 2)] = _ rw [List.flatMap_cons, List.flatMap_cons, List.flatMap_cons, List.flatMap_nil] dsimp only have hr1 : List.range 1 = [0] := rfl rw [hr1] simp only [List.flatMap_cons, List.flatMap_nil, List.append_nil]
The options from leg 2 are partitioned into the initial move, intermediate moves, and the final move
Using spider_blocked_none_one_inward_one_outward_raw_opts_eq_range_split, we split List.range r into 0, the shifted range of r - 2, and r - 1. Distributing List.flatMap over list append and map breaks the options on leg 2 into three separate concatenated lists.
uses
spider_blocked_none_one_inward_one_outward_raw_opts_eq_range_split,List.flatMap_cons,List.flatMap_append,List.flatMap_map,List.flatMap_nil,List.append_nilrw [spider_blocked_none_one_inward_one_outward_raw_opts_eq_range_split r hr] rw [List.flatMap_cons, List.flatMap_append, List.flatMap_map, List.flatMap_cons, List.flatMap_nil, List.append_nil] unfold spider_none_one_inward_one_outward_raw_opts
Each option sublist matches spider_none_one_inward_one_outward_raw_opts, completing the proof
We rewrite each sublist with its corresponding helper lemma: leg 0 with spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg0, leg 1 with spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg1, and leg 2's three parts with spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg2_zero, List.flatMap_congr with spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg2_mid, and spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg2_last. List concatenation simplification verifies that the resulting list matches spider_none_one_inward_one_outward_raw_opts.
uses
spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg0,spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg1,spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg2_zero,List.flatMap_congr,spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg2_mid,spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg2_last,List.cons_appendrw [spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg0] rw [spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg1] rw [spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg2_zero r hr] rw [List.flatMap_congr (spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg2_mid r hr φ)] rw [spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg2_last r hr φ hφ] simp [List.cons_append]
List.range_succ- List.range (n + 1) equals List.range n followed by [n]
List.map_append- List.map f (l₁ ++ l₂) = List.map f l₁ ++ List.map f l₂
List.cons_append- (a :: as) ++ bs = a :: (as ++ bs)
List.append_assoc- (as ++ bs) ++ cs = as ++ (bs ++ cs)
spider_blocked_none_one_inward_one_outward_raw_opts_eq_range_succ_two- For all n, List.range (n + 2) = 0 :: (List.map (· + 1) (List.range n) ++ [n + 1])
spider_blocked_none_one_inward_one_outward_raw_opts_eq_range_split- For r ≥ 2, List.range r = 0 :: (List.map (· + 1) (List.range (r - 2)) ++ [r - 1])
beq_false_of_ne- If a ≠ b, then the boolean equality (a == b) is false
List.mem_range.mp- If a ∈ List.range b, then a < b
spider_gamma_rotate_three_short_legs- Permuting/rotating the legs of a 3-legged spider preserves the game value computed by spider_gamma
beq_iff_eq- The boolean equality (a == b) is true if and only if a = b
spider_gamma.eq_def- Definitional unfolding equation for spider_gamma
congr_arg- If a = b, then f a = f b
List.flatMap_cons- List.flatMap f (x :: xs) = f x ++ List.flatMap f xs
List.flatMap_nil- List.flatMap f [] = []
List.append_nil- as ++ [] = as
List.flatMap_append- List.flatMap f (xs ++ ys) = List.flatMap f xs ++ List.flatMap f ys
List.flatMap_map- List.flatMap g (List.map f l) = List.flatMap (fun a => g (f a)) l
List.flatMap_congr- If f and g agree on all elements of l, then List.flatMap f l = List.flatMap g l
spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg0- Simplifies the options from playing on the first leg (1, inward) to a single incoming transition
spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg1- Simplifies the options from playing on the second leg (1, outward) to a single outgoing transition
spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg2_zero- Simplifies the cut-length-1 options on leg 2 to two transitions setting the center to incoming and outgoing
spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg2_mid- Simplifies the intermediate cut options (lengths 2 to r - 1) on leg 2 to two options leaving a shortened leg
spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg2_last- Simplifies the full-length cut option on leg 2 to a single option preserving orientation φ
- The theorem directly assembles seven preceding helper lemmas that break the range of cut lengths into parts and evaluate the resulting options on each of the three legs.
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.
lemma spider_blocked_none_one_inward_one_outward_raw_opts_eq_range_succ_two (n : ℕ) : List.range (n + 2) = 0 :: (List.map (· + 1) (List.range n) ++ [n + 1]) := by induction n with | zero => rfl | succ k ih => rw [show k + 1 + 2 = (k + 2) + 1 by ring, List.range_succ, ih] rw [show k + 1 + 1 = k + 2 by ring] rw [List.range_succ (n := k), List.map_append] simp [List.cons_append, List.append_assoc]lemma spider_blocked_none_one_inward_one_outward_raw_opts_eq_range_split (r : ℕ) (hr : 2 ≤ r) : List.range r = 0 :: (List.map (· + 1) (List.range (r - 2)) ++ [r - 1]) := by conv => lhs; rw [show r = (r - 2) + 2 by omega] rw [spider_blocked_none_one_inward_one_outward_raw_opts_eq_range_succ_two] rw [show r - 2 + 1 = r - 1 by omega]lemma spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg0 (r : ℕ) (φ : SpiderLegEnd) : (List.filterMap (fun delta => if (0 + 1 == 1) = true ∧ SpiderLegEnd.inward ≠ SpiderLegEnd.free ∧ delta ≠ SpiderLegEnd.inward then none else if 0 + 1 ≥ 2 then some (spider_rho (1 - (0 + 1)) delta SpiderLegEnd.inward ^^^ spider_gamma (r + 2) CentreStatus.none ((0 + 1 - 1, delta) :: [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (r, φ)].eraseIdx 0)) else some (spider_rho (1 - (0 + 1)) delta SpiderLegEnd.inward ^^^ spider_gamma (r + 2) (spider_update_centre CentreStatus.none delta) ([(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (r, φ)].eraseIdx 0))) [SpiderLegEnd.inward, SpiderLegEnd.outward]) = [spider_gamma (r + 2) CentreStatus.incoming [(1, SpiderLegEnd.outward), (r, φ)]] := by simp [spider_rho, spider_update_centre]lemma spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg1 (r : ℕ) (φ : SpiderLegEnd) : (List.filterMap (fun delta => if (0 + 1 == 1) = true ∧ SpiderLegEnd.outward ≠ SpiderLegEnd.free ∧ delta ≠ SpiderLegEnd.outward then none else if 0 + 1 ≥ 2 then some (spider_rho (1 - (0 + 1)) delta SpiderLegEnd.outward ^^^ spider_gamma (r + 2) CentreStatus.none ((0 + 1 - 1, delta) :: [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (r, φ)].eraseIdx 1)) else some (spider_rho (1 - (0 + 1)) delta SpiderLegEnd.outward ^^^ spider_gamma (r + 2) (spider_update_centre CentreStatus.none delta) ([(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (r, φ)].eraseIdx 1))) [SpiderLegEnd.inward, SpiderLegEnd.outward]) = [spider_gamma (r + 2) CentreStatus.outgoing [(1, SpiderLegEnd.inward), (r, φ)]] := by simp [spider_rho, spider_update_centre]lemma spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg2_zero (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) : (List.filterMap (fun delta => if (0 + 1 == r) = true ∧ φ ≠ SpiderLegEnd.free ∧ delta ≠ φ then none else if 0 + 1 ≥ 2 then some (spider_rho (r - (0 + 1)) delta φ ^^^ spider_gamma (r + 2) CentreStatus.none ((0 + 1 - 1, delta) :: [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (r, φ)].eraseIdx 2)) else some (spider_rho (r - (0 + 1)) delta φ ^^^ spider_gamma (r + 2) (spider_update_centre CentreStatus.none delta) ([(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (r, φ)].eraseIdx 2))) [SpiderLegEnd.inward, SpiderLegEnd.outward]) = [spider_rho (r - 1) SpiderLegEnd.inward φ ^^^ spider_gamma (r + 2) CentreStatus.incoming [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward)], spider_rho (r - 1) SpiderLegEnd.outward φ ^^^ spider_gamma (r + 2) CentreStatus.outgoing [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward)]] := by have : (0 + 1 == r) = false := beq_false_of_ne (by omega) simp [this, spider_update_centre]lemma spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg2_mid (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) (a : ℕ) (ha : a ∈ List.range (r - 2)) : (List.filterMap (fun delta => if (a + 1 + 1 == r) = true ∧ φ ≠ SpiderLegEnd.free ∧ delta ≠ φ then none else if a + 1 + 1 ≥ 2 then some (spider_rho (r - (a + 1 + 1)) delta φ ^^^ spider_gamma (r + 2) CentreStatus.none ((a + 1 + 1 - 1, delta) :: [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (r, φ)].eraseIdx 2)) else some (spider_rho (r - (a + 1 + 1)) delta φ ^^^ spider_gamma (r + 2) (spider_update_centre CentreStatus.none delta) ([(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (r, φ)].eraseIdx 2))) [SpiderLegEnd.inward, SpiderLegEnd.outward]) = [spider_rho (r - 2 - a) SpiderLegEnd.inward φ ^^^ spider_gamma (r + 2) CentreStatus.none [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (a + 1, SpiderLegEnd.inward)], spider_rho (r - 2 - a) SpiderLegEnd.outward φ ^^^ spider_gamma (r + 2) CentreStatus.none [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (a + 1, SpiderLegEnd.outward)]] := by have hlt : a < r - 2 := List.mem_range.mp ha have hne : (a + 1 + 1 == r) = false := beq_false_of_ne (by omega) have hge : 2 ≤ a + 1 + 1 := by omega have harith1 : r - (a + 1 + 1) = r - 2 - a := by omega have harith2 : a + 1 + 1 - 1 = a + 1 := by omega simp [hne, hge, harith1, harith2, spider_gamma_rotate_three_short_legs]lemma spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg2_last (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) : (List.filterMap (fun delta => if (r - 1 + 1 == r) = true ∧ φ ≠ SpiderLegEnd.free ∧ delta ≠ φ then none else if r - 1 + 1 ≥ 2 then some (spider_rho (r - (r - 1 + 1)) delta φ ^^^ spider_gamma (r + 2) CentreStatus.none ((r - 1 + 1 - 1, delta) :: [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (r, φ)].eraseIdx 2)) else some (spider_rho (r - (r - 1 + 1)) delta φ ^^^ spider_gamma (r + 2) (spider_update_centre CentreStatus.none delta) ([(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (r, φ)].eraseIdx 2))) [SpiderLegEnd.inward, SpiderLegEnd.outward]) = [spider_rho 0 φ φ ^^^ spider_gamma (r + 2) CentreStatus.none [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (r - 1, φ)]] := by have heq : (r - 1 + 1 == r) = true := by rw [beq_iff_eq]; omega have hge : 2 ≤ r - 1 + 1 := by omega have hsub1 : r - (r - 1 + 1) = 0 := by omega have hsub2 : r - 1 + 1 - 1 = r - 1 := by omega cases φ with | free => contradiction | inward => simp [heq, hge, hsub1, hsub2, spider_gamma_rotate_three_short_legs] | outward => simp [heq, hge, hsub1, hsub2, spider_gamma_rotate_three_short_legs]/-- One definitional unfolding step of the κ₁ root state, giving the raw option list. -/theorem spider_blocked_none_one_inward_one_outward_raw_opts_eq (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) : spider_gamma (r + 3) CentreStatus.none [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (r, φ)] = nat_mex_list (spider_none_one_inward_one_outward_raw_opts r φ) := by rw [spider_gamma.eq_def] dsimp only apply congr_arg nat_mex_list change List.flatMap _ [((1, SpiderLegEnd.inward), 0), ((1, SpiderLegEnd.outward), 1), ((r, φ), 2)] = _ rw [List.flatMap_cons, List.flatMap_cons, List.flatMap_cons, List.flatMap_nil] dsimp only have hr1 : List.range 1 = [0] := rfl rw [hr1] simp only [List.flatMap_cons, List.flatMap_nil, List.append_nil] rw [spider_blocked_none_one_inward_one_outward_raw_opts_eq_range_split r hr] rw [List.flatMap_cons, List.flatMap_append, List.flatMap_map, List.flatMap_cons, List.flatMap_nil, List.append_nil] unfold spider_none_one_inward_one_outward_raw_opts rw [spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg0] rw [spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg1] rw [spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg2_zero r hr] rw [List.flatMap_congr (spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg2_mid r hr φ)] rw [spider_blocked_none_one_inward_one_outward_raw_opts_eq_opt_leg2_last r hr φ hφ] simp [List.cons_append]