O-minimal structure framework
DefinitionMonotonicity_Theorem_Framework2The o-minimal structure interface over a dense linear order without endpoints.
import Mathlib.Data.Set.Basic
import Mathlib.Data.Fin.Tuple.Basic
import Mathlib.Order.Basic
import Mathlib.Data.Set.Finite.Basic
universe u
namespace Monotonicity_Theorem
abbrev Power (R : Type u) (n : Nat) := Fin n → R
namespace Power
variable {R : Type u}
def left {n m : Nat} (z : Power R (n + m)) : Power R n := fun i => z (Fin.castAdd m i)
def right {n m : Nat} (z : Power R (n + m)) : Power R m := fun j => z (Fin.natAdd n j)
def deleteCoord {n : Nat} (k : Fin (n + 1)) (z : Power R (n + 1)) : Power R n := fun i => z (Fin.succAbove k i)
def append {n m : Nat} (x : Power R n) (y : Power R m) : Power R (n + m) := Fin.append x y
end Power
-- Dense linear orders without endpoints are Mathlib's
-- `[LinearOrder R] [DenselyOrdered R] [NoMaxOrder R] [NoMinOrder R]`.
-- All order reasoning uses Mathlib's API directly: `lt_trans`, `lt_irrefl`,
-- `lt_trichotomy` for case splits, `exists_between` for density, and
-- `exists_lt` / `exists_gt` for no-endpoint witnesses.
inductive Endpoint (R : Type u) where
| negInf : Endpoint R
| finite (value : R) : Endpoint R
| posInf : Endpoint R
namespace Endpoint
variable {R : Type u} [LinearOrder R]
def lt : Endpoint R → Endpoint R → Prop
| .negInf, .negInf => False
| .negInf, .finite _ => True
| .negInf, .posInf => True
| .finite _, .negInf => False
| .finite a, .finite b => a < b
| .finite _, .posInf => True
| .posInf, _ => False
end Endpoint
def setEmpty {A : Type u} : Set A := fun _ => False
def setUnion {A : Type u} (X Y : Set A) : Set A := fun a => X a ∨ Y a
def setInter {A : Type u} (X Y : Set A) : Set A := fun a => X a ∧ Y a
def setCompl {A : Type u} (X : Set A) : Set A := fun a => ¬ (X a)
def pointSet {R : Type u} (a : R) : Set (Power R 1) := fun x => x 0 = a
def openInterval {R : Type u} [LinearOrder R] (a b : Endpoint R) : Set (Power R 1) := fun x => Endpoint.lt a (.finite (x 0)) ∧ Endpoint.lt (.finite (x 0)) b
inductive FiniteUnionOfPointsAndIntervals {R : Type u} [LinearOrder R] : Set (Power R 1) → Prop where
| empty : FiniteUnionOfPointsAndIntervals (fun _ => False)
| point (a : R) : FiniteUnionOfPointsAndIntervals (pointSet a)
| interval (a b : Endpoint R) : FiniteUnionOfPointsAndIntervals (openInterval a b)
| union {A B : Set (Power R 1)} : FiniteUnionOfPointsAndIntervals A → FiniteUnionOfPointsAndIntervals B → FiniteUnionOfPointsAndIntervals (fun x => A x ∨ B x)
structure OMinimalStructure (R : Type u) [LinearOrder R] where
S : (n : Nat) → Set (Set (Power R n))
empty_mem : ∀ n : Nat, S n (setEmpty : Set (Power R n))
union_mem : ∀ {n : Nat} {A B : Set (Power R n)}, S n A → S n B → S n ((A ∪ B))
inter_mem : ∀ {n : Nat} {A B : Set (Power R n)}, S n A → S n B → S n ((A ∩ B))
compl_mem : ∀ {n : Nat} {A : Set (Power R n)}, S n A → S n (Aᶜ)
diagonal_mem : ∀ {n : Nat} (i j : Fin n), i < j → S n (fun x : Power R n => x i = x j)
product_mem : ∀ {n m : Nat} {A : Set (Power R n)} {B : Set (Power R m)}, S n A → S m B → S (n + m) (fun z : Power R (n + m) => A (Power.left z) ∧ B (Power.right z))
project_mem : ∀ {n : Nat} (k : Fin (n + 1)) {A : Set (Power R (n + 1))}, S (n + 1) A → S n (fun y : Power R n => ∃ x : Power R (n + 1), A x ∧ Power.deleteCoord k x = y)
reindex_mem : ∀ {n m : Nat} (sigma : Fin n → Fin m) {A : Set (Power R n)}, S n A → S m (fun x : Power R m => A (fun i : Fin n => x (sigma i)))
existsLast_mem : ∀ {n m : Nat} {A : Set (Power R (n + m))}, S (n + m) A → S n (fun x : Power R n => ∃ y : Power R m, A (Power.append x y))
lt_mem : S 2 (fun p : Power R 2 => p 0 < p 1)
ominimal : ∀ A : Set (Power R 1), S 1 A ↔ FiniteUnionOfPointsAndIntervals A
end Monotonicity_Theorem
namespace Monotonicity_Theorem
namespace Power
variable {R : Type u}
def coord1 (x : Power R 1) : R := x 0
end Power
def FunctionGraph {m n : Nat} {R : Type u} {A : Set (Power R m)} {B : Set (Power R n)} (f : {x : Power R m // A x} → {y : Power R n // B y}) : Set (Power R (m + n)) := fun z => ∃ hx : A (Power.left z), Power.right z = (f (Subtype.mk (Power.left z) hx)).1
structure DefinableFunction {R : Type u} [LinearOrder R] (M : OMinimalStructure R) {m n : Nat} (A : Set (Power R m)) (B : Set (Power R n)) where
domain_mem : M.S m A
codomain_mem : M.S n B
toFun : {x : Power R m // A x} → {y : Power R n // B y}
graph_mem : M.S (m + n) (FunctionGraph toFun)
@[reducible] def Lt1 {R : Type u} [LinearOrder R] (x y : Power R 1) : Prop := Power.coord1 x < Power.coord1 y
def StrictlyIncreasingOn {R : Type u} [LinearOrder R] (I B : Set (Power R 1)) (f : {x : Power R 1 // I x} → {y : Power R 1 // B y}) : Prop := ∀ x y (hx : I x) (hy : I y), Lt1 x y → Lt1 (f (Subtype.mk x hx)).1 (f (Subtype.mk y hy)).1
def StrictlyDecreasingOn {R : Type u} [LinearOrder R] (I B : Set (Power R 1)) (f : {x : Power R 1 // I x} → {y : Power R 1 // B y}) : Prop := ∀ x y (hx : I x) (hy : I y), Lt1 x y → Lt1 (f (Subtype.mk y hy)).1 (f (Subtype.mk x hx)).1
def StrictlyMonotoneOn {R : Type u} [LinearOrder R] (I B : Set (Power R 1)) (f : {x : Power R 1 // I x} → {y : Power R 1 // B y}) : Prop := StrictlyIncreasingOn I B f ∨ StrictlyDecreasingOn I B f
def ContinuousPoints {R : Type u} [LinearOrder R] (I : Set (Power R 1)) (G : Set (Power R 2)) : Set (Power R 1) :=
fun x => I x ∧ ∀ w₀ : R, G (Power.append (n := 1) (m := 1) (fun _ => Power.coord1 x) (fun _ => w₀)) →
∀ ε₁ ε₂ : R, ε₁ < w₀ → w₀ < ε₂ →
∃ δ₁ δ₂ : R, δ₁ < (Power.coord1 x) ∧ (Power.coord1 x) < δ₂ ∧
∀ y v : R, I (fun _ => y) → G (Power.append (n := 1) (m := 1) (fun _ => y) (fun _ => v)) →
δ₁ < y → y < δ₂ → ε₁ < v ∧ v < ε₂
end Monotonicity_Theorem
Read-back
What the Lean code literally says, in plain math · muse-spark
Fix a universe and, for any type in that universe and any natural number , the -tuples over are the functions from an -element index set to , so the case has exactly one tuple given by the empty function and the case is identified with by evaluation at the unique index.
For fixed and fixed natural numbers and , given an -tuple , its left part is the -tuple whose -th coordinate for among the first indices equals the coordinate of at the corresponding index among the first positions of the -element index set, so when the result is always the unique empty tuple and when it is essentially itself.
For fixed and fixed natural numbers and , given an -tuple , its right part is the -tuple whose -th coordinate for among indices equals the coordinate of at the position offset by , i.e. the -th among the last positions, so when the result is always the unique empty tuple and when it is essentially itself.
For fixed and fixed natural number , given a distinguished index among positions and an -tuple , deletion of the -th coordinate is the -tuple whose -th coordinate equals the coordinate of at the -th index distinct from enumerated in increasing order skipping , so when the result is always the unique empty tuple.
For fixed and fixed natural numbers and , given an -tuple and an -tuple , their concatenation is the -tuple whose first coordinates agree with and whose last coordinates agree with , so when it is essentially and when it is essentially .
For any type , there is a type of endpoints over with exactly three forms: a negative infinity, a finite endpoint carrying a value in , and a positive infinity.
For fixed equipped with a linear order, there is a binary proposition on endpoints defined by cases as follows: negative infinity compared to negative infinity is false, negative infinity compared to a finite endpoint or to positive infinity is true, a finite endpoint compared to negative infinity is false, a finite compared to a finite holds exactly when is strictly less than in , a finite endpoint compared to positive infinity is true, and positive infinity compared to anything (negative infinity, finite, or positive infinity) is false, so negative infinity is strictly below everything except itself and positive infinity is strictly above everything except itself while the relation is irreflexive.
For any type , the empty subset of is the subset that contains no element, i.e. membership is always the false proposition, including the degenerate case where itself is empty.
For any type and any two subsets and of , their union is the subset of consisting of those such that is in or is in , in the inclusive sense.
For any type and any two subsets and of , their intersection is the subset of consisting of those such that is in and is in .
For any type and any subset of , its complement is the subset of consisting of those such that it is not the case that is in .
For any type and any element of , the point set at is the subset of -tuples over consisting of those whose unique coordinate equals , which is empty when considered vacuously and otherwise a singleton.
For any equipped with a linear order and any two endpoints and over , the open interval from to is the subset of -tuples over consisting of those such that is strictly below the finite endpoint and the finite endpoint is strictly below in the endpoint order, which is the whole -tuple space when is negative infinity and is positive infinity, a ray when exactly one endpoint is infinite, a bounded interval when both are finite, and the empty set when the lower endpoint is not strictly below the upper endpoint.
For any equipped with a linear order, there is a predicate on subsets of -tuples over that holds exactly in four kinds of cases: it holds of the empty set, it holds of any singleton for in , it holds of any open interval for endpoints and (including rays, the whole line, and degenerate empty intervals where the endpoint inequality fails), and if it holds of and holds of then it holds of the union of and , so by iteration it holds exactly of finite unions of singletons and open intervals, with the empty union giving the empty set.
For any equipped with a linear order, a structure consists of a family , one for each natural number , where each is a collection of subsets of -tuples over , satisfying all of the following: for every the empty set belongs to ; for every and any in their binary union belongs to and their binary intersection belongs to ; for every and any in its complement belongs to ; for every and any indices among with strictly less than the diagonal belongs to , with no requirement when since no such exist; for every and any in and in the Cartesian product belongs to ; for every , every index among positions, and every in the coordinate-deletion projection belongs to ; for every , every index map from an -element index set to an -element index set, and every in the reindexed set belongs to , which includes permuting, repeating, and dropping coordinates and is vacuous or constant in the degenerate cases or ; for every and every in the existential projection belongs to , which is trivial over the singleton when and is either empty or the singleton when ; the strict order set in -tuples belongs to ; and for every subset of -tuples, belongs to if and only if is a finite union of points and intervals in the sense above.
Confirmed by the mission captain (proposal self-audit).