Relation auf eine Potenzmenge

2 Antworten

Definition. Es seien X, Y Mengen. Dann schreibt man

  • X ⊆ Y genau dann, wenn ∀a∈X: a∈Y

(gelesen: »Für alle a in X gilt auch a in Y«.)

Reflexivität. Sei X ∈ P(A). Dann gilt

  • Offensichtlich gilt ∀a∈X: a∈X. Per Definition X ⊆ X.

Also (X,X) ∈ R.

Transitivität. Seien X, Y, Z ∈ P(A) mit (X,Y), (Y,Z) ∈ R. Dann gilt

  • X ⊆ Y und Y ⊆ Z.
  • Per Definition (i) ∀a∈X: a∈Y und (ii) ∀a∈Y: a∈Z.
  • (iii) Für x∈X gilt laut (i), dass x∈Y; und laut (ii) folgt x∈Z.
  • Laut (iii) gilt ∀a∈X: a∈Z.
  • Also X ⊆ Z.

Also (X,Z) ∈ R.

Also ist (P(A), R) ein Halbordnung.

reflexivität beweisn ohne zu wissen, was in der menge drin liegt, ist ja gerade der sinn........

du rechnest ja auch nicht für jede kombination aller element-paare (besonders bei unendlich vielen elementen) die eigenschaften nach....

nichts desto trotz wird deine aufgabe viel einfacher, wenn du das symbol als das nimmst, was es bedeutet. das ist KEIN beliebiger bezeichner, sondern ein BESTIMMTER bezeichner für die "mengen-inklusion".

da klar ist, dass X in sich selbst teilmenge ist, also X \subset X (\subset ist latex-symbol für deinen bezeichner), ist die relation also reflexiv.

interessantere aufgabe:

ist es eine ordnungsrelation? (zeige transitivität und antisymmetrie)

ist die ordnung total? (kann man alle dinge miteinander vergleichen? d.h.: (a,b) oder (b,a) für jedes a,b aus P(A) ist in der relation enthalten)

Danke für die Antwort. Leider kann ich das so aber der Aufgabe nicht entnehmen. \subset scheint ja hier auf nichts bezogen zu werden. Ist \subset nun die Teilmenge von A? Oder von P(A)?

Wenn da praktisch steht: "Teilmenge ist dann eine Relation...".. Teilmenge von was? Ist damit P(A) \subset P(A) gemeint?

Aber wie beweise ich dann die Reflexivität? Ich glaube ich stehe gerade auf dem Schlauch bzw. hab das Thema noch nicht so begriffen, wie ich sollte. P(A) \subset P(A) würde dann ja bedeuten, dass (x=(P(A))) xRx gilt. Das gilt für die ganze Menge. Ist das schon Beweis genug? Muss ich nicht noch zeigen, dass das für die Elemente in P(A) gilt, auch wenn diese unbestimmt sind?

Für Symmetrie: Für alle x aus P(A) gilt: xRy => yRx. Das ist der Ansatz, den ich kenne. Kann ich dann hier genauso beweisen? Da P(A) \subset P(A) gilt auch P(A) \subset P(A), somit ist Symmetrie bewiesen? Ich komme einfach mit dem Gedanken nicht klar, diesmal keine Elemente zu benutzen.

0
@Chakashio

du benutzt sehr wohl elemente. deine elemente sind mengen.

und genauso, wie es zwischen zahlen das "kleiner-gleich" gibt, gibt es für mengen das "teilmenge von" zeichen, welches das \subset-zeichen ist.

für zwei beliebige "elemente" x,y aus P(A) gilt:

(es geht hier übrigens um antisymmetrie)

falls x \subset y und y \subset x , so ist x=y (damit ist antisymmetrie gezeigt).

das zeichen \subset ist dein "R" wie in xRy. deine elemente sind teilmengen von A (P(A) sind ja alle teilmengen von A, also sind die elemente von P(A) eben die teilmengen von A), und du musst das alles für alle beliebigen "elemente" aus P(A) zeigen.

