Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Beweis durch vollständige Induktion

Beweis durch vollständige Induktion

Universität / Fachhochschule

Sonstiges

Gruppen

Tags: Beweis, Gruppen, Induktion, Injektivität, Sonstig, surjektivität, Vollständig Induktion

Mai05 aktiv_icon

13:19 Uhr, 06.01.2021

Ich soll mit vollständiger Induktion folgende Aussage beweisen:
Sei n€N und A eine beliebige Menge mit

| A | = n

. Dann ist jede injektive Funktion

f : A \to A

auch surjektiv.

Ich weiß, dass Injektivität heißt: (für alle)

x

€

A : f (x 1) = f (x 2) \Rightarrow x 1 = x 2

und dass Surjetivität heißt: (für alle)

y

€ A (existiert ein) x€A:

f (x) = y

Außerdem kann ich der Aufgabenstellung entnehmen, dass

| P (A) | = 2^{n}

(keine Ahnung ob das nützlich ist, aber ich habe es erstmal aufgeschrieben, um Informationen zu sammeln)

Mein Problem ist, dass ich überhuapt keine Idee habe, wie ich die Informationen nutzen soll, um auf einen Induktonsanfang zu kommen.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Zu diesem Thema passende Musteraufgaben einblenden

DrBoogie aktiv_icon

14:01 Uhr, 06.01.2021

Es ist in diesem Fall deutlich einfacher, eine etwas allgemeinere Aussage zu Beweisen:
wenn

A

und

B

beide aus

n

Elementen bestehen und

f : A \to B

injektiv ist, dann ist

f

auch surjektiv.

Induktionsanfang:

n = 1

. In diesem Fall gibt's nur ein Element in

A

und nur ein Element in

B

, also

A = {a}

und

B = {b}

. Die Abbildung

A \to B

muss

a

auf

b

abbilden, denn sonst gibt's ja keine anderen Elemente. Daher ist in diesem Fall jede Abbildung (es gibt nur diese eine) sowohl injektiv als auch surjektiv.

Bei dem Induktionsschritt kann vorausgesetzt werden, dass für alle Mengen aus

\leq n

Elementen die Aussage stimmt. Wenn jetzt

A

und

B

aus

n + 1

Elemente bestehen,

A = {a_{1}, . . ., a_{n + 1}}

und

B = {\ b_{1}, . . ., b_{n + 1}}

, und

f : A \to B

injektiv ist, dann betrachten

\tilde{A} = {a_{1}, . . ., a_{n}}

und

\tilde{B} = B \ f (a_{n + 1})

. Die Einschränkung von

f

auf

\tilde{A}

ist injektiv, also nach Voraussetzung surjektiv. Damit

f (\tilde{A}) = \tilde{B}

. Und da

A = \tilde{A} \cup {a_{n + 1}}

und

B = \tilde{B} \cup f (a_{n + 1})

ist auch

f

surjektiv.

Mai05 aktiv_icon

14:25 Uhr, 06.01.2021

Im Großen und Ganzen verstehe ich das, aber warum kann ich beim Induktionsschritt voraussetzen, dass für alle Mengen, die aus weniger (oder genau)n Elementen bestehen, die Aussage stimmt?

JaBaa aktiv_icon

14:56 Uhr, 06.01.2021

Das ist enfaches Standardwissen über vollständige Induktion :-). Die Induktionsvorraussetzung gilt immer in Induktionsbeweisen.

Schaue dazu auch folgende Seite an:

de.wikibooks.org/wiki/Mathe_f%C3%BCr_Nicht-Freaks:_Vollst%C3%A4ndige_Induktion

Mai05 aktiv_icon

15:18 Uhr, 06.01.2021

Dass das für mind.

1 n

wahr ist, ist klar, das steht ja auch im Induktionsanfang, mich hat nur das "

\leq n

Elementen" verwirrt

1525460

1525430

	Status: nicht eingeloggt	Noch nicht registriert?