x teilt y in der menge....

Neue Frage »

sunshine85 Auf diesen Beitrag antworten »
x teilt y in der menge....
ok, also ich habe folgendes verständnis problem....

bsp: betrachte die Relation "x tielt y" auf der Menge {1,2,3,6,12,18},

ich hab bei diesem bsp mehrere aufgaben, zunächst soll ich die geordneten paare (x,y) der relation angeben.

ist das: (1,2) (2,3) (3,6) (6,12) (12,18)??????

dann ist die frage welche vorgänger hat 6?

soll das 1,2,3 sein??? oder 1,2,3,4,5???? ich denk mal nur die, die in der menge vorkommen oder versteh ich das falsch??

und dann noch welchen unmittelbaren vorgänger 6 hat? das wäre dann 3???

und jetzt kommt: zeige, dass dies eine partialordnung definiert!

reflexiv: es sind alles natürliche zahlen, also teilen sie sich selbst, also richtig!

antisymmetrisch: 1 teilt 2, aber 2 nicht 1
2 teilt 3 nicht und umgekehrt auch nicht
aber 3 teilt 6, 6 aber nicht 3
6 teilt 12, aber 12 nicht 6
12 teilt nicht 18, und 18 nicht 12

ist es trotzdem antisymmetrisch??? obwohl es bei 2 elementen nicht stimmt??

transitiv: 1 teilt 2, 2 teilt nicht 3, aber 1 teilt 3???

aber hier: 3 teilt 6, 6 teilt 12 und 3 teilt 12 also richtig!
bier Auf diesen Beitrag antworten »

Also ich bin auch nicht gerade der Checker, aber ich würde sagen, dass deine Zahlenpaare sind zu 2/5 falsch sind. Außerdem glaub ich, dass du antisymmetrisch mit symmetrisch verwechselst.
JochenX Auf diesen Beitrag antworten »

ist (2,3) wirklich in der relation enthalten? teilt denn 2 wirklich 3?!
außerdem vermisse ich da ein paar... z.b. (1,18), denn 1 teilt 18

reflexivität ist klar, aber wie ist denn die bedingung für antisymmetrie?
wo ist die denn deines erachtens nicht erfüllt?
was bedeutet denn genau transitivität?
mache dir die definitionen noch mal klar, dann solltest du es sehen...

mfg jochen
AD Auf diesen Beitrag antworten »
RE: x teilt y in der menge....
@sunshine85

Bezeichnen wir die Relation mit .

Antisymmetrie heißt:



Dein Beispiel und hat nichts mit Antisymmetrie zu tun, wohl aber damit, dass keine vollständige, sondern nur eine partielle Ordnung ist - aber mehr sollst (und kannst) du ja auch nicht zeigen.


EDIT: Die geordneten Paare musst du natürlich nochmal völlig neu überdenken - da sind jede Menge Fehler.
sunshine85 Auf diesen Beitrag antworten »

seht ihr, genau das ist mein problem ;-)

wie setzen sich denn die geordneten paare zusammen ? einfach jede zahl mit jeder anderen, oder wie??
sunshine85 Auf diesen Beitrag antworten »

das mit den vorgängern stimmt???
 
 
AD Auf diesen Beitrag antworten »

Zitat:
Original von sunshine85
wie setzen sich denn die geordneten paare zusammen ?


Alle Paare (a,b) von je zwei Elemente der Menge hernehmen ( a<= b reicht) und überprüfen, ob a ein Teiler von b ist.

Wenn ja, dann gehört das Paar zur Relation - wenn nein, dann nicht.

So einfach ist das.
JochenX Auf diesen Beitrag antworten »

wenn du eine Menge A hast und eine Relation R, dann ist R eine Teilmenge von AxA (alle geordneten paare, also das ist wirklich jedes mit jedem), das sind einfach alle geordneten Paare (d.h. es gibt eine erste und eine zweite komponente [(c,d)!=(d,c)] und nicht einfach nur 2 , dann wärs ungeordnet), so dass diese elemente die bedingung von R erfüllen.

deine bedingung hier ist a|b, dann (a,b) in R.

also zählst du jetzt alle paare (a,b) mit a und b aus deiner menge auf, für die a b teilt.
also (1,1), (1,2),......

mfg jochen
sunshine85 Auf diesen Beitrag antworten »

das heisst: (1,2) (1,3) (1,6) (1,12) (1,18) (2,6) (3,6) (2,12) (2,18) (3,12) (3,18) (6,12) (6,18)
sunshine85 Auf diesen Beitrag antworten »

und...antisymmetrisch heisst doch a teil b, aber b teilt nicht a?!
JochenX Auf diesen Beitrag antworten »

