TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 24

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.

Dieses Beispiel ist als solved markiert. Ist dies falsch oder ungenau? Aktualisiere den Lösungsstatus (Details: Vorlage:Beispiel)

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

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

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.

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

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!