Matroids Matheplanet Forum Index
Moderiert von Buri Gockel
Mathematik » Strukturen und Algebra » Halbordnungen und lineare Ordnungen
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Halbordnungen und lineare Ordnungen
Wurftomate
Junior Letzter Besuch: im letzten Monat
Dabei seit: 17.01.2021
Mitteilungen: 7
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2021-01-17


Hallo zusammen,
ich habe verschiedene Probleme bei folgenden Aufgaben:

Betrachten Sie die durch −≤1+ festgelegte lineare Ordnung auf M1={+,−} sowie das gewöhnliche Kleiner-Gleich als ≤2 auf M2=ℕ. Gemäß Vorlesung wird auf M=M1×M2 eine Quasiordnung ≤ auf M definiert durch
(x1,x2)≤(y1,y2):⇐⇒(x1≤y1)∧(x2≤y2)

1. Zeigen Sie: Für das konkrete Beispiel ist ≤ sogar eine Halbordnung auf {+,−}×ℕ.

Um eine Menge zusammen mit einer Relation als Halbordnung bezeichnen zu können, müssen folgende Eigenschaften gegeben sein:
- Reflexivität:
Da bei der Kleiner-Gleich-Relation ≤ stets x≤x gilt, ist die Relation reflexiv.

- Antisymmetrie:
Da aus x≤y und y≤x auch x=y folgt, ist die Relation antisymmetrisch

-Transitivität:
Da aus x<y und y<z auch x<z folgt, ist die Relation transitiv.


2. Zeichnen Sie das Hasse-Diagramm für die Restriktion ≤N, wobei {+,−}×[3].
Wenn N={+,−}×[3]=>N={−3,+3}?
Hierbei bin ich mir unsicher. Wenn nur die Elemente -3 und +3 enthalten sind, wäre das Hasse-Diagramm ja sehr bescheiden. Was heißen in diesem Kontext die eckigen Klammern bei [3]? Ich kenne die Klammern ansonsten von Intervallen. Oder sind die betrachteten Element {(-3,3),(-2,2),(-1,1)}? Und wenn ja, muss ich dann zwei Hasse-Diagramme für die positiven und negativen Zahlen aufstellen?

3. Beschreiben Sie alle Teilmengen X von ℕ, sodass die Restriktion \(≤_{\left \{ +,- \right \}×X}\) eine lineare Ordnung auf {+,−}×X bildet.

Auch hier bin ich mir unsicher. Wenn X so gewählt werden soll, dass X≤{+,−}×X gelten soll, würde ich X={0} angeben. Denn würde ich beispielsweise X={1} wählen, wäre {+,−}×X={+1,−1}, wobei -1 kleiner 1 ist.



4. Statt Bedingung (1) könnte man auch definieren (lexikographische Ordnung):
(x1,x2)⊑(y1,y2):⇐⇒(x1≠y1∧x1≤1y1)∨(x1=y1∧x2≤2y2)
Zeigen Sie, dass je zwei Elemente aus M=M1×M2 bzgl. ⊑ miteinander vergleichbar sind, d.h. für alle
(x1,x2),(y1,y2)∈Mgilt
(x1,x2)⊑(y1,y2) oder (y1,y2)⊑(x1,x2).

Hier fehlt mir ein geeigneter Ansatz.

Ich bedanke mich schon jetzt für jede freundliche Unterstützung!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 5461
Herkunft: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2021-01-17


Willkommen im Forum. Hier ist es möglich, LaTeX für Formeln zu verwenden. Das hat unter anderem den Vorteil, dass Formeln besser aussehen und leicht zu lesen sind. Dein Beitrag sieht mit LaTeX so aus. Den Code siehst du durch Klicken auf 'Quote'. Falls du LaTeX noch nicht kennst, ist das eine gute Gelegenheit, es dabei zu lernen. Zum Inhalt deiner Frage schreibe ich gleich auch noch etwas.
 
 
Beitrag 1 mit LaTeX
Hallo zusammen,
ich habe verschiedene Probleme bei folgenden Aufgaben:

Betrachten Sie die durch $- \leq +$ festgelegte lineare Ordnung auf $M_1 = \{+,-\}$ sowie das gewöhnliche Kleiner-Gleich als $\leq_2$ auf $M_2 = \IN$. Gemäß Vorlesung wird auf $M=M_1 \times M_2$ eine Quasiordnung $\leq$ auf $M$ definiert durch

$(x_1,x_2) \leq (y_1,y_2) :\iff (x_1 \leq y_1) \wedge (x_2 \leq y_2)$

1. Zeigen Sie: Für das konkrete Beispiel ist $\leq$ sogar eine Halbordnung auf $\{+,−\} \times \IN$.

Um eine Menge zusammen mit einer Relation als Halbordnung bezeichnen zu können, müssen folgende Eigenschaften gegeben sein:
- Reflexivität:
Da bei der Kleiner-Gleich-Relation $\leq$ stets $x \leq x$ gilt, ist die Relation reflexiv.

- Antisymmetrie:
Da aus $x \leq y$ und $y \leq x$ auch $x=y$ folgt, ist die Relation antisymmetrisch

-Transitivität:
Da aus $x<y$ und $y<z$ auch $x<z$ folgt, ist die Relation transitiv.


2. Zeichnen Sie das Hasse-Diagramm für die Restriktion $\leq_{N}$, wobei $\{+,−\} \times [3]$.
Wenn $N = \{+,−\} \times [3] \implies N = \{−3,+3\}$?
Hierbei bin ich mir unsicher. Wenn nur die Elemente $-3$ und $+3$ enthalten sind, wäre das Hasse-Diagramm ja sehr bescheiden. Was heißen in diesem Kontext die eckigen Klammern bei $[3]$? Ich kenne die Klammern ansonsten von Intervallen. Oder sind die betrachteten Element $\{(-3,3),(-2,2),(-1,1)\}$? Und wenn ja, muss ich dann zwei Hasse-Diagramme für die positiven und negativen Zahlen aufstellen?

3. Beschreiben Sie alle Teilmengen $X$ von $\IN$, sodass die Restriktion $\leq_{\{+,−\} \times X}$ eine lineare Ordnung auf $\{+,−\} \times X$ bildet.

Auch hier bin ich mir unsicher. Wenn $X$ so gewählt werden soll, dass $X \leq \{+,−\} \times X$ gelten soll, würde ich $X=\{0\}$ angeben. Denn würde ich beispielsweise $X=\{1\}$ wählen, wäre $\{+,−\} \times X  =\{+1,−1\}$, wobei $-1$ kleiner $1$ ist.



4. Statt Bedingung (1) könnte man auch definieren (lexikographische Ordnung):
$(x_1,x_2) \sqsubseteq (y_1,y_2) :\iff (x_1 \neq y_1  \wedge x_1 \leq 1 y_1) \vee (x_1 =y_1 \wedge x_2 \leq 2 y_2)$
Zeigen Sie, dass je zwei Elemente aus $M=M_1 \times M_2$ bzgl. $\sqsubseteq$ miteinander vergleichbar sind, d.h. für alle
$(x_1,x_2),(y_1,y_2) \in M$ gilt
$(x_1,x_2) \sqsubseteq (y_1,y_2)$ oder $(y_1,y_2) \sqsubseteq (x_1,x_2)$.

Hier fehlt mir ein geeigneter Ansatz.

Ich bedanke mich schon jetzt für jede freundliche Unterstützung!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 5461
Herkunft: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2021-01-17


Zur Aufgabe 1: Erstens hast du dich bei der Transitivität verschrieben (dort schreibst du $<$). Zweitens musst du laut Aufgabenstellung gar nicht nachweisen, dass Reflexivität und Transitivität, also die Eigenschaft einer Quasiordnung gelten. Du musst beweisen, dass die Antisymmetrie gilt. Aber, drittens, das hast du gar nicht getan: Du hast lediglich die Behauptung der Antisymmetrie mit ihr selbst begründet. Eventuell hast du hier $\leq$ mit der üblichen $\leq$-Relation natürlicher Zahlen verwechselt?

Was du eigentlich zeigen musst (gemäß der Definitionen): Wenn $(x_1,x_2),(y_1,y_2) \in \{+,-\} \times \IN$ mit

(a) $(x_1,x_2) \leq (y_1,y_2)$
(b) $(y_1,y_2) \leq (x_1,x_2)$

dann gilt bereits

(c) $(x_1,x_2) = (y_1,y_2).$

Nun, schreibe dir einmal auf, was (a) und (b) gemäß der Definition von $\leq$ (die in der Aufgabenstellung noch einmal wiederholt worden ist) bedeutet. Und was bedeutet (c)? Schreibe dir also einfach auf, was hier eigentlich gegeben und was zu zeigen ist. Erst dann kannst du den Beweis antreten (der hier allerdings auch sehr kurz ausfallen wird).



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 5461
Herkunft: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2021-01-17


Zu Aufgaben 2 und 3 erst einmal nur ein Hinweis: Du hast hier das kartesische Produkt von Mengen nicht richtig erkannt. Zur Notationsfrage: Für $n \in \IN$ steht $[n]$ oftmals für die Menge $\{1,\dotsc,n\}$. Für $n=0$ ist das die leere Menge. Wie das bei euch gehandhabt wird, müsstest du in deinem Skript nachschauen und hier nachtragen. Es gilt demnach

$\{-,+\} \times [3] = \{-,+\} \times \{1,2,3\} = \{(-,1),(-,2),(-,3),(+,1),(+,2),(+,3)\}.$

Beachte auch, dass $+$ und $-$ hier nichts weiter als Symbole, keine Rechenoperationen sind. Wenn das verwirrend sein sollte, kannst du aber getrost auch in der gesamten Aufgabe mit $-1$ und $+1$ anstelle von $-$ und $+$ arbeiten (wobei ja $-1 \leq +1$ gilt).

Bei Aufgabe 3 musst du sämtliche Teilmengen mit dieser Eigenschaft bestimmen. Schreibe dir also hin, was diese Eigenschaft gemäß der Definitionen bedeutet (du hast bisher nicht mit den Definitionen gearbeitet).



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 5461
Herkunft: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2021-01-17


Bei Aufgabe 4 hast du dich vermutlich verschrieben, oder? Die übliche Definition der lexikographischen Ordnung ist jedenfalls

$(x_1,x_2) \sqsubseteq (y_1,y_2) :\iff (x_1 < y_1) \vee (x_1 =y_1 \wedge x_2 \leq y_2)$

Um hier die Behauptung zu zeigen, nimm dir zwei Elemente $(x_1,x_2),(y_1,y_2)$. Mache eine Fallunterscheidung: 1. Fall ist $x_1 = y_1$. Hier machst du dann wiederum eine Fallunterscheidung, ob $x_2 \leq y_2$ oder $y_2 \leq x_2$ gilt. 2. Fall ist $x_1 \neq y_1$. Hier machst du dann wiederum eine Fallunterscheidung, ob $x_1 < y_1$ oder $y_1 < x_1$ gilt.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wurftomate
Junior Letzter Besuch: im letzten Monat
Dabei seit: 17.01.2021
Mitteilungen: 7
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2021-01-17


2021-01-17 18:29 - Triceratops in Beitrag No. 2 schreibt:
Zur Aufgabe 1: Erstens hast du dich bei der Transitivität verschrieben (dort schreibst du $<$). Zweitens musst du laut Aufgabenstellung gar nicht nachweisen, dass Reflexivität und Transitivität, also die Eigenschaft einer Quasiordnung gelten. Du musst beweisen, dass die Antisymmetrie gilt. Aber, drittens, das hast du gar nicht getan: Du hast lediglich die Behauptung der Antisymmetrie mit ihr selbst begründet. Eventuell hast du hier $\leq$ mit der üblichen $\leq$-Relation natürlicher Zahlen verwechselt?

Was du eigentlich zeigen musst (gemäß der Definitionen): Wenn $(x_1,x_2),(y_1,y_2) \in \{+,-\} \times \IN$ mit

(a) $(x_1,x_2) \leq (y_1,y_2)$
(b) $(y_1,y_2) \leq (x_1,x_2)$

dann gilt bereits

(c) $(x_1,x_2) = (y_1,y_2).$

Nun, schreibe dir einmal auf, was (a) und (b) gemäß der Definition von $\leq$ (die in der Aufgabenstellung noch einmal wiederholt worden ist) bedeutet. Und was bedeutet (c)? Schreibe dir also einfach auf, was hier eigentlich gegeben und was zu zeigen ist. Erst dann kannst du den Beweis antreten (der hier allerdings auch sehr kurz ausfallen wird).

Um eine Menge zusammen mit einer Relation als Halbordnung bezeichnen zu können, muss die Quasiordnung antisymmetrisch sein.
Wenn für $\left(x_1,x_2\right),\left(\gamma_1,y_2\right)\in\left\{+,-\right\}\times\mathbb{N} $
(a) $\left(x_1,x_2\right)\le\left(y_1,y_2\right)$ und
(b) $\left(y_1,y_2\right)\le\left(x_1,x_2\right)$ gilt, folgt
(c) $\left(x_1,x_2\right)=\left(y_1,y_2\right)$
Aus (a) folgt gemäß der Definition von $\le$, dass $x_1 ≤_1 y_1$ und $x_2 ≤_2 y_2$ gilt. Wenn wir (b) annehmen, muss (c) gelten, da andernfalls $x_1 > y_1$ und $x_2 > y_2$ gelten würde und obige Definition ungültig wäre. Somit folgt aus (a) und (b) auch (c) und die Quasiordnung ist antisymmetrisch und somit eine Halbordnung.

Ist das so schon ausreichend?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wurftomate
Junior Letzter Besuch: im letzten Monat
Dabei seit: 17.01.2021
Mitteilungen: 7
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2021-01-17


2021-01-17 18:35 - Triceratops in Beitrag No. 3 schreibt:
Zu Aufgaben 2 und 3 erst einmal nur ein Hinweis: Du hast hier das kartesische Produkt von Mengen nicht richtig erkannt. Zur Notationsfrage: Für $n \in \IN$ steht $[n]$ oftmals für die Menge $\{1,\dotsc,n\}$. Für $n=0$ ist das die leere Menge. Wie das bei euch gehandhabt wird, müsstest du in deinem Skript nachschauen und hier nachtragen. Es gilt demnach

$\{-,+\} \times [3] = \{-,+\} \times \{1,2,3\} = \{(-,1),(-,2),(-,3),(+,1),(+,2),(+,3)\}.$

Beachte auch, dass $+$ und $-$ hier nichts weiter als Symbole, keine Rechenoperationen sind. Wenn das verwirrend sein sollte, kannst du aber getrost auch in der gesamten Aufgabe mit $-1$ und $+1$ anstelle von $-$ und $+$ arbeiten (wobei ja $-1 \leq +1$ gilt).

Bei Aufgabe 3 musst du sämtliche Teilmengen mit dieser Eigenschaft bestimmen. Schreibe dir also hin, was diese Eigenschaft gemäß der Definitionen bedeutet (du hast bisher nicht mit den Definitionen gearbeitet).

Vielen Dank für deine Antworten. Leider habe ich bei den Aufgaben 2 und 3 noch immer Probleme. Nach meinem Verständnis muss ich die Zahlen 1,2 und 3 in dem Hasse-Diagramm anordnen. Wobei ich die 1 ganz unten und die 2 und 3 darüber angeordnet hätte. Muss ich auch -1,-2 und -3 mit einbinden oder wie verwende ich die Symbole - und + in dem Diagramm? Oder muss ich doch -1,-2,-3,1,2 und 3 in einem Diagramm anordnen? Dann wüsste ich allerdings nicht, wie ich die negativen Zahlen dort mit unterbringe.

Bei der Aufgabe 3 würde ich folgendes definieren: Wenn $X≤{+,−}×X $ gelten soll, muss$\ X\le\left\{\left(+,X\right)\right\}\land X\le\left\{\left(-,X\right)\right\}$ gelten. Es ist mir allerdings nicht begreiflich, für welche natürlichen Zahlen (bis auf die 0) das gelten soll.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wurftomate
Junior Letzter Besuch: im letzten Monat
Dabei seit: 17.01.2021
Mitteilungen: 7
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2021-01-17


2021-01-17 18:42 - Triceratops in Beitrag No. 4 schreibt:
Bei Aufgabe 4 hast du dich vermutlich verschrieben, oder? Die übliche Definition der lexikographischen Ordnung ist jedenfalls

$(x_1,x_2) \sqsubseteq (y_1,y_2) :\iff (x_1 < y_1) \vee (x_1 =y_1 \wedge x_2 \leq y_2)$

Um hier die Behauptung zu zeigen, nimm dir zwei Elemente $(x_1,x_2),(y_1,y_2)$. Mache eine Fallunterscheidung: 1. Fall ist $x_1 = y_1$. Hier machst du dann wiederum eine Fallunterscheidung, ob $x_2 \leq y_2$ oder $y_2 \leq x_2$ gilt. 2. Fall ist $x_1 \neq y_1$. Hier machst du dann wiederum eine Fallunterscheidung, ob $x_1 < y_1$ oder $y_1 < x_1$ gilt.

Das heißt:
Es seien $(x_1,x_2),(y_1,y_2) \in M$:
1. Fall:$\ x_1=y_1$
$x_2\le y_2$
Wenn$\ x_2\le y_2$ und $x_1=y_1$ gilt, kann $\left(x_1,x_2\right)\ \sqsupseteq\ \left(y_1,y_2\right)$ verglichen werden.
$y_2\le x_2$
Wenn$\ y_2\le x_2$ und $x_1=y_1$ gilt, kann $\left(y_1,y_2\right)\ \sqsupseteq\ \left(x_1,x_2\right)$ verglichen werden.
2.$\ Fall\ x_1\neq y_1
x_1<y_1$
Wenn$\ x_1<y_1$ und $x_1\neq y_1$ gilt, kann $\left(x_1,x_2\right)\ \sqsupseteq\ \left(y_1,y_2\right)$ verglichen werden.
$y_1<x_1$
Wenn$\ y_1<x_1$ und $x_1\neq y_1$ gilt, kann $\left(y_1,y_2\right)\ \sqsupseteq\ \left(x_1,x_2\right)$ verglichen werden.
Somit kann für alle vier Fallunterscheidungen $(x_1,x_2)  \sqsupseteq (y_1,y_2)$ oder $(y_1,y_2) \sqsupseteq (x_1,x_2)$ verglichen werden.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Wurftomate hat die Antworten auf ihre/seine Frage gesehen.
Wurftomate wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]