Lästigster elementarer Beweis

29.05.2024, 18:59	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 $\begin{eqnarray} < \end{eqnarray}$ auf einer Menge $\begin{eqnarray} M \end{eqnarray}$ heißt klassisch wohlfundiert, wenn jede ihrer nichtleeren Teilmengen ein minimales Element enthält, das heißt, (1) $\begin{eqnarray} \forall B\subseteq M\colon B\ne\emptyset\Rightarrow \exists x\in B\colon\lnot\exists y\in B\colon y<x. \end{eqnarray}$ Das wohlfundierte Induktionsprinzip auf $\begin{eqnarray} (M,<) \end{eqnarray}$ lautet (2) $\begin{eqnarray} \forall A\subseteq M\colon (\forall x\in M\colon (\forall y\in M\colon y<x\Rightarrow y\in A)\Rightarrow x\in A)\Rightarrow A=M. \end{eqnarray}$ Es wäre nun die Äquivalenz von (1) und (2) herzustellen. Eigentlich nicht sonderlich schwierig. Man betrachtet das Komplement $\begin{eqnarray} A=M\setminus B \end{eqnarray}$ und nutzt dann boolesche Algebra mit Kontraposition, de Morgan und der Äquivalenz von $\begin{eqnarray} \varphi\Rightarrow\psi \end{eqnarray}$ und $\begin{eqnarray} \lnot \varphi\lor \psi. \end{eqnarray}$ Man beachte dabei, dass $\begin{eqnarray} \exists x\in B\colon\varphi(x) \end{eqnarray}$ und $\begin{eqnarray} \exists x\colon x\in B\land \varphi(x) \end{eqnarray}$ sowie $\begin{eqnarray} \forall x\in A\colon\varphi(x) \end{eqnarray}$ und $\begin{eqnarray} \forall x\colon x\in A\Rightarrow\varphi(x) \end{eqnarray}$ 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.
30.05.2024, 19:12	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 $\begin{eqnarray} B\subseteq M \end{eqnarray}$ wähle $\begin{eqnarray} A:=M\setminus B \end{eqnarray}$ 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
30.05.2024, 23:33	Finn_	Auf diesen Beitrag antworten »
Vielen Dank. Mit der Annahme $\begin{eqnarray} A\ne M \end{eqnarray}$ 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 $\begin{eqnarray} (\forall x\colon (\forall y\colon y<x\Rightarrow y\in A)\Rightarrow x\in A). \end{eqnarray}$ Zu zeigen ist $\begin{eqnarray} A=M. \end{eqnarray}$ Angenommen, $\begin{eqnarray} A\ne M. \end{eqnarray}$ Es folgt $\begin{eqnarray} B:=M\setminus A\ne\emptyset \end{eqnarray}$ , ergo liegt mit (1) ein $\begin{eqnarray} a\in B \end{eqnarray}$ mit $\begin{eqnarray} \lnot\exists y\in B\colon y<a \end{eqnarray}$ also $\begin{eqnarray} \forall y\colon y<a\Rightarrow y\notin B \end{eqnarray}$ vor. Man spezialisiere $\begin{eqnarray} x:=a, \end{eqnarray}$ das macht $\begin{eqnarray} (\forall y\colon y<a\Rightarrow y\in A)\Rightarrow a\in A. \end{eqnarray}$ Wir zeigen $\begin{eqnarray} \forall y\colon y<a\Rightarrow y\in A. \end{eqnarray}$ Dazu wird ein beliebiges $\begin{eqnarray} b \end{eqnarray}$ mit $\begin{eqnarray} b<a \end{eqnarray}$ angenommen, zu zeigen ist $\begin{eqnarray} b\in A. \end{eqnarray}$ Man spezialisiere $\begin{eqnarray} y:=b \end{eqnarray}$ aus der verfügbaren Allaussage, womit sich die Aussage $\begin{eqnarray} b\notin B \end{eqnarray}$ anfindet, was $\begin{eqnarray} b\in A \end{eqnarray}$ bedeutet. Nun haben wir sowohl $\begin{eqnarray} a\in B \end{eqnarray}$ als auch $\begin{eqnarray} a\in A, \end{eqnarray}$ was aber absurd ist, da eine Menge und ihr Komplement disjunkt sind. Ergo muss die Annahme $\begin{eqnarray} A\ne M \end{eqnarray}$ unrichtig gewesen sein.
31.05.2024, 09:41	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 $\begin{eqnarray} A\neq M \end{eqnarray}$ ... Widerspruch. Also $\begin{eqnarray} A=M \end{eqnarray}$ ." geführt wird.
31.05.2024, 22:08	tobit	Auf diesen Beitrag antworten »
Ergänzung: Auch die Schlussfolgerung von $\begin{eqnarray} b\notin B=M\setminus A \end{eqnarray}$ auf $\begin{eqnarray} b\in A \end{eqnarray}$ wäre intuitionistisch nicht ohne Weiteres korrekt (es würde nur $\begin{eqnarray} \neg\neg b\in A \end{eqnarray}$ folgen).

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »