Mathematik und Logik

10. Übungsaufgaben im 2007W

für 2008-01-08

1. Wiederholen Sie die Beispiele der letzten beiden Wochen.
2. Es sei M = ⎨G, P, W,M, E, C, J⎬ eine Menge von Mitarbeitern und A=⎨A, S, F, H⎬ eine Menge von Abteilungen. Die Relation Z∊M→A→ℙ sei so definiert, daß x→^Z y bedeutet, daß der Mitarbeiter x für die Abteilung y arbeitet. Für eine konkrete Firma könnte dies folgendermaßen aussehen:
   

   Z=⎨ (G,A), (P,S), (W, S), (W, A), (M, A), (M, S), (E, F), (M, F), (C, H), (C, A), (J, S) ⎬.

   Bestimmen Sie Z⁻¹ sowie Z⁻¹;Z und Z;Z⁻¹. Was bedeuten diese Relationen?
3. Weiters bedeute x→^D y, daß x an y Arbeit delegiert. Für unsere Firma sei dies folgendermaßen definiert:
   

   D=⎨ (G, C), (G, W), (C, M), (W, E), (E, M), (P, W), (P, M), (P, J), (J, W), (J, M) ⎬ .

   Bestimmen Sie, sofern definiert, S;D, D; S, S², D². Interpretieren Sie diese Relationen auch inhaltlich.
4. Eine Relation R in X heißt transitiv, wenn für alle x,y,z∊X gilt
   

   x R →   y ∧ y R →   z \implies x R →   z.

   Zeigen Sie, daß R genau dann transitiv ist, wenn R²⊆ R.
   Ist die Relation D (von oben) transitiv. Ist D² transitiv? D∪D²?
   Berechnen Sie
   

   D⁺ : = D∪ D2 ∪ D³ ∪ D4 ∪ ….

   Überzeugen Sie sich, daß D⁺ transitiv ist. Kann es eine kleinere Relation geben, die D umfaßt und transitiv ist? Interpretieren Sie D⁺ inhaltlich.
5. Sei \prec die Vorgänger-Relation in ℕ definiert durch
   

   x\prec y :⇔ 1+x=y.

   Bestimmen sie die transitive Hülle \prec⁺. Kennen Sie diese Relation?
6. Eine Relation R in X heißt reflexiv, wenn x→^R x für alle x∊X gilt. Sie ist eine Quasiordnung wenn sie reflexiv und transitiv ist. Mit R^* bezeichnen wir dann jene Relation, die gerade groß genug ist, daß sie R umfaßt und eine Quasiordnung ist (genannt auch die reflexiv-transitive Hülle) Zeigen Sie, daß
   

   D* : = D0∪ D¹ ∪ D2 ∪ D³ ∪ D4 ∪ ….

   (Wie muß dabei D⁰ definiert werden?)
   Bestimmen Sie die reflexiv-transitive Hülle \prec^* der Vorgänger-Relation von oben.
7. Betrachten Sie die Teilbarkeitsrelation in ℤ. Warum ist diese eine Quasiordnung?
   Überzeugen Sie sich, daß die Relation ≡ :X→X→ℙ, definiert durch
   

   x ≡ y :⇔ x Q →   y ∧ y Q →   x,

   für jede Quasiordnung Q∊X→X→ℙ eine Äquivalenzrelation ergibt. Was ergibt sich dabei speziell für die Teilbarkeitsrelation?
8. Es sei \prec:Σ˟→Σ˟→ℙ jene Relation, welche gerade umfassend genug ist, sodaß für alle u∊Σ˟ und α∊Σ gilt
   

   u\prec α◅u.

   Beschreiben Sie reflexiv-transitive Hülle \prec˟ möglichst direkt.