antisymmetrisch heißt:
wenn a!=b und (a,b) in der relation ==> (b,a) nicht in der relation.
anders gesagt: (a,b) und (b,a) beide in R ==> a=b
mache dir das einfach mal anschaulich klar, insbesondere muss für 2 elemente a,b nicht (a,b) in R oder (b,a) in R gelten.....

mfg jochen
sunshine85 Auf diesen Beitrag antworten »

ok, das wird jetzt mit dem überlegen ein bisschen länger dauern...

aber das mit den paaren und den vorgängern stimmt das jetzt ????
JochenX Auf diesen Beitrag antworten »

bei den paaren fehlen mir noch etwas die reflexivität...
teilt denn 1 nicht sich selbst? doch also (1,1) in R usf.

was ist denn genau mit vorgänger gemeint?
sind die vorgänger von 6 nicht einfach alle elemente b, für die gilt (b,6) in R? (und wahrscheinlich zusätzlich b != 6)...

mfg jochen
sunshine85 Auf diesen Beitrag antworten »

i glaub ich verstehs trotzdem nicht:

gehört das so: 3!=6 (3,6) --> (6,3)

aber das würde ja dann nur für dieses paar gelten, muss es nicht auch für die anderen gelten, oder brauch ich dann einfach nur ein paar aus der menge finden auf das reflexiv, antisymmetrisch und transitiv zutrifft??
sunshine85 Auf diesen Beitrag antworten »

puh... das ist ja erheblich falscher von mit als ich gedacht hab, also:

die geordneten paare:

(1,2) (1,3) (1,6) (1,12) (1,18) (2,6) (3,6) (2,12) (2,18) (3,12) (3,18) (6,12) (6,18) (1,1) (2,2) (3,3) (6,6) (12,12) (18,18)

und vorgänger von 6 sind (1,2,3) und 3!=6
JochenX Auf diesen Beitrag antworten »

Zitat:
nur ein paar aus der menge finden auf das reflexiv, antisymmetrisch und transitiv zutrifft

das sind keine eigenschaften von den paaren sondern von der menge der paare, also der ganzen relation....

und wie gesagt, was vorgänger bedeutet, weiß ich nicht.
nach meiner vermutung wären 1, 2 und 3 vorgänger von 6.
dabei wären 2 und 3 gleichberechtigte (weil niocht vergleichbare) direkte vorgänger... 1 hingegen wäre kein direkter vorgänger...
da das ganze transitiv ist, kannst dir ja mal ein schaubild zu malen...

mfg jochen
sunshine85 Auf diesen Beitrag antworten »

ach ja...und was ist denn der unterschied zwischen vorgänger und unmittelbarem vorgänger???
sunshine85 Auf diesen Beitrag antworten »

ok, dass heisst wenn ich zeigen soll, dass die relation eine partialordnung ist, reicht es wenn ich nachweise, dass es reflexiv, antisymmetrisch und transitiv ist?

ja....das mit dem zeichnen ist dann mein nächstes problem.... ich hab noch nie eine relation gezeichnet, wie geht das... in meiner angabe steht: zeichne einen graphen, der diese partialordnung beschreibt.?!?!
JochenX Auf diesen Beitrag antworten »

wenn sich da niemand sonst drum bemüht, morgen mehr dazu....
also nur kurz:

wenn du dir das als kette ansiehst, dann gilt:
1|2, 2|6, da transitiv gilt somit auch 1|6

das sieht im bild dann etwa so aus:

1---->2----->6..... die pfeile verdeutlichen die laufrichtung gewöhnlich werden solche diagramme von oben nach unten gezeichnet und dann ist die laufrichtung klar...

2 ist eindeutig unmittelbarer vorgänger, während 1 nur "normaler" vorgänger ist...

mfg jochen
bier Auf diesen Beitrag antworten »

Wenn wir hier schon bei Relationen sind...
eine kurze Frage: bei der Realtion x-y ist durch 3 teilbar
erfüllt ja 4-1 diese Bedingung. Ist andersrum 1-4=-3 auch durch 3 teilbar? Ich mein ich denk schon, da das minus nix ausmachen dürfte, aber es wäre gut wenn ich es sicher wüßte...
Ist diese Relation also, symmetrisch?
JochenX Auf diesen Beitrag antworten »

das gehört hier wirklich nicht hin... aber es ist richtig, bier, 3 teilt -3....


ich mache dir unten mal ein beispiel, wie du es bildlich lösen könntest, sunshine.
meine relation ist auch "teilt" und zwar auf der menge {2,4,6,8,24}


mfg jochen
JochenX Auf diesen Beitrag antworten »

das ist aber unübersichtlich deshalb lässt man bei solchen graphen (die eine reflexive, transitive relation zeigen) oft d ie reflexiven kanten (schlaufen) und die durch transitivität eindeutig bestimmten kanten (z.b. 2-8, ist wegen 2-4 und 4-8 klar) weg.
das sieht dann einfach so aus (s. bild)

so und jetzt bist du dran mit deiner zahlenmenge....

mfg jochen
sunshine85 Auf diesen Beitrag antworten »

habs gerade gelesen, und mit hilfe meines skriptums sollte, ichs doch hinkriegen :-) wird nur ein bisserl dauern, weil ich mir den rechten ringfinger zurückgestaucht habe, aber ich fang mal an es zu zeichnen und poste dann wieder hier...
sunshine85 Auf diesen Beitrag antworten »

ok....sollte das so aussehen:???
JochenX Auf diesen Beitrag antworten »

also das sieht relativ richtig aus, aber einzelne fehlende kanten müsste man hier auch stundenlang suchen, denn das was du da gemacht hast ist CHAOS.
vesuche, es noch etwas zu ordnen (vergleiche mein erstes bild), z.b. durch dieses übereinanderschreiben.....

mfg jochen
sunshine85 Auf diesen Beitrag antworten »

ok, ich hab da sowieso noch eines das ich zeichnen muss... ich mach das mal übereinander und geordnet ...

S={2,3,5,7,21,42,105,210}
JochenX Auf diesen Beitrag antworten »

jupp und etwas größer Augenzwinkern
sunshine85 Auf diesen Beitrag antworten »

wobei, dass sieht eigentlich auch eher nach caos aus....
JochenX Auf diesen Beitrag antworten »

die reflexiven kanten hast jetzt vergessen...
ich hab's hier nochmal unter auslassung der reflexiven kanten und der durch transitivität klaren kanten gemacht.....
dann siehts wunderschön geordnet aus....

mfg jochen
sunshine85 Auf diesen Beitrag antworten »

wow, das sieht echt viel besser aus!das heisst wenn ich die einzelnen zahlen einkreise, dann drückt das die reflexivität aus, richtig?

und jetzt meine letzte frage: gibt es teilmengen von S die total geordnet sind? Wenn ja, welche?

was ist damit gemeint, ist das so wie bei dem vorigen bsp???
JochenX Auf diesen Beitrag antworten »

muss leider gleich weg, darum nur kurz: das mit dem einkreisen habe ich oben nur gemacht damit's schöner aussieht.

eigentlich erkennt man die reflexivität an den schlaufen an jedem punkt.... aber zur übersicht kann man die weglassen (am besten neben dem bild anmerken). genauso wie einige "transitive" kanten.
die kannst aber auch alle reinmachen, bei so wenigen werten kannst du das auch einigermaßen übesichtlich gestalten...


wohlgeordnet isses dann, wenn du alle elemente daraus im direkten vergleich als nachfolger/vorgänger voneinander identifzieren kannst.

z.b. ist S nicht wohlgeordnet, weil du 2 und 3 nicht vergleichen kannst.

eine wohlgeordnete teilmenge wäre z.b. {7,21,42,210}

mfg jochen
sunshine85 Auf diesen Beitrag antworten »

aha....dass heist auch {42,105,210} wäre eine geordnete teilmenge, es gibt in dem fall also mehrere verschiedene teilmengen von s, oder?

reflexiv - ok ist klar
transitiv, mit welchen schlaufen, kanten, etc, stell ich das dar??
JochenX Auf diesen Beitrag antworten »

Zitat:
{42,105,210}

ist nicht total geordnet.... gilt denn "42 vor 105" oder "105 vor 42"? die beiden elemente sind nicht vergleichbar!
bei einer totalen ordnung muss zusätzlich zu deiner gegebenen ordnung noch für alle x und y gelten: (x,y) oder (y,x). für x ungleich y ausschließendes oder.
beispiel für eine totale ordnung wäre zum beispiel "größergleich" auf der menge der ganzen zahlen....


Zitat:
transitiv, mit welchen schlaufen, kanten, etc, stell ich das dar??

diese sind einfach implizit gegeben.
aus den gerichteten kanten (2,4) und (4,8) folgt dank transitivität, das auch die gerichtete kante (2,8) im graphen ist.
diese kann man dann zur besseren übersicht weglassen...

leider erinnere ich mich nicht mehr an meine informatik1-vorlesung, da hatten wir, wie man diesen vereinfachten graphen dann nennt....
aber das ist ja auch egal.....

mfg jochen
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »