Elimination of simultaneous fixed points
Lax369799.FixedPointElimination · concepts/Lax369799/FixedPointElimination.lean · lax-369799
No public endorsements yet.
Loading review…
Sign in with ORCIDNatural Language Statement
Theorem
Bekić's identity expresses a simultaneous least or greatest fixed point on a product as two nested fixed points. Iterating the identity eliminates finite vectors of modal fixed-point variables.
Concept map
Evidence
Lean source view on GitHub
| 1 | import Mathlib.Order.FixedPoints |
| 2 | |
| 3 | /-! |
| 4 | --- |
| 5 | title: Elimination of simultaneous fixed points |
| 6 | type: theorem |
| 7 | --- |
| 8 | Bekić's identity expresses a simultaneous least or greatest fixed point |
| 9 | on a product as two nested fixed points. Iterating the identity eliminates |
| 10 | finite vectors of modal fixed-point variables. |
| 11 | -/ |
| 12 | namespace Lax369799.FixedPointElimination |
| 13 | |
| 14 | variable {α β : Type} [CompleteLattice α] [CompleteLattice β] |
| 15 | |
| 16 | def sectionMap (F : α × β →o α × β) (a : α) : β →o β where |
| 17 | toFun := fun b => (F (a, b)).2 |
| 18 | monotone' := fun b c h => (F.monotone (show (a, b) ≤ (a, c) from ⟨le_rfl, h⟩)).2 |
| 19 | |
| 20 | def leastSection (F : α × β →o α × β) : α →o β where |
| 21 | toFun := fun a => (sectionMap F a).lfp |
| 22 | monotone' := fun a b h => OrderHom.lfp.monotone |
| 23 | (fun c => (F.monotone (show (a, c) ≤ (b, c) from ⟨h, le_rfl⟩)).2) |
| 24 | |
| 25 | def greatestSection (F : α × β →o α × β) : α →o β where |
| 26 | toFun := fun a => (sectionMap F a).gfp |
| 27 | monotone' := fun a b h => OrderHom.gfp.monotone |
| 28 | (fun c => (F.monotone (show (a, c) ≤ (b, c) from ⟨h, le_rfl⟩)).2) |
| 29 | |
| 30 | def firstMap (F : α × β →o α × β) (s : α →o β) : α →o α where |
| 31 | toFun := fun a => (F (a, s a)).1 |
| 32 | monotone' := fun _ _ h => (F.monotone ⟨h, s.monotone h⟩).1 |
| 33 | |
| 34 | axiom least (F : α × β →o α × β) : |
| 35 | F.lfp = ((firstMap F (leastSection F)).lfp, |
| 36 | leastSection F (firstMap F (leastSection F)).lfp) |
| 37 | |
| 38 | axiom greatest (F : α × β →o α × β) : |
| 39 | F.gfp = ((firstMap F (greatestSection F)).gfp, |
| 40 | greatestSection F (firstMap F (greatestSection F)).gfp) |
| 41 | |
| 42 | end Lax369799.FixedPointElimination |
| 43 |
Discussion
Ask a question or add context. Endorsements and structured flags are kept in the review panel above.
0 comments