DISKRETE MATHEMATIK
Dr. E. Prisner, Dr. J. Sustal,
Dr. W. Preuß, S. Fröhlich,
Sommersemester 2000

9.1 Welche der geordneten Mengen rechts hat die Fixpunkteigenschaft?

9.2 Geben Sie eine Bijektion zwischen den Ordinalzahlen w und 2w+3 an.

9.3 Zeigen Sie, daß die Ordnungsrelationen R und S auf N₀ × N₀ Wohlordnungen sind, und finden Sie Ordinalzahlen, zu denen sie ordnungsisomorph sind. Dabei ist

• (x₁,y₁) R (x₂,y₂) falls (x₁ £ x₂ und x₁ ¹ x₂) oder (x₁ = x₂ und y₁ £ y₂) ist,
• (x₁,y₁) S (x₂,y₂) falls (x₁+y₁ £ x₂+y₂ und x₁+y₁ ¹ x₂+y₂) oder (x₁+y₁ = x₂+y₂ und x₁ £ x₂) ist.

9.4 Zeigen Sie, daß die Menge aller Graphen, für die es eine natürliche Zahl n gibt, so daß die Eckenmenge des Graphen die Menge {1,2,...,n} ist, abzählbar ist.