In den mathematischen Gebieten der Ordnung und Gitter-Theorie setzt der Lehrsatz von Knaster-Tarski, genannt nach Bronisław Knaster und Alfred Tarski, den folgenden fest:

:Let L, ein ganzes Gitter sein und f zu lassen: L  L, eine Ordnung bewahrende Funktion sein. Dann ist der Satz von festen Punkten von f in L auch ein ganzes Gitter.

Es war Tarski, der das Ergebnis in seiner allgemeinsten Form festgesetzt hat, und so ist der Lehrsatz häufig als der feste Punkt-Lehrsatz von Tarski bekannt. Eine Zeit früher haben Knaster und Tarski das Ergebnis für den speziellen Fall eingesetzt, wo L das Gitter von Teilmengen eines Satzes, das Macht-Satz-Gitter ist.

Der Lehrsatz hat wichtige Anwendungen in der formellen Semantik von Programmiersprachen.

Eine Art gegenteiliger von diesem Lehrsatz wurde von Anne C. Davis bewiesen: Wenn jede Ordnung, die Funktion f bewahrt: L  L auf einem Gitter hat L einen festen Punkt, dann ist L ein ganzes Gitter.

Folgen: meist und größte feste Punkte

Da ganze Gitter, der Lehrsatz in besonderen Garantien die Existenz von mindestens einem festem Punkt von f und sogar die Existenz von kleinsten nicht leer (oder am größten sein können) befestigter Punkt. In vielen praktischen Fällen ist das die wichtigste Implikation des Lehrsatzes.

Kleinster fixpoint von f ist kleinstes Element x solch dass f (x) = x, oder, gleichwertig, solch dass f (x)  x; der Doppel-hält für den größten fixpoint, das größte Element x solch dass f (x) = x.

Wenn f (lim x) =lim f (x) für alle steigenden Folgen x, dann ist kleinster fixpoint von f lim f (0), wo 0 kleinstes Element von L ist, so eine "konstruktivere" Version des Lehrsatzes gebend. (Sieh: Fixpunktsatz von Kleene.) Mehr allgemein, wenn f monotonisch ist, dann ist kleinster fixpoint von f die stationäre Grenze von f (0), α über die Ordnungszahlen nehmend, wo f durch die transfinite Induktion definiert wird: f = f (f) und f für eine Grenze ist Ordnungs-γ das am wenigsten obere, das des f für alle β Ordnungszahlen weniger gebunden ist als γ. Der Doppellehrsatz hält für den größten fixpoint.

Zum Beispiel, in der theoretischen Informatik, werden am wenigsten feste Punkte von Eintönigkeitsfunktionen verwendet, um Programm-Semantik zu definieren. Häufig wird eine mehr spezialisierte Version des Lehrsatzes verwendet, wo, wie man annimmt, L das Gitter aller Teilmengen eines bestimmten durch die Teilmenge-Einschließung bestellten Satzes ist. Das widerspiegelt die Tatsache, dass in vielen Anwendungen nur solche Gitter betrachtet werden. Man sucht dann gewöhnlich nach dem kleinsten Satz, der das Eigentum hat, ein fester Punkt der Funktion f zu sein. Abstrakte Interpretation macht großen Gebrauch des Lehrsatzes von Knaster-Tarski und der Formeln, die meist und größten fixpoints geben.

Lehrsatz von Knaster-Tarski kann für einen einfachen Beweis des Cantor-Bernstein-Schroeder Lehrsatzes verwendet werden.

Schwächere Versionen des Lehrsatzes

Schwächere Versionen des Lehrsatzes von Knaster-Tarski können für bestellte Sätze formuliert werden, aber mehr komplizierte Annahmen einschließen. Zum Beispiel:

