Zeigen Sie mittels vollständiger Induktion, dass es 2^(|A|) verschiedene 2-Färbungen von A gibt

Question

Aufgabe:

Sei A eine nicht leere, endliche Menge. Eine Abbildung f heißt 2-Färbung von A, wenn sie jedem Element von A eine von zwei Farben zuweist.
Zeigen Sie mittels vollständiger Induktion, dass es \( 2^{|A| } \) verschiedene 2-Färbungen von A gibt

Problem/Ansatz:

könnte mir jemand mit dem Bewis helfen?

danke im Voraus für eure Hilfe.

Comments

Eine 2-Färbung von A mit |A|=n liegt vor, nachdem k aus n ausgewählt wurden und eine Farbe erhalten haben.(Die restlichen Elemente haben dann automatisch die zweite Farbe). Es geht also  um die Summe aller \( \begin{pmatrix} n\\k \end{pmatrix} \) mit k von 0 bis n. Dass diese Summe 2ⁿ ist, wurde schon so oft bewiesen, dass man sich fragt, was hier noch zu beweisen sei.

Answer 1

Für |A|=1 ist es wohl klar. Dem einzigen Element wird entweder die eine oder

die eine ( z.B. rot) oder die andere (z.B. blau) Farbe zugeordnet.

Es ginbt also zwei = 2^0 Abbildungen

f1: A → {rot, blau}  ; f1(a) = rot

und

f2: A → {rot, blau}  ; f2(a) = blau.

Gilt nun die Aussage für alle Mengen X mit |X|=n    #

und sei nun A eine n+1 elementige Menge.

Dann ist A nicht leer und enthält also ein Element a.

Und A \ {a} ist eine n-elementige Menge.

Sei nun f eine 2-Färbung von A, dann ist die Einschränkung

von f auf  A \ {a}  eine 2-Färbung von  A \ {a} .

Es gibt also gemäß # genau 2^n verschiedene

Einschränkungen von f auf  A \ {a}.

Und f entsteht aus einer solchen Einschränkung entweder

durch f(a) = rot oder durch f(a)=blau.

Also ist die Anzahl der Möglichkeiten für f

  2^n * 2 = 2^(n+1) .   Also gilt die Aussage auch

für (n+1) - elementige Mengen.   q.e.d.

Comments

Könntest du bitte nur zeigen wo IA IV IS sind bzw. wo sollen geschrieben werden oder wenn es einfacher wäre, füge bitte dein Klmmentar hier hinzu und schreib die an der richtige Stellen wenn es möglich wäre.danke schön

---

IA: 

Für |A|=1 ist es wohl klar. Dem einzigen Element wird entweder die eine oder

die eine ( z.B. rot) oder die andere (z.B. blau) Farbe zugeordnet.

Es ginbt also zwei = 20 Abbildungen

f1: A → {rot, blau}  ; f1(a) = rot

und

f2: A → {rot, blau}  ; f2(a) = blau.

 IV :  Gilt nun die Aussage für alle Mengen X mit |X|=n    #

IS : Rest!

Die Methode der vollst. Ind. musst du aber wohl noch was üben !

Answer 2

Ind.Anf.: Eine Menge mit einem Element kann in jeder der beiden Farben gefärbt werden, also auf 2¹ verschiedene Arten.

Ind.Vorr.: Eine Menge mit n Elementen kann auf 2ⁿ verschiedene Arten gefärbt werden.

Ind.Bew.: Ein neu hinzukommendes Element kann jede der beiden Farben haben. Die Anzahl der Färbungen verdoppelt sich also.