Mathematik und Logik

9. Übungsaufgaben im 2007W

für 2007-12-11

1. Beweisen Sie die aussagelogische Formel
   

   ¬(A∧B) ⇔ ¬A ∨ ¬B.

   Versuchen Sie, diese Aussage ohne Prinzip des ausgeschlossenen Dritten zu beweisen, und verwenden Sie für diejenige Richtung, für die das nicht möglich ist, (und nur für diese) eine Wahrheitstafel.
2. Beweisen Sie
   

   ¬∀x∊XP(x) ⇔ ∃x∊X¬P(x),

   und verwenden sie auch hier das Prinzip des ausgeschlossenen Dritten nur für jene Richtung, für die es notwendig ist.
3. Zeigen Sie, daß ℕ und ℕ˟ gleichmächtig sind.
4. Seien A,B,C beliebige Mengen. Warum sind die Menge aller Funktionen vom Typ A→B→C und die Menge aller Funktionen vom Typ A×B → C gleichmächtig? (Anmerkung: Dies läßt sich auch als
   

   ⎜CA ×B⎟ = ⎜CBA⎟

   lesen.)
5. Sei X irgendeine Menge, und \mathbb B =⎨⊥,⊤⎬ . Zeigen Sie, daß X niemals gleichmächtig zu \mathbb B^X sein kann.
   Hinweis: Nehmen Sie an, f∊ℕ→(ℕ→\mathbb B) und g∊(ℕ→\mathbb B)→ℕ sei ein passendes Paar von Funktionen und betrachten Sie w definiert durch
   

   w(n) = ¬(f(n)(n)).

   Leiten Sie daraus einen Widerspruch her.
6. Eine Funktion f∊X→Y heißt injektiv wenn
   

   ∀x,y∊X(f(x)=f(y) \implies x=y).

   Finden Sie eine injektive Funktion von ℕ nach ℤ, und auch eine von ℤ nach ℕ.
7. Sei X eine endliche Menge. Dann gibt es genau ein n∊ℕ, sodaß X gleichmächtig zu ⎨0,1,…,n−1⎬ ist. Man schreibt dann ⎜X⎟=n. Zeigen Sie mittels Induktion
   

   ⎜\mathbb BX⎟=2⎜X⎟.
8. Für jede Menge X und k∊ℕ bezeichne \binom X k die Menge aller Teilmengen von X mit exakt k Elementen. (\binom X k ist also eine Teilmenge der Potenzmenge.)
   Sei Y eine weitere Menge. Zeigen Sie
   

   ⎜\binom X k⎟=⎜\binom Y k⎟,

   wann immer ⎜X⎟=⎜Y⎟.