Diskussion:Satz von Dilworth

Frage der Äquivalenz / Änderung durch Wdvorak vom 26. 10. 2011, 16:44 h

Die Zwischenüberschrift "Zum Satz von Dilworth äquivalente Sätze" in meiner letzten Version vom 26. 10. 2011, 14:37 h, hat Wdvorak kurz darauf verworfen und daraus "Verwandte Sätze" gemacht. Da nun der Satz von Birkhoff und von Neumann hinzugefügt wurde, kann man das gelten lassen. Ob der Satz von Birkhoff und von Neumann in voller Allgemeinheit als zum Satz von Dilworth äquivalent bewiesen vorliegt, kann ich derzeit nicht sagen. Möglicherweise ist es so! (Nebenbei gefragt: Hat hier jemand einen Tip?!)

Klar ist jedoch, dass die Sätze von Dilworth, Hall, König und Menger sowie das Max-Flow-Min-Cut-Theorem als Lehrsätze der Diskreten Mathematik äquivalent sind. Ich meine hier Gleichwertigkeit im Sinne der Aussagenlogik! Soll heißen: Jeder der genannten Sätze impliziert jeden anderen und wird von diesem impliziert, ist also genau dann wahr, wenn der jeweils andere wahr ist. Diesen wichtigen Zusammenhang kann jeder Interessierte anhand der von mir angegebenen Literatur, etwa bei JUNGNICKEL, mit etwas Aufwand nachprüfen.

Das Erläuterung von Wdvorak (s. Versionsgeschichte) zu seiner Änderung war übrigens:

"..., da Äquivalenz für mich (streng genommen) nur bei Axiomen Sinn macht".

Ich erlaube mir zu entgegen: Nein! Wir reden hier über MATHEMATIK. Mathematik ist kein Meinungsforum. (WIKIPEDIA auch nicht.) In der Mathematik ist die Frage, welche Sätze einander implizieren, von fundamentaler Bedeutung. Und wenn wie im vorliegenden Fall bewiesen ist, dass wichtige Sätze äquivalent sind, so muss dies Erwähnung finden. Aus diesem Grunde widmen ja die Autoren dieser Frage in den von mir genannten Quellen einige Aufmerksamkeit. -- Schojoha 16:43, 2. Nov. 2011 (CET)

Dem angegebenen Zitat zufolge hat Wdvorak recht. Von Sätzen, also in einem vorausgesetzten Axiomensystem wahren Aussagen, kann man nicht sinnvoll sagen, sie seien nicht äquivalent (alle Sätze implizieren einander). Das ist nur für Eigenschaften sinnvoll. --84.130.162.178 16:54, 19. Sep. 2014

Ich denke, hier gibt es ein Missverständnis. Von Nichtäquivalenz ist nicht die Rede. Die Rede ist zunächst von Implikationen. Dafür ist im Artikel - und auch oben - ja auch eine Erläuterung beigegeben.

Also: Nimmt man je zwei dieser fünf Sätze - Sätze von Dilworth, Hall, König und Menger sowie das Max-Flow-Min-Cut-Theorem - und nennt diese zwei (etwa) Satz A und Satz B, so gilt stets (Satz A => Satz B). Denn wie gezeigt wurde, kann jeder solche Satz B aus jedem solchen Satz A abgeleitet werden. Vertauscht man die Rollen von A und B, so hat man auch (Satz B => Satz A). Also gilt stets (Satz B <=> Satz B) in allen nur erdenklichen Kombinationen. Folglich sind alle fünf Sätze äquivalent. Deswegen betrachtet man diese fünf Sätze in der Diskreten Mathematik - wohlgemerkt auf endlichen Strukturen! - als gleichwahr.

Der einzige Satz, der aus diesem Rahmen fällt, ist der Satz von Birkhoff-von Neumann. Hier ist meines Wissens nur eine Herleitung (Satz von Hall => Satz von Birkhoff-von Neumann) bekannt. D. h.: Jeder der fünf genannten Sätze impliziert den Satz von Birkhoff-von Neumann.

Also alles in allem: Alles sechs Sätze sind wahr, denn der Satz von Hall etwa lässt sich problemlos per vollständiger Induktion beweisen.

--Schojoha (Diskussion) 22:27, 19. Sep. 2014 (CEST)

Es handelt sich um Sätze, also in gängigen Axiomatisierungen in der Mathematik wahre und bewiesene Aussagen. Dann ist es zwar korrekt, diese Sätze als äquivalent zu bezeichnen, denn dies ist eine logische Tautologie, aber insofern sinnlos, als Sätze gar nicht nicht äquivalent sein können. Noch deutlicher wird die Sinnlosigkeit in der Formulierung, die Sätze seien "gleichwahr", da ja alle Sätze uneingeschränkt wahre Aussagen sind. Etwas ganz anderes ist es, dass man zum Beweis jeden der Sätze aus jedem der anderen leicht herleiten kann, also mit einem einfacheren Beweis als von Grund auf. Erst wenn ein Beweis von Grund auf nicht möglich oder nicht bekannt ist, die Sätze also nur Axiome oder Eigenschaften oder Vermutungen sind, aber weiterhin jede der Aussagen aus jeder der anderen bewiesen werden kann, ist die Rede von Äquivalenz sinnvoll. --84.130.155.159 09:47, 20. Sep. 2014 (CEST)

Beteilige mich doch noch an der Diskussion: Es scheint mir dass wir uns hier eigentlich beim Sachverhalt einig sind aber unterschiedliche Begrifflichkeiten verwenden, insbesondere unterschiedliche Meinungen bezüglich des Begriffs "äquivalent" haben. Nach einem Besuch in der Bibliothek scheint es mit dass der Begriff in der Kombinatorik etwas anders verwendet wird als in der Logik.

Jungnickel defeniert "äquivalent" in dem erwähnten Buch so:

"Wir meinen mit dieser unklaren (aber kurzen) Formulierung, daß sich jeder dieser beiden Sätze leicht aus dem anderen herleiten läßt: Die beiden Sätze gehen durch eine geeignete "Umformung" auseinander hervor" (Seite 66 Fussnote 1).

Ich denke dieser Formulierung kann man folgen und die Theoreme als äquivalent bezeichnen. Gut wäre es dann aber im Artikel auch klar zustellen wie das zu verstehen ist.

--lg Wdvorak (Diskussion) 19:08, 23. Sep. 2014 (CEST)

Hallo, Wdvorak!

Stimmt! Hinsichtlich des eigentlichen Sachverhalts sehe ich auch keine Probleme. Dass der Terminus "äquivalent" unterschiedlich aufgefasst werden kann, war mir - nicht zuletzt wegen des Hinweises von Jungnickel - bewusst und ist es auch noch. Aber dieser Terminus wird in der einschlägigen Literatur nun doch benutzt, nicht nur bei Jungnickel, sondern auch in der Kombinatorik von Jacobs. (Jacobs überschreibt etwa in Kap. II (Der Heiratssatz und seine Verwandten) den § 2, Abschnitt 2 mit Die logische Äquivalenz des Heiratssatzes, des Satzes von König und des Satzes von Dilworth.)

Ich habe versucht, diesem Auffassungsproblem Rechnung zu tragen und dazugeschrieben, was gemeint ist:

"Die Sätze von Dilworth, Hall, König und Menger sowie das Max-Flow-Min-Cut-Theorem sind als Lehrsätze der Diskreten Mathematik zueinander äquivalent. Das heißt: Jeder dieser fünf Sätze impliziert jeden anderen und wird von diesem impliziert, ist also genau dann wahr, wenn der jeweils andere wahr ist."

Diese Formulierung gibt mE das wieder, was in der Diskreten Mathematik allgemein als gesichert angesehen wird. Ich will jedoch nicht unbedingt auf dem Wortlaut bestehen. Wenn also eine stimmige und mit weniger Missverständnispotential versehene Formulierung gefunden werden könnte, hätte ich keine Einwände, diese anstelle der jetztigen zu nehmen.

--Schojoha (Diskussion) 20:17, 23. Sep. 2014 (CEST)

Es geht nicht darum, ob die Äquivalenz bezweifelt wird, oder was "äquivalent" heißt, sondern um die Sinnhaftigkeit der Behauptung. In ZFC sind zum Beispiel das Auswahlaxiom und $\emptyset \subseteq \emptyset$ äquivalent zueinander, einfach weil beides Sätze sind.

Man kann sich natürlich streiten, ob das eine eine "Umformung" des anderen ist, aber die Implikationsbeweise sind in beiden Richtungen höchst "einfach" ;)

Die Lösung besteht darin, anzugeben, in welchem Kontext die Äquivalenz gezeigt wird (etwa: nur Logik, keinerlei Mengenlehreaxiome). Wenn nichts angegeben wird, muss der Leser davon ausgehen, dass dies im selben Kontext geschieht, der eh gerade aktiv ist, in dem also die Aussagen Sätze sind -- wodurch die Äquivalenz hochgradig uninteressant wird.

Alternativ kann man auch die Beweise selbst angeben -- dann kann sich der Leser selbst heraussuchen, was minimal benötigt wird. --Daniel5Ko (Diskussion) 23:08, 23. Sep. 2014 (CEST)

