imported>Nhabedi: /* Verwendung in der Informatik */ Grammatik

2025-05-15T16:52:43Z

Verwendung in der Informatik: Grammatik

Neue Seite

In der [[Mathematik]] ist eine '''fundierte Menge''' (auch '''wohlfundierte Menge''', '''fundierte Ordnung''', '''terminierende Ordnung''', '''noethersche Ordnung''') eine [[Halbordnung|halbgeordnete Menge]], die keine unendlichen echt absteigenden Ketten enthält. Äquivalent dazu heißt eine halbgeordnete Menge ''fundiert'', wenn jede nichtleere [[Teilmenge]] mindestens ein [[minimales Element]] enthält.

Alle [[wohlgeordnete Menge|wohlgeordneten Mengen]] sind fundiert, weil in einer wohlgeordneten Menge jede nichtleere Teilmenge ein [[kleinstes Element]] haben muss und das kleinste Element einer Menge immer auch minimal ist. Anders als wohlgeordnete Mengen brauchen fundierte Mengen nicht [[Totalordnung|totalgeordnet]] zu sein. Alle total geordneten fundierten Mengen sind wohlgeordnet.

== Noethersche Induktion ==
Fundierte Mengen erlauben die Anwendung der noetherschen Induktion, einer Version der [[transfinite Induktion|transfiniten Induktion]]: Sei <math>P</math> eine Eigenschaft von Elementen einer unter einer Ordnungsrelation <math>\le</math> fundierten Menge <math>X</math> und sei die folgende Aussage wahr:
::Wenn <math>x</math> ein Element von <math>X</math> ist und <math>P(y)</math> für alle <math>y<x</math> wahr ist, dann ist auch <math>P(x)</math> wahr.
Dann ist <math>P(x)</math> wahr für alle Elemente <math>x</math> aus <math>X</math>.

== Verwendung in der Informatik ==

Siehe auch: [[Termersetzungssystem#Terminierung]]

[[Terminiertheit]] ist ein zentrales Konzept in der theoretischen Informatik. Obige Begriffe werden dazu von Ordnungen auf homogene Relationen <math>a \rightarrow b \in A \times A</math> abgeschwächt, wobei <math>a \rightarrow b</math> etwa den Schritt einer Berechnung repräsentiert. In diesem Zusammenhang ist ein Element <math>m</math> einer Teilmenge <math>B \subseteq A</math> <math>\rightarrow</math>-minimal, wenn für alle <math>x \in A</math> mit <math>m \rightarrow x</math> folgt <math>x \notin B</math>.<ref>{{Literatur |Autor=Wolfgang Wechler |Titel=Universal Algebra for Computer Scientists |Verlag=Springer-Verlag|Ort=Berlin |Datum=1992 |ISBN=3-540-54280-9 |Seiten=35-39}}</ref> Neben der Terminiertheit von Algorithmen können vermittels der Noetherschen Induktion dann deren Eigenschaften nachgewiesen werden.

== Beispiele ==
Die [[ganze Zahlen|ganzen Zahlen]], die [[rationale Zahlen|rationalen Zahlen]] und die [[reelle Zahlen|reellen Zahlen]] enthalten in ihrer natürlichen Anordnung jeweils unendliche absteigende Ketten und sind somit nicht fundiert.

Die [[Potenzmenge]] einer Menge mit der Teilmengenbeziehung als Ordnung ist genau dann fundiert, wenn die Menge [[endliche Menge|endlich]] ist. Alle endlichen halbgeordneten Mengen sind fundiert, weil endliche Mengen nur endliche Ketten haben können.

Die folgenden Mengen sind fundiert, aber nicht totalgeordnet:
* die [[natürliche Zahl|natürlichen Zahlen]] <math>\N=\left\{1, 2, 3, \ldots\right\}</math> mit der Ordnung
::<math>a\le b</math> genau dann, wenn <math>a</math> ein Teiler von <math>b</math> ist
* die Menge der Untermoduln eines [[noetherscher Modul|noetherschern Moduls]] mit der Ordnung
::<math>M\le N</math> genau dann, wenn <math>N\subseteq M</math>
* die Menge <math>\N\times\N</math> aller Paare natürlicher Zahlen mit der Ordnung
::<math>(m,n)\le(a,b)</math> genau dann, wenn <math>m\le a</math> und <math>n\le b</math>
* die Menge der endlichen [[Wort (Theoretische Informatik)|Wörter]] über einem vorgegebenen [[Alphabet (Informatik)|Alphabet]] mit der Ordnung
::<math>s\le t</math> genau dann, wenn <math>s</math> eine Teilzeichenkette von <math>t</math> ist
* die Menge der [[regulärer Ausdruck|regulären Ausdrücke]] über einem vorgegebenen Alphabet mit der Ordnung
::<math>s\le t</math> genau dann, wenn <math>s</math> ein Teilausdruck von <math>t</math> ist
* jede Menge von Mengen mit der Ordnung
::<math>A\le B</math> genau dann, wenn <math>A</math> ist ein Element von <math>B</math> (wirklich Element, nicht Teilmenge!)

== Länge absteigender Ketten ==
Ist <math>(X,\le)</math> eine fundierte Menge und <math>x \in X</math>, dann sind die bei <math>x</math> beginnenden absteigenden Ketten allesamt endlich, aber ihre Länge muss nicht beschränkt sein. Betrachte z. B. die Menge

:<math>X := \left\{(a,b) \in \N_0 \times \N_0 \mid a\ge b > 0 \vee a=b=0\right\}</math>

(wobei <math>\N_0=\left\{0, 1, 2, 3,\ldots\right\}</math>) mit der Ordnung

:<math>(m,n)\le(a,b)</math> genau dann, wenn <math>(a,b)=(0,0)</math> oder <math>m=a \wedge n\ge b</math>

Darin sind z. B. <math>(0,0)>(4,1)>(4,2)>(4,3)>(4,4)</math> und <math>(0,0)>(2,1)>(2,2)</math>. <math>X</math> ist fundiert, aber es gibt bei <math>(0,0)</math> beginnende absteigende Ketten beliebiger (endlicher) Länge.

== Siehe auch ==
* [[Strukturelle Induktion]]
* [[Wohlfundierte Relation]]

== Einzelnachweise ==
<references />

[[Kategorie:Ordnungstheorie]]
[[Kategorie:Theoretische Informatik]]

Fundierte Menge - Versionsgeschichte

imported>Nhabedi: /* Verwendung in der Informatik */ Grammatik