In der Mathematik ist eine binäre Beziehung, R, wohl begründet (oder wohl begründet), auf einer Klasse X, wenn, und nur wenn jede nichtleere Teilmenge X ein minimales Element in Bezug auf R hat; d. h. für jede nichtleere Teilmenge S X gibt es ein Element M von solchem S, dass für jedes Element s S das Paar (s, m) nicht in R ist:

(Einige Autoren schließen eine Extrabedingung ein, dass R einem Satz ähnlich ist, d. h., dass die Elemente weniger als jedes gegebene Element einen Satz bilden.)

Gleichwertig, etwas Wahl annehmend, ist eine Beziehung wohl begründet, wenn, und nur wenn es keine zählbaren unendlichen hinuntersteigenden Ketten enthält: D. h. es gibt keine unendliche Folge x, x, x... Elemente X solch dass x R x für jede natürliche Zahl n.

In der Ordnungstheorie wird eine teilweise Ordnung wohl begründet genannt, wenn die entsprechende strenge Ordnung eine wohl begründete Beziehung ist. Wenn die Ordnung ein Gesamtbezug dann ist, wird es eine Gut-Ordnung genannt.

In der Mengenlehre wird ein Satz x einen wohl begründeten Satz genannt, wenn die Satz-Mitgliedschaft-Beziehung auf dem transitiven Verschluss von x wohl begründet ist. Das Axiom der Regelmäßigkeit, die eines der Axiome der Zermelo-Fraenkel Mengenlehre ist, behauptet, dass alle Sätze wohl begründet sind.

Eine Beziehung R ist wohl begründet, aufwärts wohl begründet oder Noetherian auf X gegenteilig, wenn die gegenteilige Beziehung R auf X wohl begründet ist. In diesem Fall, wie man auch sagt, befriedigt R die steigende Kettenbedingung.

Induktion und recursion

Ein wichtiger Grund, dass wohl begründete Beziehungen interessant sind, besteht darin, weil eine Version der transfiniten Induktion auf ihnen verwendet werden kann: Wenn (X, R) eine wohl begründete Beziehung ist, P (x) ist ein Eigentum von Elementen X, und wir wollen dem zeigen

:P (x) hält für alle Elemente x von X,

es genügt, um dass zu zeigen:

: Wenn x ein Element X ist und P (y) für den ganzen solchen y wahr ist, dass y R x, dann muss P (x) auch wahr sein.

Das, ist

Wohl begründete Induktion wird manchmal Induktion von Noetherian nach Emmy Noether genannt.

Gleichwertig mit der Induktion unterstützen wohl begründete Beziehungen auch Aufbau von Gegenständen durch transfiniten recursion. Lassen Sie (X, R), eine einem Satz ähnliche wohl begründete Beziehung und F eine Funktion zu sein, die einen Gegenstand F (x, g) jedem Paar eines Elements x  X und eine Funktion g auf dem anfänglichen Segment {y zuteilt: y R x\X. Dann gibt es eine einzigartige Funktion G solch das für jeden x  X,

D. h. wenn wir eine Funktion G auf X bauen wollen, können wir G (x) das Verwenden der Werte von G (y) für y R x definieren.

Als ein Beispiel, denken Sie die wohl begründete Beziehung (N, S), wo N der Satz aller natürlichen Zahlen ist, und S der Graph der Nachfolger-Funktion x  x + 1 ist. Dann ist die Induktion auf S die übliche mathematische Induktion, und recursion auf S gibt primitiven recursion. Wenn wir die Ordnungsbeziehung (N, n), m) wenn und nur wenn n und n denken.

• der Satz aller regelmäßigen Ausdrücke über ein festes Alphabet, mit der durch s definierten Ordnung ("ist ein Element"). Das ist das Axiom der Regelmäßigkeit.
• die Knoten von irgendwelchem begrenzt haben angeordnet, dass acyclic Graph mit der Beziehung R solch dass ein R b wenn und nur definiert hat, wenn es einen Rand von bis b gibt.

Beispiele von Beziehungen, die nicht wohl begründet sind, schließen ein:

• die negativen ganzen Zahlen {-1,-2,-3, …}, mit der üblichen Ordnung, seit jeder unbegrenzten Teilmenge haben nicht kleinstes Element.
• Der Satz von Schnuren über ein begrenztes Alphabet mit mehr als einem Element, laut der üblichen (lexikografischen) Ordnung, seit der Folge "B"> "AB"> "AAB"> "AAAB"> … ist eine unendliche hinuntersteigende Kette. Diese Beziehung scheitert, wohl begründet zu sein, wenn auch der komplette Satz ein minimales Element, nämlich die leere Schnur hat.
• die rationalen Zahlen (oder reals) unter der Standardeinrichtung, seitdem, zum Beispiel, der Satz von positivem rationals (oder reals) haben an einem Minimum Mangel.

Andere Eigenschaften

Wenn (X. Um diese trivialen hinuntersteigenden Folgen zu vermeiden, wenn man mit einer reflexiven Beziehung R arbeitet, ist es üblich zu verwenden (vielleicht implizit) die abwechselnde Beziehung R  hat solch dass ein R  b wenn und nur wenn ein R b und ein  b definiert. Im Zusammenhang der natürlichen Zahlen bedeutet das dass die Beziehung