:Let L, ein teilweise bestellter Satz mit dem kleinsten Element (Boden) sein und f zu lassen: L  L, eine Ordnung bewahrende Funktion sein. Denken Sie weiter dort besteht u in solchem L dass f (u)  u und dass jede Kette in der Teilmenge {x in L: x  f (x), x  hat u\Supremum. Dann lässt f den am wenigsten festen Punkt zu.

Das kann angewandt werden, um verschiedene Lehrsätze auf Invariant-Sätzen, z.B der Lehrsatz von Ok zu erhalten:

:For die Eintönigkeitskarte F: P (X)  P (X) auf der Familie von (geschlossenen) nichtleeren Teilmengen X der folgende sind gleichwertig: (o) gibt F in P (X) s.t zu., (i) gibt F zu, dass invariant in P (X) d. h., (ii) untergehen, gibt F zu, dass maximale invariant A, (ii) setzen, gibt F zu, dass die größten invariant A setzen.

Insbesondere mit dem Grundsatz von Knaster-Tarski kann man die Theorie von globalem attractors für nichtzusammenziehende diskontinuierliche (mehrgeschätzte) wiederholte Funktionssysteme entwickeln. Für schwach zusammenziehende wiederholte Funktionssysteme genügt Lehrsatz von Kantorovitch fixpoint.

Andere Anwendungen fester Punkt-Grundsätze für bestellte Sätze kommen aus der Theorie von unterschiedlichen, integrierten und Maschinenbediener-Gleichungen.

Beweis

Wollen wir den Lehrsatz neu formulieren.

Für ein ganzes Gitter und eine Eintönigkeitsfunktion auf L ist der Satz des ganzen fixpoints von f auch ganzes Gitter, mit:

• als der größte fixpoint von f

• als kleinster fixpoint von f.

Beweis. Wir beginnen, indem wir zeigen, dass P am wenigsten und größtes Element hat. Lassen Sie D = {x | x  f (x)} und x  D (wir wissen, dass mindestens 0 D gehören). Dann, weil f Eintönigkeit ist, haben wir f (x)  f (f (x)), der f (x)  D ist.

Lassen Sie jetzt u = D. Then x  u und f (x)  f (u), so x  f (x)  f (u). Deshalb f ist (u) ein D gebundener oberer, aber u ist das gebundene am wenigsten obere, so u  f (u), d. h. u  D. Then f (u)  D und f (u)  u, von dem f (u) = u folgt. Weil jeder fixpoint in D ist, haben wir das u ist der größte fixpoint von f.

Die Funktion f ist Eintönigkeit auf dem (ganzen) Doppelgitter. Da wir uns gerade erwiesen haben, besteht sein größter fixpoint dort. Es sind kleinste ein auf L, so hat P am wenigsten und größte Elemente, oder mehr allgemein, dass jede Eintönigkeitsfunktion auf einem ganzen Gitter am wenigsten und größter fixpoints hat.

Wenn ein  L und b  L, wir [a, b] für den geschlossenen Zwischenraum mit Grenzen a und b schreiben werden: {x  L | ein  x  b}. Wenn ein  b, dann [a, b] ist ein ganzes Gitter.

Es muss, bewiesen zu werden, dass P ganzes Gitter ist. Lassen Sie 1 = L, W  P und w = W. Well zeigen dass f ([w, 1])  [w, 1]. Tatsächlich für jeden x  W haben wir x = f (x)  f (w). Da w das am wenigsten obere ist, das W, w  f (w) gebunden ist. Dann von y  [w, 1] folgt dem w  f (w)  f (y), f (y)  [w, 1] oder einfach f ([w, 1])  [w, 1] gebend. Das erlaubt uns, auf f als eine Funktion auf dem ganzen Gitter [w, 1] zu schauen. Dann hat es kleinsten fixpoint dort, uns das W gebundene am wenigsten obere gebend. Gezeigter Weve, dass die willkürliche Teilmenge von P Supremum hat, das P ins ganze Gitter verwandelt.

Siehe auch

• Lehrsatz von Kleene fixpoint
• Lehrsatz von Kantorovitch fixpoint (bekannt auch als Grundsatz von Tarski-Kantorovitch fixpoint)
• Modaler μ-calculus

Zeichen

Neue Entwicklungen

Links

• J. B. Nation, Zeichen auf der Gitter-Theorie.