Induktion < Lin. Algebra/Vektor < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:03 Do 20.10.2005 | | Autor: | Nataliee |
Hallo zunächst mal das Formale:
Seien n eine natürliche Zahl und A eine Menge mit n Elementen. zeigen Sie durch vollständige Induktion:
Die Anzahl der Paare [mm] (X_1,X_2) [/mm] element P(A) kreuz P(A) mit [mm] X_1 [/mm] Schnittmenge [mm] X_2 [/mm] = leere Menge ist [mm] 3^n.
[/mm]
Also hab ein Überblick über Induktion und verstehe auch den Inhalt der Aufgabe aber diese scheint mir zu schwer und ich hoffe jemand kann mir sie einwenig erklären.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:28 Do 20.10.2005 | | Autor: | Stefan |
Hallo Nataliee!
Es sei [mm] $a_1 \in [/mm] A$ fest gewählt.
Dann musst du dir klar machen, dass die Elemente $(X,Y)$ aus
[mm] ${\cal P}(A \setminus \{a_1\}) \times {\cal P}(A \setminus \{a_1\})$,
[/mm]
[mm] $({\cal P}(A) \setminus {\cal P}(A \setminus \{a_1\})) \times {\cal P}(A\setminus \{a_1\})$
[/mm]
und
[mm] ${\cal P}(A\setminus \{a_1\}) \times ({\cal P}(A) \setminus {\cal P}(A \setminus \{a_1\}))$
[/mm]
mit $X [mm] \cap [/mm] Y = [mm] \emptyset$ [/mm] jeweils die gleichen sind!
Nach Induktionsannahme enthält [mm] ${\cal P}(A \setminus \{x_1\}) \times {\cal P}(A \setminus \{x_1\})$ [/mm] aber [mm] $3^{n-1}$ [/mm] solcher Elemente, also auch [mm] $({\cal P}(A) \setminus {\cal P}(A \setminus \{a_1\})) \times {\cal P}(A\setminus \{a_1\})$ [/mm] und [mm] ${\cal P}(A\setminus \{a_1\}) \times ({\cal P}(A) \setminus {\cal P}(A \setminus \{a_1\}))$.
[/mm]
Nun kann aber offenbar
[mm] $({\cal P}(A) \setminus {\cal P}(A \setminus \{a_1\}) \times ({\cal P}(A) \setminus {\cal P}(A\setminus \{a_1\}))$
[/mm]
keine solcher Elemente $(X,Y)$ mit $X [mm] \cap [/mm] Y [mm] =\emptyset$ [/mm] enthalten (wegen [mm] $a_1 \in [/mm] X$ und [mm] $a_1 \in [/mm] Y$).
Damit ist alles gezeigt. 
Liebe Grüße
Stefan
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:10 Do 20.10.2005 | | Autor: | Nataliee |
DAnke, bin etwas am Grübeln wo nun die volständige Induktion steckt. Kann man das vielleicht besser an diesem Beispiel zeigen ?
Seien n eine natürliche Zahl und A eine Menge mit n Elementen. zeigen Sie durch vollständige Induktion:
Die Anzahl der Elemente von P(A) ist [mm] 2^n.
[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:19 Do 20.10.2005 | | Autor: | Stefan |
Hallo!
Ich habe doch geschrieben, wo ich die Induktionsvoraussetzung verwende. ![[haee]](/images/smileys/haee.gif "[haee]")
Naja, egal, zur nächsten Aufgabe:
Sei [mm] $a_1 \in [/mm] A$ beliebig gewählt. Dann enthält [mm] ${\cal P}(A \setminus\{a_1\})$ [/mm] nach Induktionsvoraussetzung [mm] $2^{n-1}$ [/mm] Elemente. Via
[mm] $\begin{array}{ccc} {\cal P}(A \setminus \{a_1\}) & \to & {\cal P}(A) \setminus {\cal P}(A \setminus \{a_1\}) \\[5pt] X & \mapsto & X \cup \{a_1\} \end{array}$
[/mm]
wird eine Bijektion zwischen [mm] ${\cal P}(A \setminus \{a_1\})$ [/mm] und [mm] ${\cal P}(A) \setminus {\cal P}(A \setminus \{a_1\})$ [/mm] gegeben. Daher gilt
[mm] $|{\cal P}(A)| [/mm] = | [mm] {\cal P}(A \setminus \{a_1\})| [/mm] + | [mm] {\cal P}(A) \setminus {\cal P}(A \setminus \{a_1\})| [/mm] = 2 [mm] \cdot [/mm] | [mm] {\cal P}(A \setminus \{a_1\}) [/mm] | = 2 [mm] \cdot 2^{n-1} [/mm] = [mm] 2^n$.
[/mm]
Liebe Grüße
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:00 Do 20.10.2005 | | Autor: | Nataliee |
Ok nun ist es irgenwie klarer geworden danke
|
|
|
|
