Prof. Dr. Michael Eisermann
Download 302.12 Kb. Pdf ko'rish
|
- Bu sahifa navigatsiya:
- R e a l i t ä t / A n w e n d u n g
- T h e o r i e / M a t h e m a t i k
- Beispiel
- Menge
- Vereinigung
- Alternativen
- Transitivität
- Aufgabe
|
Prof. Dr. Michael Eisermann • Institut für Geometrie und Topologie Der Satz vom Diktator Kenneth Arrows geniale Antwort auf die Frage Wie schreibe ich meine Doktorarbeit in fünf Tagen und erhalte dafür den Wirtschaftsnobelpreis? Try Science! Workshop Mathematik für Schülerinnen und Schüler www.igt.uni-stuttgart.de/eiserm • 10. März 2017, 15–18 Uhr Willkommen! 002
Ich begrüße Sie herzlich zu Try Science! und unserem Workschop. Es geht um Mathematik. Das birgt besondere Chancen und Risiken, die muss ich erklären. Viele Schüler kommen ja mit Mathematik nicht mehr in Kontakt. – „Was? Wir haben doch Mathematik in der Schule!“ – Naja, das Fach wird so genannt; wenn’s gut läuft, lernen Sie dort Rechnen. Rechnen ist gut und nützlich, doch Mathematik bietet so viel mehr! Mathematik ist nicht (nur) die sture Anwendung vorgefertigter Formeln, sondern (auch und vor allem) die Entwicklung neuer (Denk-)Werkzeuge. Mathematik (gr. μαθηματική τέχνη) ist die Kunst des Erkennens. Sie ist ein schöpferischer Prozess zum Lösen von Problemen. Was zeichnet mathematische Arbeit aus? Ehrlich sein zu sich selbst und zu allen anderen, präzise formulieren, sorgfältig argumentieren, nachvollziehbar, nach logischen Regeln, alle Fälle berücksichtigen. Sorgfalt und Ehrlichkeit sind mühsam, viele mögen das nicht, manche spotten gar darüber. Beides ist dennoch bitter nötig, und es lohnt sich! Was Sie einmal als richtig erkannt und nachgewiesen haben, behält seine Gültigkeit, auch nach Jahrhunderten, für immer! Andere Bereiche des Wissens sind modischer – aber flüchtiger. Kenneth Arrow (1921–2017) 003
Kenneth Arrow bei der Nobelpreisverleihung, Stockholm 10.12.1972 (Associated Press) Kenneth Arrow (1921–2017) 004 Kenneth Arrow starb vor wenigen Tagen, am 21. Februar 2017, im Alter von 95 Jahren. Er war Professor in Harvard, später Stanford. Dieser Vortrag handelt von seiner Doktorarbeit aus dem Jahre 1951. Für diese und weitere bahnbrechende Arbeiten zur Wohlfahrtstheorie und zur Theorie ökonomischer Gleichgewichte bekam Arrow 1972 den Wirtschaftsnobelpreis, mit 51 Jahren als bislang jüngster Preisträger. Die Arbeiten von Nobelpreisträgern sind oft spannend und wegweisend. Für populärwissenschaftliche Vorträge eignen sie sich leider selten, oder nur mit großen Mühen. Es gibt ein paar bemerkenswerte Ausnahmen, wie Nashs Gleichgewicht in der Spieltheorie, von dem ich ein andermal sprechen will, oder Arrows Satz vom Diktator, um den es heute geht. Dieses Theorem ist ein schönes Lehrstück mathematischen Denkens. Der Beweis ist genial-einfach, die Aussage ist gesellschaftlich relevant. Dieser Vortrag steht Ihnen schriftlich zur Verfügung, auch online. Sie müssen nicht mitschreiben; mir ist lieber, dass Sie mitdenken. Bitte unterbrechen Sie mich, wenn etwas unklar ist! Zögern Sie nicht, Ihre Fragen zu stellen! Aperitif: ein klassischer Beweis 005
Erläuterung 1 1 r Sie erinnern sich an √ 2 = 1.4142 . . . . Ist diese Zahl rational oder irrational? Wir suchen einen Bruch r = a/b ∈ Q, der r
2 = 1
2 + 1
2 erfüllt, also r · r = 2. Satz 1 (Irrationalität von √ 2 , Euklid ca. 300 v.Chr.) Es gibt keine rationale Zahl r ∈ Q mit der Eigenschaft r 2 = 2
. Beweis: Angenommen, es gäbe r ∈ Q mit r 2 = 2 . Rational bedeutet r = a/b mit a, b ∈ Z und b > 0. Zudem sei der Bruch a/b vollständig gekürzt. Aus der Gleichung (a/b) 2 = 2
folgt a 2 = 2b 2 . Daher ist a gerade, also a = 2a mit a ∈ Z. Einsetzen ergibt 4a 2 = 2b 2 , also 2a 2 = b
2 . Daher ist b gerade, also b = 2b mit b ∈ Z. Somit ließe sich a/b = a/b weiter kürzen. Also gibt es keine rationale Zahl r ∈ Q mit r 2 = 2
. Rational, irrational, scheißegal? 006 Erläuterung Der Beweis ist klar und einfach, allerdings trickreich: Es ist ein indirekter Beweis, durch Widerspruch. Das müssen Sie erst einmal verarbeiten. Am besten Sie lesen den Beweis in den nächsten Tagen immer wieder durch und prüfen schrittweise alle Argumente, bis Sie sich an den Schock gewöhnen und die raffinierte Logik verstehen. Es hat keinen Sinn, einen Bruch für √ 2
Wohl gibt es gute Approximationen, etwa 14142/10000 wie angegeben, aber kein Bruch kann exakt √ 2
Es hat keinen Sinn, nach etwas zu suchen, das nicht existiert. Nutzen Sie Ihre Lebenszeit lieber für lohnendere Dinge! Zum Beispiel ist es durchaus interessant, lehrreich und lohnend, zu verstehen, warum √ 2
Aufgabe: Finden Sie heraus, ob √ 3 rational oder irrational ist. Und √ 4 ? Manch Amateur sucht nach der Quadratur des Kreises, einem weiteren klassischen Konstruktionsproblem. Es ist leider unmöglich, der Beweis ist allerdings komplizierter als der obige. Viele suchen daher lieber nach einer Quadratur, die es nicht gibt. Einige werden darüber verrückt. Rational, irrational, scheißegal? 007 Erläuterung Zur Irrationalität von √ 2 schreibt Platon (428–348 v.Chr.): „Ihr wackeren Helenen, das ist eins von den Dingen, von denen gesagt wird, es sei eine Schande, wenn man es nicht wisse, und wenn man das Notwendige weiß, ist’s erst noch keine sonderliche Ehre.“ (Heutigen Schülern wird dies vorenthalten, vorgeblich können sie’s nicht begreifen; eine selbsterfüllende Prophezeiung, eher Fluch und Betrug.) Die Irrationalität von √ 2 war lange vor Euklid bekannt, etwa Hippasos von Metapont. Er lebte um 500 v.Chr. und gehörte der Bruderschaft des Pythagoras an, eine Art philosophisch-esoterische Sekte. Der Kernsatz ihrer Lehre lautete: „Alles ist Zahl.“ Damit meinten sie, alles in der Natur kann durch ganze Zahlen und ihre Verhältnisse (Brüche) beschrieben werden. Der Legende nach waren sie über die Irrationalität von √ 2
ermordeten, indem sie ihn über Bord warfen. Ignoranz schlägt Geist. Ähnlich schockierend wirkt bis heute der Satz vom Diktator, den ich im Folgenden erkläre. Damit er ebenso klar und verständlich wird, nehmen wir uns die nötige Zeit, um alle Ideen und Begriffe sorgfältig einzuführen. Wozu dient Mathematik? 008
R e a l i t ä t / A n w e n d u n g 1. Empirie Beobachtung / Experiment Erfahrungen, Probleme, Ziele 4. Anwendung Interpretation der Ergebnisse Überprüfung des Modells ? anpassen überprüfen T h e o r i e / M a t h e m a t i k 2. Modell grundlegende Eigenschaften Formulierung von Axiomen modellieren abstrahieren auswählen vereinfachen 3. Theorie aufbauende Eigenschaften Regeln, Sätze, Beweise analysieren folgern konkretisieren kalibrieren spezialisieren anpassen Mathematik untersucht sowohl abstrakte Strukturen als auch konkrete Anwendungen. Dies sind keine Gegensätze, sondern sie ergänzen sich! Sie erklärt und quantifiziert Zusammenhänge: Das ist ihr Nutzen! Dank Abstraktion ist sie universell anwendbar: Das ist ihre Stärke! Es gibt nichts Praktischeres als eine gute Theorie. (Immanuel Kant) Problemstellung 101
Beispiel: Eine vierköpfige Familie {1, 2, 3, 4} plant ihren gemeinsamen Urlaub. Zur Wahl stehen a = Venedig, b = London, c = Paris. 1 : b
a 2 :
a c b 3 : a ≈ b c 4 : c b a Was ist ein sinnvoller Kompromiss? rational? nachvollziehbar? gerecht? Geht das überhaupt? Wenn ja, nach welchen Regeln? Beispiel: A = {a, b, c, . . .} sind Gesetzesvorlagen, jeder Abgeordnete i hat seine Präferenz P i . Gesucht ist ein Abstimmungsergebnis P . Beispiel: A = {a, b, c, . . .} sind Universitäten, P i ist das Ranking nach Kriterium i. Gesucht ist ein zusammengefasstes Ranking P . Beispiel: Berufung eines Professors, Kandidaten A = {a, b, c, . . .}. Die Kriterien sind Forschung, Lehre, Drittmittel, Administration. Die Übungen erklären weitere Beispiele und Anwendungen. Beispiele illustrieren. Abstraktion strukturiert und vereinfacht! Problemstellung 102
Erläuterung Abstimmungen sind jedem von uns aus dem Alltag vertraut. Eine Gruppe von Personen 1, 2, . . . , n darf / soll / muss über mögliche Alternativen a, b, c, . . . abstimmen. Doch nach welchem Verfahren soll abgestimmt werden? Welche Anforderungen soll das Verfahren erfüllen? Diese Frage tritt in zahlreichen Anwendungen auf, sie ist daher für die Praxis überaus wichtig. . . und auch theoretisch höchst interessant! Jedes Individuum hat seine individuelle Präferenz. Daraus soll nun eine gemeinsame Präferenz gebildet werden, also ein Gesamtclassement. Wir wollen nicht nur Einzelfälle behandeln, sondern eine allgemeine Regel finden, ein Wahlverfahren, das vernünftigen Ansprüchen genügt. Das klingt zunächst recht einfach, aber es erweist sich als überraschend schwierig, mitunter gar unmöglich! Um dies im Detail zu verstehen und als Ergebnis zusammenzufassen, müssen wir sehr präzise formulieren und argumentieren. Dann jedoch wird alles wunderbar klar und leicht. Wir benötigen hierzu „nur“ elementare Logik und Mengenlehre. Das wird leider in der Schule nicht (mehr) unterrichtet. Deshalb entwickeln wir parallel zur Thematik eine geeignete Sprache zu ihrer Behandlung. Mengen und Elemente 103
Erläuterung Sie kennen Mengen wie die natürlichen Zahlen N = {0, 1, 2, 3, . . .} oder die ganzen Zahlen Z = {. . . , −3, −2, −1, 0, 1, 2, 3, . . .}, die rationalen Zahlen Q = { a/b | a, b ∈ Z, b > 0 }, die reellen Zahlen R, etc. Eine
a, b, c, . . . . Wir schreiben a ∈ A für „a ist Element von A“, kurz „a in A“. Zum Beispiel gilt x ∈ {a, b} genau dann, wenn x = a oder x = b gilt. Die
Wir nennen B eine Teilmenge von A, geschrieben B ⊆ A, wenn jedes Element von B auch in A liegt, also für jedes x ∈ B auch x ∈ A gilt. Im Falle B ⊆ A und A ⊆ B gilt A = B: Sie haben dieselben Elemente. Demnach gilt {a, b} = {b, a}. Es gilt N ⊆ Z aber nicht Z ⊆ N, kurz Z ⊆ N. Aussonderung: Mit { x ∈ A | p(x) } bezeichnen wir die Teilmenge aller Elemente x ∈ A, die eine gegebene Eigenschaft p(x) haben. Beispiele sind Lösungsmengen wie { x ∈ Z | x 2
und { x ∈ R | x 2 = 2 } = {− √ 2, √ 2} sowie { x ∈ Q | x 2 = 2 } = ∅ . Operationen: Vereinigung A ∪ B = { x | x ∈ A oder x ∈ B }, Schnitt A ∩ B = { x | x ∈ A und x ∈ B },
B = { x ∈ A | x / ∈ B }. Paare und Funktionen 104 Erläuterung Ein
Genau dann gilt (a, b) = (c, d), wenn a = c und b = d gilt. Wir schreiben A × B = { (a, b) | a ∈ A, b ∈ B } für die Menge aller geordneten Paare. Dies nennt man auch das
Als Beispiel: {0, 1, 2} × {a, b} = {(0, a), (0, b), (1, a), (1, b), (2, a), (2, b)}. Ist A eine endliche Menge mit n Elementen, so schreiben wir A = n. Es gilt (A ∪ B) = A + B − (A ∩ B) und (A × B) = ( A) · ( B). Sie kennen Funktionen wie q(x) = x 2 , ausführlich q : R → R ≥0 : x → x
2 , sowie r : R ≥0 → R : x → √ x
die Notation [a, b] = { x ∈ R | a ≤ x ≤ b } und R ≥0 = { x ∈ R | x ≥ 0 }. Eine Funktion f : X → Y von der Startmenge X in die Zielmenge Y ordnet jedem Element x ∈ X genau ein Element y ∈ Y zu, kurz x → y, gelesen „x wird abgebildet auf y“, oder f (x) = y, „f von x ist gleich y“. Formal wird f festgelegt durch alle Paare (x, y) ∈ X × Y mit f (x) = y. Dies entspricht dem
Umgekehrt definiert F ⊆ X × Y genau dann eine Funktion f : X → Y , wenn gilt: Zu jedem x ∈ X existiert genau ein y ∈ Y mit (x, y) ∈ F .
Präferenzen 105
Sei A = {a, b, c, . . .} die Menge der betrachteten Alternativen, A ≥ 2. Wir vereinbaren die folgende Schreib- und Sprechweise. Schwache Präferenz: x y bedeutet x ist mindestens so gut wie y. Indifferenz/Äquivalenz: x ≈ y bedeutet x y und y x .
x y
y und nicht y x .
Ebenso anschaulich ist „vor-oder-gleichauf“, „gleichauf“ und „vor“. Definition A1 (Präferenz) Für jede Präferenz fordern wir gewisse Grundregeln: Transitivität: Gilt x y und y z , so auch x z .
Für jedes Paar x, y ∈ A gilt x y oder y x . Im Folgenden bezeichnet P die Menge aller Präferenzen auf A. Wozu brauchen wir Definitionen? Damit wir wissen, wovon wir sprechen! Eine Definition ist eine Vereinbarung: Damit präzisieren wir die Objekte, die wir untersuchen wollen. Nun können Sie selbstständig überprüfen, ob ein vorgelegtes Objekt die genannten Eigenschaften hat oder nicht. Präferenzen 106
Erläuterung Formal wird festgelegt durch alle Paare (x, y) ∈ A × A mit x y , also P = { (x, y) ∈ A × A | x y }
. Genau dann gilt x y , wenn (x, y) ∈ P . Wir nutzen hier zwei Schreibweisen für dasselbe Objekt: Die Schreibweise als Relation ist bequem und suggestiv, die Schreibweise als Menge P ⊆ A × A ist ausführlicher. Beide sind äquivalent und nützlich, wir nutzen beide je nach Situation.
(1) R = {(a, b)} auf A = {a, b} (2) S = {(a, a), (b, b)} auf A = {a, b} (3) T = {(a, a), (a, b), (b, b)} auf A = {a, b} (4) U = {(a, a), (a, b), (b, a), (b, b)} auf A = {a, b} (5) V = {(a, a), (a, b), (b, b), (b, c), (c, c)} auf A = {a, b, c}
(1) Nein, es fehlen (a, a) und (b, b). (2) Nein, es fehlt (a, b) oder (b, a). (3) Ja, kurz a b . (4) Ja, kurz a ≈ b. (5) Nein, es fehlt Transitivität. Präferenzen 107
Aufgabe: Wie viele Präferenzen gibt es auf der Menge A = {a, b}? Lösung: Es gibt genau drei Präferenzen, nämlich: a b b a a ≈ b = P Aufgabe: Wie viele Präferenzen gibt es auf der Menge A = {a, b, c}? Lösung: Es gibt genau 13 Präferenzen, nämlich: a b c a c b b a c b c a c a b c b a (strikte Präferenzen) a b ≈ c b a ≈ c c a ≈ b a ≈ b c a ≈ c b b ≈ c a a ≈ b ≈ c = P Präferenzen 108
Erläuterung Aufgabe: Wie viele strikte Präferenzen gibt es bei n Alternativen? Lösung: Für den ersten Platz haben wir genau n Möglichkeiten, für den zweiten bleiben noch n − 1, für den dritten nur n − 2, usw. Insgesamt erhalten wir das Produkt n · (n − 1) · (n − 2) · · · 3 · 2 · 1. Diese Zahl schreibt man n!, gesprochen „n Fakultät“. Diese Zahlen wachsen schnell, wie folgende Tabelle erahnen lässt: n 1 2 3 4 5 6 7 8 9 10 n! 1 2 6 24 120 720 5040
40320 362880
3628800 P 1 3 13 75 541 4683
47293 545835
7087261 102247563 Für Präferenzen (nicht notwendig strikt) erhalten wir noch mehr; ihre Berechnung ist komplizierter, ich zitiere nur die ersten Werte. Man nennt die Anzahl P auch Fubini–Zahl (oeis.org/A000670), oder Bell–Zahl (en.wikipedia.org/wiki/Ordered_Bell_number). Wahlverfahren für 2 Individuen und 2 Alternativen 109
Aufgabe: Zählen Sie alle möglichen Abstimmungen (Voten) auf bei zwei Individuen, I = {1, 2}, und zwei Alternativen, A = {a, b}. Was ist jeweils das Ergebnis bei Mehrheitswahl M ?
1 :
a b 2 : a b a b 1 :
a b 2 : b a a ≈ b 1 : a b 2 : a ≈ b a b 1 : b a 2 : a b a ≈ b 1 : b a 2 : b a b a 1 :
b a 2 : a ≈ b b a 1 : a ≈ b 2 : a b a b 1 : a ≈ b 2 : b a b a 1 : a ≈ b 2 : a ≈ b a ≈ b Dies definiert das Wahlverfahren M : P × P → P : (P 1 , P
2 ) → P
. Wahlverfahren für 2 Individuen und 2 Alternativen 110 Erläuterung Zur Eingewöhnung betrachten wir zunächst den einfachsten Fall. Das klingt harmlos, ist aber bereits erstaunlich kompliziert! Aufgabe: Wie viele Wahlverfahren V : P × P → P gibt es? Lösung: Für n = 2 und A = 2 gibt es 3 9 = 19 683 Wahlverfahren. Ausführlich: Die Menge P aller Präferenzen auf A = {a, b} hat genau 3 Elemente, wie oben erklärt, geschrieben P = 3. Demnach sind für Wähler 1 genau 3 Präferenzen P 1 möglich, gleiches gilt für P 2 . Da beide Wähler unabhängig voneinander sind, gibt es genau 3 · 3 = 9 geordnete Paare (P 1 , P
2 ) , geschrieben (P × P) = 9. Ein Wahlverfahren V : P × P → P ordnet jedem Paar (P 1 , P 2 ) ein Ergebnis P zu. Für jedes Ergebnis gibt es drei Möglichkeiten. Da wir diese 9 Ergebnisse zunächst beliebig festlegen dürfen, entstehen so insgesamt 3 9 mögliche Wahlverfahren. (Die allermeisten davon sind wenig sinnvoll.) Zur Illustration nenne ich weitere, durchaus realistische Wahlverfahren. Anschließend wollen wir alle Wahlverfahren beschreiben und versuchen, solche mit möglichst guten Eigenschaften zu konstruieren. Wahlverfahren für 2 Individuen und 2 Alternativen 111
Aufgabe: Beschreiben Sie ebenso folgendes Wahlverfahren D 1 : „Allein 1 entscheidet.“ (Das ist die lupenreine Diktatur.) Lösung: 1 :
a b 2 : a b a b 1 :
a b 2 : b a a b 1 :
a b 2 : a ≈ b a b 1 : b a 2 : a b b a 1 :
b a 2 : b a b a 1 :
b a 2 : a ≈ b b a 1 : a ≈ b 2 : a b a ≈ b 1 : a ≈ b 2 :
b a b ≈ a 1 : a ≈ b 2 : a ≈ b a ≈ b Dies definiert das Wahlverfahren D 1 : P × P → P : (P 1 , P
2 ) → P
. Hier ist 1 der Diktator, und 2 hat keinerlei Einfluss auf das Ergebnis. Wahlverfahren für 2 Individuen und 2 Alternativen 112
Download 302.12 Kb. Do'stlaringiz bilan baham: 
|