In order theory, a branch of mathematics, the least fixed point (lfp or LFP, sometimes also smallest fixed point) of a function from a partially ordered set ("poset" for short) to itself is the fixed point which is less than each other fixed point, according to the order of the poset. A function need not have a least fixed point, but if it does then the least fixed point is unique.
With the usual order on the real numbers, the least fixed point of the real function f(x) = x2 is x = 0 (since the only other fixed point is 1 and 0 < 1). In contrast, f(x) = x + 1 has no fixed points at all, so has no least one, and f(x) = x has infinitely many fixed points, but has no least one.
Let be a directed graph and be a vertex. The set of vertices accessible from can be defined as the least fixed-point of the function , defined as The set of vertices which are co-accessible from is defined by a similar least fix-point. The strongly connected component of is the intersection of those two least fixed-points.
Let be a context-free grammar. The set of symbols which produces the empty string can be obtained as the least fixed-point of the function , defined as , where denotes the power set of .
Many fixed-point theorems yield algorithms for locating the least fixed point. Least fixed points often have desirable properties that arbitrary fixed points do not.
In computer science, the denotational semantics approach uses least fixed points to obtain from a given program text a corresponding mathematical function, called its semantics. To this end, an artificial mathematical object, , is introduced, denoting the exceptional value "undefined". Given e.g. the program datatype int
, its mathematical counterpart is defined as it is made a partially ordered set by defining for each and letting any two different members be uncomparable w.r.t. , see picture.
The semantics of a program definition int f(int n){...}
is some mathematical function If the program definition f
does not terminate for some input n
, this can be expressed mathematically as The set of all mathematical functions is made partially ordered by defining if, for each the relation holds, that is, if is less defined or equal to For example, the semantics of the expression x+x/x
is less defined than that of x+1
, since the former, but not the latter, maps to and they agree otherwise.
Given some program text f
, its mathematical counterpart is obtained as least fixed point of some mapping from functions to functions that can be obtained by "translating" f
. For example, the C definition
intfact(intn){if(n==0)return1;elsereturnn*fact(n-1);}
is translated to a mapping
The mapping is defined in a non-recursive way, although fact
was defined recursively. Under certain restrictions (see Kleene fixed-point theorem), which are met in the example, necessarily has a least fixed point, , that is for all . [1] It is possible to show that
A larger fixed point of is e.g. the function defined by
however, this function does not correctly reflect the behavior of the above program text for negative e.g. the call fact(-1)
will not terminate at all, let alone return 0
. Only the least fixed point, can reasonably be used as a mathematical program semantic.
Immerman [2] [3] and Vardi [4] independently showed the descriptive complexity result that the polynomial-time computable properties of linearly ordered structures are definable in FO(LFP), i.e. in first-order logic with a least fixed point operator. However, FO(LFP) is too weak to express all polynomial-time properties of unordered structures (for instance that a structure has even size).
The greatest fixed point of a function can be defined analogously to the least fixed point, as the fixed point which is greater than any other fixed point, according to the order of the poset. In computer science, greatest fixed points are much less commonly used than least fixed points. Specifically, the posets found in domain theory usually do not have a greatest element, hence for a given function, there may be multiple, mutually incomparable maximal fixed points, and the greatest fixed point of that function may not exist. To address this issue, the optimal fixed point has been defined as the most-defined fixed point compatible with all other fixed points. The optimal fixed point always exists, and is the greatest fixed point if the greatest fixed point exists. The optimal fixed point allows formal study of recursive and corecursive functions that do not converge with the least fixed point. [5] Unfortunately, whereas Kleene's recursion theorem shows that the least fixed point is effectively computable, the optimal fixed point of a computable function may be a non-computable function. [6]
In mathematics, the absolute value or modulus of a real number , denoted , is the non-negative value of without regard to its sign. Namely, if is a positive number, and if is negative, and . For example, the absolute value of 3 is 3, and the absolute value of −3 is also 3. The absolute value of a number may be thought of as its distance from zero.
In mathematics, a complex number is an element of a number system that extends the real numbers with a specific element denoted i, called the imaginary unit and satisfying the equation ; every complex number can be expressed in the form , where a and b are real numbers. Because no real number satisfies the above equation, i was called an imaginary number by René Descartes. For the complex number ,a is called the real part, and b is called the imaginary part. The set of complex numbers is denoted by either of the symbols or C. Despite the historical nomenclature, "imaginary" complex numbers have a mathematical existence as firm as that of the real numbers, and they are fundamental tools in the scientific description of the natural world.
In mathematics, a continuous function is a function such that a small variation of the argument induces a small variation of the value of the function. This implies there are no abrupt changes in value, known as discontinuities. More precisely, a function is continuous if arbitrarily small changes in its value can be assured by restricting to sufficiently small changes of its argument. A discontinuous function is a function that is not continuous. Until the 19th century, mathematicians largely relied on intuitive notions of continuity and considered only continuous functions. The epsilon–delta definition of a limit was introduced to formalize the definition of continuity.
In mathematics, a directed set is a nonempty set together with a reflexive and transitive binary relation , with the additional property that every pair of elements has an upper bound. In other words, for any and in there must exist in with and A directed set's preorder is called a direction.
In mathematics, a partial functionf from a set X to a set Y is a function from a subset S of X to Y. The subset S, that is, the domain of f viewed as a function, is called the domain of definition or natural domain of f. If S equals X, that is, if f is defined on every element in X, then f is said to be a total function.
In commutative algebra, the prime spectrum of a commutative ring R is the set of all prime ideals of R, and is usually denoted by ; in algebraic geometry it is simultaneously a topological space equipped with the sheaf of rings .
In topology, the closure of a subset S of points in a topological space consists of all points in S together with all limit points of S. The closure of S may equivalently be defined as the union of S and its boundary, and also as the intersection of all closed sets containing S. Intuitively, the closure can be thought of as all the points that are either in S or "very near" S. A point which is in the closure of S is a point of closure of S. The notion of closure is in many ways dual to the notion of interior.
In combinatory logic for computer science, a fixed-point combinator, is a higher-order function that returns some fixed point of its argument function, if one exists.
In the mathematical discipline of set theory, forcing is a technique for proving consistency and independence results. Intuitively, forcing can be thought of as a technique to expand the set theoretical universe to a larger universe by introducing a new "generic" object .
Algebraic varieties are the central objects of study in algebraic geometry, a sub-field of mathematics. Classically, an algebraic variety is defined as the set of solutions of a system of polynomial equations over the real or complex numbers. Modern definitions generalize this concept in several different ways, while attempting to preserve the geometric intuition behind the original definition.
Domain theory is a branch of mathematics that studies special kinds of partially ordered sets (posets) 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 semantics, especially for functional programming languages. Domain theory formalizes the intuitive ideas of approximation and convergence in a very general way and is closely related to topology.
In mathematics, the support of a real-valued function is the subset of the function domain containing the elements which are not mapped to zero. If the domain of is a topological space, then the support of is instead defined as the smallest closed set containing all points not mapped to zero. This concept is used very widely in mathematical analysis.
In mathematics, a fixed point, also known as an invariant point, is a value that does not change under a given transformation. Specifically, for functions, a fixed point is an element that is mapped to itself by the function.
In mathematics, a closure operator on a set S is a function from the power set of S to itself that satisfies the following conditions for all sets
In algebra, the length of a module is a generalization of the dimension of a vector space which measures its size. page 153 It is defined to be the length of the longest chain of submodules.
In mathematics, Milnor maps are named in honor of John Milnor, who introduced them to topology and algebraic geometry in his book Singular Points of Complex Hypersurfaces and earlier lectures. The most studied Milnor maps are actually fibrations, and the phrase Milnor fibration is more commonly encountered in the mathematical literature. These were introduced to study isolated singularities by constructing numerical invariants related to the topology of a smooth deformation of the singular space.
In mathematics, a complex logarithm is a generalization of the natural logarithm to nonzero complex numbers. The term refers to one of the following, which are strongly related:
In mathematics, a filter on a set is a family of subsets such that:
Filters in topology, a subfield of mathematics, can be used to study topological spaces and define all basic topological notions such as convergence, continuity, compactness, and more. Filters, which are special families of subsets of some given set, also provide a common framework for defining various types of limits of functions such as limits from the left/right, to infinity, to a point or a set, and many others. Special types of filters called ultrafilters have many useful technical properties and they may often be used in place of arbitrary filters.
In mathematical logic, fixed-point logics are extensions of classical predicate logic that have been introduced to express recursion. Their development has been motivated by descriptive complexity theory and their relationship to database query languages, in particular to Datalog.