symmetrie ist somit FALSCH!

für beliebige x,y aus P(A) soll gelten x \subset y. angenommen die symmetrie gilt, also y \subset x, so ist offenbar x=y (vgl. antisymmetrie), sodass aber x,y nicht beliebig waren, weil x=y eben einschränkt, dass die beiden elemente gleich sein müssen. diese können aber auch ungleich sein.

(das liegt daran, dass A nicht-leer ist, also P(A) mindestens 2 elemente hat, also 2 verschiedene x,y gewählt werden können)

0
@isbowhten

Danke, ich verstehe es langsam mehr!

Wenn ich jetzt ein ein Beispiel mache gegen die Symmetrie und von den beiden bekannten Elementen A und { } ausgehe, kann ich sagen: { } \subset A (schließlich ist die leere Menge Teilmenge jeder Menge), jedoch gilt A \subset { } _nicht_.

Bei Antisymmetrie gilt: Wenn xRy und yRx, dann x=y. In anderen Worten: Wenn M \subset N und N \subset M, dann müssen M und N identisch sein. Die Voraussetzung lässt sich so schreiben: Jedes x aus M muss auch in N sein und jedes y aus N muss auch in M sein. Daraus folgt: M = N.

Aber ist das nicht die Formel, die erfüllt sein muss für Antisymmetrie? Wie beweise ich diese Formel dann tatsächlich? Für einzelne Beispiele könnte ich das anwenden, bspw. könnte ich mir die Teilmenge A nehmen. Wenn ich also sage M=A und N=A ist es ja klar, dass M = N ist, also A=A gilt.

Da stecke ich aber schon wieder in meiner blöden Masche - ich versuche, etwas an Hand von Beispielen zu zeigen. Für Gegenbeispiele ist das ja gut, aber so wie hier darf ich halt eigentlich nicht denken.

Danke nochmal für die Erklärungen!

0
@Chakashio

"Jedes x aus M muss auch in N sein und jedes y aus N muss auch in M sein. Daraus folgt: M = N."

das ist genau schon der beiwes der antisymmetrie. denn aus der tatsache, dass jedes x aus N auch in M ist und jedes x aus M wiederum in N folgt ja gerade, das alle elemente von M in N sind und umgekehrt. die mengen sind also gleich.

ein konkretes beispiel zu wählen ist falsch. aber diese allgemeine aussage oben ist der beweis.

0

Äquivalenzrelation - Theoretische Informatik?

Hallo Leute,

ich habe eine Frage zur Äquivalenzrelation. An sich habe ich die Relationen untereinander zu verstanden (reflexiv, symmetrisch und transitiv). Hier ist mal ein Beispiel. Die Äquivalenzrelation gilt für dieses Beispiel laut dem Prof.

Gegeben ist die Menge M = {1, 2, 3, 9, 10, 12, 18, 21, 30, 45}. Jetzt soll man nachweise das die Relation R = {(x, y) ∈ M × M | x hat die gleiche Quersumme wie y} eine Äquivalenzrelation darstellt.

Das ganze wurde in einer Tabelle dargestellt (Tabelle im Anhang). Die Reflexivität und die Symmetrie zu beweisen ist kein Problem, aber wie stellt man hier die Transitivität da? Man hat ja nur x und y. Um die Transitivität darzustellen braucht man ja eigentlich auch jetzt z. Die Transitivität wird ja erfüllt wenn: Für x,y,z sind Elemente aus M. Wenn x R y und y R z dann folgt daraus das x R z ist. Aber woher bekomme ich das z jetzt?

Der Prof schreibt z.B. folgendes: Transitiv: Ja, denn wenn x1 und y sowie x2 und y die gleiche Quersumme haben, dann hat auch x1 und x2 die gleiche Quersumme. --> Wie ist das jetzt zu erklären?

...zur Frage

Habe hier eine Aufgabe in Mathe zum Thema Mengenlehre (geordnete Paare) und komme nicht weiter.. kann mir jemand helfen?

Das ist die Aufgabe: Erinnern sie sich daran, dass ein geordnetes Paar (a,b) definiert wurde als (a,b) ={a},{a,b} . Zeigen Sie, dass für zwei geordnete Paare (a,b) und (x,y) gilt: (a,b) = (x,y) ⇐⇒ a = x∧b = y.

Hinweis: Sie müssen hier zwei Richtungen zeigen. Machen Sie eine Fallunterscheidung in zwei Fälle, je nachdem ob es sich bei(a,b) ={a},{a,b} um eine ein- oder zweielementig Menge handelt.

Ich habe versucht zu zeigen, dass x=y sein muss, aber irgendwie kommt da was nicht hin, sodass am ende die Gleichung rauskommt. ich weiß auch nicht welche fälle ich unterscheiden soll, da ich ja eine Fallunterscheidung machen muss...

...zur Frage

Reelle Zahlen Referat

Ich muss bald ein 20 minütiges Referat über Reelle Zahlen halten. Alles ist beisammen, nur finde ich nirgends eine Begründung WIESO man denn die Reellen Zahlen entwickelt hat/wieso man sie braucht/wieso die rationalen nicht mehr reichen. Zweitens werde ich das ganze mit Hilfe dieses Kreis Beispiels mit den Teil/Mengen zeigen. Nur ist da die Frage; Mit den Reellen Zahlen kommen im Prinzip einfach die irrationalen Zahlen zu den rationalen hinzu und bilden so als gemeinsame Menge die Reellen Zahlen? Danke für fachlich korrekte Antworten!

...zur Frage

(Mathe) Frage zu Relationen und zur Antisymmetrie

Hiho, dies ist keine Hausaufgabe sondern nur eine Frage zu besserem Verständnis. Folgendes: Die Relation R ist Teilmenge des kartesischen Produktes aus der Potenzmenge N und der Potenzmenge N (ja 2 mal die natürlichen Zahlen). Dadurch habe ich nun auch nur alle erdenklichen Kombinationen der natürlichen Zahlen. Und dadurch, dass ich alle Kombinationen habe, ist diese Relation sowohl reflexiv, symmetrisch alsauch transitiv und damit eine Ordnungsrelation. Ist diese Relation aber nicht auch antisymmetrisch? Ich kapiere den Unterschied nicht ganz zwischen Symmetrisch und Antisymmetrisch.

...zur Frage

Potenzmenge der leeren Menge?

Hi Leute, ich hab folgendes Problem: Ich soll von einer Menge 0 = leere Menge die Potenzmenge bilden. Das ist noch nicht das Problem, aber dann soll ich von Menge M1-M5 die Elemente EXPLIZIT angeben.
M1 ist als P(Menge 0) definiert also als deren Potenzmenge usw. Also M2 ist die Potenzmenge von M1, M3 von M2 usw. Meine Frage ist da ich ja die Elemente explizit angeben soll und die Elemente der Potenzmenge immer 2^n (wobei n=Elemente der vorigen Menge ist) bekomme ich bei M5 2^16 Elemente also 2^16 mal die leere Menge das sind etwa 65000 Elemente. Hab ich irgendwo einen Denkfehler oder gibt es eine andere EXPLIZITE Schreibweise die Elemente aufzuführen ohne 65000 Elemente schreiben zu müssen? Wäre sehr dankbar für eine Antwort! LG

...zur Frage

Wie zeige ich, dass diese Aussage gilt und bei welchem Beispiel liegt keine Gleichheit vor?

Seien X, Y Mengen und f: X -> Y eine Abbildung. A, B sind Teilmenge von X.

Die Aussage ist:

f( A geschnitten B) ist Teilmenge von f( A) geschnitten f( B).

...zur Frage

Was möchtest Du wissen?