TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 24

Aus VoWi
Zur Navigation springen Zur Suche springen

Wo steckt der Fehler im "Beweis" der Behauptung:

Je zwei natürliche Zahlen a,b sind gleich groß.

Beweis: vollständige Induktion nach dem \max\{a, b\}

a) \max\{a, b\} = 0: Hier gilt a = b = 0. Induktionsanfang

b) Die Behauptung gelte für \max\{a, b\} = n. Induktionsbehauptung

Sei nun \max\{a, b\} = n + 1. Dann ist \max\{a-1, b-1\} = n.

Es folgt aus der Induktionsvoraussetzung b), daß a-1 = b-1, womit auch a = b gilt.

möglicher Fehler: Beschränkung des Definitionsbereichs auf die "Natürlichen Zahlen", d.h. Werte

kleiner als 0 (negative Zahlen sind nicht zulässig.

Ist \max\{a, b\}=n+1= 0, dann wäre \max\{a-1, b-1\}=n \text{oder} -1 (keine natürliche Zahl)

Hapi

-- (Anm. (Baccus): Kommt mir zwar nach wie vor spanisch vor :-), wurde aber von unserem UE-Leiter heute so akzeptiert, bzw. auch so erklärt!).

-- (Anm. (Blµb): Nun, der Induktionsanfang ist max{a,b} = n, nicht = n+1, daher fallen negative Zahlen weg. Habe meine Lösung dazugeschrieben.)

Vorschlag von Blµb[Bearbeiten]

Kommt irgendwie aufs selbe hinaus, aber:

Der Induktionsanfang max{a,b} = 1 lässt in \mathbb{N} ohne 0 (da bei a n = 1 steht nehm ich an wir haben keine 0) gar keine verschiedenen Zahlen a,b zu, daher stimmt die Behauptung nicht. Man müsste entweder sagen: "Je zwei gleiche Zahlen a,b sind gleich groß" - na wie passend - oder max\{a,b\} = n \Rightarrow a = b = n explizit für ein n > 0 zeigen, womit man dann auf dieselbe Weise auf n+1 schließen könnte. Wers jetz schafft das ganze für ein n > 1 explizit zu beweisen bekommt von mir ein Keks ;)

Vorschlag von Tonico[Bearbeiten]

Wenn ich es richtig verstehe scheitert es schon am Induktionsanfang.

IV: Die Aussage P(n) lautet
max(a, b) = n ⇒ a = b, mit a, b, n ∈ ℕ.

IA: P(0) ist nicht wahr denn max(a, b) = 0 ⇒ a = b gilt z.B. nicht für a = 0, b = 1.

Anm (BlµB): Es geht darum, dass aus \mbox{max}\{a, b\} = 0 FOLGT, dass a und b = 0.

Lösung nach der Übung am 25.[Bearbeiten]

Wenn der IA: \mbox{max}\{a, b\} = n \Rightarrow a = b = n, dann ist der Induktionsschritt:

\mbox{max}\{a, b\} = n + 1 \Rightarrow
\begin{cases}
\mbox{max}\{a + 1, b + 1\} = n + 1 & \mbox{Folgerung } a = b \mbox{ wahr} \\
\mbox{max}\{a, b + 1\} = n + 1 & \mbox{Folgerung } a = b \mbox{ falsch} \\
\mbox{max}\{a + 1, b\} = n + 1 & \mbox{Folgerung } a = b \mbox{ falsch}
\end{cases}

Es gilt also nicht in allen Fällen.

Noch eine Lösung[Bearbeiten]

Setzt man für a-1 oder b-1 0 ein so ist dies keine Natürliche Zahl mehr und widerspricht der Annahme am Anfang. (s.o) Alle anderen Vorschläge wurden bei uns nicht akzeptiert!