hallo Daniel5Ko

Ich kann dein Argument nachvollziehen, das war auch mein Grund für die hier diskutierte Änderung.

Aufgrund Schojohas energischen Protests habe ich dann aber in der Bibliothek (unteranderem in den zitierten Büchern) nachgeschlagen und es hat sich herausgestellt dass in der Literatur diese Probleme als äquivalent bezeichnet werden.

Bei genauerem Nachlesen hat sich dann aber herausgestellt, dass der Äquivalenzbegriff in der Kombinatorik eben nicht im streng logischen Sinne verwendet wird sondern eher so wie von Jungnickel "definiert" (siehe meinen letzten beitrag)

Ich habe jetzt versucht das im Artikel etwas klarer zu formulieren.

-- Wdvorak (Diskussion) 20:20, 24. Sep. 2014 (CEST)

Das Zitat habe ich gesehen. Dass "leicht" nicht ausreicht, um eine realistische "Definition" für das zu erhalten, was man meint, habe ich mit meinem Beispiel zu zeigen versucht. Das war vor allem für Schojoha, weil seine Beiträge nicht den Anschein machen, als hätte er verstanden, wo das Problem liegt.

Aber ich muss mich auch leicht korrigieren: Es kann durchaus Sätze geben, deren Äquivalenz im strengen Sinn interessant ist: Nämlich dann, wenn keine Beweise für die Sätze bekannt sind. Natürlich kann man dann eigentlich erstmal nicht von Sätzen sprechen, aber sobald ein Beweis bekannt wird, war die bewiesene Aussage rückwirkend schon immer ein Satz, nach meiner Philosophie jedenfalls. :) --Daniel5Ko (Diskussion) 21:00, 24. Sep. 2014 (CEST)

Hallo Kollegen!

Daniel5Ko hat Recht. Mir war oben nicht klar, wo genau das Problem liegt. Denn ich hatte nicht verstanden, dass hinsichtlich der Diskreten Mathematik (in die der Satz von Dilworth ja in erster Linie gehört) nicht allen bewusst ist, dass nirgends, selbst nicht in der einschlägigen Literatur, exakt gesagt wird, wie diese eigentlich einzuordenen und abzugrenzen ist und welcher Mittel sie sich bedient.

Soweit ich sehe, ist es so: Die Diskrete Mathematik dreht sich fast ausschließlich um endliche Strukturen und bewegt sich dabei ganz innerhalb der naiven Mengenlehre und der Alltagssprache. Mathematische Logik etwa spielt dabei keine Rolle und auch nicht die Axiomatische Mengenlehre. Dass auf diesem Wege Ungenauigkeiten entstehen, ist den Diskreten Mathematikern bewusst und - wenn man es offen und ehrlich sagt - ziemlich gleichgültig. Sie nehmen dies einfach hin, wie es ja auch ein wenig in der oben zitierten Fußnote von Jungnickel deutlich wird. Konkret bedeutet das: Der interessierte Leser soll sich sein eigenes Bild machen und man verlässt sich darauf, dass aus dem Kontext heraus klar wird, wie es gemeint ist. (Übrigens klappt das meistens auch.)

Was ich in dieser Situation dann jedoch für problematisch hielte, wäre ein Versuch, hier auf Wikipedia die zweifelsohne bestehenden Lücken durch eigene Interpretationen zu füllen. Letztendlich muss auch hier der Grundsatz gelten: Es soll in Wikipedia nur das wiedergegeben werden, was in den Quellen zu finden ist.

Abschließend ein Sorry an Wdvorak: Mein Protest damals war zu heftig. Da ist der Gaul mit mir durchgegangen. Und dankenswerterweise hast Du ja dann auch die Fußnote von Jungnickel ausgebuddelt. Das hat der Sache nur gut getan.

--Schojoha (Diskussion) 22:34, 28. Sep. 2014 (CEST)

Ich stimme Schojoha zu dass der Artikel die Begrifflichkeiten Literatur wiedergeben sollte, mit dem Zusatz das idealer Weise auch klar gestellt wird wie die Begriffe zu verstehen sind (da es ja kein geschlossenes Lehrbuch ist). Ich denke dass ist jetzt hinreichend der Fall und wir können diese (durchaus interessante) Diskussion beenden -- Wdvorak (Diskussion) 21:07, 30. Sep. 2014 (CEST)

Ich habe aus gegebenem Anlass im Artikel noch was ergänzt, insbesondere den schönen Beweis von Tverberg und weitere Literatur.--Schojoha (Diskussion) 23:38, 2. Okt. 2014 (CEST)