Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenDonnerstag, 14. November 2019 

Fundierte Menge


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Eine fundierte Menge ist eine halbgeordnete Menge die keine unendlichen absteigenden Ketten Eine halbgeordnete Menge ist genau dann fundiert jede nichtleere Teilmenge ein minimales Element enthält. die Ordnung total dann ist die Menge wohlgeordnet (jede nichtleere Teilmenge enthält ein kleinstes

Ein Grund warum fundierte Mengen interessant ist die Anwendbarkeit einer Version der transfiniten Induktion : Ist ( X <=) eine fundierte Menge P eine von Elementen aus X und man möchte zeigen dass P( x ) für alle Elemente x aus X wahr ist dann kann man versuchen zu beweisen:

  1. P( x ) ist wahr für alle minimalen Elemente X .
  2. Ist x ein Element von X und P( y ) wahr für alle y < x dann ist auch P( x ) wahr.

Beispiele fundierter Mengen:

  • jede wohlgeordnete Menge
  • jede endliche halbgeordnete Menge

Beispiele fundierter Mengen die nicht totalgeordnet

  • die natürlichen Zahlen N ={1 2 3 ...} mit der Ordnung a <= b gdw. a teilt b
  • die Menge N × N aller Paare natürlicher Zahlen mit der ( m n )<=( a b ) gdw. m <= a und n <= b
  • die Menge der endlichen Zeichenketten über vorgegebenen Alphabet mit der Ordnung s <= t gdw. s ist eine Teilzeichenkette von t
  • die Menge der regulären Ausdrücke über vorgegebenen Alphabet mit der Ordnung s <= t gdw. s ist ein Teilausdruck von t
  • jede Menge von Mengen mit der A <= B gdw. A ist ein Element von B (wirklich Element nicht Teilmenge!)

Beispiele von nicht fundierten Mengen:

Ist ( X <=) eine fundierte Menge und x aus X dann sind die bei x beginnenden absteigenden Ketten allesamt endlich aber Länge muss nicht beschränkt sein. Betrachte z.B. Menge

X := {( a b ) | a b aus N 0 a >= b > 0 oder a = b =0}

(wobei N 0 ={0 1 2 3 ...}) mit der

( m n )<=( a b ) gdw. ( a b )=(0 0) oder ( m = a und n >= b )

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



Bücher zum Thema Fundierte Menge

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Fundierte_Menge.html">Fundierte Menge </a>