TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/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 $\text{max}\{a,b\}=0$ FOLGT, dass a und b = 0.

Lösung nach der Übung am 25.

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

$\text{max}\{a,b\}=n+1\Rightarrow \{\begin{array}{cc}\text{max}\{a+1,b+1\}=n+1& \text{Folgerung }a=b\text{ wahr}\\ \text{max}\{a,b+1\}=n+1& \text{Folgerung }a=b\text{ falsch}\\ \text{max}\{a+1,b\}=n+1& \text{Folgerung }a=b\text{ falsch}\end{array}$

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!