Partielle Ordnung, Ketten und Antiketten

Neue Frage »

Nala.... Auf diesen Beitrag antworten »
Partielle Ordnung, Ketten und Antiketten
Meine Frage:
Hallo liebes Forum!

Ich habe da eine Aufgabe bei der ich nicht weiter komme.

Es sei und eine partielle Ordnung wobei x<y genau dann gilt, wenn x ein Teiler von y ist. Zeige das die maximale Anzahl an Elmenten in einer Antikette gleich der minimalen Anzahl von Ketten aus R ist, mit denen man die Menge M partitionieren kann.

Meine Ideen:
Durch etwas rumprobieren denke ich mal das sowohl die Maximale Antikette als auch die minimale Anzahl an Ketten mit denen man M partitionieren kann n ist. Beweisen wollte ich das ganze über Induktion nur komme ich da nicht wirklich Weiter. Für n=1 ist es ja klar. Bei n+1 kommen ja zur Menge M nur zwei Zahlen dazu 2n+2 und 2n+1. Wie ich dann aber die Antikette bzw die Ketten konstruiere ist mir nicht klar. Hoffe ihr könnt mir da einen Tip geben wie ich den Induktionsschritt weiter führen könnte und ob überhaupt mein Ansatz mit der Induktion zielführend ist.
Huggy Auf diesen Beitrag antworten »
RE: Partielle Ordnung, Ketten und Antiketten
Man kann doch ohne Induktion zeigen, dass beide Zahlen gleich sind.
Nala.... Auf diesen Beitrag antworten »
RE: Partielle Ordnung, Ketten und Antiketten
Ja? Induktion war ein verzweifelter versuch irgendeinen Ansatz zu haben. Ohne weiß ich ehrlich gesagt gar nicht weiter... Hättest du vielleicht eine Ansatz wie ich anfangen könnte?
Huggy Auf diesen Beitrag antworten »
RE: Partielle Ordnung, Ketten und Antiketten
Fangen wir mal mit der maximalen Größe einer Anitkette an. ist eine Antikette. Sie hat Elemente.

a) Weshalb ist das eine Antikette?
b) Kann es eine größere geben?
Nala.... Auf diesen Beitrag antworten »

Zur a) Es ist eine Antikette, da der größte Teiler von 2n n ist, also sind alle Zahlen n+1,...,2n keine Teiler von 2n. Nimmt man an das sich in der Zahlenmenge n+1,...,2n zwei verschiedene Zahlen befinden s.d. eine Zahl ein Teiler der anderen ist so heißt das:

Es existieren l,k mit 0 < l,k < n+1 , s.d für ein m gilt . Für m = 1 wäre n+l = n+k ein Widerspruch das die beiden Zahlen verschieden sind. Für m>1 ist n+k nicht in der Zahlenmenge n+1,...,2n drinnen.

Zur b) Nein. Würde man eine Zahl hinzunehmen, dann würde diese der Form n-l sein für ein . Dann gilt aber



Also wäre n-l ein Teiler von einer Zahl in der Menge {n+1,...,2n}.

Da wir also bereits n Zahlen haben und dieser Menge keine weiteren Zahl hinzunehmen können ist das die Größte Antikette (? ist etwas schwamming. Kann man das irgendwie präziser formulieren?).

Ich schätze mal die Ketten müssten wir dann so konstruieren, dass immer jeweils eine Zahl aus {n+1,....,2n} und eine aus {1,....,n} drinnen liegt? Dann wären das n Ketten und würden M partitionieren? Man müsste schätze ich mal noch beweisen, dass diese Partitionierung minimal ist.

Dazu noch eine Frage: Vielleicht verstehe ich ja die Definition falsch aber was wäre, wenn ich einfach in jede Kette genau ein Element aus M rein tue? Also besteht jede Kette aus genau einem Element und für so ein Element x gilt x<x, da x ja ein Teiler von sich selber ist. Hätte ich dann nicht 2n Ketten?
Huggy Auf diesen Beitrag antworten »

Das passt ungefähr Ich hätte es so formuliert:

a) Jedes Vielfache einer Zahl aus der genannten Menge ist , da ja mindestens mit multipliziert wird. Jeder Teiler einer Zahl aus der genannten Menge ist , da ja mindestens durch geteilt wird. Also ist von den Zahlen in der genannten Menge weder ein Vielfaches noch ein Teiler auch in der Menge.

b) Hätte man eine Antikette mit mehr als Elementen, so müssten darin auch Elemente enthalten sein, weil es ja nur mögliche Elemente gibt. Jedes Element hat aber mindestens ein Vielfaches im Bereich , das dann nicht in der Antikette sein kann. Sie kann also nicht mehr als Elemente haben.

Bei der Partitionierung in Ketten beginne jede Kette mit einer ungeraden Zahl und multipliziere diese dann so oft mit , bis man überschreitet. Bei z. B. wären das die Ketten











Das sind Ketten.

c)Weshalb bilden diese eine Partitionierung?

d) Weshalb gibt es keine Partitionierung mit weniger Ketten? Partitionierungen mit mehr Ketten stören nicht, da ja nach dem Minimum gefragt ist.
 
 
Nala.... Auf diesen Beitrag antworten »

Per Konstruktion liegt ja jede ungerade Zahl in einer Kette. Da wir jede ungerade Zahl mit zwei Multiplizieren (insbesondere die < n) liegt auch jede gerade Zahl in einer Kette.

Auch ist jede Zahl in genau einer Kette, da für zwei Zahlen x,y die nicht in einer Kette liegen gilt, dass sie dargestellt werden können als . Daraus folgt



die Zahl auf der rechten Seite ist ungerade und die Zahl auf der linken Seite ist nur für n-m = 0 ungerade. Also ist l=k und x,y sind von der gleichen Zahl erzeugt, liegen also in der selben Kette.

Wieso es aber keine kleinere Partition gibt will mir nicht einfallen. Also ich habe durch probieren gemerkt, dass es nicht möglich ist aber wie man das allgemein zeigt sehe ich nicht.

Und ja völlig vergessen dass nach einer minimalen Partitionierung gefragt war. Big Laugh
Huggy Auf diesen Beitrag antworten »

Zitat:
Original von Nala....
Wieso es aber keine kleinere Partition gibt will mir nicht einfallen. Also ich habe durch probieren gemerkt, dass es nicht möglich ist aber wie man das allgemein zeigt sehe ich nicht.

Für je zwei Elemente einer Kette muss gelten oder . Angenommen, es gäbe eine Partitionierung mit weniger als Ketten, dann müssten in einer dieser Ketten mindestens 2 Elemente aus liegen (Schubfachprinzip). Das kann aber nicht sein, da ja für diese beiden Elemente weder noch gilt.
Nala.... Auf diesen Beitrag antworten »

Ach jetzt sehe ich es. Mein alter Erzfeind das Schubfachprinzip! Zwar eine solche schöne und intuitive Aussage aber wenn es mal irgendwo angewandt werden kann sehe ich es einfach nicht! Hammer

Ich danke dir vielmals für deine Tips, Erklärungen und Gedult! smile
Huggy Auf diesen Beitrag antworten »

Es bereitet mir immer Freude zu helfen, wenn der/die Fragende die Anregungen aufgreift und versteht und das war bei dir der Fall.
Neue Frage »
Antworten »



Verwandte Themen

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