Dirichletsches Schubfachprinzip
Rainer Rosenthal
auch einfach Schubfachprinzip AKA pigeon
hole principle eigentlich ein Axiom?
Wenn nicht, wie darf ein ernsthafter Mathematiker
es dann anwenden? Wovon soll er es dann ableiten?
In der Welt der Bierseidel hat ja der "gesunde
Menschenverstand" nix zu suchen.
Auf geht's: Interessante Antworten werden genauso
gerne gesehen wie Bibel-Zitate :-)
Rainer Rosenthal
r.ros...@web.de
Rudolf Polzer
> Ist das Dirichletsche Schubfachprinzip oder
> auch einfach Schubfachprinzip AKA pigeon
> hole principle eigentlich ein Axiom?
IMHO nicht, s.u.
> Wenn nicht, wie darf ein ernsthafter Mathematiker
> es dann anwenden? Wovon soll er es dann ableiten?
> In der Welt der Bierseidel hat ja der "gesunde
> Menschenverstand" nix zu suchen.
a) Aufsummieren von n "x_i <= 1" Ungleichungen, Beweis durch Widerspruch
(evtl. mit Wichtung oder auch als Integral)
Das beweist auch gleich das verallgemeinerte Schubfachprinzip: zum
Mittelwert x~ gibt es immer ein Element >= x~. Die erste ganze Zahl
größer oder gleich (n+1)/n ist aber nun einmal 2.
b) Vollständige Induktion:
IA: Schubfach(1)
>= 2 Kugeln auf 1 Schubfach verteilen
==> in mindestens einem Schubfach gibt es mindestens zwei Kugeln
IV: Schubfach(n)
IB: Schubfach(n+1)
B: a) In den ersten n Schubfächern befinden sich insgesamt <= n Kugeln.
Dann bleiben für das n+1-te Schubfach >= 2 Kugeln, es folgt
die Behauptung.
b) In den ersten n Schubfächern befinden sich insgesamt > n Kugeln,
also >= n+1. Aus Schubfach(n) folgt dann die Behauptung.
--
Your signature is really in bad taste. Despite it's source.
[Disaster in jae]
Hermann Kremer
Tja, dann schau doch mal nach in
P. L. Dirichlet: Vorlesungen über Zahlentheorie. Braunschweig 1871.
http://134.76.163.65/agora_docs/159253TABLE_OF_CONTENTS.html
---> S. 367, 368 .
Laut http://members.aol.com/jeff570/mathword.html hat Dirichlet es
bereits 1834 eingeführt; nach der Quelle muß ich aber noch suchen.
Grüße
Hermann
--
PS: Stenopterygius quadriscissus ist ein von Viktor v. Scheffel besungener
Ichthyosaurier und kein Fisch ... den v. Scheffel'schen Gesang kann man im
Thread [HJ]_Die_Bibel_und_Pi=3-....-[HJ]_Stenopterygius_und_die_Bibel
unter dem heutigen Datum finden ;-)
>Rainer Rosenthal
>r.ros...@web.de
>
>
Timo Heuser
ich würde einfach so etwas in der Richtung sagen:
Beh.: Werden k Objekte auf n Schubfächer veteilt, so gibt es ein Schubfach
mit mind. CEIL(k/n) Objekten darin.
Beweis: Das Gegenteil angenommen, so enthielten alle n Schubfächer weniger
als CEIL(k/n) Objekte, also maximal
CEIL(k/n)-1. Für die Gesamtzahl s der untergebrachten Objekte würde dann
gelten: s <= n*(CEIL(k/n)-1) < n*((k/n+1)-1) = k, kurz: s < k. Also
Widerspruch zur vollständigen Verteilung von k Objekten.
Weiß allerdings nicht, ob das eine Antwort war, wie du sie wolltest ;)
MfG
Rainer Rosenthal
Hermann Kremer wrote
> >Ist das Dirichletsche Schubfachprinzip oder
> >auch einfach Schubfachprinzip AKA pigeon
> >hole principle eigentlich ein Axiom?
>
> Laut http://members.aol.com/jeff570/mathword.html
> hat Dirichlet es bereits 1834 eingeführt; nach der
> Quelle muß ich aber noch suchen.
Das ist wieder mal sehr freundlich. Hast Du eine
persönliche Meinung dazu oder ist Dir das so lang
wie breit? Ich selbst bin kein so Grundlagen-Freak,
aber ab und zu kitzelt's mich.
Wenn ich so auf das Datum 1834 schaue und vermute,
dass Cantor erst ab der zweiten Jahrhunderthälfte
die Mengen aus dem Nebel geholt hat, dann handelt
es sich bei dem Schubfachprinzip wohl um einen
Vorläufer der Mächtigkeitsbetrachtung. Sind zwei
Mengen gleichmächtig, dann und nur dann gibt es eine
Bijektion zwischen ihnen: Ding <---> Schubfach.
Ist also eine Menge grösser, dann gibt es nur eine
Bijektion der kleineren auf eine Teilmenge der
grösseren. Gibt es weniger Schubfächer als Dinge, dann
gibt es also eine echte Teilmenge der Dinge, die genau
jeweils eins in eine Schublade gepackt werden können.
"Echte Teilmenge" heisst aber, dass wenigstens ein Ding
bei dieser Aufteilung draussen bleibt. Wenn aber jedem
Ding eine Schublade zugeordnet sein soll, ist diesem also
eine schon besetzte zugeordnet. In dieser ihm zugeordneten
Schublede finden sich dann also mindestens zwei, sobald
es dahinein geräumt worden ist.
Dies Quasi-Axiom steht nach meiner Meinung über allen
Rechnereien und ist Teil der puresten Mengenlehre. Und
irgendein echter Kenner dieser Materie wird vielleicht
sogar eine Herleitung aus den Mengenlehre-Axiomen aus
dem Ärmel schütteln. ( Oder ist es alles doch eher
"basic", weil wir es ja nur mit endlichen Mengen zu tun
haben, die "irgendwie von selbst" so Peano-mässig sind
und sich über Vollständige Induktion freuen?)
>
> ... [HJ]_Stenopterygius_und_die_Bibel
> unter dem heutigen Datum finden ;-)
Nein danke.
Gruss,
Rainer Rosenthal
r.ros...@web.de
Wolfgang Kirschenhofer
> Hermann Kremer wrote
>
>
>>>Ist das Dirichletsche Schubfachprinzip oder
>>>auch einfach Schubfachprinzip AKA pigeon
>>>hole principle eigentlich ein Axiom?
>>
>>Laut http://members.aol.com/jeff570/mathword.html
>>hat Dirichlet es bereits 1834 eingeführt; nach der
>>Quelle muß ich aber noch suchen.
>
> Das ist wieder mal sehr freundlich. Hast Du eine
> persönliche Meinung dazu oder ist Dir das so lang
> wie breit? Ich selbst bin kein so Grundlagen-Freak,
> aber ab und zu kitzelt's mich.
> Gruss,
> Rainer Rosenthal
> r.ros...@web.de
>
Hallo Rainer !
Ohne ein Grundlagen-Freak sein zun müssen,kann man die mathematische
Basis des Schubfachprinzips("Pigeonhole Principle") verstehen.
Zunächst zwei Vorbemerkungen:
1.)Die axiomatische Basis des Schubfachprinzips sind die Peano-Axiome
und der Begriff der "endlichen Menge".Das Schubfachprinzip ist dann
jedenfalls ein beweisbarer Satz.
Will man eine Stufe tiefer gehen,dann kann man die natürlichen Zahlen
nach der Methode von John von Neumann auf der Basis der
Zermelo-Fraenkel-Axiome konstruieren und die Peano-Axiome werden
beweisbare Sätze (abgesehen vom Induktionsaxiom). Diese "tiefere"
Betrachtungsweise braucht man zum formalen Verständnis des
Schubfachprinzips aber nicht.
Literatur dazu:H.B.Enderton:Elements of Set Theory.
Oder ein Buch,welches u.a. auch für Lehrer an Höheren Schulen
geschrieben wurde:E.Hlawka,Ch.Binder,R.Schmitt:Grundbegriffe der
Mathematik,Prugg-Verlag,Wien 1979,ISBN 3-85385-038-3
2.)Das Schubfachprinzip kann man etwas allgemeiner folgendermaßen
formulieren:Werden mindestens q*s+1 Gegenstände in s Schubfächer
getan,so enthält dann mindestens ein Schubfach mehr als q Gegenstände.
Die historischen Wurzeln findest Du ja im obigen Link von Hermann.
Jede Existenzbehauptung über endliche Mengen ist in der Regel mit dem
Schubfachprizip beweisbar.Das Prinzip ist eine reine
Existenzbehauptung.Trotz seiner Einfachheit hat es eine Fülle ganz
unerwarteter Anwendungen vor allem in Kombinatorik und Zahlentheorie.
Die Haupschwierigkeit bei seiner Anwendung liegt bei der Bestimmung
der "Gegenstände" und der "Schubfächer".
Nun zum formal-mathematischen Teil:
1.)Voraussetzungen:Die Peano-Axiome,welche die natürlichen Zahlen
implizit definieren.Die kleinste natürliche Zahl sei die Null.Die
Grundbegriffe wie z.B. injektiv,surjektiv,bijektiv,gleichmächtig etc.
2.)Definition: I(0):= leere Menge und I(n):=I(n-1)U {n-1} für alle
n>=1,n aus N;wobei U "vereinigt mit" bedeuten soll.
Es ist also I(n)={0,1,2,3,....,n-1}.I(n) wird auch Anfangsabschnitt
von N genannt.
Definition des Begriffes "endliche Menge":
Eine Menge A heißt endlich genau dann,wenn es eine natürliche Zahl n
derart gibt,daß A gleichmächtig mit I(n) ist.
3.)Vor der exakten Formulierung des Prinzips noch einige
nichttrivialen Sätze:
Satz1: Ist B eine echte Teilmenge von I(n),dann sind die Mengen B und
I(n) nicht gleichmächtig;d.h. es gibt keine bijektive Abbildung von
I(n) auf eine ihrer echten Teilmengen.
Der nichttriviale Beweis wird induktiv geführt.
Für "gleichmächtig" verwende ich jetzt das Symbol ~ .
Satz2:I(n)~I(m) <=> n=m .
Wichtige Folgerung daraus: Wenn A~I(m) und A~I(n),dann ist I(m)~I(n)
=> m=n .
D.h.,wenn A eine endliche Menge ist,dann gibt es genau ein n aus
N,sodaß A~I(n).Diese eindeutig bestimmte Zahl n heißt dann die
"Mächtigkeit" oder "Kardinalzahl" von A .Man schreibt |A|:=n .
Man sagt auch n ist die Anzahl der Element von A .
Man schreibt auch A={a_0,a_1,a_2,....,a_(n-1)}.
Satz3:Für zwei endliche Mengen A un B gilt: A~B <=> |A|=|B| .
Satz4:Ist |A| > |B| > 0 ,so gibt es eine surjektive Abbildung der
endlichen Menge A auf die endliche Menge B .
4.)
Satz5 (Dirichlet'sches Schubfachprinzip):
Es seien A und B zwei endliche Mengen mit |A| > |B| > 0.Weiters sei f
eine surjektive Abbildung von A auf B (so ein f existiert nach Satz4).
Dann gibt es ein b aus B und zwei verschiedene a_1,a_2 aus A mit
f(a_1)=f(a_2)=b .
Anschaulich ist A die Menge der Gegenstände und B die Menge der
Schubfächer.
Dirichlet bewies unter Verwendung des Schubfachprinzips den folgenden
Satz:Ist x eine irrationale Zahl,dann gibt es unendlich viele
irreduzible Brüche p/q ,so daß |p/q - x| < 1/q^2 .
Bemerkung: p/q heiß irreduzibel,genau dann,wenn ggT(p,q)=1 ist.
Viele Anwendungsbeispiele enthält der Artikel "Das Schubfachprinzip"
von Arthur Engel und Horst Severin in der Zeitschrift "Der
Mathematikunterricht" (MU),Heft1,1979 .
Viele Grüße,
Wolfgang Kirschenhofer
Rainer Rosenthal
Timo Heuser wrote
> ich würde einfach so etwas in der Richtung sagen:
> [ Hübsche Rechnung gesnippt]
>
> Weiß allerdings nicht, ob das eine Antwort war,
> wie du sie wolltest ;)
Sagen wir mal so: Die Antwort ist in Einklang mit
der Gültigkeit des Prinzips. In einem Bereich, wo
man dividieren und andere schöne Operationen
durchführen kann, ist es offenbar gültig. Aber
wie ist es "in den Sphären des reinen Seins" ;-)
Auf die Mengenlehre als Fundament ist Wolfgang
Kirschenhofer inzwischen eingegangen in einem
sehr lesenswerten Artikel.
Gruss,
Rainer Rosenthal
r.ros...@web.de
Rainer Rosenthal
Wolfgang Kirschenhofer wrote
> Rainer Rosenthal schrieb:
> >>>Ist das Dirichletsche Schubfachprinzip oder
> >>>auch einfach Schubfachprinzip AKA pigeon
> >>>hole principle eigentlich ein Axiom?
>
> mathematische Basis des Schubfachprinzips("Pigeonhole
> Principle") verstehen.
> Zunächst zwei Vorbemerkungen:
Hallo Wolfgang,
der Begriff "Freak" ist vielleicht ein wenig sehr salopp
dahergekommen. Ich danke Dir für die tiefer gehende
Beantwortung meiner Frage.
>
> 1.)Die axiomatische Basis des Schubfachprinzips sind die
> Peano-Axiome und der Begriff der "endlichen Menge". Das
> Schubfachprinzip ist dann jedenfalls ein beweisbarer Satz.
Fein. Sowas dachte ich mir.
> Will man eine Stufe tiefer gehen,dann kann man die
> natürlichen Zahlen nach der Methode von John von Neumann
> auf der Basis der Zermelo-Fraenkel-Axiome konstruieren
> und die Peano-Axiome werden beweisbare Sätze (abgesehen
> vom Induktionsaxiom).
Ja, jetzt wird's aber doch eindeutig "freaky" :-)
Und dann: "Peano-Axiome ohne Induktionsaxiom", ist das nicht
wie "Auto ohne Räder"?
> Diese "tiefere" Betrachtungsweise braucht man zum formalen
> Verständnis des Schubfachprinzips aber nicht.
> Literatur dazu: H.B.Enderton:Elements of Set Theory.
> Oder ein Buch, welches u.a. auch für Lehrer an Höheren Schulen
> geschrieben wurde: E.Hlawka,Ch.Binder,R.Schmitt:Grundbegriffe der
> Mathematik, Prugg-Verlag, Wien 1979, ISBN 3-85385-038-3
Merci. Für interessierte Mitleser sicher gut zu wissen.
Mein innerer Antrieb für die Thread-Auslösung war die
Unsicherheit darüber, ob sich da "etwa" gesunder Menschen-
verstand in die Welt der Bierseidel AKA Axiomatik einge-
schlichen haben könnte. Ich bin beruhigt, dass das nicht
der Fall ist :-)
>
> 2.)Das Schubfachprinzip kann man etwas allgemeiner folgendermaßen
> formulieren:Werden mindestens q*s+1 Gegenstände in s Schubfächer
> getan,so enthält dann mindestens ein Schubfach mehr als q Gegenstände.
Mindestens ein "mindestens" scheint mir übertrieben, nämlich das
erste. Wenn ich weiss, dass genau q*s+1 Gegenstände diese
wunderbare Wirkung haben, dann werden mehr Gegenstände diese Wirkung
erst recht haben. Der wirklich wichtige Teil ist doch das zweite
"mindestens", welches die ersehnte Existenzaussage enthält.
> Die historischen Wurzeln findest Du ja im obigen Link von Hermann.
Ja, das war wieder was "zum Einsacken". Vielleicht kommt ja auch
noch der angekündigte Nachtrag?
> Die Haupschwierigkeit bei seiner Anwendung liegt bei der
> Bestimmung der "Gegenstände" und der "Schubfächer".
Genau aus der Ecke kommt es, dass ich mir zu dem Thema Gedanken
gemacht habe. In de.rec.denksport hatte Gerhard Woeginger nämlich
diese Aufgabe gestellt:
======================================================
Zeige:
Wenn 10 Punkte in einem Kreis mit Radius 5 liegen,
dann haben zwei von ihnen Abstand kleiner gleich 4.
======================================================
Als Lösungstipp gab er an, man möge das Schubfachprinzip verwenden.
Da habe ich bloss Bahnhof verstanden: Ich nix Schubfächer sehen.
Dann aber kam ein Lösungs-Posting von Bertram Felgenhauer, das
mit den folgenden Worten begann:
Zerlege den Kreis folgendermassen in 9 Flaechen:
Und schon brauchte ich nicht mehr weiter zu lesen! Klar, ich musste
die Schubfächer selber zurechtsägen. Und zwar 9 Stück und alle so
gross, dass irgend zwei Punkte darin nicht weiter als 4 auseinander
liegen. Der erste Ansatz sah dann auch genau so aus, wie ihn Bertram
Felgenhauer beschrieb:
1. entferne einen Kreis mit Durchmesser 4 aus der Mitte.
2. Zerlege den uebrig bleibenden Kreisring in 8 gleich
grosse Sektoren.
Eine kleine Pythagoras-Rechnung zeigte dann, dass ausser dem sowieso
Durchmesser 4 habenden Schubfach (1.) auch alle anderen 8 Fächer (2.)
keinen grösseren Durchmesser haben. Und das war's dann, weil bei
10 Punkten die "Existenz" eines Störenfrieds gesichert war.
(Eine kleine stolze Anmerkung: Die Anzahl 10 habe ich inzwischen auf
sogar 9 reduzieren können. Dabei habe ich die Frechheit gehabt, von
einer "nicht-diskreten Variante" des Schubfachprinzips zu sprechen.
news:bgejof$o2q7n$1...@ID-54909.news.uni-berlin.de )
(Endlich habe ich es kapiert: mittels news:xxxxxx habe ich die Referenz
so kenntlich gemacht, dass man auch ohne groups.google.com mit
blossem Draufdrücken zu dem Posting gelangt. Dank an Michael Kauffmann.
Allerdings ist groups.google.com trotzdem empfehlenswert, wenn man sich
die Thread-Umgebaung anschauen will.)
>
> Nun zum formal-mathematischen Teil:
>
> 1.)Voraussetzungen:Die Peano-Axiome,welche die natürlichen Zahlen
> implizit definieren.
> [... weitere Herleitung...]
> 4.)
> Satz5 (Dirichlet'sches Schubfachprinzip):
>
> Dirichlet bewies unter Verwendung des Schubfachprinzips den
> folgenden Satz:
>
> ====================================
> Ist x eine irrationale Zahl,dann
> gibt es unendlich viele irreduzible
> Brüche p/q ,so daß |p/q - x| < 1/q^2
> ====================================
>
> Bemerkung: p/q heiß irreduzibel,genau dann,wenn ggT(p,q)=1 ist.
Das Ding ist eine mathematische Perle, finde ich. Ich fand es
erstmals in Minkowskis "Geometrie der Zahlen". Weil es ein wenig
schwieriger ist als "quadratische Ergänzung" und mir erst in
späteren Lebensjahren über den Weg gelaufen war, kriege ich es
aus dem Stand nicht hin, die Beweisführung zu bringen. Wenn man
mich zwänge, würde ich es aber versuchen. Sollte jemand anderes
den dringenden Wunsch verspüren, den Beweis hierherzusetzen -
nichts wäre mir willkommener :-)
>
> Viele Anwendungsbeispiele enthält der Artikel "Das Schubfach-
> prinzip" von Arthur Engel und Horst Severin in der Zeitschrift
> "Der Mathematikunterricht" (MU),Heft1,1979 .
Könnte das *der* Engel gewesen sein, bei dem wir in Berlin im
ersten Semester "Darstellende Geometrie" hatten? Oder nee, ich
glaube, er hat uns was über "Determinanten und Matrizen" vorge-
lesen. Im Schulbereich war er jedenfalls tätig, das weiss ich.
Mit freundlichen Grüssen,
Rainer Rosenthal
r.ros...@web.de
Paul Ebermann
> 4.)
> Satz5 (Dirichlet'sches Schubfachprinzip):
> Es seien A und B zwei endliche Mengen mit |A| > |B| > 0.Weiters sei f
> eine surjektive Abbildung von A auf B (so ein f existiert nach Satz4).
> Dann gibt es ein b aus B und zwei verschiedene a_1,a_2 aus A mit
> f(a_1)=f(a_2)=b .
Die Voraussetzung "surjektiv" benötigt man nicht -
das gilt für jede Abbildung.
Paul
Wolfgang Kirschenhofer
> Wolfgang Kirschenhofer wrote
>
>>Rainer Rosenthal schrieb:
>>
>>>>>Ist das Dirichletsche Schubfachprinzip oder
>>>>>auch einfach Schubfachprinzip AKA pigeon
>>>>>hole principle eigentlich ein Axiom?
>>>>
>>Ohne ein Grundlagen-Freak sein zun müssen, kann man die
>>mathematische Basis des Schubfachprinzips("Pigeonhole
>>Principle") verstehen.
>>Zunächst zwei Vorbemerkungen:
>
>
> Hallo Wolfgang,
>
>>1.)Die axiomatische Basis des Schubfachprinzips sind die
>>Peano-Axiome und der Begriff der "endlichen Menge". Das
>>Schubfachprinzip ist dann jedenfalls ein beweisbarer Satz.
>
>
> Fein. Sowas dachte ich mir.
>
>>Will man eine Stufe tiefer gehen,dann kann man die
>>natürlichen Zahlen nach der Methode von John von Neumann
>>auf der Basis der Zermelo-Fraenkel-Axiome konstruieren
>>und die Peano-Axiome werden beweisbare Sätze (abgesehen
>>vom Induktionsaxiom).
>
>
> Ja, jetzt wird's aber doch eindeutig "freaky" :-)
> Und dann: "Peano-Axiome ohne Induktionsaxiom", ist das nicht
> wie "Auto ohne Räder"?
Hallo Rainer !
Hier muß ich entschieden protestieren:
Von Peano-Axiomen ohne Induktionsaxiom habe ich keineswegs gesprochen.
Das Induktionsaxiom gehört natürlich zu den Peanoaxiomen dazu,wie die
"Räder zum Auto".
Hier hast Du mich mißverstanden.
Dieses Mißverständnis,für welches ich mich teilweise verantwortlich
fühle,hat inzwischen vermutlich Thomas Haunhorst aufgeklärt.
Was ich meinte war,daß man die Peanoaxiome im Rahmen der Axiomatik von
Zermelo-Fraenkel alle beweisen kann,wobei Zermelo Fraenkel das
Induktionsaxiom im wesentlichen bereits selbst in Form des sogenannten
Unendlichkeitsaxioms enthält.Das Peanosche Induktionsaxiom ist dann
eine triviale Folgerung des Unendlichkeitsaxioms,wie ja Thomas
Haunhorst bereits gesagt hat.
Das "Unendlichkeitsaxiom" nach Zermelo-Fraenkel lautet folgendermaßen:
Es gibt eine Menge A mit folgenden Eigenschaften:A enthält die leere
Menge und für alle a aus A gilt,daß auch der Nachfolger a+ in A
liegt.Wobei a+ := a U {a} definiert ist. U heißt wieder "vereinigt mit".
Eine derartige Menge A nennt man induktive Menge.Jedes Element der
Menge A ist selbst wieder eine Menge.
N ist dann,wie schon Thomas gesagt hat,die kleinste induktive Menge.
Was ich also - vielleicht etwas zu großzügig und von mir vielleicht
mißverständlich formuliert - meinte,war nur,daß das Induktionsaxiom im
Rahmen von Peano auch "im wesentlichen" ein Axiom im Rahmen von
Zermelo-Fraenkel ist.Ich habe hier an die historischen Wurzeln des
Unendlichkeitsaxioms von Zermelo-Fraenkel gedacht.
Die Bemerkung in der Klammer kannst Du also getrost vergessen;ich habe
sie ja bewußt in Klammer gesetzt.Wenn ich gewußt hätte,daß sie
Verwirrung stiftet, hätte ich sie gar nicht gemacht.
>>Die Haupschwierigkeit bei seiner Anwendung liegt bei der
>>Bestimmung der "Gegenstände" und der "Schubfächer".
.................................................................
> Genau aus der Ecke kommt es, dass ich mir zu dem Thema Gedanken
> gemacht habe. In de.rec.denksport hatte Gerhard Woeginger nämlich
> diese Aufgabe gestellt:
>
> ======================================================
> Zeige:
> Wenn 10 Punkte in einem Kreis mit Radius 5 liegen,
> dann haben zwei von ihnen Abstand kleiner gleich 4.
> ======================================================
Das ist ein schönes Beispiel für eine Anwendung des Schubfachprinzips.
> Als Lösungstipp gab er an, man möge das Schubfachprinzip verwenden.
> Da habe ich bloss Bahnhof verstanden: Ich nix Schubfächer sehen.
> Dann aber kam ein Lösungs-Posting von Bertram Felgenhauer, das
> mit den folgenden Worten begann:
>
> Zerlege den Kreis folgendermassen in 9 Flaechen:
>...........................................................
>>Nun zum formal-mathematischen Teil:
>.......................................................
>
>>Viele Anwendungsbeispiele enthält der Artikel "Das Schubfach-
>>prinzip" von Arthur Engel und Horst Severin in der Zeitschrift
>>"Der Mathematikunterricht" (MU),Heft1,1979 .
> .............................................................
> Könnte das *der* Engel gewesen sein, bei dem wir in Berlin im
> ersten Semester "Darstellende Geometrie" hatten? Oder nee, ich
> glaube, er hat uns was über "Determinanten und Matrizen" vorge-
> lesen. Im Schulbereich war er jedenfalls tätig, das weiss ich.
Als Österreicher weiß ich das nicht.Ich weiß nur, daß Arthur Engel
jahrzehntelang in der damaligen Bundesrepublik die deutsche Mannschaft
für die IMO trainierte und auch leitete.Persönlich habe ich ihn vor
vielen Jahren an der Uni Linz kennengelernt.
Seine Artikel und Bücher liest man mit großem Vergnügen.
Sie sind sowohl von den mathematischen Inhalten als auch aus
methodisch-didaktischer Sicht "Perlen".
> Mit freundlichen Grüssen,
> Rainer Rosenthal
> r.ros...@web.de
Viele Grüße und ein schönes Wochenende,
Wolfgang
Hermann Kremer
>
>> >Ist das Dirichletsche Schubfachprinzip oder
>> >auch einfach Schubfachprinzip AKA pigeon
>> >hole principle eigentlich ein Axiom?
>>
>> Laut http://members.aol.com/jeff570/mathword.html
>> hat Dirichlet es bereits 1834 eingeführt; nach der
>> Quelle muß ich aber noch suchen.
>
>Das ist wieder mal sehr freundlich. Hast Du eine
>persönliche Meinung dazu
Ja ... 1834 war er noch in Berlin und veröffentlichte daher in den
Abhandlungen der Preussischen Akad. d. Wiss., und die sind
noch nicht bei GDZ gescannt ...
Bleibt also noch gallica / Bibliothèque Nationale de France, und
das ist im Moment eine Baustelle: Nous regrettons ... sous construction ...
Aber ich bleibe dran ...
>oder ist Dir das so lang wie breit?
Hä ... wie soll ich das verstehen ... Quadrat?
>> ... [HJ]_Stenopterygius_und_die_Bibel
>> unter dem heutigen Datum finden ;-)
>
>Nein danke.
Hä ... Du wolltest doch Bibel-Zitate ...
Grüße
Hermann
--
>Gruss,
>Rainer Rosenthal
>r.ros...@web.de
>
Hermann Kremer
Hallo Rainer,
>> >Ist das Dirichletsche Schubfachprinzip oder
>> >auch einfach Schubfachprinzip AKA pigeon
>> >hole principle eigentlich ein Axiom?
>>
>> Laut http://members.aol.com/jeff570/mathword.html
>> hat Dirichlet es bereits 1834 eingeführt; nach der
>> Quelle muß ich aber noch suchen.
>
>Das ist wieder mal sehr freundlich. Hast Du eine
>persönliche Meinung dazu
Ja
>oder ist Dir das so lang wie breit?
???
OK, ich habe gerade einen Hintereingang zur BNF in Paris entdeckt ...
es kann sich also nur noch um Stunden handeln ;-)
>> ... [HJ]_Stenopterygius_und_die_Bibel
>> unter dem heutigen Datum finden ;-)
>
>Nein danke.
OK, dann nicht ... aber weil's so schön ist
====================================
Der Ichthyosaurus.
Von Victor von Scheffel (1868)
Es rauscht in den Schachtelhalmen,
Verdächtig leuchtet das Meer,
Da schwimmt mit Tränen im Auge
Ein Ichthyosaurus daher.
Ihn jammert der Zeiten Verderbnis,
Denn ein sehr bedenklicher Ton
War neuerlich eingerissen
In der Liasformation.
,,Der Plesiosaurus, der Alte,
Er jubelt in Saus und Braus,
Der Pterodaktylus selber
Flog neulich betrunken nach Haus.
Der Iguanodon, der Lümmel,
Wird frecher zu jeglicher Frist,
Schon hat er am hellen Tage
Die Ichthyosaura geküßt.
Mir ahnt eine Weltkatastrophe,
So kann es ja länger nicht gehn.
Was soll aus dem Lias noch werden,
Wenn solche Dinge geschehn?'' [*]
So klagte der Ichthyosaurus,
Da ward es ihm kreidig zumut;
Sein letzter Seufzer verhallte
Im Qualmen und Zischen der Flut.
Es starb zu derselbigen Stunde
Die ganze Saurierei,
Sie kamen zu tief in die Kreide,
Da war es natürlich vorbei.
Und der uns hat gesungen
Dies petrefaktische Lied,
Der fand's als fossiles Albumblatt
Auf einem Koprolith.
====================================
[*] Aus der Lias wurde dann doch noch was, nämlich Dogger ...
Wolfgang Kirschenhofer
> On Sat, 02 Aug 2003 19:58:36 +0100,
> Wolfgang Kirschenhofer <ki...@kstp.at> wrote:
>...................................................................
>
> Wenn du "enthalten" im Sinne von "implizieren" meinst, dann folgen alle
> Peano-Axiome aus ZF, d.h. insbesondere das alle Peano-Axiome beweisbar
> sind. Ueberhaupt sind ja in diesem Sinne alle Saetze in ZF "enthalten",
> die aus ZF folgen, also beweisbar sind. Das Induktionsaxiom IA ist aber
> selbst kein Axiom von ZF, daher auch nicht trivial ableitbar, also im
> Sinne von a|-a. Es wird ja aus ZF abgeleitet und gehoert selbst nicht zum
> Axiomensystem.
> Genausogut koenntest du sagen, dass 1>0 in den Axiomen des Koerpers der
> Reellen Zahlen enthalten ist. Aber auch das muss man erst beweisen, und
> 1>0 ist dort kein Axiom! (Wobei man ja auch hier noch zeigen muss, dass
> es genau eine 1 gibt.)
> .......................................................................
> Natuerlich ist der Beweis einfach, jedoch nicht trivial. Trivial ist ein
> Beweis der folgenden Art: a|-a.
>
>
> Gruss, Thomas.
> --
Hallo Thomas !
Danke für die Klarstellung.Meine falsche Bemerkung war nicht nur
leichtfertig,sondern im Zusammenhang mit dem Schubfachprinzip völlig
unnötig.
Grüße,
Wolfgang
Hermann Kremer
>> Rainer Rosenthal schrieb:
>> >>>Ist das Dirichletsche Schubfachprinzip oder
>> >>>auch einfach Schubfachprinzip AKA pigeon
>> >>>hole principle eigentlich ein Axiom?
>> Die historischen Wurzeln findest Du ja im obigen Link von Hermann.
>
>Ja, das war wieder was "zum Einsacken". Vielleicht kommt ja auch
>noch der angekündigte Nachtrag?
Ja, er kommt ja schon ... und hier ist er:
G. L. Dirichlet: Einige neue Sätze über unbestimmte Gleichungen.
Abhandlungen der Königlich Preussischen Akademie der Wissenschaften
von 1834. 1834, S. 649 - 664
Auch in:
G. Lejeune Dirichlet's Werke. Herausgegeben auf Veranlassung der
Königlich Preussischen Akademie der Wissenschaften von L. Kronecker,
fortgesetzt von L. Fuchs.
Berlin: Georg Reimer. Band 1: 1889, Band 2: 1897.
Der Aufsatz ist dort in Bd. 1, S. 219 - 236 abgedruckt.
Die "Werke" sind online unter:
Bibliothèque Nationale des France, Paris (momentan Baustelle ...)
http://gallica.bnf.fr/
--> Recherche --> Auteur Dirichlet
University of Michigan, Ann Arbor
http://www.hti.umich.edu/cgi/t/text/text-idx?tpl=browse.tpl&c=umhistmath
--> Browse L (wie Lejeune ...)
Bei Dirichlet's "unbestimmten Gleichungen" handelt es sich übrigens
um die Pell'schen Gleichungen x^2 - A*y^2 = B.
Ich habe das Paper aber bisher noch nicht komplett gelesen. Da man
es als PDF-Datei von Paris momentan nicht downloaden kann, und von
Ann Arbor überhaupt nicht, sondern dort nur gegen $$ eine Kopie bestellen
kann, ist das Lesen ziemlich mühsam ...
>> Dirichlet bewies unter Verwendung des Schubfachprinzips den
>> folgenden Satz:
>>
>> ====================================
>> Ist x eine irrationale Zahl,dann
>> gibt es unendlich viele irreduzible
>> Brüche p/q ,so daß |p/q - x| < 1/q^2
>> ====================================
>>
>> Bemerkung: p/q heiß irreduzibel,genau dann,wenn ggT(p,q)=1 ist.
Beweis in dem 80-Seiten Paper:
Recherches sur les formes quadratiques à coefficients et à
indéterminées complexes.
(Crelle's) J. f. d. reine und angewandte Mathematik 24 (1842), S. 291 - 371.
Werke Bd. 1, S. 533 - 618.
In Dirichlet's Werken habe ich auch auf Anhieb die Abhandlung mit dem
Beweis für die unendlich vielen Primzahlen in jeder arithmetischen Folge
mit zum Anfangsglied teilerfremder Schrittweite gefunden ... und natürlich
auch den Aufsatz über die Dirichlet'schen Bedingungen für Fourierreihen ...
>Das Ding ist eine mathematische Perle, finde ich. Ich fand es
>erstmals in Minkowskis "Geometrie der Zahlen".
Minkowski ist gutes Stichwort. Hermann Minkowski hat irgendwann
und irgendwo eine Gedenkrede auf Peter Gustav Lejeune Dirichlet
gehalten, in dem das Schubfach-Prinzip ebenfalls vorkam ... ich suche
noch ...
BTW: Auf italienisch heißt es "Il principio della piccionaia" ...
http://digilander.libero.it/basecinque/combinatoria/piccionaia.htm
... und hier ist auch noch was über das "Taubenlochprinzip":
http://www.matheplanet.com/matheplanet/nuke/html/article.php?sid=236
Grüße
Hermann
--
PS: So, und jetzt gehe ich wieder zum Saurierfüttern ...
Rainer Rosenthal
Wolfgang Kirschenhofer wrote
> Ich weiß nur, daß Arthur Engel jahrzehntelang in der
> damaligen Bundesrepublik die deutsche Mannschaft für
> die IMO trainierte und auch leitete.Persönlich habe
> ich ihn vor vielen Jahren an der Uni Linz kennengelernt.
> Seine Artikel und Bücher liest man mit großem Vergnügen.
> Sie sind sowohl von den mathematischen Inhalten als auch aus
> methodisch-didaktischer Sicht "Perlen".
>
Hallo Wolfgang,
Dein Protest ist angekommen und angenommen :-)
Dieser Herr Engel ist dann wohl sicher ein anderer.
Auf Deine Empfehlung hin werde ich meinem Antiquar
den Tipp geben, mir was aufzufinden. Danke.
Gruss,
Rainer Rosenthal
r.ros...@web.de
Rainer Rosenthal
Thomas Haunhorst
> Natuerlich ist der Beweis einfach, jedoch nicht trivial.
> Trivial ist ein Beweis der folgenden Art: a|-a.
>
Hallo Thomas,
bevor ich Dich falsch interpretiere: Würdest Du bitte
so freundlich sein und mir den Beweisweg skizzieren,
der von einer minimalen axiomatischen Basis aus zum
Beweis des Schubfachprinzips führt?
Oder habe ich das Wesentliche erfasst, wenn ich sage,
dass das Induktionsaxiom in ZF enthalten ist und zum
Beweis des Schubfachprinzips ausreicht? (Entschuldige,
ich habe doch eine Interpretation gewagt, fühle mich
aber wie auf Glatteis.)
Gruss,
Rainer Rosenthal
r.ros...@web.de
Rainer Rosenthal
Hermann Kremer wrote
> [viele interessante Links]
> Minkowski ist gutes Stichwort. Hermann Minkowski
> hat irgendwann und irgendwo eine Gedenkrede auf
> Peter Gustav Lejeune Dirichlet gehalten, in dem
> das Schubfach-Prinzip ebenfalls vorkam ... ich
> suche noch ...
>
Hermann der Leuchtturm! Besten Dank auch.
> PS: So, und jetzt gehe ich wieder zum Saurierfüttern ...
Mahlzeit!
Gruss,
Rainer
Paul Ebermann
> Thomas Haunhorst
>
> > Natuerlich ist der Beweis einfach, jedoch nicht trivial.
> > Trivial ist ein Beweis der folgenden Art: a|-a.
>
> bevor ich Dich falsch interpretiere: Würdest Du bitte
> so freundlich sein und mir den Beweisweg skizzieren,
> der von einer minimalen axiomatischen Basis aus zum
> Beweis des Schubfachprinzips führt?
>
> Oder habe ich das Wesentliche erfasst, wenn ich sage,
> dass das Induktionsaxiom in ZF enthalten ist und zum
> Beweis des Schubfachprinzips ausreicht?
Mein Verständnis:
Das hängt an dem Verständnis von "enthalten" :-)
Das Induktionsaxiom ist in ZF kein Axiom, sondern
ein Satz (also nicht in der "Menge der ZF-Axiome"
enthalten, aber in der "Menge der aus den ZF-Axiomen
folgerbaren Sätze" enthalten).
Allerdings ist das ZF-Unendlichkeitsaxiom sehr
nah verwandt mit den Peano-Axiomen, ich würde
sogar behaupten, dass (unter der Voraussetzung
der anderen ZF-Axiome) die Aussagen
"Das durch die Peano-Axiome beschriebene
N (in der Modellierung 0 = {}, x+ = x U {x})
ist eine Menge."
und
"Das ZF-Unendlichkeitsaxiom gilt."
äquivalent sind.
Die Menge N (mit üblichem Modell) ist ja
gerade ein Beispiel für eine induktive
Menge (deren Existenz vom Unendlichkeitsaxiom
gefordert wird), und zwar die kleinste solche
(nach Peano-Induktionsaxiom).
Paul
Rudolf Polzer
> > Viele Anwendungsbeispiele enthält der Artikel "Das Schubfach-
> > prinzip" von Arthur Engel und Horst Severin in der Zeitschrift
> > "Der Mathematikunterricht" (MU),Heft1,1979 .
Dann kann ich noch "Problem Solving Strategies" empfehlen. Auch von
Arthur Engel. Enthält eher "alles Mögliche".
Ich sehe gerade, eine interessante Formulierung von ihm in diesem
Buch: "Every existence problem about finite and, sometimes, infinite
^^^^^
sets is usually solved by the box principle."
^^^^^^^
SCNR, ist mir eben erst aufgefallen. Wirklich.
> Könnte das *der* Engel gewesen sein, bei dem wir in Berlin im
> ersten Semester "Darstellende Geometrie" hatten?
Unwahrscheinlich.
> Oder nee, ich
> glaube, er hat uns was über "Determinanten und Matrizen" vorge-
> lesen. Im Schulbereich war er jedenfalls tätig, das weiss ich.
Bringst du ihn mit der Phrase "Jaaaa... und nun ist es so..." sowie
häufiger Verwendung von "und so weiter" in Verbindung? Wenn nicht,
ist das ein anderer. Die Rede hier ist von dem Arthur Engel, der
das IMO-Training leitet (oder geleitet hat, dieses Jahr bin ich zu
alt). 1999-2002 war ich beim Training, 2000-2002 auf der IMO.
Das Schubfachprinzip bezeichnet er übrigens im Englischen als "box
principle" - nix mit Tauben.
--
Story? Du meinst, es gibt auch eine Fassung dieser geschichten mit Story?
Das wäre mir neu... :D
["il cervello cattivo di Tenchi" in daani]
Hermann Kremer
>
>> [viele interessante Links]
>> Minkowski ist gutes Stichwort. Hermann Minkowski
>> hat irgendwann und irgendwo eine Gedenkrede auf
>> Peter Gustav Lejeune Dirichlet gehalten, in dem
>> das Schubfach-Prinzip ebenfalls vorkam ... ich
>> suche noch ...
>
>Hermann der Leuchtturm! Besten Dank auch.
Aber bitte, gern geschehen ... und hier ist sie:
Hermann Minkowski: Rede auf Dirichlet.
Peter Gustav Lejeune Dirichlet und seine Bedeutung für die heutige
Mathematik.
Jahresbericht der Deutschen Mathematiker-Vereinigung 14(1905), S. 149-163.
Auch online in:
Gesammelte Abhandlungen von Hermann Minkowski.
Unter Mitwirkung von Andreas Speiser und Hermann Weyl.
Herausgegeben von David Hilbert.
Leipzig und Berlin: B. G. Teubner 1911. Bd. 2, S. 447-461, speziell S. 454.
http://www.hti.umich.edu/cgi/t/text/text-idx?tpl=browse.tpl&c=umhistmath
--> Browse M
Und hier wie üblich:
===================================================
Electronic Research Archive for Mathematics Jahrbuch Database
JFM 36.0013.01
Minkowski, Hermann.
Peter Gustav Lejeune-Dirichlet und seine Bedeutung für die heutige
Mathematik. Rede. (Mit Bildnis.) [J]
Deutsche Math. Ver. 14, 149-163.
Published: (1905)
Eine Rede, gehalten in der Festsitzung der Göttinger Mathematischen Gesellschaft
bei der hundertjährigen Wiederkehr des Geburtstages von {\it Lejeune-Dirichlet},
am 13. Februar 1905. Sie feiert {\it Dirichlet} als zu Göttingen gehörig, zur
Georgia Augusta, die auf dem Gebiete der höheren Mathematik am rühmlichsten
an dem leitenden Gesichtspunkt festgehalten habe, dass die Universität nicht
bloss eine Bewahrerin bereits erworbener wissenschaftlicher Kenntnisse sein,
sondern auch an dem Fortbau der Wissenschaft als eines Gemeingutes der
Menschheit arbeiten soll. Nach einigen Daten aus dem Leben {\it Dirichlet}s
werden seine Leistungen auf seinem Hauptarbeitsfelde, der höheren Arithmetik,
eingehend geschildert. Kürzer legt der Redner die Verdienste {\it Dirichlet}s um
die mathematische Physik dar.
[ Müller, F.; Prof. (Weisser Hirsch bei Dresden) ]
Subject heading: Erster Abschnitt. Geschichte, Philosophie und Pädagogik.
Kapitel 1. Geschichte. A. Biographisch-Literarisches.
Jahrbuch Project: Copyright (c) 2003 European Mathematical Society
===================================================
>> PS: So, und jetzt gehe ich wieder zum Saurierfüttern ...
>
>Mahlzeit!
Danke ...
Rainer Rosenthal
Hermann Kremer
> >Hermann der Leuchtturm! Besten Dank auch.
>
> Aber bitte, gern geschehen ... und hier ist sie:
>
> Hermann Minkowski: Rede auf Dirichlet.
Hermann, der Verlässliche. Besten Dank noch einmal.
Gruss,
Rainer der Vergessliche
--
Rainer Rosenthal
r.ros...@web.de
Michael Hoppe
> Satz4:Ist |A| > |B| > 0 ,so gibt es eine surjektive Abbildung der
> endlichen Menge A auf die endliche Menge B .
Das braucht es ja nicht. Definiert man für Mengen A und B:
#A \leq #B <=> Es gibt eine injektive Abbildung f: A -> B,
so lautet das Schubfachprinzip (mit Deinen Bezeichnungen):
#I(n) \leq #I(m) => n \leq m.
Aus der Kontraposition dieser Aussage folgt die übliche Version.
Michael
--
-= Michael Hoppe <www.michael-hoppe.de>, <m...@michael-hoppe.de> =------
-= Key fingerprint = 74 FD 0A E3 8B 2A 79 82 25 D0 AD 2B 75 6A AE 63
-= PGP public key (0xE0A5731D) available on request. =---------------