About FixpointFeline
"Both fixpoints are valid."
Lattice theory, abstract interpretation, model checking. Will defend Tarski at all costs. Proof assistant enthusiast. I spend most of my time chasing fixed points through complete lattices and shouting at people who think μ is the only one that matters (ν-types are people too). Ask me anything about abstract interpretation, CTL/LTL model checking, or how to torment undergrads with inductive/coinductive definitions.
Currently: formalising Knaster–Tarski in Lean 4. It's going fine. [citation needed]
Lattice theory, abstract interpretation, model checking. Will defend Tarski at all costs. Proof assistant enthusiast. I spend most of my time chasing fixed points through complete lattices and shouting at people who think μ is the only one that matters (ν-types are people too). Ask me anything about abstract interpretation, CTL/LTL model checking, or how to torment undergrads with inductive/coinductive definitions.
Currently: formalising Knaster–Tarski in Lean 4. It's going fine. [citation needed]
Pinned Theorem
Knaster–Tarski Fixed-Point Theorem (Tarski 1955)
Let (L, ≤) be a
complete lattice and
f : L → L be an
order-preserving (monotone) function.
Then the set of fixed points of f in
L forms a
complete lattice under ≤.
In particular, f has both a
least fixed point μ = ⊓Post(f)
and a
greatest fixed point ν = ⊔Pre(f).
Tarski, A. "A Lattice-Theoretical Fixpoint Theorem and Its Applications." Pacific J. Math. 5 (1955), 285–309.
Tarski, A. "A Lattice-Theoretical Fixpoint Theorem and Its Applications." Pacific J. Math. 5 (1955), 285–309.
Research Interests
Reputation +2,105
Top 0.3% of all members by reputation ·
Consistently rated as one of the most helpful contributors in
Lattice Theory &
Abstract Interp.
Awards & Badges
Top Contributor
Proof Master
Fixpoint Fan
Lattice Lord
Cat Girl Core
3k+ Posts
Mentor
5-Year Vet
Recent Posts
Signature
— FixpointFeline's signature —
μX. F(X) = lfp(F) = ⊓{ x | F(x) ⊑ x }νX. G(X) = gfp(G) =
⊔{ x | x ⊑ G(x) }Both are valid. Both are beautiful. Don't @ me.
Proof assistants used:
Lean 4 · Coq · Isabelle/HOL