Matroids Matheplanet Forum Index
Moderiert von mire2 StrgAltEntf
Mathematik » Logik, Mengen & Beweistechnik » Nichtexistenzbeweise ohne Widerspruch?
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Nichtexistenzbeweise ohne Widerspruch?
traveller
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 08.04.2008
Mitteilungen: 2600
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-09-10


Hallo,

Gibt es eigentlich auch Nichtexistenzbeweise, die ohne Widerspruch geführt werden, und wie geht man da vor?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1827
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-09-10

\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner} \newcommand{\upamp}{\mathbin {⅋}}\)
Was meinst du mit "ohne Widerspruch"?
Ein *direkter* Beweis von $\lnot A$ sieht jedenfalls so aus: Man nimmt $A$ an, und führt dies zu einem Widerspruch. Man kann das als (Teil der) *Definition* von $\lnot A$ sehen.
Ein *indirekter* Beweis von $B$ ist etwas ganz anderes und sieht so aus: Man nimmt $\lnot B$ an, und führt dies zu einem Widerspruch.

Nur die zweite Variante heißt unbestritten "Widerspruchsbeweis".
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2443
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2020-09-10


Wenn ich ihn recht verstehe, so möchte er

$\lnot (\exists e: P(e))$

zeigen ohne

$(\exists e: P(e)) \to \bot$

zu verwenden.

In wiefern er den offensichtlichen Ansatz

$\forall e: \lnot P(e)$

zulässt, sollte er präzisieren.


-----------------
Why waste time learning when ignorance is instantaneous?
- Bill Watterson -



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
tactac
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 15.10.2014
Mitteilungen: 1827
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-09-10

\(\begingroup\)\(\newcommand{\sem}[1]{[\![#1]\!]} \newcommand{\name}[1]{\ulcorner#1\urcorner} \newcommand{\upamp}{\mathbin {⅋}}\)
2020-09-10 12:46 - DerEinfaeltige in Beitrag No. 2 schreibt:
zeigen ohne

$(\exists e: P(e)) \to \bot$

zu verwenden.

In wiefern er den offensichtlichen Ansatz

$\forall e: \lnot P(e)$

zulässt, sollte er präzisieren.

Wahrscheinlich ist das nicht zugelassen, denn die direkten Beweise von beidem sind beinahe identisch: man hat ein $e$ und ein $P(e)$ zur Verfügung und leitet daraus einen Widerspruch her.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 4749
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-09-10


Man kann gleich allgemeiner fragen, ob man eine Negation $\neg A$ ohne Widerspruch beweisen kann. Weil aber $\neg A$ durch $A \to \bot$ definiert ist (siehe tactac), schätze ich, dass die Antwort Nein ist, außer man verwendet für den Beweis andere Resultate, die diese Zurückführung auf den Widerspruch unsichtbar machen. Zum Beispiel könnte ich bereits $A \implies B$ wissen und $\neg B$ wissen. Und dann verwende ich lediglich die Regel $(A \implies B) \implies (\neg B \implies \neg A)$. Zum Beispiel gibt es keine Injektion $\IR \to \IN$, weil es keine Injektion $P(\IN) \to \IN$ gibt und Binärzahlen eine Injektion $P(\IN) \to \IR$ liefern.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6248
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2020-09-10


Satz: Es gibt keine endliche nichtleere Menge, deren Potenzmenge eine ungerade Kardinalität hat.

Beweis: Die Kardinalität der Potenzmenge einer endlichen nichtleeren Menge ist eine Zweierpotenz > 1, also durch 2 teilbar. q. e. d.

War das jetzt ein Widerspruchsbeweis??



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
traveller
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 08.04.2008
Mitteilungen: 2600
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2020-09-23


Hallo,

Sorry, dieser Thread ist mir etwas untergegangen.

Was ich meinte sind Beweise der folgenden Form:

Theorem: Es gibt kein A mit der Eigenschaft E.
Beweis: Angenommen, es gäbe ein A mit der Eigenschaft E. Dann ...
...
Widerspruch!

Nach Beitrag #1 wäre das wohl ein direkter Beweis und kein Widerspruchsbeweis.

Und die Frage war, ob das auch irgendwie anders gehen könnte als einen Widerspruch herzuleiten.

Naja, wird wohl endlich Zeit, dass ich mich mal mit Logik beschäftige.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Red_
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.09.2016
Mitteilungen: 782
Aus: Erde
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2020-09-24


StrgAltEntf hat doch ein prima Beispiel gegeben?

Und es wäre sehr wohl ein Widerspruchsbeweis.




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Bernhard
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.10.2005
Mitteilungen: 6319
Aus: Merzhausen, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2020-09-24


Hallo!

Ist das nicht auch eine Frage der Formulierung?

Behauptung:
"Er gibt außer 2 keine Primzahl die gerade ist."

Beweise:
1. -> "Jede andere gerade Zahl hat einen Teiler >1, der ungleich ihrer selbst ist, und kann deshalb keine Primzahl sein."

2. -> "Angenommen, p wäre eine gerade Primzahl >2, dann hätte sie in der Faktorzerlegung mindestens einen weiteren Teiler ungleich p und könnte deshalb keine Primzahl sein. -> Widerspruch!!"

Die beiden "Beweise" sind eigentlich äquivalent, nur dröselt der eine die Sache von vorne, der andere von hinten auf.

Viele Grüße, Bernhard



-----------------
"Wichtig ist, daß man nie aufhört zu fragen"
"Weisheit ist nicht das Ergebnis der Schulbildung, sondern des lebenslangen Versuches, sie zu erwerben"
Albert Einstein



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
traveller hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]