In Discrete Mathematics
The Knaster–Tarski theorem is somewhat removed from analysis and does not deal with continuous functions. It states that any order-preserving function on a complete lattice has a fixed point, and indeed a smallest fixed point. See also Bourbaki–Witt theorem.
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. 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. These results are not equivalent theorems; the Knaster–Tarski theorem is a much stronger result than what is used in denotational semantics. 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.
Read more about this topic: Fixed-point Theorem
Famous quotes containing the words discrete and/or mathematics:
“One can describe a landscape in many different words and sentences, but one would not normally cut up a picture of a landscape and rearrange it in different patterns in order to describe it in different ways. Because a photograph is not composed of discrete units strung out in a linear row of meaningful pieces, we do not understand it by looking at one element after another in a set sequence. The photograph is understood in one act of seeing; it is perceived in a gestalt.”
—Joshua Meyrowitz, U.S. educator, media critic. “The Blurring of Public and Private Behaviors,” No Sense of Place: The Impact of Electronic Media on Social Behavior, Oxford University Press (1985)
“The three main medieval points of view regarding universals are designated by historians as realism, conceptualism, and nominalism. Essentially these same three doctrines reappear in twentieth-century surveys of the philosophy of mathematics under the new names logicism, intuitionism, and formalism.”
—Willard Van Orman Quine (b. 1908)