IndisputableMonolith.Foundation.OrderedLogicRealization

   1import IndisputableMonolith.Foundation.ModularLogicRealization
   2
   3/-!
   4  OrderedLogicRealization.lean
   5
   6  Ordered faithful realization for Universal Forcing.
   7-/
   8
   9namespace IndisputableMonolith
  10namespace Foundation
  11namespace OrderedLogicRealization
  12
  13/-- Equality cost on `Nat`. -/
  14def natCost (m n : Nat) : Nat :=
  15  if m = n then 0 else 1
  16
  17@[simp] theorem natCost_self (n : Nat) : natCost n n = 0 := by
  18  simp [natCost]
  19
  20theorem natCost_symm (m n : Nat) : natCost m n = natCost n m := by
  21  by_cases h : m = n
  22  · subst h
  23    simp [natCost]
  24  · have h' : n ≠ m := by intro hnm; exact h hnm.symm
  25    simp [natCost, h, h']
  26
  27/-- The ordered natural-number realization. -/
  28def natOrderedRealization : LogicRealization where
  29  Carrier := Nat
  30  Cost := Nat
  31  zeroCost := inferInstance
  32  compare := natCost
  33  zero := 0
  34  step := Nat.succ
  35  Orbit := ArithmeticFromLogic.LogicNat
  36  orbitZero := ArithmeticFromLogic.LogicNat.zero
  37  orbitStep := ArithmeticFromLogic.LogicNat.succ
  38  interpret := ArithmeticFromLogic.LogicNat.toNat
  39  interpret_zero := ArithmeticFromLogic.LogicNat.toNat_zero
  40  interpret_step := by
  41    intro n
  42    exact ArithmeticFromLogic.LogicNat.toNat_succ n
  43  orbit_no_confusion := by
  44    intro n h
  45    exact ArithmeticFromLogic.LogicNat.zero_ne_succ n h
  46  orbit_step_injective := ArithmeticFromLogic.LogicNat.succ_injective
  47  orbit_induction := by
  48    intro P h0 hs n
  49    exact ArithmeticFromLogic.LogicNat.induction (motive := P) h0 hs n
  50  orbitEquivLogicNat := Equiv.refl ArithmeticFromLogic.LogicNat
  51  orbitEquiv_zero := rfl
  52  orbitEquiv_step := by intro n; rfl
  53  identity := natCost_self
  54  nonContradiction := natCost_symm
  55  excludedMiddle := True
  56  composition := True
  57  actionInvariant := True
  58  nontrivial := by
  59    refine ⟨1, ?_⟩
  60    simp [natCost]
  61
  62/-- Ordered arithmetic is invariant with every realization. -/
  63noncomputable def ordered_arithmetic_invariant (R : LogicRealization.{0, 0}) :
  64    (UniversalForcing.arithmeticOf natOrderedRealization).peano.carrier
  65      ≃ (UniversalForcing.arithmeticOf R).peano.carrier :=
  66  ArithmeticOf.equivOfInitial
  67    (UniversalForcing.arithmeticOf natOrderedRealization)
  68    (UniversalForcing.arithmeticOf R)
  69
  70/-- The ordered realization interprets arithmetic faithfully. -/
  71theorem ordered_faithful :
  72    LogicRealization.FaithfulArithmeticInterpretation natOrderedRealization where
  73  injective := by
  74    intro a b h
  75    exact (ArithmeticFromLogic.LogicNat.eq_iff_toNat_eq).mpr h
  76  zero_step_noncollapse := by
  77    intro n h
  78    have hnat := congrArg id h
  79    simp [natOrderedRealization] at hnat
  80    exact Nat.succ_ne_zero _ hnat.symm
  81
  82/-- Order on the carrier matches the recovered Peano order. -/
  83theorem ordered_interpret_le_iff (a b : ArithmeticFromLogic.LogicNat) :
  84    ArithmeticFromLogic.LogicNat.toNat a ≤ ArithmeticFromLogic.LogicNat.toNat b ↔ a ≤ b := by
  85  exact (ArithmeticFromLogic.LogicNat.toNat_le a b).symm
  86
  87end OrderedLogicRealization
  88end Foundation
  89end IndisputableMonolith
  90