import MazeAI.Trit /-! # Vacuum.Net Foundations 9.2 — Part III en IV, machinaal bewezen (Lean 4, geen mathlib) Canoniek model: `docs/vacuum-net-canon.md` (Foundations ed. 9.2, sha256 89315591…). Elke stelling hieronder draagt het nummer uit Foundations 9.2. Waar de editie "computed" zegt en het domein eindig is, beslist Lean het hele domein (`decide`); waar het domein oneindig is, staat een algemeen bewijs. Niets hieronder is een aanname behalve de definities. -/ namespace Foundations open Trit /-! ## T1 — de trinity als register -/ /-- Het gebalanceerde residu van een geheel getal: het cijfer d ∈ {−1, 0, +1} met d ≡ s (mod 3). -/ def cijfer (s : Int) : Int := (s + 1) % 3 - 1 /-- De overdracht naar de volgende schaal: (s − d)/3. -/ def overdracht (s : Int) : Int := (s - cijfer s) / 3 theorem cijfer_bereik (s : Int) : -1 ≤ cijfer s ∧ cijfer s ≤ 1 := by unfold cijfer; omega theorem cijfer_congruent (s : Int) : (s - cijfer s) % 3 = 0 := by unfold cijfer; omega /-- T1, uniciteit van het laatste cijfer: er is precies één d ∈ {−1,0,1} met d ≡ s (mod 3). -/ theorem cijfer_uniek (s d : Int) (h1 : -1 ≤ d) (h2 : d ≤ 1) (h3 : (s - d) % 3 = 0) : d = cijfer s := by unfold cijfer; omega /-- T1 (i): een som van trits laat geen residu op haar eigen schaal precies als s ≡ 0 (mod 3). -/ theorem T1_i (s : Int) : cijfer s = 0 ↔ s % 3 = 0 := by unfold cijfer; omega /-- T1 (ii): wat niet blijft, gaat heel over als overdracht: s = d + 3·overdracht. -/ theorem T1_ii (s : Int) : s = cijfer s + 3 * overdracht s := by unfold overdracht cijfer; omega /-- T1 (iii): in ℤ₁ en ℤ₂ is elk element gelijk aan zijn tegengestelde; in ℤ₃ niet. -/ theorem T1_iii : (∀ x : Fin 1, x = -x) ∧ (∀ x : Fin 2, x = -x) ∧ (∃ x : Fin 3, x ≠ -x) := by decide /-- T1 (iii), de groep: het residu respecteert optellen — cijfer(s + t) = cijfer(cijfer s + cijfer t) —, dus {−1, 0, +1} met "optellen en het residu nemen" is ℤ₃. -/ theorem cijfer_hom (s t : Int) : cijfer (s + t) = cijfer (cijfer s + cijfer t) := by unfold cijfer; omega theorem cijfer_cijfer (s : Int) : cijfer (cijfer s) = cijfer s := by unfold cijfer; omega /-! ## Vensters -/ def alle : List Trit := [neg, nul, pos] /-- Een venster: drie opeenvolgende trits. -/ abbrev Venster := Trit × Trit × Trit def vensters : List Venster := alle.flatMap fun a => alle.flatMap fun b => alle.map fun c => (a, b, c) def som (w : Venster) : Int := w.1.toInt + w.2.1.toInt + w.2.2.toInt /-- Een venster sluit als zijn som ≡ 0 (mod 3): zijn cijfer is 0. -/ def sluit (w : Venster) : Bool := som w % 3 == 0 theorem vensters_27 : vensters.length = 27 := by decide /-- T2 (venster van drie): een run van k gelijke trits x ≠ 0 laat voor het eerst geen residu bij k = 3. -/ theorem T2 (x : Trit) (hx : x ≠ nul) : (1 * x.toInt) % 3 ≠ 0 ∧ (2 * x.toInt) % 3 ≠ 0 ∧ (3 * x.toInt) % 3 = 0 := by cases x <;> simp_all [Trit.toInt] /-- T3: precies 9 van de 27 vensters sluiten. -/ theorem T3_negen : (vensters.filter sluit).length = 9 := by decide /-- Optellen van trits in ℤ₃ (gebalanceerd residu). -/ def plus (a b : Trit) : Trit := match cijfer (a.toInt + b.toInt) with | -1 => neg | 0 => nul | _ => pos /-- T1 (iii): {T, 0, 1} met `plus` is een groep: nul is neutraal, spiegelen is het tegengestelde, optellen is associatief en commutatief — over alle 27 drietallen beslist. Dit is ℤ₃. -/ theorem plus_groep : (alle.all fun a => plus a nul == a) = true ∧ (alle.all fun a => plus a a.spiegel == nul) = true ∧ (alle.all fun a => alle.all fun b => plus a b == plus b a) = true ∧ (alle.all fun a => alle.all fun b => alle.all fun c => plus (plus a b) c == plus a (plus b c)) = true ∧ (alle.any fun a => a != a.spiegel) = true := by decide def plusV (v w : Venster) : Venster := (plus v.1 w.1, plus v.2.1 w.2.1, plus v.2.2 w.2.2) /-- T3: de sluitende vensters vormen een ondergroep van ℤ₃³: dicht onder optellen en spiegelen, met nul erin. -/ theorem T3_ondergroep : sluit (nul, nul, nul) = true ∧ (vensters.all fun v => vensters.all fun w => !(sluit v && sluit w) || sluit (plusV v w)) = true ∧ (vensters.all fun v => !sluit v || sluit (v.1.spiegel, v.2.1.spiegel, v.2.2.spiegel)) = true := by decide def gelijk3 (w : Venster) : Bool := w.1 == w.2.1 && w.2.1 == w.2.2 def verschillend3 (w : Venster) : Bool := w.1 != w.2.1 && w.2.1 != w.2.2 && w.1 != w.2.2 /-- T4 (twee soorten sluiting): een venster sluit precies als zijn trits alle gelijk of alle verschillend zijn. -/ theorem T4 : (vensters.all fun w => sluit w == (gelijk3 w || verschillend3 w)) = true := by decide /-- T4, de tellingen: 3 homogeen, 6 heterogeen; de 18 open vensters hebben precies twee gelijke trits. -/ theorem T4_tellingen : (vensters.filter gelijk3).length = 3 ∧ (vensters.filter verschillend3).length = 6 ∧ (vensters.filter fun w => !sluit w).length = 18 ∧ (vensters.all fun w => sluit w || (!gelijk3 w && !verschillend3 w)) = true := by decide def nietNul (w : Venster) : Nat := [w.1, w.2.1, w.2.2].countP (· != nul) /-- T5 (de tritkubus): cellen met k niet-nul coördinaten: 1, 6, 12, 8; de sluitende: 1 + 0 + 6 + 2. -/ theorem T5 : ([0, 1, 2, 3].map fun k => (vensters.filter fun w => nietNul w == k).length) = [1, 6, 12, 8] ∧ ([0, 1, 2, 3].map fun k => (vensters.filter fun w => sluit w && nietNul w == k).length) = [1, 0, 6, 2] := by decide /-- De niet-nul coördinaten van een cel. -/ def nz (w : Venster) : List Trit := [w.1, w.2.1, w.2.2].filter (· != nul) /-- Twee niet-nul coördinaten van tegengesteld teken. -/ def tegengesteld2 (w : Venster) : Bool := (nz w).length == 2 && ((nz w).getD 0 nul).spiegel == (nz w).getD 1 nul /-- T5, welke cellen sluiten: met één niet-nul coördinaat geen; met twee precies die met tegengesteld teken; met drie precies (1, 1, 1) en (T, T, T). -/ theorem T5_welke : (vensters.all fun w => nietNul w != 1 || !sluit w) = true ∧ (vensters.all fun w => nietNul w != 2 || (sluit w == tegengesteld2 w)) = true ∧ (vensters.all fun w => nietNul w != 3 || (sluit w == (w == (pos, pos, pos) || w == (neg, neg, neg)))) = true := by decide /-! ## T7 — elementaire sluitingen (algemeen bewijs, elke lengte) -/ def somL (w : List Trit) : Int := (w.map Trit.toInt).foldr (· + ·) 0 theorem somL_append (a b : List Trit) : somL (a ++ b) = somL a + somL b := by induction a with | nil => simp [somL] | cons x r ih => simp only [somL, List.map_cons, List.foldr_cons, List.cons_append] at *; rw [ih]; omega /-- De drie elementaire sluitingen: een stand (0), een ontmoeting (x, −x), een ring (x, x, x). -/ def elementair : List Trit → Prop | [nul] => True | [a, b] => a ≠ nul ∧ b = a.spiegel | [a, b, c] => a ≠ nul ∧ b = a ∧ c = a | _ => False /-- Een woord reduceert tot niets door telkens een elementaire sluiting weg te nemen. -/ inductive Reduceert : List Trit → Prop | leeg : Reduceert [] | stap (l r p : List Trit) : elementair p → Reduceert (l ++ r) → Reduceert (l ++ p ++ r) theorem elementair_som (p : List Trit) (h : elementair p) : somL p % 3 = 0 := by match p, h with | [nul], _ => simp [somL, Trit.toInt] | [a, b], h => simp only [elementair] at h obtain ⟨_, hb⟩ := h; subst b; cases a <;> simp [somL, Trit.toInt, Trit.spiegel] | [a, b, c], h => simp only [elementair] at h obtain ⟨_, hb, hc⟩ := h; subst b; subst c; cases a <;> simp [somL, Trit.toInt] /-- T7, eerste helft: alleen gesloten woorden reduceren (elke wegname bewaart de som mod 3). -/ theorem T7_gezond (w : List Trit) (h : Reduceert w) : somL w % 3 = 0 := by induction h with | leeg => simp [somL] | stap l r p hp _ ih => have := elementair_som p hp rw [somL_append, somL_append] at * omega /-- Twee niet-nul trits zijn gelijk of elkaars spiegel. -/ theorem nietnul_twee (a b : Trit) (ha : a ≠ nul) (hb : b ≠ nul) : b = a ∨ b = a.spiegel := by cases a <;> cases b <;> simp_all [Trit.spiegel] theorem somL_cons (a : Trit) (r : List Trit) : somL (a :: r) = a.toInt + somL r := by simp [somL] /-- Hulp voor T7, langs de route van de editie: haal een nul weg; anders vooraan een ontmoeting x, −x; anders vooraan een ring x, x, x. Sterke inductie op de lengte. -/ theorem T7_volledig : ∀ (n : Nat) (w : List Trit), w.length = n → somL w % 3 = 0 → Reduceert w := by intro n induction n using Nat.strongRecOn with | _ n ih => intro w hl hs by_cases hz : nul ∈ w · -- een stand: haal de nul weg obtain ⟨l, r, hw⟩ := List.append_of_mem hz subst hw have e : somL (l ++ nul :: r) = somL (l ++ r) := by rw [somL_append, somL_append, somL_cons]; simp [Trit.toInt] have hs' : somL (l ++ r) % 3 = 0 := by rw [← e]; exact hs have hr := ih (l ++ r).length (by simp at hl ⊢; omega) (l ++ r) rfl hs' have h2 := Reduceert.stap l r [nul] trivial hr simpa using h2 · match w, hl, hz with | [], _, _ => exact Reduceert.leeg | [a], _, hz => exfalso have ha : a ≠ nul := by intro h; apply hz; simp [h] cases a <;> simp_all [somL, Trit.toInt] | a :: b :: r, hl, hz => have ha : a ≠ nul := by intro h; apply hz; simp [h] have hb : b ≠ nul := by intro h; apply hz; simp [h] rcases nietnul_twee a b ha hb with hab | hab · -- a, a, … subst b match r, hl, hz with | [], _, _ => exfalso; cases a <;> simp_all [somL, Trit.toInt] | c :: r', hl, hz => have hc : c ≠ nul := by intro h; apply hz; simp [h] rcases nietnul_twee a c ha hc with hac | hac · -- een ring vooraan subst c have hs' : somL r' % 3 = 0 := by rw [somL_cons, somL_cons, somL_cons] at hs; omega have hr := ih r'.length (by simp at hl ⊢; omega) r' rfl hs' have h2 := Reduceert.stap [] r' [a, a, a] (by simp [elementair, ha]) (by simpa using hr) simpa using h2 · -- een ontmoeting op plaats 2: a, (a, −a), … subst c have hs' : somL (a :: r') % 3 = 0 := by rw [somL_cons, somL_cons, somL_cons] at hs; rw [somL_cons] cases a <;> simp_all [Trit.toInt, Trit.spiegel] <;> omega have hr := ih (a :: r').length (by simp at hl ⊢; omega) (a :: r') rfl hs' have h2 := Reduceert.stap [a] r' [a, a.spiegel] (by simp [elementair, ha]) (by simpa using hr) simpa using h2 · -- een ontmoeting vooraan subst b have hs' : somL r % 3 = 0 := by rw [somL_cons, somL_cons] at hs cases a <;> simp_all [Trit.toInt, Trit.spiegel] <;> omega have hr := ih r.length (by simp at hl ⊢; omega) r rfl hs' have h2 := Reduceert.stap [] r [a, a.spiegel] (by simp [elementair, ha]) (by simpa using hr) simpa using h2 /-- T7: een trit-woord reduceert tot niets precies als het gesloten is. -/ theorem T7 (w : List Trit) : Reduceert w ↔ somL w % 3 = 0 := ⟨T7_gezond w, T7_volledig w.length w rfl⟩ /-- T7.1 (wat een sluiting meedraagt): stand en ontmoeting met overdracht 0, een ring met overdracht ±1. -/ theorem T7_1 : overdracht 0 = 0 ∧ cijfer 0 = 0 ∧ overdracht 3 = 1 ∧ cijfer 3 = 0 ∧ overdracht (-3) = -1 ∧ cijfer (-3) = 0 ∧ cijfer 2 = -1 ∧ overdracht 2 = 1 ∧ cijfer (-2) = 1 ∧ overdracht (-2) = -1 := by decide /-- T7.1: een ring x, x, x (x ≠ 0) heeft som ±3, cijfer 0 en overdracht ±1 = x. -/ theorem T7_1_ring (x : Trit) (hx : x ≠ nul) : cijfer (3 * x.toInt) = 0 ∧ overdracht (3 * x.toInt) = x.toInt := by cases x <;> simp_all [Trit.toInt] <;> decide /-! ## T8–T11 — woorden en ringen die overal sluiten, de herschrijving, de naad -/ /-- T8, de voortplanting: s(k+1) ≡ s(k) + t(k+3) − t(k) (mod 3), als identiteit van gehele getallen. -/ theorem T8_voortplanting (a b c d : Int) : (b + c + d) = (a + b + c) + d - a := by omega /-- Twee trits met dezelfde rest mod 3 zijn gelijk. -/ theorem trit_mod3 (x y : Trit) (h : (x.toInt - y.toInt) % 3 = 0) : x = y := by cases x <;> cases y <;> simp_all [Trit.toInt] /-- T8: een woord (als functie op de posities 0..n−1) sluit in elk venster precies als het eerste venster sluit en het woord periode 3 heeft. -/ theorem T8 (n : Nat) (t : Nat → Trit) : (∀ k, k + 2 < n → ((t k).toInt + (t (k+1)).toInt + (t (k+2)).toInt) % 3 = 0) ↔ ((2 < n → ((t 0).toInt + (t 1).toInt + (t 2).toInt) % 3 = 0) ∧ ∀ k, k + 3 < n → t (k+3) = t k) := by constructor · intro h refine ⟨fun hn => h 0 hn, fun k hk => ?_⟩ have h1 := h k (by omega) have h2 := h (k+1) (by omega) simp only [show k + 1 + 1 = k + 2 from by omega, show k + 1 + 2 = k + 3 from by omega] at h2 apply trit_mod3 omega · intro ⟨h0, hp⟩ k induction k with | zero => exact h0 | succ k ih => intro hk have h1 := ih (by omega) have e := hp k (by omega) simp only [show k + 1 + 1 = k + 2 from by omega, show k + 1 + 2 = k + 3 from by omega, e] omega /-- T9 (een ring die overal sluit): een ring van n trits (periode n) die in elk venster sluit, heeft periode 3. -/ theorem T9 (n : Nat) (t : Nat → Trit) (hring : ∀ i, t (i + n) = t i) (h : ∀ k, ((t k).toInt + (t (k+1)).toInt + (t (k+2)).toInt) % 3 = 0) : ∀ i, t (i + 3) = t i := by intro i have h1 := h i have h2 := h (i+1) simp only [show i + 1 + 1 = i + 2 from by omega, show i + 1 + 2 = i + 3 from by omega] at h2 apply trit_mod3 omega /-- Alle woorden van lengte n. -/ def woorden : Nat → List (List Trit) | 0 => [[]] | n + 1 => (woorden n).flatMap fun w => alle.map fun a => a :: w /-- Sluit een woord, cyclisch gelezen, in elk venster? -/ def ringSluit (w : List Trit) : Bool := (List.range w.length).all fun i => (((w.getD i nul).toInt + (w.getD ((i+1) % w.length) nul).toInt + (w.getD ((i+2) % w.length) nul).toInt) % 3 == 0) /-- T9, de tellingen met gelabelde posities: 9 ringen als 3 | n, anders 3 (n = 3 … 6, het hele domein). -/ theorem T9_tellingen : ([3, 4, 5, 6].map fun n => ((woorden n).filter ringSluit).length) = [9, 3, 3, 9] := by decide /-- T10 (de herschrijving van het register): R(t)ᵢ = −(tᵢ₋₁ + tᵢ₊₁); een trit is vast onder R precies als zijn venster sluit. Pointwise, over alle 27 combinaties. -/ theorem T10 : (vensters.all fun w => (cijfer (-(w.1.toInt + w.2.2.toInt)) == w.2.1.toInt) == sluit w) = true := by decide /-- T11 (de naadregel): een naad tussen gesloten vensters A en B. De vensters over de naad zijn (A₂, A₃, B₁) en (A₃, B₁, B₂). -/ def naadOpen (A B : Venster) : Nat := (if sluit (A.2.1, A.2.2, B.1) then 0 else 1) + (if sluit (A.2.2, B.1, B.2.1) then 0 else 1) def gesloten : List Venster := vensters.filter sluit /-- T11: over alle 81 geordende paren gesloten vensters: 9 gesloten naden, 36 met één open venster, 36 met twee; en een naad is gesloten precies als B = A. -/ theorem T11 : (gesloten.flatMap fun A => gesloten.map fun B => naadOpen A B).count 0 = 9 ∧ (gesloten.flatMap fun A => gesloten.map fun B => naadOpen A B).count 1 = 36 ∧ (gesloten.flatMap fun A => gesloten.map fun B => naadOpen A B).count 2 = 36 ∧ (gesloten.all fun A => gesloten.all fun B => (naadOpen A B == 0) == (A == B)) = true := by decide /-- T11, de formule: het aantal open vensters op de naad is [A₁ ≠ B₁] + [A₃ ≠ B₃]; en per vaste A geven de 9 vensters B: 1 zonder, 4 met één, 4 met twee open vensters. -/ theorem T11_formule : (gesloten.all fun A => gesloten.all fun B => naadOpen A B == (if A.1 == B.1 then 0 else 1) + (if A.2.2 == B.2.2 then 0 else 1)) = true ∧ (gesloten.all fun A => ([0, 1, 2].map fun k => (gesloten.filter fun B => naadOpen A B == k).length) == [1, 4, 4]) = true := by decide end Foundations