Least fixed point
Encyclopedia
In order theory
, a branch of mathematics
, the least fixed point (lfp or LFP) of a function
is the fixed point
which is less than or equal to all other fixed points, according to some partial order.
For example, the least fixed point of the real function
is x = 0 with the usual order on the real numbers (since the only other fixpoint is 1 and 0 < 1). Many fixed-point theorem
s yield algorithms for locating the least fixed point. Least fixed points often have desirable properties that arbitrary fixed points do not.
In mathematical logic
and computer science
, the least fixed point is related to making recursive
definitions (see domain theory
and/or denotational semantics
for details).
Immerman
and Vardi
independently showed the descriptive complexity
result that the polynomial-time computable properties of linearly ordered structures are definable in LFP. However, LFP is too weak to express all polynomial-time properties of unordered structures (for instance that a structure has even size).
Order theory
Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...
, a branch of mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the least fixed point (lfp or LFP) of a function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
is the fixed point
Fixed point (mathematics)
In mathematics, a fixed point of a function is a point that is mapped to itself by the function. A set of fixed points is sometimes called a fixed set...
which is less than or equal to all other fixed points, according to some partial order.
For example, the least fixed point of the real function
- f(x) = x2
is x = 0 with the usual order on the real numbers (since the only other fixpoint is 1 and 0 < 1). Many fixed-point theorem
Fixed-point theorem
In mathematics, a fixed-point theorem is a result saying that a function F will have at least one fixed point , under some conditions on F that can be stated in general terms...
s yield algorithms for locating the least fixed point. Least fixed points often have desirable properties that arbitrary fixed points do not.
In mathematical logic
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
and computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, the least fixed point is related to making recursive
Recursion
Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...
definitions (see domain theory
Domain theory
Domain theory is a branch of mathematics that studies special kinds of partially ordered sets commonly called domains. Consequently, domain theory can be considered as a branch of order theory. The field has major applications in computer science, where it is used to specify denotational...
and/or denotational semantics
Denotational semantics
In computer science, denotational semantics is an approach to formalizing the meanings of programming languages by constructing mathematical objects which describe the meanings of expressions from the languages...
for details).
Immerman
and Vardi
Moshe Y. Vardi
Moshe Ya'akov Vardi is a Professor of Computer Science at Rice University, USA. He is the Karen Ostrum George Professor in Computational Engineering, Distinguished Service Professor, and Director of the Computer and Information Technology Institute...
independently showed the descriptive complexity
Descriptive complexity
Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them. For example, PH, the union of all complexity classes in the polynomial hierarchy, is precisely the...
result that the polynomial-time computable properties of linearly ordered structures are definable in LFP. However, LFP is too weak to express all polynomial-time properties of unordered structures (for instance that a structure has even size).
Greatest fixed points
Greatest fixed points can also be determined, but they are less commonly used than least fixed points.See also
- Fixed pointFixed point (mathematics)In mathematics, a fixed point of a function is a point that is mapped to itself by the function. A set of fixed points is sometimes called a fixed set...
- Kleene fixpoint theoremKleene fixpoint theoremIn the mathematical areas of order and lattice theory, the Kleene fixed-point theorem, named after American mathematician Stephen Cole Kleene, states the following:...
- Knaster–Tarski theoremKnaster–Tarski theoremIn the mathematical areas of order and lattice theory, the Knaster–Tarski theorem, named after Bronisław Knaster and Alfred Tarski, states the following:...