Partition und Ordnungsrelation < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei A eine nichtleere Menge und M die Menge aller Partitionen von A.
i) Zeigen Sie, daß durch P [mm] \le [/mm] Q [mm] :\gdw \forall [/mm] X [mm] \in [/mm] P [mm] \exists [/mm] Y [mm] \in [/mm] Q : X [mm] \subseteq [/mm] Y
eine Ordnungsrelation [mm] \le [/mm] auf M definiert wird.
ii) Zeigen Sie, daß M ein größtes und ein kleinstes Element besitzt und bestimmen Sie beide. |
Hallo,
was die Partitionen einer Menge sind und wie die gebildet werden habe ich bereits verstanden.
Nur wie zeige ich das es eine Ordungsrelationen zu der Menge M definiert ist ?
Wie kann ich das kleinste bzw. größte Element dieser Menge bestimmen ?
Bitte hilft mir.
|
|
| |
|
> Sei A eine nichtleere Menge und M die Menge aller
> Partitionen von A.
Hallo,
na, das ist ja ein echter Gehirnverzwirner!
M ist eine Menge von Mengen, und diese Mengen bestehen wieder aus Mengen, nämlich aus Teilmengen von A.
Falls Dir M nicht ganz klar ist, kannst Du ja mal alle Partitionen von [mm] A:=\{1,2,3\} [/mm] aufschreiben. Mir hilft so etwas oft.
>
> i) Zeigen Sie, daß durch P [mm]\le[/mm] Q [mm]:\gdw \forall[/mm] X [mm]\in[/mm] P
> [mm]\exists[/mm] Y [mm]\in[/mm] Q : X [mm]\subseteq[/mm] Y
> eine Ordnungsrelation [mm]\le[/mm] auf M definiert wird.
>
> ii) Zeigen Sie, daß M ein größtes und ein kleinstes
> Element besitzt und bestimmen Sie beide.
> Hallo,
>
> was die Partitionen einer Menge sind und wie die gebildet
> werden habe ich bereits verstanden.
> Nur wie zeige ich das es eine Ordungsrelationen zu der
> Menge M definiert ist ?
Weißt Du denn, was Du zeigen mußt für "Ordnungsrelation"
> Wie kann ich das kleinste bzw. größte Element dieser
> Menge bestimmen ?
Zunächst ist natürlich die Def. für größtes/kleinstes Element wichtig.
Vielleicht schaust Du dann mal die Partitionen von [mm] A:=\{1,2,3\} [/mm] an.
Bekommst Du eine Idee für Kandidaten?
Gruß v. Angela
|
|
|
| |
|
Hallo,
- nein leider weiß ich nicht was ich mit Ordnungsrelation zeigen soll.
- Bei der Partition von A wird es wohl die 1 und 3 sein ?
|
|
|
| |
|
> - nein leider weiß ich nicht was ich mit Ordnungsrelation
> zeigen soll.
Hallo,
hast Du denn schonmal nachgeschlagen, was eine Ordnungsrelation ist? Was?
An welcher Stelle gibt es dabei Unklarheiten?
> - Bei der Partition von A wird es wohl die 1 und 3 sein ?
Nein.
Bist Du Dir sicher, daß Du "Partition" wirklich verstanden hast?
Gib die Definition wieder und schreib mal alle (oder ein paar) Partitionen von [mm] A:=\{1,2,3\} [/mm] auf.
Das solltest Du Dir erarbeitet haben, bevor es an die Lösung der Aufgabe geht.
Gruß v. Angela
|
|
|
| |
|
> Sei A eine nichtleere Menge und M die Menge aller
> Partitionen von A.
>
> i) Zeigen Sie, daß durch P [mm]\le[/mm] Q [mm]:\gdw \forall[/mm] X [mm]\in[/mm] P
> [mm]\exists[/mm] Y [mm]\in[/mm] Q : X [mm]\subseteq[/mm] Y
> eine Ordnungsrelation [mm]\le[/mm] auf M definiert wird.
>
> ii) Zeigen Sie, daß M ein größtes und ein kleinstes
> Element besitzt und bestimmen Sie beide.
> Hallo,
>
> was die Partitionen einer Menge sind und wie die gebildet
> werden habe ich bereits verstanden.
> Nur wie zeige ich das es eine Ordungsrelationen zu der
> Menge M definiert ist ?
> Wie kann ich das kleinste bzw. größte Element dieser
> Menge bestimmen ?
>
> Bitte helft mir.
Hallo,
vielleicht nützt es dir, zuerst ein etwas einfacher zu
überblickendes Beispiel aus einem anderen Bereich,
aber mit ähnlichen Eigenschaften zu betrachten.
Nimm eine natürliche Zahl n wie z.b. n=6, n=12
oder n=30 und betrachte die Menge [mm] T_n [/mm] aller Teiler
von n. Bei n=12 also [mm] T_{12}=\{1,2,3,4,6,12\}. [/mm] Dann wird
auf der Menge [mm] T_n [/mm] eine Relation definiert:
[mm] $p\le{q}:\gdw\ \exists k\in\IN: [/mm] q=k*p$
(mit anderen Worten: [mm] p\le{q} [/mm] falls p Teiler von q ist)
Stelle die Relation in einem Pfeildiagramm dar und
zeige, dass sie eine (Halb-) Ordnung ist, d.h. dass sie
reflexiv, transitiv und antisymmetrisch ist. Die genaue
Bedeutung dieser Begriffe solltest du in deinem Skript
finden, andernfalls google halt ein wenig.
Übrigens: In der Menge [mm] T_n [/mm] gibt es genau ein kleinstes
und genau ein grösstes Element, so wie in deiner
Aufgabe. Allerdings sind die extremalen Objekte in
der Aufgabe keine einzelnen Zahlen, sondern Mengen
von Mengen von Elementen aus der Grundmenge A.
(deshalb der Ausdruck "Hirnverzwirner" laut Angela)
LG Al-Chw.
|
|
|
| |
|
Hi,
bei der Teilmenge n=12 also [mm][mm] T_{12}=\{1,2,3,4,6,12\} [/mm] gibt es doch als kleinstes Element nur die 1 und als größtes Element nur die 12.
Bin ich jetzt auf einem falschen Dampfer, wenn ich sage, dass es für die eigentliche Aufgabe als kleinstes Element die leere Menge ist und als größtest Element die Menge von A ??
Würde mich über eine schnelle Antwort freuen.
Gruß
Navigator
|
|
|
| |
|
> Hi,
>
> bei der Teilmenge n=12 also [mm] T_{12}=\{1,2,3,4,6,12\} [/mm] gibt es doch als kleinstes Element nur die 1 und als größtes Element nur die 12.
Hallo,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") .
das ist richtig.
> Bin ich jetzt auf einem falschen Dampfer, wenn ich sage, dass es für die eigentliche Aufgabe als kleinstes Element die leere Menge ist
Ja.
Denn die Elemente der Menge M auf welcher die Relation "spielt", sind ja die Partitionen von A.
Die Partitionen sind doch gewisse Mengen von Teilmengen von A, und die leere Menge ist gewiß keine solche.
> und als größtest Element die Menge von A ??
Falls Du hier die Partition [mm] \{A\} [/mm] meinst, hast Du recht.
Gruß v. Angela
|
|
|
| |
|
Jetzt noch einmal zum Verständnis:
Wenn A=[mm]\{1,2,3\}[/mm] ist, dann sind die Partitionen davon
[mm]\{1,2,3\}[/mm]
[mm]\{\{1,2\},\{3\}\}[/mm]
[mm]\{\{1\},\{2,3\}\}[/mm]
[mm]\{\{1,3\},\{2\}\}[/mm]
[mm]\{\{1\},\{2\},\{3\}\}[/mm]
und das kleinste Element ist [mm]\{\{1\},\{2\},\{3\}\}[/mm] und das größte [mm]\{1,2,3\}[/mm]?
Wenn ich das jetzt soweit richtig verstanden habe, dann bräuchte ich nur noch einen Tipp, wie ich das reflexiv, antisymmetrisch und transitiv beweise mit der Ordnungsrelation auf M.
Vielen dank für eure Hilfe.
Gruß
Navigator
|
|
|
| |
|
> Jetzt noch einmal zum Verständnis:
>
> Wenn A=[mm]\{1,2,3\}[/mm] ist, dann sind die Partitionen davon
>
> [mm]\{1,2,3\}[/mm]
> [mm]\{\{1,2\},\{3\}\}[/mm]
> [mm]\{\{1\},\{2,3\}\}[/mm]
> [mm]\{\{1,3\},\{2\}\}[/mm]
> [mm]\{\{1\},\{2\},\{3\}\}[/mm]
>
> und das kleinste Element ist [mm]\{\{1\},\{2\},\{3\}\}[/mm] und das
> größte [mm]\red{\{}\{1,2,3\}\red{\}}[/mm]?
Hallo,
ja, das ist richtig so.
Damit dürfte der zweite Aufgabenteil nun kein Problem mehr sein.
> Wenn ich das jetzt soweit richtig verstanden habe, dann
> bräuchte ich nur noch einen Tipp, wie ich das reflexiv,
> antisymmetrisch und transitiv beweise mit der
> Ordnungsrelation auf M.
Zunächst einmal mußt Du Dir alles übersetzten in die Sprache Deiner Ordnungsrelation.
z.B. transitiv:
Behauptung: die Relation [mm] \le [/mm] ist transitiv, dh
Seinen P,Q,R [mm] \in [/mm] M mit [mm] P\le [/mm] Q und [mm] Q\le [/mm] R.
Dann folgt: [mm] P\le [/mm] R
Voraussetzung: [mm] P\le [/mm] Q und [mm] Q\le [/mm] R,
dh. für alle [mm] X\in [/mm] P gilt : es gibt ein [mm] Y\in [/mm] Q mit [mm] X\subseteq [/mm] Y
und
für alle [mm] X\in [/mm] Q gilt : es gibt ein [mm] Y\in [/mm] Q mit [mm] X'\subseteq [/mm] Y
zu zeigen: dann ist [mm] P\subseteq [/mm] R, dh.
dh. für alle [mm] X\in [/mm] P gilt : es gibt ein [mm] Y\in [/mm] R mit [mm] X\subseteq [/mm] Y.
Beweis: sei X [mm] \in [/mm] P.
Weil [mm] P\subseteq [/mm] Q gibt es ein [mm] Y\in [/mm] ...,
und weil [mm] Q\subseteq [/mm] R, findet man zu diesem Y ein [mm] Z\in [/mm] ... mit ...
Also ...
Versuch mal!
Gruß v. A«ngela
|
|
|
|
