import MazeAI.Trit /-! # Vacuum.Net Foundations 9.2 — Part V (adressen) en Part VI (ladders), machinaal bewezen T12 bouwt voort op de MAZE.AI-kern (`MazeAI/Trit.lean`): bereik (`waarde_bereik`), uniciteit bij gelijke diepte (`waarde_inj`) en terugkeer (`waarde_ofInt`). Hier komt de volle stelling van de editie bij: elk geheel getal ≠ 0 heeft precies één eindig woord met niet-nul leidende trit, van welke lengte ook. -/ namespace Foundations open Trit Adres /-- Een genormaliseerd woord: leeg (voor 0) of met niet-nul leidende trit. -/ def genormaliseerd : Adres → Prop | [] => True | t :: _ => t ≠ nul theorem bereik_nonneg (k : Nat) : 0 ≤ bereik k := by have := two_mul_bereik k; have := three_pow_pos k; omega theorem bereik_succ (k : Nat) : bereik (k + 1) = 3 * bereik k + 1 := by have h1 := two_mul_bereik k; have h2 := two_mul_bereik (k + 1) rw [Int.pow_succ] at h2; omega theorem bereik_mono (j k : Nat) (h : j ≤ k) : bereik j ≤ bereik k := by induction k with | zero => have : j = 0 := by omega subst this; omega | succ k ih => by_cases hj : j ≤ k · have := ih hj; have := bereik_succ k; have := bereik_nonneg k; omega · have : j = k + 1 := by omega subst this; omega /-- Een woord met niet-nul leidende trit en lengte k+1 heeft |waarde| > bereik k. -/ theorem leidend_ondergrens (t : Trit) (r : Adres) (ht : t ≠ nul) : bereik r.length < waarde (t :: r) ∨ waarde (t :: r) < - bereik r.length := by have hb := waarde_bereik r have h2 := two_mul_bereik r.length have hp := three_pow_pos r.length simp only [waarde] generalize (3 : Int) ^ r.length = p at * cases t <;> simp_all [Trit.toInt] <;> omega /-- T12, uniciteit: twee genormaliseerde woorden met dezelfde waarde zijn hetzelfde woord, ook bij verschillende lengte (de lengte volgt uit de waarde). -/ theorem T12_uniek (a b : Adres) (ha : genormaliseerd a) (hb : genormaliseerd b) (h : waarde a = waarde b) : a = b := by have lengte : a.length = b.length := by match a, b, ha, hb with | [], [], _, _ => rfl | [], u :: s, _, hb => exfalso; have l := leidend_ondergrens u s hb; have := bereik_nonneg s.length rw [← h] at l; simp [waarde] at l; omega | t :: r, [], ha, _ => exfalso; have l := leidend_ondergrens t r ha; have := bereik_nonneg r.length rw [h] at l; simp [waarde] at l; omega | t :: r, u :: s, ha, hb => have l1 := leidend_ondergrens t r ha have l2 := leidend_ondergrens u s hb have b1 := waarde_bereik (t :: r) have b2 := waarde_bereik (u :: s) simp only [List.length_cons] at * rw [h] at l1 rcases Nat.lt_trichotomy r.length s.length with hl | hl | hl · have := bereik_mono (r.length + 1) s.length (by omega); omega · omega · have := bereik_mono (s.length + 1) r.length (by omega); rw [← h] at b2; omega exact waarde_inj a b lengte h /-- Leidende nullen weglaten verandert de waarde niet. -/ theorem waarde_nul_cons (r : Adres) : waarde (nul :: r) = waarde r := by simp [waarde, Trit.toInt] def normaliseer : Adres → Adres | [] => [] | nul :: r => normaliseer r | neg :: r => neg :: r | pos :: r => pos :: r theorem normaliseer_waarde (a : Adres) : waarde (normaliseer a) = waarde a := by induction a with | nil => rfl | cons t r ih => cases t <;> simp [normaliseer, waarde_nul_cons, ih] theorem normaliseer_ok (a : Adres) : genormaliseerd (normaliseer a) := by induction a with | nil => trivial | cons t r ih => cases t · simp [normaliseer, genormaliseerd] · simpa [normaliseer] using ih · simp [normaliseer, genormaliseerd] theorem bereik_groeit (k : Nat) : (k : Int) ≤ bereik k := by induction k with | zero => simp [bereik] | succ k ih => have := bereik_succ k; have := bereik_nonneg k; omega /-- T12, bestaan: elk geheel getal heeft een genormaliseerd woord. -/ theorem T12_bestaat (v : Int) : ∃ a : Adres, genormaliseerd a ∧ waarde a = v := by let k := v.natAbs have hk := bereik_groeit k refine ⟨normaliseer (ofInt k v), normaliseer_ok _, ?_⟩ rw [normaliseer_waarde] exact waarde_ofInt k v (by omega) /-- T12.1 (spiegellading): het adres van −Q is het adres van Q, tritsgewijs gespiegeld. -/ theorem T12_1 (a : Adres) : waarde (spiegel a) = - waarde a := waarde_spiegel a /-- T12.2 (zelfcentrerende diepte): de weggelaten staart van een woord met L cijfers is in absolute waarde strikt kleiner dan een halve eenheid van de laatst behouden plaats: 2·|staart| < 3ᴸ. Afkappen is dus afronden naar de dichtstbijzijnde waarde (behalve op het exacte midden, dat hier niet bereikt wordt: de ongelijkheid is strikt). -/ theorem T12_2 (staart : Adres) : 2 * waarde staart < 3 ^ staart.length ∧ -(3 ^ staart.length) < 2 * waarde staart := by have hb := waarde_bereik staart have h2 := two_mul_bereik staart.length omega /-- T12.3: een getal v ≠ 0 heeft precies d cijfers als bereik (d−1) < |v| ≤ bereik d (de lengte volgt uit de waarde). -/ theorem T12_3_lengte (t : Trit) (r : Adres) (ht : t ≠ nul) : bereik r.length < (waarde (t :: r)).natAbs ∧ (waarde (t :: r)).natAbs ≤ bereik (r.length + 1) := by have l := leidend_ondergrens t r ht have b := waarde_bereik (t :: r) simp only [List.length_cons] at b omega /-- T12.3 (capaciteit): de grootste waarde met n cijfers is (3ⁿ − 1)/2 = 1, 4, 13, 40, 121. -/ theorem T12_3_capaciteit : ([1, 2, 3, 4, 5].map bereik) = [1, 4, 13, 40, 121] := by decide /-- T12.3, de omkering: ligt v in (bereik (d−1), bereik d], dan heeft het genormaliseerde woord van v precies d cijfers. -/ theorem T12_3_omkering (v : Int) (d : Nat) (hd : 0 < d) (h1 : bereik (d - 1) < v.natAbs) (h2 : (v.natAbs : Int) ≤ bereik d) (a : Adres) (ha : genormaliseerd a) (hv : waarde a = v) : a.length = d := by match a, ha with | [], _ => simp [waarde] at hv; subst hv; have := bereik_nonneg (d - 1); simp at h1; omega | t :: r, ha => have l := T12_3_lengte t r ha rw [hv] at l simp only [List.length_cons] rcases Nat.lt_trichotomy (r.length + 1) d with hl | hl | hl · have := bereik_mono (r.length + 1) (d - 1) (by omega); omega · exact hl · have := bereik_mono d r.length (by omega); omega /-! ## Part VI — twee ladders -/ /-- T15 (ladder): blokken van grootte 2 (ontmoetingen) en 3 (ringen); na a ontmoetings- en b ringsamenvoegingen bevat één grove doorgang 2ᵃ · 3ᵇ fijnste doorgangen. -/ theorem T15 (blokken : List Nat) (h : ∀ x ∈ blokken, x = 2 ∨ x = 3) : blokken.foldr (· * ·) 1 = 2 ^ (blokken.count 2) * 3 ^ (blokken.count 3) := by induction blokken with | nil => simp | cons x r ih => have hr := ih (fun y hy => h y (List.mem_cons_of_mem x hy)) rcases h x (List.mem_cons_self) with rfl | rfl · simp [List.count_cons, hr, Nat.pow_succ]; ac_rfl · simp [List.count_cons, hr, Nat.pow_succ]; ac_rfl theorem twee_macht_even (n : Nat) (h : 0 < n) : 2 ^ n % 2 = 0 := by cases n with | zero => omega | succ k => rw [Nat.pow_succ]; omega theorem drie_macht_oneven (k : Nat) : 3 ^ k % 2 = 1 := by induction k with | zero => rfl | succ k ih => rw [Nat.pow_succ]; omega theorem drie_macht_gt_een (k : Nat) (h : 0 < k) : 1 < 3 ^ k := by cases k with | zero => omega | succ j => have : 0 < 3 ^ j := by induction j with | zero => decide | succ i ih => rw [Nat.pow_succ]; omega rw [Nat.pow_succ]; omega /-- T16 (geen exacte ontmoeting): 2ⁿ = 3ᵏ alleen voor n = k = 0. De ladders ×2 en ×3 sluiten nooit op elkaar. -/ theorem T16 (n k : Nat) (h : 2 ^ n = 3 ^ k) : n = 0 ∧ k = 0 := by by_cases hn : n = 0 · subst hn by_cases hk : k = 0 · exact ⟨rfl, hk⟩ · have := drie_macht_gt_een k (by omega); simp at h; omega · have e := twee_macht_even n (by omega) have o := drie_macht_oneven k rw [h] at e; omega /-- T16, gemengde tekens: 2ᵃ · 3ᵇ = 1 alleen voor a = b = 0 (dit dekt 2ⁿ = 3ᵏ met n en k van verschillend teken). -/ theorem T16_gemengd (a b : Nat) (h : 2 ^ a * 3 ^ b = 1) : a = 0 ∧ b = 0 := by have h1 := Nat.eq_one_of_mul_eq_one_right h have h2 := Nat.eq_one_of_mul_eq_one_left h constructor · cases a with | zero => rfl | succ k => have := twee_macht_even (k + 1) (by omega); omega · cases b with | zero => rfl | succ k => have := drie_macht_gt_een (k + 1) (by omega); omega /-- T16 voor alle gehele exponenten, in de vorm zonder breuken: voor gehele n, k geldt 2ⁿ = 3ᵏ (als rationale getallen) precies als 2^(n⁺) · 3^(k⁻) = 2^(n⁻) · 3^(k⁺), met x⁺ = max(x, 0) en x⁻ = max(−x, 0). Dat kan alleen voor n = k = 0. -/ theorem T16_geheel (n k : Int) (h : 2 ^ n.toNat * 3 ^ (-k).toNat = 2 ^ (-n).toNat * 3 ^ k.toNat) : n = 0 ∧ k = 0 := by rcases Int.le_total 0 n with hn | hn <;> rcases Int.le_total 0 k with hk | hk · -- n, k ≥ 0: 2ⁿ = 3ᵏ have e1 : (-k).toNat = 0 := by omega have e2 : (-n).toNat = 0 := by omega rw [e1, e2] at h; simp at h have := T16 n.toNat k.toNat h; omega · -- n ≥ 0, k ≤ 0: 2ⁿ · 3^|k| = 1 have e1 : (-n).toNat = 0 := by omega have e2 : k.toNat = 0 := by omega rw [e1, e2] at h; simp at h have := T16_gemengd n.toNat (-k).toNat h; omega · -- n ≤ 0, k ≥ 0: 1 = 2^|n| · 3ᵏ have e1 : n.toNat = 0 := by omega have e2 : (-k).toNat = 0 := by omega rw [e1, e2] at h; simp at h have := T16_gemengd (-n).toNat k.toNat h.symm; omega · -- n, k ≤ 0: 3^|k| = 2^|n| have e1 : n.toNat = 0 := by omega have e2 : k.toNat = 0 := by omega rw [e1, e2] at h; simp at h have := T16 (-n).toNat (-k).toNat h.symm; omega /-- T18 (de komma): op diepte 12 missen de ladders met 3¹²/2¹⁹ = 531441/524288; het verschil verdwijnt nooit (T16). -/ theorem T18_komma : 3 ^ 12 = 531441 ∧ 2 ^ 19 = 524288 ∧ (3 : Nat) ^ 12 ≠ 2 ^ 19 := by decide end Foundations