Beweis des Schubfachprinzips?

29.09.2022, 13:30

Pippen

Beweis des Schubfachprinzips?

Sei n > m, n,m $\begin{eqnarray*} \in \mathbb N \end{eqnarray*}$ . Verteilt man m Dinge in n Schubfächer, so bleibt mind. ein Schubfach leer (IV).

Beweis über Induktion:

IA: m = 1, dann mind. n = 2, so dass ein Schubfach leer bliebe.

Wenn IV (s.o.), dann gilt es auch für m+1 Dinge und n+1 Schubfächer. Annahme des Gegenteils, d.h. verteilt man m+1 Dinge auf n+1 Schubfächer, dann kein Schubfach leer, doch dann gleiches Ergebnis, wenn man jeweils Eins abzieht, also m Dinge in n Schubfächer und kein Schubfach leer, im Widerspruch zur IV.

Stimmt die Beweisidee, die ich hier habe? Oder wie würdet ihr das Schubfachprinzip in dieser Variante beweisen? (Ich habe bewußt eine plastische Variante gewählt, normal würde man wahrscheinlich beweisen, dass f: {m} -> {n} nicht surjektiv ist, aber das ist so seelenlos unanschaulich.)

29.09.2022, 14:24

Elvis

Auf diesen Beitrag antworten »

Wo bleibt denn die selige Beschaulichkeit, wenn m und n wesentlich größer sind als die Anzahl der Photonen im beobachtbaren und nicht beobachtbaren Universum?

Deinen Beweis verstehe ich nicht.

29.09.2022, 16:47

Finn_

Auf diesen Beitrag antworten »

Sei $\begin{eqnarray*} M \end{eqnarray*}$ die Menge der Dinge und $\begin{eqnarray*} N \end{eqnarray*}$ die Menge der Schubfächer, so dass $\begin{eqnarray*} m=|M| \end{eqnarray*}$ und $\begin{eqnarray*} n=|N| \end{eqnarray*}$ gilt. Sei $\begin{eqnarray*} f\colon M\to N \end{eqnarray*}$ die Belegung der Schubfächer mit den Dingen. Die zu $\begin{eqnarray*} \neg N\subseteq f(M) \end{eqnarray*}$ äquivalente Aussage $\begin{eqnarray*} N\setminus f(M)\ne\emptyset \end{eqnarray*}$ stellt die Zusicherung der Existenz eines unbelegten Schubfachs dar.

Es gilt $\begin{eqnarray*} n>m\Rightarrow \neg N\subseteq f(M) \end{eqnarray*}$ zu beweisen. Dafür muss gezeigt werden, dass die Annahme von sowohl $\begin{eqnarray*} n>m \end{eqnarray*}$ als auch $\begin{eqnarray*} N\subseteq f(M) \end{eqnarray*}$ zu einem Widerspruch führt. Die Aussage $\begin{eqnarray*} N\subseteq f(M) \end{eqnarray*}$ zieht $\begin{eqnarray*} |N|\le |f(M)| \end{eqnarray*}$ nach sich. Allgemein vergrößert die Bild-Operation nicht die Mächtigkeit, womit zumal $\begin{eqnarray*} |f(M)|\le |M| \end{eqnarray*}$ gilt. Es findet sich

$\begin{eqnarray*} |M|=m<n=|N|\le|f(M)|\le |M|. \end{eqnarray*}$

Ergo gelangt man zur absurden Aussage $\begin{eqnarray*} |M|<|M|. \end{eqnarray*}$

29.09.2022, 17:34

Elvis

Auf diesen Beitrag antworten »

Wir bezweifeln nicht die Richtigkeit des Schubfachprinzips. Dein Beweis ist sicher richtig, du beweist das Schubfachprinzip sogar für beliebige Kardinalzahlen, nicht nur für endliche Mengen, das geht nicht mehr besser. Kannst du etwas zu Pippens Beweis sagen?

29.09.2022, 18:30

Finn_

Auf diesen Beitrag antworten »

Soweit ich sehe, ist Pippens Argumentation kein gültiger Beweis. Es sollte $\begin{eqnarray*} n \end{eqnarray*}$ bzw. $\begin{eqnarray*} N \end{eqnarray*}$ fest sein. Nun kann man die Induktion über $\begin{eqnarray*} m \end{eqnarray*}$ führen. Man nimmt also an, dass die Aussage für alle Funktionen $\begin{eqnarray*} M\to N \end{eqnarray*}$ gilt. Zu zeigen ist im Schritt, dass sie dann ebenso für eine beliebige Funktion $\begin{eqnarray*} f\colon M\cup\{x\}\to N \end{eqnarray*}$ mit $\begin{eqnarray*} x\notin M \end{eqnarray*}$ gilt. Der Induktionsanfang darf in $\begin{eqnarray*} m=0 \end{eqnarray*}$ liegen, da die leere Abbildung schlicht keine Schubfächer belegt.

29.09.2022, 18:48

Elvis

Auf diesen Beitrag antworten »

