Partielle Ordnung und binäre Abbildung

04.01.2013, 13:09	Samaina	Auf diesen Beitrag antworten »
Partielle Ordnung und binäre Abbildung Meine Frage: Guten Tag, ich habe im Fach Diskrete Mathematik folgende Aufgabe zu lösen : Es sei (Y , <= dies soll das Relationszeichen sein, nicht das kleiner gleich) eine partielle Ordnung, X eine Menge und f : X -> Y eine Injektive Abbildung . a) Zeigen sie : die binäre Relation <=f wieder Relationszeichen := {(x1,x2) e X x X : f (x1) <= wieder Relationszeichenf(x2) ist eine partielle Ordnung auf X. b) Offensichtlich ist ( P([n] , c) für alle n aus den natürlichen Zahlen eine partielle Ordnung, Betrachten Sie die Abbildung f : {0,1}^n -> P([n], (i1, .... , in) -> {j e [n] : ij = 1}. Zeigen sie , dass f bijektiv ist und zeichnen sie das Hasse-Diagramm von ({0,1}^3, <=f). Meine Ideen: Bei der a) habe ich einfach geschrieben, dass f(x1) und f(x2) ja beide aus der Menge Y stammen. Da f injektiv ist, ist auch jedes y eindeutig durch ein f(x) bestimmt und somit kann man die 3 Merkmale reflexiv, asymmetrisch und transitiv nachweisen... Hoffe ich Mit der b) komme ich nicht so ganz klar . Um zu zeigen, dass f bijektiv ist, muss ich ja eine Umkehrabbildung angeben, also eine Abbildung von der Potentmenge P[n] auf {0,1}^n. Mein Problem ist, dass ich schon die Abbildung f nicht so recht verstehe, {0,1} ^n bedeutet ja, dass ich ein Tupel mit drei Einträgen hab , also zB {1,0,1}, aber i1, ..., in sind doch einfach Zahlen oder nicht? Ist die Umkehrabbildung dann einfach " Ich nehme ein Beliebiges Element aus der Potenzmenge und bilde es auf 0 ab, falls es nicht Element der Relation ist und 1, falls doch ?" Mein Vorschlag zum Hassediagramm wäre ganz unten (0,0,0) und ganz oben (1,1,1) und dann dazwischen alle Elemente der Potenzmenge einzufügen , also zB (0,0,0) ist vergleichbar mit (0,0,1) , aber (1,1,0) ist nicht nicht vergleichbar mit 1,0,1) . Es ist viel Text ich weiß, aber es wäre wirklich super, wenn mir jemand helfen könnte . Vielen Dank im Voraus !!
04.01.2013, 15:52	Jack Prince	Auf diesen Beitrag antworten »
Hallo Samaina, Zunächst ist es wichtig partielle Ordnung und partiell geordnete Menge nicht durcheinander zu bringen: $\begin{eqnarray} \le \end{eqnarray}$ ist partielle Ordnung und $\begin{eqnarray} (Y, \le ) \end{eqnarray}$ die partiell geordente Menge oder kurz Poset. zu a) Deine Begründung mit der Injektivität und der partiellen Ordnung $\begin{eqnarray} \le \end{eqnarray}$ ist nicht ganz ausreichend. Du musst, denk ich, es noch ein bisschen ausführlicher gestalten. Reflexivität: Sei $\begin{eqnarray} x \in X \Longrightarrow f(x) \in Y \quad \stackrel{ (Y,\le) \textrm { ist Poset}} \Longrightarrow \quad f(x) \le f(x) \Longrightarrow (x,x) \in \le_f \quad \Longrightarrow \quad x \le_f x \end{eqnarray}$ und dann genauso die Symmetrie und Transitivität (Vorsicht: nicht die Injektivität unterschlagen). zu b) Genau, man muss die Umkehrabbildung angeben. Zum Verständnis $\begin{eqnarray} [n]:=& \, \{1, \ldots ,n \} \end{eqnarray}$ $\begin{eqnarray} \{0,1\}^n:= \Big\{ (i_1, \ldots ,i_n ) \mid \forall \, j \in [n]: i_j \in \{0,1\} \Big\} \end{eqnarray}$ $\begin{eqnarray} \mathfrak{P}([n]) :=\{X \mid X \subseteq [n]\} \end{eqnarray}$ . Wenn nun $\begin{eqnarray} f \colon \{0,1\}^n \longrightarrow \mathfrak{P}([n]) \quad \textrm{mit} \quad f\Big( (i_1, \ldots ,i_n ) \Big):= \{ j \in [n] \mid i_j =1 \} \end{eqnarray}$ , dann wird jedem n- Tupel aus $\begin{eqnarray} \{0,1\}^n \end{eqnarray}$ die Teilmenge $\begin{eqnarray} X \subseteq [n] \end{eqnarray}$ zugeordnet, welche aus den Indizes $\begin{eqnarray} j \end{eqnarray}$ besteht, für die die $\begin{eqnarray} j \end{eqnarray}$ -te Komponente von $\begin{eqnarray} (i_1, \ldots ,i_n ) \end{eqnarray}$ eine 1 ist. So kann man demnach eine elegante Umkehrabbildung angeben. Zum Hasse-Diagramm musst du dir nur überlegen, welche Elemente am größten und am kleinsten bezüglich $\begin{eqnarray} \le_f \end{eqnarray}$ sind und dann alle anderen dazwischen packen. Dabei ist aber immer die Ordnung zu beachten! LG

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »