Beweis durch Kontraposition < Sonstiges / Diverses < Vorhilfe
|
| Aufgabe | Es seien m endliche Mengen M1, . . . , Mm für ein m ∈ N>0 gegeben. Beweisen Sie die folgende Aussage:
Falls die Summe der Kardinalitäten der Mengen M1, . . . , Mm größer als n ∈ N ist, so existiert eine Menge M ∈ {M1, . . . , Mm}, deren Kardinalität größer als n/m ist. |
ich komm leider nicht weiter, hoffe ihr könnt mir weiterhelfen.
formal haben ich es so interpretiert:
Für i,m [mm] \in \IN>0 [/mm] (also i,m > 0) und beliebig n [mm] \in \IN:
[/mm]
Falls [mm] \summe_{i=1}^{m} [/mm] |Mi| > n, dann existiert M [mm] \in [/mm] {M1,...Mm} sodass |M| > n/m
und wir müssen beweisen:
Falls [mm] \summe_{i=1}^{m} [/mm] |Mi| < n, dann existiert M [mm] \in [/mm] {M1,...Mm} sodass |M| < n/m
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:21 Fr 11.11.2011 | | Autor: | M.Rex |
Hallo
> Es seien m endliche Mengen M1, . . . , Mm für ein m ∈
> N>0 gegeben. Beweisen Sie die folgende Aussage:
> Falls die Summe der Kardinalitäten der Mengen M1, . . . ,
> Mm größer als n ∈ N ist, so existiert eine Menge M ∈
> {M1, . . . , Mm}, deren Kardinalität größer als n/m
> ist.
> ich komm leider nicht weiter, hoffe ihr könnt mir
> weiterhelfen.
>
> formal haben ich es so interpretiert:
>
> Für i,m [mm]\in \IN>0[/mm] (also i,m > 0) und beliebig n [mm]\in \IN:[/mm]
>
>
> Falls [mm]\summe_{i=1}^{m}[/mm] |Mi| > n, dann existiert M [mm]\in[/mm]
> {M1,...Mm} sodass |M| > n/m
>
So ist es.
> und wir müssen beweisen:
>
>
> Falls [mm]\summe_{i=1}^{m}[/mm] |Mi| < n, dann existiert M [mm]\in[/mm]
> {M1,...Mm} sodass |M| < n/m
Das stimmt leider nicht.
Kontraposition bedeutet, dass man anstatt [mm] A\Rightarrow B[/mm] folgendes zeigt: [mm] \neg B\Rightarrow\neg A[/mm], hier also:
[mm]\frac{n}{m}\leq|M|\Rightarrow n\leq\summe_{i=1}^{m}|M_{i}|[/mm]
Marius
|
|
|
| |
|
mhh ok ich verstehe... aber wenn wir folgendes haben:
[mm] \summe_{i=1}^{n} [/mm] |Mi| > n [mm] \Rightarrow [/mm] |M| > [mm] \bruch{n}{m}
[/mm]
müssen wir dann nicht folgedes beweisen:
[mm] \bruch{n}{m} [/mm] [mm] \ge [/mm] |M| [mm] \Rightarrow [/mm] n [mm] \ge [/mm] [mm] \summe_{i=1}^{n} [/mm] |Mi|
anstatt:
[mm] \bruch{n}{m} [/mm] [mm] \le [/mm] |M| [mm] \Rightarrow [/mm] n [mm] \le [/mm] [mm] \summe_{i=1}^{n} [/mm] |Mi|
oder irre ich mich da?
|
|
|
| |
|
Hallo jess240890,
> mhh ok ich verstehe... aber wenn wir folgendes haben:
>
> [mm]\summe_{i=1}^{n}[/mm] |Mi| > n [mm]\Rightarrow[/mm] |M| > [mm]\bruch{n}{m}[/mm]
>
> müssen wir dann nicht folgedes beweisen:
>
> [mm]\bruch{n}{m}[/mm] [mm]\ge[/mm] |M| [mm]\Rightarrow[/mm] n [mm]\ge[/mm] [mm]\summe_{i=1}^{n}[/mm] |Mi|
>
> anstatt:
>
> [mm]\bruch{n}{m}[/mm] [mm]\le[/mm] |M| [mm]\Rightarrow[/mm] n [mm]\le[/mm] [mm]\summe_{i=1}^{n}[/mm]
> |Mi|
>
> oder irre ich mich da?
Nein, du irrst nicht, genauer lautet die Aussage formal (unter den gegebenen Voraussetzungen):
[mm]\sum\limits_{i=1}^m\left|M_i\right| \ > \ n \ \ \Rightarrow \ \ \exists M\in\{M_1,M_2,\ldots,M_m\}: \left|M\right| \ > \ \frac{n}{m}[/mm]
Mit Kontraposition ist dies äquivalent zu:
[mm]\forall M\in\{M_1,M_2,\ldots,M_m\}:\frac{n}{m} \ \ge \ \left|M\right| \ \ \Rightarrow \ \ n \ \ge \ \sum\limits_{i=1}^m\left|M_i\right|[/mm]
Gruß
schachuzipus
|
|
|
|
