Beweis mit der vollständiger Induktion, dass Γ+^k ({0,1}) = {0,1,.......,2^k } für alle k∈ℕ gilt.

Question

Hi Guys,

 

Ich habe eine Aufgab für euch:

 

Zeigen Sie mittels vollständiger Induktion, dass Γ₊^k ({0,1}) = {0,1,.......,2^k } für alle k∈ℕ gilt.

 

 

Nachtrag: Definiton:

Es sei f: Aⁿ → A eine n-stellige Funktion(Operation).Dann sind die Abbildungen Γ_ƒ : P(A) →P(A) sowie

Γ_ƒ^k : P(A) →P(A) für alle k∈ℕ wie folgt definiert (für B⊆A):

Γ⁰_ƒ(B) = _def B

Γ^k_f(B) = _def Γ_ƒ^k-1 (B) ∪ {ƒ(a₁,....,a_n)|a₁,.....,a_n∈Γ_ƒ^k-1(B)}

Die Menge Γ_f (B) heißt Abschluss von B unter ƒ

Comments

Welches Gamma ist hier gemeint?

https://de.wikipedia.org/wiki/Gammafunktion scheint auf den ersten Blick nicht zu passen.

Grössere Auswahl an Gammasymbolen https://de.wikipedia.org/wiki/Gamma

@Anonym: Bitte wählen.

---

Definiton:

 

Es sei f: Aⁿ → A eine n-stellige Funktion(Operation).Dann sind die Abbildungen Γ_ƒ : P(A) →P(A) sowie

Γ_ƒ^k : P(A) →P(A) für alle k∈ℕ wie folgt definiert (für B⊆A):

Γ⁰_ƒ(B) = _def B

Γ^k_f(B) = _def Γ_ƒ^k-1 (B) ∪ {ƒ(a₁,....,a_n)|a₁,.....,a_n∈Γ_ƒ^k-1(B)}

 

Die Menge Γ_f (B) heißt Abschluss von B unter ƒ

Answer 1

Behauptung Γ₊^k ({0,1}) = {0,1,.......,2k } für alle k∈ℕ

P(A) dürfte die Potenzmenge von A sein.

+ ist eine zweistellige Operation (Funktion)

Verankerung: k=1

Γ₊⁰(B) = _def B = {0,1}

Γ₊^1(B) = Γ₊^0(B) u {0,1,2} = {0,1,2^1}   

 

Induktionsschritt k----> k+1 (Pluszeichen gezählt: Es kommt eines dazu)

Behauptung Γ₊^{k+1} ({0,1}) = {0,1,.......,2^{k+1} } für alle k∈ℕ gilt.

 

Beweis

Γ₊^k+1(B) =  Γ₊^k (B) ∪ {+(a1,a2)|a1,a2∈Γ₊^k(B)}
Als Summe von 2 Elementen von Γƒ^k(B) kommt nach Induktionsvoraussetzung maximal 2^k+2^k= 2*2^k = 2^{k+1}  raus. Das ist das verlangte grösste Element der zweiten Menge. Vereinigt mit allen möglichen Summen auch von 2 kleineren Elementen erreicht die Resultatmenge alle Zahlen von 0 bis 2^{k+1}. Also:

Γ₊^{k+1} (B) = {0,1,2,3,…2^{k+1}} qed Induktionsschritt.