Intervallbeweis < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:18 Do 16.02.2012 | | Autor: | clemenum |
| Aufgabe | Sei $n>1 [mm] \in \mathbb{Z}.$ [/mm] Sei $M$ eine Menge abg. Intervalle. $u,v$ von $[u,v] [mm] \in [/mm] M$ seien natürliche Zahlen mit [mm] $1\le u
Man zeige: Für $I, I' [mm] \in [/mm] M $ mit [mm] $I\cap [/mm] I' = [mm] \emptyset$ [/mm] oder [mm] $I\subset [/mm] I'$ oder [mm] $I'\subset [/mm] I$ $ [mm] \Rightarrow [/mm] |M| = n-1 $ |
Es ist wohl offensichtlich, dass ich nur die Bedingung [mm] $I\subset [/mm] I'$ zu betrachten habe
Nun, der Beweis scheint doch einfach:
Sei [mm] $I\subset [/mm] I', [mm] v_i \in \mathbb{N} [/mm] $
Sei $M:= [mm] \{ [u,v_1], [u,v_2],\ldots, [u,v_n = n ] \} [/mm] $ Die Intervalle seien allesamt [mm] $I_j$ [/mm] genannt.
Laut Voraussetzung gilt [mm] $v_1< v_2 [/mm] < [mm] v_3
[mm] $\Rightarrow [/mm] |M| = [mm] v_n [/mm] - [mm] v_1 [/mm] + 1 = [mm] n-v_1 [/mm] +1 [mm] \le [/mm] n-1 $
Letztere Ungleichung gilt wegen [mm] $v_1 \in \mathbb{N} [/mm] $
Kann das echt so einfach sein ? :-O
[mm] Rein$\mathbb{R}$eelle [/mm] Intervalle können nicht gemeint sein, denn es lässt sich sofort ein Gegenbeispiel finden, wenn man das [mm] $\epsilon$ [/mm] kleiner als 1 wählt. Das folgt sofort aus meinem Beweis.
Wo ist mein Hund? Ich finde ihn leider nicht! :-(
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:59 Do 16.02.2012 | | Autor: | Marcel |
Hallo,
> Sei [mm]n>1 \in \mathbb{Z}.[/mm] Sei [mm]M[/mm] eine Menge abg. Intervalle.
> [mm]u,v[/mm] von [mm][u,v] \in M[/mm] seien natürliche Zahlen mit [mm]1\le u
>
> Man zeige: Für [mm]I, I' \in M[/mm] mit [mm]I\cap I' = \emptyset[/mm] oder
> [mm]I\subset I'[/mm] oder [mm]I'\subset I[/mm] [mm]\Rightarrow |M| = n-1[/mm]
nun, dann müssen wir erst mal über die Aufgabe sprechen: Was soll das denn genau heißen?
1. Möglichkeit: Wenn für alle $I,I'$ aus [mm] $M\,$ [/mm] eine der darauffolgenden Bedingungen gilt (also die Intervalle sind disjunkt oder eines der Intervalle umfasst das andere), dann folgt $|M|=n-1$?
2. Möglichkeit: Falls es Intervalle $I,I'$ in [mm] $M\,$ [/mm] so gibt dass eine der darauf erwähnten Eigenschaften erfüllt ist, dann folgt $|M|=n-1$?
> Es ist
> wohl offensichtlich, dass ich nur die Bedingung [mm]I\subset I'[/mm]
> zu betrachten habe
Wenn es offensichtlich ist: Warum ist es offensichtlich?
> Nun, der Beweis scheint doch einfach:
> Sei [mm]I\subset I', v_i \in \mathbb{N}[/mm]
> Sei [mm]M:= \{ [u,v_1], [u,v_2],\ldots, [u,v_n = n ] \}[/mm]
Ich sehe keinen Grund, warum [mm] $M\,$ [/mm] genau diese Form haben soll. Wenn Du glaubst, dass Du das o.E. annehmen kannst, dann würde ich gerne eine Begründung dafür erhalten!
Warum kann [mm] $M\,$ [/mm] nicht etwa so aussehen:
[mm] $$M=\{[6,7],[4,8],[3,9],[10,12]\}?$$
[/mm]
> Die
> Intervalle seien allesamt [mm]I_j[/mm] genannt.
Deine Ausdrucksweise ist ein wenig schlecht. Du kannst ja auch sagen, dass [mm] $M=\{I_j : j=1,\ldots,k\}$ [/mm] mit einem noch zu bestimmenden [mm] $k\,$ [/mm] ist, und alle diese Intervalle [mm] $I_j$ [/mm] eine gewisse Form haben und für alle $i [mm] \not=p$ [/mm] auch [mm] $I_i \not=I_p$ [/mm] gilt.
> Laut Voraussetzung gilt [mm]v_1< v_2 < v_3
> Es gilt weiters: [mm]I_1 \subset I_2 \subset \ldots \subset I_n .[/mm]
> Für Erzeugung einer möglichst großen Menge [mm]M[/mm], sei [mm]|v_j - v_i| =1[/mm]
> für [mm]|j-i|=1[/mm] [mm]\forall 1\le i
> [mm]\Rightarrow |M| = v_n - v_1 + 1 = n-v_1 +1 \le n-1[/mm]
> Letztere Ungleichung gilt wegen [mm]v_1 \in \mathbb{N}[/mm]
>
> Kann das echt so einfach sein ? :-O
Ich glaube es nicht - außerdem: Was ist mit [mm] $\ge$? [/mm] Du willst ja $=$ zeigen, das geht natürlich oft auch so, indem man [mm] $\le$ [/mm] und [mm] $\ge$ [/mm] zeigt.
Aber ich denke, in der eigentlichen Aufgabe steht auch $|M| [mm] \red{\;\le\;}n-1$, [/mm] oder?
> Rein[mm]\mathbb{R}[/mm]eelle Intervalle können nicht gemeint sein,
> denn es lässt sich sofort ein Gegenbeispiel finden, wenn
> man das [mm]\epsilon[/mm] kleiner als 1 wählt.
Das ist ziemlich banal, dass man die Grenzen nicht reell lassen kann! Was ist hier übrigens das von Dir angepriesene [mm] $\epsilon$? [/mm] Es tauchte bis dato nirgends vorher auf...
> Das folgt sofort aus
> meinem Beweis.
Das folgt auch ohne Deinen Beweis!
> Wo ist mein Hund? Ich finde ihn leider nicht! :-(
Wie gesagt: Ehrlich gesagt verstehe ich noch nichtmal die Aufgabe in dieser Formulierung richtig. Vielleicht fangen wir da mal an, also:
Was ist zu zeigen?
P.S.:
> Sei $n > 1 [mm] \in \IZ$ [/mm] ...
ist auch eine schlechte Formulierung. Dass $1 [mm] \in \IZ$ [/mm] ist, ist klar. Wenn man das schon verkürzt hinschreiben will, dann wenigstens etwa so:
"Sei [mm] $\IZ \ni [/mm] n > 1$"
Natürlich ist auch oben klar, dass $n > [mm] 1\,$ [/mm] und $n [mm] \in \IZ$ [/mm] sein soll. Aber nicht, weil da $n > 1 [mm] \in \IZ$ [/mm] steht, sondern "weil ein mitdenkender Mensch weiß, was gemeint ist". Aber man soll seine Mitmenschen nicht überstrapazieren - zumal es m.E. nach immer unsinnig ist, Leute durch "schlechte oder eigentlich sogar falsche Schreibweisen" dazu zu "zwingen", sich wegen Banalitäten den Kopf zu zerbrechen!! Gerade zu Beginn meines Studiums hatte ich auch so'n Menschen, der oft einfach fast alle Studenten verwirrte, weil man viele seiner Schreibweisen erstmal verstehen lernen musste (was bei manch' speziellen Schreibweisen, die dann auch nur dieser spezielle Mensch so macht und für klar hält, nur zu Frust führt!). Bevor man eine Übungsaufgabe bearbeiten konnte, saß man erstmal zwei Stunden da und fragte sich "Was verdammt nochmal soll der Scheiß?" Nach 5 möglichen Interpretationen war man froh, wenn man eine gefunden hatte, für die die Aufgabenstellung wenigstens annähernd Sinn zu machen schien. Ich hab' mir aber oft auch den Spaß gegönnt, für die Aufgabe in der gegebenen Formulierung einfach ein Gegenbeispiel hinzuschreiben - das wurde übrigens auch anerkannt, es sei denn, die Aufgabe wurde zwischenzeitlich "abgeändert" mit einem Hinweis auf die Änderung.
Was lernt man daraus? Egal, wie chaotisch man ist: "Sauber" sollte man die Mathematik immer aufschreiben! Und sauber heißt: Alles ist klar und verständlich, und man muss nicht zwischen verschiedenen Möglichkeiten raten, was denn gemeint sein könnte.
P.P.S.:
Leider schreiben viele ja auch, dass eine lineare Abbildung [mm] $\phi$ [/mm] genau dann injektiv ist, wenn [mm] $kern(\phi)=0\,.$ [/mm] Sowas kann man gerade noch akzeptieren (was ich übrigens dennoch markieren würde) - sauber ist es aber keineswegs: Denn [mm] $kern(\phi)$ [/mm] ist eine MENGE. Also [mm] $kern(\phi)=\{0\}$ [/mm] sollte man wenigstens schreiben (und noch sauberer würde man etwa dazuschreiben, "was das für eine [mm] $0\,$ [/mm] ist" - ich bin der Meinung, dass gerade die "Neuankömmlinge" in den Mathevorlesungen erstmal insofern streng korrigiert werden müssen, damit sie lernen, die Sprache sauber zu benutzen - und so hatte ich auch korrigiert, und soweit ich das gesehen habe, hat das den meisten Studenten/Studentinnen sehr genutzt. Denn sie haben gelernt, auch Sachen, die zunächst unklar waren und vielleicht so "WischiWaschie"n mal erklärt worden sind, für sich selbst sauber aufzuschreiben und so (zumindest teilweise) gelernt, sich selbst Mathematik beizubringen - bzw. herauszufinden, was eigentlich "das Wesentliche" ist!).
Schlussendlich
Ich fasse die Aufgabe übrigens so auf:
"Falls für $I,I' [mm] \in [/mm] M$ stets ... gilt, dann folgt [mm] $|M|\;\red{\le}\;n-1\,.$"
[/mm]
Also:
"Falls für alle $I,I' [mm] \in [/mm] M$ gilt..."
Du hast dann die Aufgabe nur für einen speziellen Fall behandelt. Was ist mit allen anderen Fällen? Ich denke übrigens, dass man den Beweis hier so beginnen kann, dass man mit einem [mm] $I_1 \in [/mm] M$ startet, dass keines der anderen enthält. Dann sind entweder alle anderen [mm] $I_\ell$ ($\ell \not=1$) [/mm] disjunkt mit [mm] $I_1\,,$ [/mm] oder es gibt wenigstens ein Intervall, das [mm] $I_1$ [/mm] umfasst. Wenn es eines gibt, dann nehmen wir das und nennen es nun [mm] $I_2\,.$ [/mm] Wenn es keines gibt, dann ist, wenn wir $M [mm] \setminus \{I_1\}$ [/mm] betrachten, die Wahl eines [mm] $I_2$ [/mm] als ein Intervall, dass keines der anderen Intervalle aus $M [mm] \setminus \{I_1,I_2\}$ [/mm] umfasst, möglich. Etc. pp..
Ich denke, dass das ein Algorithmus ist, mit dem man am Ende zum Ziel kommen könnte.
(Man könnte bei dem Algorithmus auch "nach und nach Intervalle aussortieren, die zu allen anderen disjunkt sind", wenn wir quasi "gezählte Intervalle markieren" oder "aus [mm] $M\,$ [/mm] entfernen und in eine separate Menge schmeißen, wo wir in dieser die Elemente mitzählen").
Ganz sauber ist das nicht, was ich da sage: Vielleicht übersehe ich auch noch was, so dass es nicht ganz korrekt ist. Aber das sollte wenigstens eine "Idee für einen Beweis" liefern können!
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 08:51 Fr 17.02.2012 | | Autor: | clemenum |
Hallo Marcel!
Erstmal möchte ich mich herzlich für deine vielen, ausführlichen Erklärungen bedanken!! So etwas ausführliches habe ich noch nie bekommen! 
Ich werde zur Sicherheit nochmal haar genau die Angabe hinschreiben, wie sie uns gegeben wurde:
Sei $n>1$ eine ganze Zahl. Sei $M$ eine Menge abgeschlossener Intervalle. Die Endpunkte $u,v$ eines jeden Intervalls $[u,v] [mm] \in [/mm] M $ seien natürliche Zahlen mit [mm] $1\le [/mm] u< [mm] v\le [/mm] n .$ Angenommen, für je zwei verschiedene Intervalle $I,I' [mm] \in [/mm] M $ tritt einer der folgenden Fälle ein: [mm] ($I\cap [/mm] I' = [mm] \emptyset [/mm] $) oder [mm] ($I\subset [/mm] I$') oder [mm] ($I'\subset [/mm] I$ (d.h. je zwei Intervalle überlappen ganz oder gar nicht)). Man zeige, dass [mm] $|M|\le [/mm] n -1$
Verzeih, ich war schreibfaul (bei diesem langen Text) und habe dabei einen Großteil der nötigen Sauberkeit verloren.
Ich werde in den nächsten Stunden einen neuen Beweisversuch hier veröffentlichen.
Nochmals, dankeschön!
Grüße,
Clemenum
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:20 Fr 17.02.2012 | | Autor: | fred97 |
Weiter unten hast Du geschrieben, dass die Aufgabe so lautet:
"Sei $ n>1 $ eine ganze Zahl. Sei $ M $ eine Menge abgeschlossener Intervalle. Die Endpunkte $ u,v $ eines jeden Intervalls $ [u,v] [mm] \in [/mm] M $ seien natürliche Zahlen mit $ [mm] 1\le [/mm] u< [mm] v\le [/mm] n . $ Angenommen, für je zwei verschiedene Intervalle $ I,I' [mm] \in [/mm] M $ tritt einer der folgenden Fälle ein: ($ [mm] I\cap [/mm] I' = [mm] \emptyset [/mm] $) oder ($ [mm] I\subset [/mm] I $') oder ($ [mm] I'\subset [/mm] I $ (d.h. je zwei Intervalle überlappen ganz oder gar nicht)). Man zeige, dass $ [mm] |M|\le [/mm] n -1 $"
So macht die Aufgabe Sinn, und wenn ich es richtig sehe, kann man das mit einem einfachen Induktionsbeweis erledigen.
FRED
|
|
|
|