Dem kann ich zustimmen. Wir sehen wieder einmal, dass die Sprache der Mengenlehre, die über Mengen und Funktionen spricht, wesentlich stärker ist als die Sprache der elementaren Arithmetik, die über natürliche und ganze Zahlen spricht.

29.09.2022, 20:58

zweiundvierzig

Auf diesen Beitrag antworten »

Das Schubfachprinzip kann man schon in Peano-Arithmetik beweisen, siehe z.B. M. Ajtai: Parity and the Pigeonhole Principle oder SE: Show that PA can prove the pigeon-hole principle.

29.09.2022, 22:12

Elvis

Auf diesen Beitrag antworten »

Danke für den Hinweis, dieser rein arithmetische Beweis sieht sehr interessant aus. Er geht anscheinend ein wenig über Pippens Beweisversuch hinaus. Wie Albert Einstein schon sagte : "Man sollte alles so einfach wie möglich machen, aber nicht einfacher."

29.09.2022, 23:45

Pippen

Auf diesen Beitrag antworten »

Finn‘s Beweis ist Freude

.

Bei der Gelegenheit: Warum kann man bei einem Induktionsbeweis nicht über mehrere Variablen gleichzeitig induzieren, sondern muss darauf achten, dass nur über eine induziert wird?

@Finn: Und wenn wir schonmal beim Beweisen sind. Wie findest du meinen u.g. Beweis? Elvis ist nicht angetan, ich finde aber, gerade weil {0, 1, …, n} immer nur eine endliche Menge ist, kann man so argumentieren.

[attach]56016[/attach]

30.09.2022, 01:43

Finn_

Auf diesen Beitrag antworten »

Zitat:

Original von Pippen
Bei der Gelegenheit: Warum kann man bei einem Induktionsbeweis nicht über mehrere Variablen gleichzeitig induzieren, sondern muss darauf achten, dass nur über eine induziert wird?

Sagen wir mal, $\begin{eqnarray*} A(m,n) \end{eqnarray*}$ ist irgendeine Aussage. Nun willst du beweisen, dass die für alle $\begin{eqnarray*} (m,n)\in\mathbb N\times\mathbb N \end{eqnarray*}$ erfüllt ist. Wenn es Ausnahmen geben sollte, können die als Prämisse zur Aussage hinzugefügt werden.

Würdest du den Anfang $\begin{eqnarray*} (0,0) \end{eqnarray*}$ und den Schluss von $\begin{eqnarray*} A(m,n) \end{eqnarray*}$ auf $\begin{eqnarray*} A(m+1,n+1) \end{eqnarray*}$ korrekt beweisen, ist $\begin{eqnarray*} A \end{eqnarray*}$ ja lediglich für den Streifen $\begin{eqnarray*} \{(n,n)\mid n\in\mathbb N\} \end{eqnarray*}$ bewiesen.

Vollständigkeit erreicht eine der folgenden drei Varianten:

1. Für jedes beliebige feste $\begin{eqnarray*} n \end{eqnarray*}$ den Anfang $\begin{eqnarray*} A(0,n) \end{eqnarray*}$ und den Schluss von $\begin{eqnarray*} A(m,n) \end{eqnarray*}$ auf $\begin{eqnarray*} A(m+1,n) \end{eqnarray*}$ beweisen.

2. Den Anfang $\begin{eqnarray*} A(0,0) \end{eqnarray*}$ und den Schluss von $\begin{eqnarray*} A(m,n) \end{eqnarray*}$ auf $\begin{eqnarray*} A(m+1,n) \end{eqnarray*}$ und $\begin{eqnarray*} A(m,n+1) \end{eqnarray*}$ beweisen.

3. Den Anfang $\begin{eqnarray*} A(m,0) \end{eqnarray*}$ sowie $\begin{eqnarray*} A(0,n) \end{eqnarray*}$ und den Schluss von $\begin{eqnarray*} A(m,n) \end{eqnarray*}$ auf $\begin{eqnarray*} A(m+1,n+1) \end{eqnarray*}$ für beliebige $\begin{eqnarray*} m,n \end{eqnarray*}$ beweisen.

30.09.2022, 09:15

IfindU

Auf diesen Beitrag antworten »

Zitat:

Original von Finn_
Soweit ich sehe, ist Pippens Argumentation kein gültiger Beweis. Es sollte $\begin{eqnarray*} n \end{eqnarray*}$ bzw. $\begin{eqnarray*} N \end{eqnarray*}$ fest sein. Nun kann man die Induktion über $\begin{eqnarray*} m \end{eqnarray*}$ führen. Man nimmt also an, dass die Aussage für alle Funktionen $\begin{eqnarray*} M\to N \end{eqnarray*}$ gilt. Zu zeigen ist im Schritt, dass sie dann ebenso für eine beliebige Funktion $\begin{eqnarray*} f\colon M\cup\{x\}\to N \end{eqnarray*}$ mit $\begin{eqnarray*} x\notin M \end{eqnarray*}$ gilt. Der Induktionsanfang darf in $\begin{eqnarray*} m=0 \end{eqnarray*}$ liegen, da die leere Abbildung schlicht keine Schubfächer belegt.

