M. Sperber Sommersemester 1997

Funktionale Programmierung

Blatt 7

Abgabe: 12.6.1997

1. [5 Punkte] Geben Sie Beispiele für partielle Halbordnungen , und an, so daß
   1. X keine obere Schranke hat,
   2. X zwei obere Schranken, aber kein Supremum hat,
   3. X unendlich viele obere Schranken, aber kein Supremum hat.
2. [5 Punkte] Seien D und E vollständige Halbordnungen, wobei alle aufsteigenden Ketten in D abbrechen. Zeigen Sie, daß alle monotonen Funktionen stetig sind.
3. [10 Punkte]
   1. Wieviele Funktionen gibt es? Wieviele davon sind strikt? Wieviele monoton?
   2. Geben Sie alle monotonen Fortsetzungen der Funktionen and und or (mit den offensichtlichen Definitionen) auf . Zeichnen Sie Hasse-Diagramme für die Inklusionsbeziehungen zwischen den verschiedenen Fortsetzungen. Was ist die operationelle Intuition der einzelnen Fortsetzungen?
   3. Bestimmen Sie alle monotonen Fortsetzungen von .
4. [10 Punkte] Benutzen Sie den Fixpunktsatz über vollständigen Halbordnungen, um den Satz von Schröder-Bernstein zu beweisen:

   Seien S und T Mengen. Wenn und Injektionen sind, so gibt es eine Bijektion .

   Hinweis: Betrachten Sie die Funktion mit

   

   und ihren Fixpunkt Y, vereinfachen Sie die Beschreibung von Y mit Mitteln aus der Mengenlehre, und konstruieren Sie aus f und mit Hilfe von g und Y die Bijektion.

• Über dieses Dokument ...