Existenzaussagen fuer Beweise

XFame

Gibt es eigentlich schon Versuche, lediglich Existenzaussagen fuer Beweise von Vermutungen zu machen, ohne den Beweis selbst zu fuehren?

Jester

XFame schrieb:

Gibt es eigentlich schon Versuche, lediglich Existenzaussagen fuer Beweise von Vermutungen zu zumachen, ohne den Beweis selbst zu fuehren?

Das ist doch letztlich auch ein Beweis. Wenn Du beweist, dass ein Beweis für Aussage X existiert, dann ist damit auch X bewiesen (schließlich gibt es einen Beweis).

tawa

Jester ich glaube das ist dem op schon klar.

Kennt jemand ein Beispiel?
Ist eine Interessante Frage.

knivil

Ist ne bloede Frage! Oder haste 'nen Beispiel?

Jester

tawa schrieb:

Jester ich glaube das ist dem op schon klar.

Und was soll dann der Nachsatz "ohne den Beweis selbst zu fuehren"? Ich habe darauf hingewiesen, dass es sich dabei um einen Beweis handelt und dieser somit auch geführt wurde: Wann kann einen Beweis nicht führen ohne den Beweis zu führen.

Was wohl noch am ehesten in die Richtung gehört sind nicht-konstruktive Existenzbeweise: Statt ein konkretes Beispiel anzugeben (zeigt man nur die Existenz eines Beispiels, ohne es anzugeben). Da gibt es ein sehr schönes Beispiel:

Behauptung: Es gibt zwei Zahlen a,b aus R\Q mit a^b in Q.

Beweis:
Betrachte z:=sqrt(2)^sqtr(2).
Fall 1: z ist rational, dann ist a=b=sqrt(2) ein Beispiel
Fall 2: z ist irrational, dann ist a=z, b=sqrt(2) ein Beispiel

edit: Sachen die in eine ähnliche Richtung gehen, könnten was mit der Frage nach der Vollständigkeit von Kalkülen zu tun haben: http://de.wikipedia.org/wiki/Kalkül

XFame

Natuerlich hat man dann einen Beweis, ganz richtig.
Mir wird nur etwas mulmig bei dem Gedanken, und zwar deshalb:

Wir erkennen doch bei einem ueblichen Beweis, warum denn nun genau die Aussage gilt.
Zeigt man aber nur, dass es einen Beweis fuer die Vermutung gibt, so kann man u. U. nicht direkt ersehen, warum sie denn gelten soll. Wir wissen nur, dass sie aus dem gegebenen Axiomensystem ableitbar ist

An deinem Beispiel Jester kann man z.B. sehen, warum es solche a und b geben muss. Zeigt man jedoch nur, dass es einen Beweis dafuer gibt, so versteht man doch evtl. garnicht warum.

außerdem gibt es mehrere Beweise, die so kompliziert sind, daß sie jeweils nur von einer Handvoll Menschen weltweit lückenlos nachvollzogen werden können (FLT, Gruppenklassifikation, ...). Alle anderen können zwar glauben, daß der Beweis richtig ist, aber sich nicht davon überzeugen. Das sind im Grunde auch Beweise, die zwar existieren, aber für die Mehrheit nicht greifbar oder nachvollziehbar sind.

Prof84

XFame schrieb:

Gibt es eigentlich schon Versuche, lediglich Existenzaussagen fuer Beweise von Vermutungen zu machen, ohne den Beweis selbst zu fuehren?

Ja, zum Bleistift gängige Verfahren in der Kryptographie:
http://de.wikipedia.org/wiki/Zero_Knowledge
http://de.wikipedia.org/wiki/Secret_Sharing
etc.

das sind keine beweise, nur wkeit

Kontinuumshypothese und den beweis der unbeweisbarkeit.
Soetwas gibt es sicher auch in der anderen richtung.

Jester

XFame schrieb:

An deinem Beispiel Jester kann man z.B. sehen, warum es solche a und b geben muss. Zeigt man jedoch nur, dass es einen Beweis dafuer gibt, so versteht man doch evtl. garnicht warum.

Kann man das wirklich? Ich habe zwar zwei Kandidatenpaare angegeben und gezeigt, dass es eines davon tun muß. Aber dem Ziel wirklich ein konkretes Beispiel in der Hand zu halten sind wir nur bedingt näher gekommen.

XFame

Man erkennt aber, warum es solche a und b geben muss. Wenns der erste Fall nicht tut, dann doch aber der zweite.

Bashar

Jester schrieb:

Das ist doch letztlich auch ein Beweis. Wenn Du beweist, dass ein Beweis für Aussage X existiert, dann ist damit auch X bewiesen (schließlich gibt es einen Beweis).

Wenn ich die Existenz eines Elementes E eines Universums, das ein Prädikat P erfüllt, nichtkonstruktiv zeige, kenne ich E normalerweise nicht. Aber sobald ich das Universum der Beweise betrachte und P(E) bedeutet, dass E ein Beweis einer bestimmtem Aussage ist, ist jeder nichtkonstruktive Beweis automatisch konstruktiv, da er selbst dieses E darstellt. Klingt irgendwie paradox, Gödel kann da nicht weit sein.

Jester

Ich glaub da verstehe ich Dich nicht ganz richtig. Kann es sein, dass Du zwei Sachen vermengst? Der nicht konstruktive Beweis, ist natürlich Beweis für zweierlei Dinge, einmal die bewiesene Aussage selbst und einem für die Existenz eines Beweises für diese Aussage. Während er für erstere nicht konstruktiv ist, ist er für letztere natürlich konstruktiv, nämlich einfach durch Angabe eines Beweises. Oder ist total an mir vorbeigegangen, was Du sagen wolltest?

Bashar

Hm. Ich vesuchs nochmal

"Es existiert ein E in U, so dass P(E) gilt." U kann alles mögliche sein, die Menge der natürlichen Zahlen, der reellen Folgen etc. Finde ich für so eine Behauptung einen nichtkonstruktiven Beweis, so kenne ich E normalerweise noch nicht. Das ist ja gerade das Wesen eines nichtkonstruktiven Beweises.

Jetzt den Spezialfall: U = Menge aller Beweise, P(E) = "E ist ein Beweis für Aussage xyz". Finde ich jetzt einen nichtkonstruktiven Beweis (also einen Beweis, dass es einen Beweis E für die Aussage xyz geben muss), so habe ich damit auch mein E gefunden. In dieser Situation ist also jeder Beweis konstruktiv. Das ist klar, das hast du ja vorhin auch schon gesagt. Die Frage ist nur, ob das irgendwie paradox ist, oder ob das nur so aussieht.

Jester

Ich finde nicht, dass das paradox klingt. Es spiegelt nur die Tatsache wieder, dass der Beweis für die Existenz eines Beweises einer Aussage A selbst bereits ein Beweis für A ist. In der Tat ist die Konsequenz daraus natürlich, dass Beweise für die Existenz von Beweisen stets konstruktiv sind.

Jester

Prof84 schrieb:

XFame schrieb:

Gibt es eigentlich schon Versuche, lediglich Existenzaussagen fuer Beweise von Vermutungen zu machen, ohne den Beweis selbst zu fuehren?

Ja, zum Bleistift gängige Verfahren in der Kryptographie:
http://de.wikipedia.org/wiki/Zero_Knowledge
http://de.wikipedia.org/wiki/Secret_Sharing
etc.

Das hat damit nichts zu tun. Bei Zero_Knowledge weist der Beweiser nach, dass er im Besitz einer bestimmten geheimen Information ist. Er führt also tatsächlich einen Beweis. Allerdings führt er ihn so geschickt, dass ein Überprüfer zwar nachvollziehen kann, ob der Beweis korrekt ist, aber anschließend dennoch nicht selbst im Besitz der geheimen Information ist.

Jester schrieb:

Prof84 schrieb:

XFame schrieb:

Gibt es eigentlich schon Versuche, lediglich Existenzaussagen fuer Beweise von Vermutungen zu machen, ohne den Beweis selbst zu fuehren?

Ja, zum Bleistift gängige Verfahren in der Kryptographie:
http://de.wikipedia.org/wiki/Zero_Knowledge
http://de.wikipedia.org/wiki/Secret_Sharing
etc.

Das hat damit nichts zu tun. Bei Zero_Knowledge weist der Beweiser nach, dass er im Besitz einer bestimmten geheimen Information ist. Er führt also tatsächlich einen Beweis. Allerdings führt er ihn so geschickt, dass ein Überprüfer zwar nachvollziehen kann, ob der Beweis korrekt ist, aber anschließend dennoch nicht selbst im Besitz der geheimen Information ist.

Er kann sich aber nie zu 100% sicher sein, dass die Person wirklich die geheime Information besitzt oder einfach nur verdammt gut im Raten ist. Somit ist ein interaktiver Beweis kein mathematischer Beweis, da immer ein Rest an Unsicherheit übrig bleibt.

Prof84

Bashar schrieb:

Hm. Ich vesuchs nochmal

"Es existiert ein E in U, so dass P(E) gilt." U kann alles mögliche sein, die Menge der natürlichen Zahlen, der reellen Folgen etc. Finde ich für so eine Behauptung einen nichtkonstruktiven Beweis, so kenne ich E normalerweise noch nicht. Das ist ja gerade das Wesen eines nichtkonstruktiven Beweises.

Jetzt den Spezialfall: U = Menge aller Beweise, P(E) = "E ist ein Beweis für Aussage xyz". Finde ich jetzt einen nichtkonstruktiven Beweis (also einen Beweis, dass es einen Beweis E für die Aussage xyz geben muss), so habe ich damit auch mein E gefunden. In dieser Situation ist also jeder Beweis konstruktiv. Das ist klar, das hast du ja vorhin auch schon gesagt. Die Frage ist nur, ob das irgendwie paradox ist, oder ob das nur so aussieht.

Wunderbar! - Du hast viel mehr verstanden, als manche Prof. 3 x Dr. Institutsleiter die mir bisher begegnet sind! Respekt!

Nichtkonstruktive Beweise können Beweise auf Basis der Statisik sein oder Fuzzy-Zustände bei denen die Kalibration noch nicht klar ist. Die Vollständigkeit der Beweisführung (100%) ist nur möglich, wenn die gesamte Systembeschreibung erfasst wurde (konstruktive Beweisführung - NP Vollständigkeit)).

@Mathematikker: Und? "Falsches" Beurteilungskonzept?!
Thema: Existenzaussagen für Beweises!

Dein Zero Knowledge gibt keinen Existenzbeweis.