Was ich an dem Beweis nicht verstehe, ist wie der Induktionsschritt funktionieren soll. Aus $\begin{eqnarray*} m < n \end{eqnarray*}$ folgt i.A. nicht $\begin{eqnarray*} m+1 < n \end{eqnarray*}$ . D.h. es kann gut sein, dass $\begin{eqnarray*} m+1 = n \end{eqnarray*}$ und man damit keine leeren Schließfächer hätte.

D.h. hier müsste auch das $\begin{eqnarray*} N \end{eqnarray*}$ sich ändern. Ich denke praktischer wäre eine Induktion über $\begin{eqnarray*} n \end{eqnarray*}$ zu führen. Und der sieht dann Pippens Beweisidee ähnlich:

Angenommen es gilt für $\begin{eqnarray*} n \end{eqnarray*}$ und alle $\begin{eqnarray*} m < n \end{eqnarray*}$ . Dann zeigt man es für $\begin{eqnarray*} n+1 \end{eqnarray*}$ und alle $\begin{eqnarray*} m' <n+1 \end{eqnarray*}$ . Nun ist $\begin{eqnarray*} f^{-1}(n+1) = \emptyset \end{eqnarray*}$ oder $\begin{eqnarray*} f^{-1}(n+1) \neq \emptyset \end{eqnarray*}$ . Im ersten Fall hat man ein leeres Fach gefunden, im zweiten Fall ist die Einschränkung $\begin{eqnarray*} f|_{f^{-1}(\{1, \ldots, n\})}^{\{1, \ldots, n\}}: f^{-1}(\{1, \ldots, n\}) \to \{1, \ldots, n\} \end{eqnarray*}$ wohldefiniert und die Induktion greift.

30.09.2022, 09:51

Elvis

Auf diesen Beitrag antworten »

Zitat:

Original von Pippen

@Finn: Und wenn wir schonmal beim Beweisen sind. Wie findest du meinen u.g. Beweis? Elvis ist nicht angetan, ich finde aber, gerade weil {0, 1, …, n} immer nur eine endliche Menge ist, kann man so argumentieren.

[attach]56016[/attach]

Matthäus 5:37 Eure Rede aber sei: Ja, ja; nein, nein. Was darüber ist, das ist vom Übel.
Jakobus 5:12 Vor allen Dingen aber, meine Brüder, schwöret nicht, weder bei dem Himmel noch bei der Erde noch mit einem andern Eid. Es sei aber euer Wort: Ja, das Ja ist; und: Nein, das Nein ist, auf daß ihr nicht unter das Gericht fallet.
Johannes 8:44 Ihr seid von dem Vater, dem Teufel, und nach eures Vaters Lust wollt ihr tun. Der ist ein Mörder von Anfang und ist nicht bestanden in der Wahrheit; denn die Wahrheit ist nicht in ihm. Wenn er die Lüge redet, so redet er von seinem Eigenen; denn er ist ein Lügner und ein Vater derselben.
Für Mathematiker heißt das: Was wahr ist, bleibt wahr; was falsch ist, bleibt falsch.

30.09.2022, 10:21

laila49

Auf diesen Beitrag antworten »

Zitat:

Original von Elvis

Für Mathematiker heißt das: Was wahr ist, bleibt wahr; was falsch ist, bleibt falsch.

Johannes 18,38: Was ist Wahrheit?

30.09.2022, 11:12

Elvis

Auf diesen Beitrag antworten »

Das wissen wir auch heute noch nicht so ganz genau. In der Aussagenlogik fängt man damit an, von jeder Aussage per Axiom zu verlangen, dass sie entweder wahr oder falsch ist. Was eine Aussage ist wissen wir auch nicht so ganz genau. Was bleibt ist die Relation, die durch das Axiom festgelegt wird : Eine Aussage ist entweder wahr oder falsch. Wie der Baron von Münchhausen zieht sich die Logik am eigenen Schopf aus dem Sumpf des Unwissens. So macht man das in der gesamten Mathematik und der Wissenschaft überhaupt.

30.09.2022, 13:59

Finn_

Auf diesen Beitrag antworten »

Zitat:

Original von IfindU
Was ich an dem Beweis nicht verstehe, ist wie der Induktionsschritt funktionieren soll. Aus $\begin{eqnarray*} m < n \end{eqnarray*}$ folgt i.A. nicht $\begin{eqnarray*} m+1 < n \end{eqnarray*}$ . D.h. es kann gut sein, dass $\begin{eqnarray*} m+1 = n \end{eqnarray*}$ und man damit keine leeren Schließfächer hätte.

Im Schritt ist $\begin{eqnarray*} m+1<n\Rightarrow\neg N\subseteq f(M\cup\{x\}) \end{eqnarray*}$ zu zeigen. Das heißt, es darf $\begin{eqnarray*} m+1<n \end{eqnarray*}$ im Beweis von $\begin{eqnarray*} \neg N\subseteq f(M\cup\{x\}) \end{eqnarray*}$ benutzt werden.

Neue Frage »

Antworten »

Beweis des Schubfachprinzips?

Verwandte Themen