Bourbaki–Witt theorem

Bourbaki–Witt theorem

In mathematics, the Bourbaki–Witt theorem in order theory, named after Nicolas Bourbaki and Ernst Witt, is a basic fixed-point theorem for partially ordered sets. It states that if "X" is a chain complete poset, and

: f : X o X

such that

: f (x) geq x,

then "f" has a fixed point. Such a function "f" is called "inflationary" or "progressive".

Proof

The most common proof of the theorem is unwieldy and involved, so this is often thought of as a hard theorem. Here is a sketch of a shorter proof, done by recursion on the ordinals.

Pick some y in X. Define a function "K" recursively on the ordinals as follows:

:,K(0) = y

:,K( alpha+1 ) = f( K( alpha ) ).

If eta is a limit ordinal, then by construction

:{ K( alpha ) : alpha < eta }

is a chain in "X". Define

:K( eta ) = sup { K( alpha ) : alpha < eta }.

This is now an increasing function from the ordinals into "X". It cannot be strictly increasing, as if it were we would have an injective function from the ordinals into a set, violating Hartogs' lemma. Therefore the function must be eventually constant, so for some

: alpha , K( alpha+1 ) = K ( alpha );

that is,

:,f( K( alpha ) ) = K ( alpha ).

So letting

:,x = K ( alpha ),

we have our desired fixed point. Q.E.D.

Applications

The Bourbaki–Witt theorem has various important applications. One of the most common is in the proof that the axiom of choice implies Zorn's lemma. We first prove it for the case where "X" is chain complete and has no maximal element. Let "g" be a choice function on

:P(X) - { varnothing }.

Define a function

:f : X o X

by

:f(x) = g( { y : y > x } ).

This is allowed as, by assumption, the set is non-empty. Then "f"("x") > "x", so "f" is an inflationary function with no fixed point, contradicting the theorem.

This special case of Zorn's lemma is then used to prove the Hausdorff maximality principle, that every poset has a maximal chain, which is easily seen to be equivalent to Zorn's Lemma.

Bourbaki–Witt has other applications. In particular in computer science, it is used in the theory of computable functions.It is also used to define recursive data types, e.g. linked lists, in domain theory.

ee also

* Nicolas Bourbaki


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Poincaré–Birkhoff–Witt theorem — In the theory of Lie algebras, the Poincaré–Birkhoff–Witt theorem (Poincaré (1900), G. D. Birkhoff (1937), Witt (1937); frequently contracted to PBW theorem) is a result giving an explicit description of the universal enveloping algebra of a Lie… …   Wikipedia

  • Witt's theorem — or the Witt theorem may also refer to the Bourbaki–Witt fixed point theorem of order theory. Witt s theorem, named after Ernst Witt, concerns symmetric bilinear forms on finite dimensional vector spaces. It tells us when we can extend an isometry …   Wikipedia

  • Nicolas Bourbaki — This article is about the group of mathematicians named Nicolas Bourbaki. For the family of French officers named Bourbaki, see Bourbaki family (disambiguation). For the computer scientist, see Nikolaos Bourbakis. Nicolas Bourbaki is the… …   Wikipedia

  • Ernst Witt — (June 26 1911 July 3 1991) was a German mathematician born on the island of Als, (German: Alsen ). Shortly after his birth, he and his parents moved to China, and he didn t return to Europe until he was nine.After his schooling, Witt went to the… …   Wikipedia

  • Fixed point theorem — 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. Results of this kind are amongst the …   Wikipedia

  • List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… …   Wikipedia

  • List of theorems — This is a list of theorems, by Wikipedia page. See also *list of fundamental theorems *list of lemmas *list of conjectures *list of inequalities *list of mathematical proofs *list of misnamed theorems *Existence theorem *Classification of finite… …   Wikipedia

  • Chain complete — In mathematics, a partially ordered set in order theory is chain complete if every chain in it has a least upper bound. Unlike complete posets, chain complete posets are relatively common. Examples include: Any complete poset The set of all… …   Wikipedia

  • Free Lie algebra — In mathematics, a free Lie algebra, over a given field K, is a Lie algebra generated by a set X, without any imposed relations. Contents 1 Definition 2 Universal enveloping algebra 3 Hall sets …   Wikipedia

  • mathematics — /math euh mat iks/, n. 1. (used with a sing. v.) the systematic treatment of magnitude, relationships between figures and forms, and relations between quantities expressed symbolically. 2. (used with a sing. or pl. v.) mathematical procedures,… …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”