Lästigster elementarer Beweis

Neue Frage »

Finn_ Auf diesen Beitrag antworten »
Lästigster elementarer Beweis
Zurzeit beschäftige ich mich mit den Prinzipien der Induktion und Rekursion. Gestern wollte ich diesbezüglich mal nebenbei einen Beweis aufstellen, der in elementarer Weise existieren muss, dessen Auffindung sich jedoch für mich als ausgesprochen widerspenstig herausgestellt hat.

Eine Relation auf einer Menge heißt klassisch wohlfundiert, wenn jede ihrer nichtleeren Teilmengen ein minimales Element enthält, das heißt,

(1)

Das wohlfundierte Induktionsprinzip auf lautet

(2)

Es wäre nun die Äquivalenz von (1) und (2) herzustellen. Eigentlich nicht sonderlich schwierig. Man betrachtet das Komplement und nutzt dann boolesche Algebra mit Kontraposition, de Morgan und der Äquivalenz von und Man beachte dabei, dass und sowie und definitionsgemäß gleichbedeutend sind.

Aufgabe sei es nun aber, den Beweis ohne Äquivalenzumformungen bzw. Ersetzungsregel zu führen. Außerdem soll es hierbei möglich sein, (2) aus (1) intuitionistisch zu folgern. Man kann auch versuchen, den Beweis über die Descending Chain Condition zu führen, dafür mag aber das abhängige Auswahlaxiom vonnöten sein.
tobit Auf diesen Beitrag antworten »

Hallo Finn_,

entweder stelle ich mich doof an oder der intuitionistische Beweis der Implikation von (1) nach (2) hat es in sich.

Ich habe die Frage nach Hinweisen dazu mal im Matheplanet (https://matheplanet.com/matheplanet/nuke...hp?topic=265367) gepostet, wo einige Experten in intuitionistischer Logik vertreten sind.


Die naheliegenden klassischen Beweise erscheinen mir jedoch ohne besondere Ideen durchzulaufen.

Die entscheidende Idee bei der Implikation von (2) nach (1) (gegeben eine Teilmenge wähle und wende (2) darauf an) hast du ja schon genannt.

Eine ähnliche Idee hilft bei der Implikation von (1) nach (2) nach klassischer Logik.


Falls du mehr Input zu den klassischen Beweisen benötigst, melde dich gerne nochmal.
Ansonsten freue ich mich, wenn du später eine Lösung(sidee) zum intuitionistischen Beweis posten könntest. Danke.

Viele Grüße
Tobias
Finn_ Auf diesen Beitrag antworten »

Vielen Dank. Mit der Annahme konnte ich den Sachverhalt entwirren, wie es scheint.

Es ist (2) unter Annahme von (1) zu beweisen. Wir nehmen dafür zunächst die Prämisse von (2) an, also



Zu zeigen ist Angenommen, Es folgt , ergo liegt mit (1) ein mit also vor. Man spezialisiere das macht



Wir zeigen Dazu wird ein beliebiges mit angenommen, zu zeigen ist Man spezialisiere aus der verfügbaren Allaussage, womit sich die Aussage anfindet, was bedeutet.

Nun haben wir sowohl als auch was aber absurd ist, da eine Menge und ihr Komplement disjunkt sind. Ergo muss die Annahme unrichtig gewesen sein.
tobit Auf diesen Beitrag antworten »

Ja, genauso wäre ich auch vorgegangen, um den klassischen Beweis zu führen.

Er ist natürlich nicht intuitionistisch zulässig, weil ein Widerspruchsbeweis der intuitionistisch nicht erlaubten Form "Angenommen ... Widerspruch. Also ." geführt wird.
tobit Auf diesen Beitrag antworten »

Ergänzung: Auch die Schlussfolgerung von auf wäre intuitionistisch nicht ohne Weiteres korrekt (es würde nur folgen).
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »