Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Beweis einer partiellen Ordnung

Beweis einer partiellen Ordnung

Universität / Fachhochschule

Sonstiges

Tags: Sonstiges

Underfaker aktiv_icon

15:46 Uhr, 20.01.2012

Ich weiß nicht ob jemand versteht was zu tun ist, da ich nciht sicher bin man das allgemein kennt oder sich unser Dozent was eigenes ausgedacht hat.

Satz.

Ist

(M, \leq)

eine transitive, reflexive Ordnung, so ist

\equiv,

definiert durch

a \equiv b \leftrightarrow a \leq b \land b \leq a

eine Äquivalenzrelation.

Sei

M \ \equiv

die Menge aller Äquivalenzklassen, dann ist hierauf die Relation

[a] \leq_{\equiv} [b] \leftrightarrow a \leq b

wohldefiniert und eine partielle Ordnung.

Dieser Satz ist zu beweisen, als Hinweis solle man Folgendes machen:

- Zeigen Sie, dass die Relation

\equiv

eine Äquivalenzrelation ist.
- Zeigen Sie, dass die Relation

\leq_{\equiv}

wohldeniert ist.

D . h

. Wenn

a, a', b, b' \in M

sind, sodass

a \equiv a'

und

b \equiv b',

so ist

[a] \leq_{\equiv} [b]

genau dann wenn

[a'] \leq_{\equiv} [b']

.
- Zeigen Sie, dass

\leq_{\equiv}

eine partielle Ordnung ist.

Sooo.

Wie ist denn

\equiv

ist eine Äquivalenzrelation zu beweisen?. Also hat das überhaupt was mit dem Kongruenzzeichen der Modulorechnung zu tun? Oder muss ich die Definition von oben benutzen.

Also

a \equiv a \Rightarrow a \leq a \land a \geq a,

a = a

folgt die Behauptung zwangsläufig und

a \leq a \land a \geq a

???

Ich bin mir da nicht so sicher, was die Grundlage für den Teilbeweis ist.

Zu dem Zweiten "wohldefiniert", betrachte ich

[a]

wie a oder gelten dort andere Regeln?

also ich habe so getan als wenn die eckigen Klammern nciht da wären und einfach aus der größer kleiner Definition gezeigt, dass beide Richtungen gelten oder wie muss man das hier machen?

Das dritte habe ich noch überhaupt nicht wirklich begonnen, da ich die ersten beiden ja nicht hatte.

Ich wäre echt froh wenn mir hier jemand weiterhelfen könnte.

michaL aktiv_icon

19:34 Uhr, 20.01.2012

Nochmals hallo,

nun, in diesem Zusammenhang wird doch das Zeichen "

\equiv

" mit einer (neuen) Bedeutung belegt. In diesem Zusammenhang musst du das Zeichen verstehen, alles andere ist doch sinnlos.
Du musst also für "

\equiv

" beweisen, dass sie (die Relation) transitiv, symmetrisch und reflexiv ist und hast als Grundlage nur die Definition a≡b↔a≤b∧b≤a.

Wohldefiniert, hm. Also, die (neue) Ordnung "

\leq_{\equiv}

" wird anhand eines VERTRETERS einer Klasse definiert.
Also eine ganze Klasse

[a]

heiße kleiner oder gleich einer ganzen Klasse

[b]

(in Zeichen

[a] \leq_{\equiv} [b]

), wenn nur schon

a \leq b

gilt.
Wer sagt denn, dass es nicht möglich ist, dass für Elemente

x, y \in [a]

und

u, v \in [b]

gilt:

x \leq y

aber auch

v \leq u

?
Und das ist mit Wohldefiniertheit gemeint: dass die Definition NICHT von der Wahl eines speziellen VERTRETERS abhängig ist.

^{[1]}

Um dazu deine konkrete Frage zu beantworten, du musst für Wohldefiniertheit zeigen, dass aus

[a] \leq_{\equiv} [b]

und

x \in [a]

und

y \in [b]

folgt, dass auch

x \leq y

gilt.

Mfg Michael

Weblinks:
[1] de.wikipedia.org/wiki/Wohldefiniertheit#Repr.C3.A4sentantenunabh.C3.A4ngigkeit

Underfaker aktiv_icon

19:54 Uhr, 20.01.2012

Das Problem ist, wir hatten schonmal eine solche Aufgabe in der eine Definition gegeben war, die wir aber nciht benutzen durften, ohne diese zu beweisen, ich wusste also nicht ob ich nun diese Definition einfach so benutzen soll, alles andere machte für mich aber keinen Sinn.

a \equiv a \Rightarrow a \leq a \land a \geq a

aus der Gleichheit von a folgt

a \leq a \land a \geq a

womit nach Definition trivialerweise die Reflexivität gezeigt ist.

a \equiv

b \Leftrightarrow b \equiv a

a \equiv b \Rightarrow a \leq b \land b \leq a \Leftrightarrow b \leq a \land a \leq b \Rightarrow b \equiv a

also ist

\equiv

symmetrisch

a \equiv b

und

b \equiv c

?=>

a \equiv c

a \equiv b \Rightarrow a \leq b \land b \leq a

b \equiv c \Rightarrow b \leq c \land c \leq b

a \leq b

und

b \leq c \Rightarrow a \leq c

und da

c \leq b

und

b \leq a \Rightarrow c \leq a

damit insgesamt

a \leq c

und

c \leq a \Rightarrow \equiv

ist transitiv.

Wenn das so richtig ist, hat man hier ja nun nicht wirklich was gemacht.

- wohldefiniert: Kurze Frage, du hast geschrieben

[a] \leq_{\equiv} [b]

wenn nur schon

a \leq b

gilt. kommt dort

\leq

oder

\leq_{\equiv}

hin?

Also mit diesen Elemente mit den Eckigen Klammern (Klassen?!) komme ich ncihtklar:

Seien

a, a', b, b' \in M

sodass

a \equiv a'

und

b \equiv b'

\Rightarrow

z . z

[a] \leq_{\equiv} [b] \Rightarrow [a'] \leq_{\equiv} [b']

also: Sei

x \in [a]

und

y \in [b]

und

[a] \leq_{\equiv} [b]

folgt nun

a \leq b

?

Ich weiß dann einfach nciht weiter, Das Problem ist ich weiß nicht was diese Elemente in den Klassen sind und was die Klassen sind.

wie steht denn nun

x

zu a ?

michaL aktiv_icon

20:40 Uhr, 20.01.2012

Hallo,

es ist nur abstrakt, aber es steckt sonst nicht viel dahinter! Ich zeig dir mal die Wogldefiniertheit:
Seien also

[a] \leq_{\equiv} [b]

und

x \in [a]

y \in [b]

.
Zu zeigen:

x \leq y

Aus

[a] \leq_{\equiv} [b]

folgt per def

a \leq b

.
Aus

x \in [a]

folgt

x \equiv a

, was ja definitionsgemäß

a \leq x \leq a

bedeutet.
Ebenso gilt

b \leq y \leq b

.

Also haben wir insbesondere

x \leq a \leq b \leq y

also insbesondere

x \leq y

.

So, auf dieser Ebene laufen die Beweise ab.

> Kurze Frage, du hast geschrieben [a]≤≡[b] wenn nur schon a≤b gilt. kommt dort ≤ oder ≤≡ hin?

Nun, das hast du auch selbst so geschrieben:
> [a]≤≡[b]↔a≤b

Gut wäre es aus meiner Sicht, die Fragen nicht zu sammeln, sondern nur eine am Stück zu klären.

Mfg Michael

Underfaker aktiv_icon

20:51 Uhr, 20.01.2012

"Nun, da shast du auch selbst so geschrieben"

Ja das war Teil des Satzes der bewiesen werden sollte. Muss man das nicht Beweisen?

Ich weiß tut mir leid aber mir fällt es bei unserem Dozenten manchmal schwer zu unterscheiden was zu beweisen ist und was benutzt werden kann.

Was meinst du mit "Fragen sammeln" Weil das hier aus 3 Teilfragen besteht?

ich hatte befürchtet man verlöre sonst den Zusammenhang.

Ahso danke dass du mir hierbei hilfst :-)

Underfaker aktiv_icon

09:27 Uhr, 21.01.2012

Es gilt

a \leq x \leq a

b \leq y \leq b

a \equiv a' \Rightarrow a \leq a' \leq a

Aus

x \leq a \land a \leq a' \Rightarrow x \leq a'

analog

a' \leq x

b \equiv b' \Rightarrow b \leq b' \leq b

Da ebenfalls

b \leq y \leq b \Rightarrow y \leq b'

Da nun wegen oben

x \leq y

und

y \leq b' \Rightarrow x \leq b'

Wegen

a' \leq x

also auch

a' \leq b \to [a'] \leq_{\equiv} [b']

Muss ich überhaupt noch die andere Richtung machen?

Die geht doch im Prinzip ganz genauso, allso ebenso analog.

Ist das was zu tun ist bei der Wohldefiniertheit?

Underfaker aktiv_icon

09:49 Uhr, 21.01.2012

Und ein letztes:

z . z

\leq_{\equiv}

ist eine partielle Ordnung. Also ist insbesondere

z . z

. :
- Reflexivität
- Transitivität
- Antisymmetrie

Was benutze ich nun hierfür? Ich habe folgendermaßen angefangen:

[a] \leq_{\equiv} [a] :

Aus der Gleichheit von a folgt trivialerweise

a \leq a

(und sogar

a \geq a)

und damit muss

[a] \leq_{\equiv} [a]

gelten. Das verstehe ich irgendwie nicht, muss man hier noch mehr machen? Oo

Transitivität:

z . z

. Aus

[a] \leq_{\equiv} [b]

und

[b] \leq_{\equiv} [c]

folgt

[a] \leq_{\equiv} [c]

Also aus

[a] \leq_{\equiv} [b]

und

[b] \leq_{\equiv} [c]

folgt per Definition

a \leq b \land b \leq c

und damit auch sofort

a \leq c

und damit also auch wieder

[a] \leq_{\equiv} [c]

.

Auch das kommt mir zu simpel vor...

Antisymmetrie:

Benutzt man hier nun die normale Gleichheit?

z . z . :

Aus

[a] \leq_{\equiv} [b] \land [b] \leq_{\equiv} [a]

folgt

[a] = [b]

[a] \leq_{\equiv} [b] \Rightarrow a \leq b

[b] \leq_{\equiv} [a] \Rightarrow b \leq a

Also

a \leq b \land b \leq a \Rightarrow a = b

Folgt hieraus

[a] = [b]

Underfaker aktiv_icon

09:49 Uhr, 21.01.2012

Sorry (Doppelpost)

michaL aktiv_icon

10:21 Uhr, 21.01.2012

Hallo,

es sieht recht ordentlich aus, was ich in den letzten 3 posts gelesen hab.
Nun, ich sagte ja schon (eingangs zu deiner anderen Frage), dass es sich manchmal nur um Abstraktion, nicht aber um mathematisch Schwieriges handelt.
Die Definition von "

\leq_{\equiv}

" führt aussschließlich auf die Eigenschaften von "

\leq

" zurück, also muss man bei den Beweisen eben auch wieder auf diese Stufe hinunter.

Mfg Michael

Underfaker aktiv_icon

10:31 Uhr, 21.01.2012

Morgen,

also die Reflexivität ist mit der Gleichheit schon fast trivial?

Die Transitivität da passierte ja dann auch nichts.

Und die Antisymmetrie stimmt so?

Folgt aus

a = b \to [a] = [b]

?

Dann wäre mein Fazit nämlich, dass was du schon sagtest, viel Denken im Sinne von sich überlegen wie das Problem zu lösen ist, muss man hier nicht man muss tatsächlich nur die Definitionen korrekt und an richtiger Stelle einsetzen/anwenden.

michaL aktiv_icon

10:50 Uhr, 21.01.2012

Hallo,

a = b \Rightarrow [a] = [b]

ist doch trivial!
Wenn du nur den Namen änderst, bleibt doch die Klasse die gleiche, oder? Eben nur unter einem anderen Namen!

Mfg Michael

Underfaker aktiv_icon

10:53 Uhr, 21.01.2012

Ist ja gut ich schäme mich ja schon :-)

Ich danke dir sehr, wie immer eine große Hilfe

965372

965128

	Status: nicht eingeloggt	Noch nicht registriert?