Fixed-point theorem

Last updated

In mathematics, a fixed-point theorem is a result saying that a function F will have at least one fixed point (a point x for which F(x) = x), under some conditions on F that can be stated in general terms. [1]

Contents

In mathematical analysis

The Banach fixed-point theorem (1922) gives a general criterion guaranteeing that, if it is satisfied, the procedure of iterating a function yields a fixed point. [2]

By contrast, the Brouwer fixed-point theorem (1911) is a non-constructive result: it says that any continuous function from the closed unit ball in n-dimensional Euclidean space to itself must have a fixed point, [3] but it doesn't describe how to find the fixed point (see also Sperner's lemma).

For example, the cosine function is continuous in [−1, 1] and maps it into [−1, 1], and thus must have a fixed point. This is clear when examining a sketched graph of the cosine function; the fixed point occurs where the cosine curve y = cos(x) intersects the line y = x. Numerically, the fixed point (known as the Dottie number) is approximately x = 0.73908513321516 (thus x = cos(x) for this value of x).

The Lefschetz fixed-point theorem [4] (and the Nielsen fixed-point theorem) [5] from algebraic topology is notable because it gives, in some sense, a way to count fixed points.

There are a number of generalisations to Banach fixed-point theorem and further; these are applied in PDE theory. See fixed-point theorems in infinite-dimensional spaces.

The collage theorem in fractal compression proves that, for many images, there exists a relatively small description of a function that, when iteratively applied to any starting image, rapidly converges on the desired image. [6]

In algebra and discrete mathematics

The Knaster–Tarski theorem states that any order-preserving function on a complete lattice has a fixed point, and indeed a smallest fixed point. [7] See also Bourbaki–Witt theorem.

The theorem has applications in abstract interpretation, a form of static program analysis.

A common theme in lambda calculus is to find fixed points of given lambda expressions. Every lambda expression has a fixed point, and a fixed-point combinator is a "function" which takes as input a lambda expression and produces as output a fixed point of that expression. [8] An important fixed-point combinator is the Y combinator used to give recursive definitions.

In denotational semantics of programming languages, a special case of the Knaster–Tarski theorem is used to establish the semantics of recursive definitions. While the fixed-point theorem is applied to the "same" function (from a logical point of view), the development of the theory is quite different.

The same definition of recursive function can be given, in computability theory, by applying Kleene's recursion theorem. [9] These results are not equivalent theorems; the Knaster–Tarski theorem is a much stronger result than what is used in denotational semantics. [10] However, in light of the Church–Turing thesis their intuitive meaning is the same: a recursive function can be described as the least fixed point of a certain functional, mapping functions to functions.

The above technique of iterating a function to find a fixed point can also be used in set theory; the fixed-point lemma for normal functions states that any continuous strictly increasing function from ordinals to ordinals has one (and indeed many) fixed points.

Every closure operator on a poset has many fixed points; these are the "closed elements" with respect to the closure operator, and they are the main reason the closure operator was defined in the first place.

Every involution on a finite set with an odd number of elements has a fixed point; more generally, for every involution on a finite set of elements, the number of elements and the number of fixed points have the same parity. Don Zagier used these observations to give a one-sentence proof of Fermat's theorem on sums of two squares, by describing two involutions on the same set of triples of integers, one of which can easily be shown to have only one fixed point and the other of which has a fixed point for each representation of a given prime (congruent to 1 mod 4) as a sum of two squares. Since the first involution has an odd number of fixed points, so does the second, and therefore there always exists a representation of the desired form. [11]

List of fixed-point theorems

See also

Footnotes

  1. ↑ Brown, R. F., ed. (1988). Fixed Point Theory and Its Applications. American Mathematical Society. ISBN   0-8218-5080-6.
  2. ↑ Giles, John R. (1987). Introduction to the Analysis of Metric Spaces. Cambridge University Press. ISBN   978-0-521-35928-3.
  3. ↑ Eberhard Zeidler, Applied Functional Analysis: main principles and their applications, Springer, 1995.
  4. ↑ Solomon Lefschetz (1937). "On the fixed point formula". Ann. of Math. 38 (4): 819–822. doi:10.2307/1968838.
  5. ↑ Fenchel, Werner; Nielsen, Jakob (2003). Schmidt, Asmus L. (ed.). Discontinuous groups of isometries in the hyperbolic plane. De Gruyter Studies in mathematics. Vol. 29. Berlin: Walter de Gruyter & Co.
  6. ↑ Barnsley, Michael. (1988). Fractals Everywhere . Academic Press, Inc. ISBN   0-12-079062-9.
  7. ↑ Alfred Tarski (1955). "A lattice-theoretical fixpoint theorem and its applications". Pacific Journal of Mathematics. 5:2: 285–309.
  8. ↑ Peyton Jones, Simon L. (1987). The Implementation of Functional Programming. Prentice Hall International.
  9. ↑ Cutland, N.J., Computability: An introduction to recursive function theory, Cambridge University Press, 1980. ISBN   0-521-29465-7
  10. ↑ The foundations of program verification, 2nd edition, Jacques Loeckx and Kurt Sieber, John Wiley & Sons, ISBN   0-471-91282-4, Chapter 4; theorem 4.24, page 83, is what is used in denotational semantics, while Knaster–Tarski theorem is given to prove as exercise 4.3–5 on page 90.
  11. ↑ Zagier, D. (1990), "A one-sentence proof that every prime p ≡ 1 (mod 4) is a sum of two squares", American Mathematical Monthly , 97 (2): 144, doi:10.2307/2323918, MR   1041893 .

Related Research Articles

In mathematics, especially functional analysis, a Banach algebra, named after Stefan Banach, is an associative algebra over the real or complex numbers that at the same time is also a Banach space, that is, a normed space that is complete in the metric induced by the norm. The norm is required to satisfy

<span class="mw-page-title-main">Kazimierz Kuratowski</span> Polish mathematician and logician

Kazimierz Kuratowski was a Polish mathematician and logician. He was one of the leading representatives of the Warsaw School of Mathematics. He worked as a professor at the University of Warsaw and at the Mathematical Institute of the Polish Academy of Sciences. Between 1946 and 1953, he served as President of the Polish Mathematical Society.

In mathematics, the Banach fixed-point theorem is an important tool in the theory of metric spaces; it guarantees the existence and uniqueness of fixed points of certain self-maps of metric spaces, and provides a constructive method to find those fixed points. It can be understood as an abstract formulation of Picard's method of successive approximations. The theorem is named after Stefan Banach (1892–1945) who first stated it in 1922.

In computer science, denotational semantics is an approach of formalizing the meanings of programming languages by constructing mathematical objects that describe the meanings of expressions from the languages. Other approaches providing formal semantics of programming languages include axiomatic semantics and operational semantics.

In combinatory logic for computer science, a fixed-point combinator, denoted , is a higher-order function that returns some fixed point of its argument function, if one exists.

In computability theory, Kleene's recursion theorems are a pair of fundamental results about the application of computable functions to their own descriptions. The theorems were first proved by Stephen Kleene in 1938 and appear in his 1952 book Introduction to Metamathematics. A related theorem, which constructs fixed points of a computable function, is known as Rogers's theorem and is due to Hartley Rogers, Jr.

In the mathematical areas of order and lattice theory, the Knaster–Tarski theorem, named after Bronisław Knaster and Alfred Tarski, states the following:

<span class="mw-page-title-main">Involution (mathematics)</span> Function that is its own inverse

In mathematics, an involution, involutory function, or self-inverse function is a function f that is its own inverse,

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.

Reverse mathematics is a program in mathematical logic that seeks to determine which axioms are required to prove theorems of mathematics. Its defining method can briefly be described as "going backwards from the theorems to the axioms", in contrast to the ordinary mathematical practice of deriving theorems from axioms. It can be conceptualized as sculpting out necessary conditions from sufficient ones.

In mathematical logic, the diagonal lemma establishes the existence of self-referential sentences in certain formal theories of the natural numbers—specifically those theories that are strong enough to represent all computable functions. The sentences whose existence is secured by the diagonal lemma can then, in turn, be used to prove fundamental limitative results such as Gödel's incompleteness theorems and Tarski's undefinability theorem.

<span class="mw-page-title-main">Fixed point (mathematics)</span> Element mapped to itself by a mathematical function

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, the phrase complete partial order is variously used to refer to at least three similar, but distinct, classes of partially ordered sets, characterized by particular completeness properties. Complete partial orders play a central role in theoretical computer science: in denotational semantics and domain theory.

Tarski's undefinability theorem, stated and proved by Alfred Tarski in 1933, is an important limitative result in mathematical logic, the foundations of mathematics, and in formal semantics. Informally, the theorem states that "arithmetical truth cannot be defined in arithmetic".

<span class="mw-page-title-main">Least fixed point</span>

In order theory, a branch of mathematics, the least fixed point of a function from a partially ordered set 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.

In numerical analysis, fixed-point iteration is a method of computing fixed points of a function.

References

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.