Maths - Fixpoint

Here we look at structures where some part, or parts, of it also have the same structure. This is discussed on the page about sub-objects here.

fixpoint

For an endofunction a fixpoint is certain value or values that map to themselves.

This concept is useful in mathematics generally and also in computing for the study of recursive type definitions.

Example 1 - Real Numbers

fixpoint

Given an endofunction from the reals to itself. There may be some point on the line that the endofunction will map to themselves.

Some of those fixpoints may be attractors and some may be repellers. That is, if we choose a non-fixpoint and continuously apply the endofunctor, then the resulting point may move towards or away from the fixpoints.

Brouwer's fixed-point theorem

For any continuous function f with certain properties mapping a compact convex set into itself there is a point x0 such that f(x0) = x0.

Can be proved using Sperner's Lemma.

Here is an outline of an intuitive 'proof' for a mapping on the reals from 0 to 1.

We will try to avoid a fixpoint to see how it is forced on us.

Starting with the point at '0', we cant map it to '0' or that would be a fixpoint, so it must map to some point greater than '0'.

fixpoint
Again with the point '1', since we are trying to avoid a fixpoint, we must map to some point less than '1'. fixpoint
Now we fill in the gaps. Since the mapping is continuous and '0' is increasing and '1' is decreasing, there must be some point in between that is fixed. There could be more than one fixpoint but there must be an odd number. fixpoint

We can extend this from the reals R to Rn. For instance, a classic example in R2 is a map. If a map is held over the land that it represents then there will always be at least one point on the map that is directly over the point that it represents.

Recursion

Recursion is related to fixpoints.

We can extend the map example above. If the map is so accurate that it shows itself on the map, then we have a form of recursion, with the map showing a map which shows an even smaller map and so on.

Then there will be a fixpoint that goes through the same point on all the maps.

fixpoint map

Example 2 - Finite Sets

fixpoint finite set

Here is an example of a fixpoint for a finite set.

I have drawn the arrows representing the endofunction internally. That is, not going out round the light blue arrow, this makes the diagram less cluttered although we may think of the endofunction as being external.

The red dot is a fixpoint, so we can apply the endofunction as many times as we like, it will always map to itself.

For a finite set, like this, following the arrows (applying endofunction repeatedly) will always lead us to a fixpoint or a loop.

Example 3 - Lattice

In a similar way to Brouwer's theorem above, we will try to construct a lattice endofunctor without fixpoints (to show that it can't be done).

We will start with bottom, since we are trying to avoid fixpoints this must map to a different point.

fixpoint

Similarly with top. fixpoint top

We must now map all the other nodes, in a way that respects the meet and join structure.

This does have a fixpoint as marked.

fixpoint lattice

Knaster-Tarski theorem

If L is a complete lattice, then every monotone (i.e., order-preserving) map

f : L → L has a fixed point

and the fixed points of f form a complete lattice.

proof

On the diagram (right), the nodes with a yellow background map to values with a lower or equal value (f(x)≤x), the nodes with a blue background map to values with a greater or equal value (x≤f(x)).

The intersection of this (green background) have both f(x)≤x and x≤f(x) that is x=f(x). In other words this is the fixpoint.

This works because:

  • top 'T' will always decrease or remain the same.
  • bottom '_|_' will always increase or remain the same.
  • We can only go between decreasing and increasing values by going through equal values, as shown below, so there will always be fixpoints.
knaster tarski proof
Imagine that, for a given edge, the highest node increased and the lowest node decreased. Then we would end up with intermediate nodes that are not in the codomain. fixpoint proof

Imagine that, for a given edge, the lowest node increased and the highest node decreased. Then f would not be monotone.

Therefore there must be fixpoints inbetween.

fixpoint proof

These fixed points form a complete lattice because if 'x' is a fixpoint and 'y' is a fixpoint then 'x/\y' is a fixpoint and 'x\/y' is a fixpoint.

For more discussion about mappings between lattices see page here.

Example 4 - Inductive Partial Order

Pataraia’s theorem

If L is an inductive partial order (ipo), then every monotone map f:L→L has a (least) fixed point.

Definition of ipo - A poset with a bottom element and joins of directed subsets

(related concept - An inductive poset is a poset in which every chain has an upper bound. )

Partially Ordered Sets

Bourbaki–Witt theorem

if X is a non-empty chain complete poset, and

f : XX

such that

for allx. f(x) ≥ x

then f has a fixed point.

Such a function f is called inflationary or progressive.

The proof is similar to Knaster-Tarski above.

  • top 'T' will always decrease or remain the same.
  • bottom '_|_' will always increase or remain the same.
  • We can only go between decreasing and increasing values by going through equal values, as shown below, so there will always be fixpoints.
bourbaki witt
Imagine that, for a given edge, the highest node increased and the lowest node decreased. Then we would end up with intermediate nodes that are not in the codomain. fixpoint proof

Imagine that, for a given edge, the lowest node increased and the highest node decreased. Then f would not be monotone.

Therefore there must be fixpoints inbetween.

fixpoint proof

Initial Algebra

initial algebra

An Initial Algebra is a fixpoint (Lambek’s theorem)

F A≡A

Kleene's recursion theorems

Quine

A quine is a computer program which takes no input and produces a copy of its own source code as its only output.

A quine is a fixed point of an execution environment, when the execution environment is viewed as a function


metadata block
see also:

other sites:

Correspondence about this page

Book Shop - Further reading.

Where I can, I have put links to Amazon for books that are relevant to the subject, click on the appropriate country flag to get more details of the book or to buy it from them.

cover Modern Graph Theory (Graduate Texts in Mathematics, 184)

Terminology and Notation

Specific to this page here:

 

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2017 Martin John Baker - All rights reserved - privacy policy.