Könnte mir jemand erklären wie man die Aufgabe aus der Klausur (zum 1. Termin) löst? Ich denke das es vielleicht garnicht so schwer ist, aber irgendwie erinnert mich das an FGI1 und da graut es mir.


Gibt es jemanden der eine Musterlösung des ersten Termines hat. Das wäre für meinen weiteren Lernverlauf sehr vorteilhaft.

Aufgabenstellung?

http://www.informatik.uni-hamburg.de/Fachschaft/gprot/db/informatik/gprot345.pdf

Aufgabe 6

Generell würde ich gerne mal wissen, ob jemand von der Klausur eine lösung?

ich habe mich mal an folgender aufgabe probiert:

Nach den Axiomen zu einer sigma Algebra sollte folgendes richtig sein:

A={leere Menge, Omega, A, Ac, B, Bc, AuB} (c ist das Komplement)
also: ({leere Menge}, {omega}, {2,3,4},{1}, {1,2},{3,4},{1,2,3,4})

Kann mir das jemand Bestätigen?

Da fehlt noch {2}. Kleiner Tipp zur Kontrolle: Die Mächtigkeit einer endlichen sigma-Algebra ist immer eine Zweierpotenz (hier 8). (Um pingelig zu sein: Die leere mege und Omega gehören nicht in { }.)

Wieso die {2} ? Wo kommt die her?
und wieso Zweierpotenz = 8 ? Wir haben doch vier Elemente in Omega also wären das doch 2^4 Elemente = 16 Elemente

Klingt plausibel, weil die {2} der Schnitt von A und B ist. Allerdings sehen die drei Axiome für eine abgeschlossene Sigma-Algebra doch keinen Schnitt vor, oder?

Die Abgeschlossenheit gegen Schnitt folgt automatisch, wenn die Sigma-Algebra gegen Vereinigung und Komplement abgeschlossen ist. Siehe die Regel von De-Morgan:
[latex] A \cap B = \overline{\overline A \cup \overline B} [/latex]

[latex] A \cap B = \overline{\overline A \cup \overline B} [/latex]

Hmm jetzt verstehe ich nicht wieso es ein "doppeltes" Komplement sein soll. Das würde sich ja wieder aufheben und dann steht da:

[latex] A \cap B = A \cup B[/latex]

Magst du mir das bitte noch ein wenig deutlicher erklären?

Cool - jetzt habe ich die Aufgabe endlich verstanden.

Zu der letzten Frage vom Anonymen über mir:
! = nicht/negation, !Schnitt = Vereinigung

A Schnitt B = !(!A !Schnitt !B)

Ergo:
!A = {1}, !B = {3,4}
!A !Schnitt !B = {1,3,4}

Und das ganze nochmal negieren, also !({1,3,4}) = {2} womit wir bei "!(!A !Schnitt !B)" wären, was gleich A Schnitt B (laut DeMorgan) ist. Für Beweis von DeMorgan siehe Unterlagen vergangener Semester.

Ich hoffe das ist richtig so :D. (denke aber schon).

DeMorgan geht übrigens so:


[latex] A \cap B = \overline{\overline{( A \cup B)}} [/latex]


Das wird zu dem Missverständnis geführt haben :D.

DeMorgan geht übrigens so:


[latex] A \cap B = \overline{\overline{( A \cup B)}} [/latex]


Das wird zu dem Missverständnis geführt haben :D.

(…)nicht so(…)

Sollte da stehen :D. Also so hast du es aufgelöst.

{1,3,4} fehlt auch oder nicht?

@ bui:

die Sigma-Algebra enthält nicht einfach alle Elementkombinationen, sondern ist lediglich abgeschlossen gegenüber komplement und vereinigung (somit ggf auch schnitt) der elemente die sie enthält (hier A und B) + die komplette grundmenge + der leeren menge,

oder?

@ bui:

die Sigma-Algebra enthält nicht einfach alle Elementkombinationen, […]

das habe ich auch nie behauptet

ich habe mich mal an folgender aufgabe probiert:

Nach den Axiomen zu einer sigma Algebra sollte folgendes richtig sein:

A={leere Menge, Omega, A, Ac, B, Bc, AuB} (c ist das Komplement)
also: ({leere Menge}, {omega}, {2,3,4},{1}, {1,2},{3,4},{1,2,3,4})

Kann mir das jemand Bestätigen?

[…]
sondern ist lediglich abgeschlossen gegenüber komplement und vereinigung (somit ggf auch schnitt) der elemente die sie enthält (hier A und B) + die komplette grundmenge + der leeren menge,

und {1} vereinigt mit {3,4} ist doch {1,3,4}

Hm, eigentlich müsstest du recht haben.

Da A drin ist, ist auch !A drin. Da !A drin ist hat es ja auch einen "index" bzw ist eines der Ai - analog B und !B. Und es wird die Vereinigung aller "Ai"s verlangt. Allerdings landen wir dann nicht mehr bei einer Zweierpotenz.

Auch wenn manches für die Menge "redundant" ist, müsste es wohl sowas sein:
u= Vereinigung

{Omega, leereMenge, A , !A , B , !B , AuB , !AuB , Au!B , !Au!B }

Im Endeffekt also
(leereMenge,omega, {2,3,4},{1}, {1,2},{3,4},{1,2,3,4},{1,3,4})

Und die {2} natürlich wieder vergessen. ^^

Hm, eigentlich müsstest du recht haben.

Da A drin ist, ist auch !A drin. Da !A drin ist hat es ja auch einen "index" bzw ist eines der Ai - analog B und !B. Und es wird die Vereinigung aller "Ai"s verlangt. Allerdings landen wir dann nicht mehr bei einer Zweierpotenz.

Auch wenn manches für die Menge "redundant" ist, müsste es wohl sowas sein:
u= Vereinigung

{Omega, leereMenge, A , !A , B , !B , AuB , !AuB , Au!B , !Au!B }

Im Endeffekt also
(leereMenge,omega, {2,3,4},{1}, {1,2},{3,4},{1,2,3,4},{1,3,4})

Noch viel mehr als nur die zwei. Habe den schnitt wieder nicht beachtet.

{Omega, leereMenge, A , !A , B , !B , AuB , !AuB , Au!B , !Au!B, AnB, !AnB, An!B, !An!B}

Damit käme sogar noch die {1} dazu?

(leere Menge, omega, {2,3,4},{1}, {1,2},{3,4},{1,2,3,4},{1,3,4},{2},{1},)

Ich poste schneller als ich denken kann :D. Die {1} war schon drin. ^^ Also wieder redundant. Bei der "theoretischen" Menge fehlen immernoch zwei bis zur Zweierpotenz. (Oder stimmt das überhaupt?)

{Omega, leereMenge, A , !A , B , !B , AuB , !AuB , Au!B , !Au!B, AnB, !AnB, An!B, !An!B}

(leere Menge, omega, {2,3,4},{1}, {1,2},{3,4},{1,2,3,4},{1,3,4},{2},)

(leere Menge, omega, {2,3,4},{1}, {1,2},{3,4},{1,2,3,4},{1,3,4},{2},)

Streich das doppelte omega raus, und Du bist wieder bei 2^3=8 Elementen.

Recht hast du!

(leere Menge, omega, {2,3,4},{1}, {1,2},{3,4},{1,3,4},{2},)

Also muss nur die tatsächliche Menge eine Zweierpotenz darstellen. Fein,fein.

kann mir jemand sagen wieso das 2^3 ist ? die drei kommt woher ?

kann mir jemand sagen wieso das 2^3 ist ? die drei kommt woher ?

Nirgendwoher. Lies mal genauer:

Die Mächtigkeit einer endlichen sigma-Algebra ist immer eine Zweierpotenz (hier 8)

Hat deine gebastelte Menge also nicht 2,4,8,16,32… Elemente weisst du, dass du etwas zuviel/zuwenig hast. Du berechnest nicht im Vorhinein die Anzahl derselben.

Ja das hatte ich verstanden, aber woher weiß ich nun
ob das 2 hoch 3 oder 2 hoch 4 ist ?

Das siehst Du am Ende, wenn Du zählst.

asooo ich dachte eher man rechnet das vorher aus um zu wissen
wie viele da rein gehören hmm, ok dann kommt mir aber ne andere
Frage in den Sinn wie krieg ich denn dann raus was da reingehört :S
also leere menge und omega stehen schon immer fest und A und A^c
auch aber der rest ? wie kann ich das wissen ?

ach und A(vereinigt mit)B auch

Du schaust im Hübner oder sonstwo, was eine Sigma-Algebra haben muss.

Hübner Seite 17 stehen die Axiome.

ja da hab ichs ja her ganz unten seite 17 da steht

1)leere Menge
2) A^c falls A element A
3) A(vereinigt mit)B

Aber wie komme ich jetzt auf den ganzen rest, z.B hier in der
Aufgabe?

Ok bei B und B^c Komplement kann ich mir auch noch denken
aber wieso noch A\B ?

ja da hab ichs ja her ganz unten seite 17 da steht

1)leere Menge
2) A^c falls A element A
3) A(vereinigt mit)B

Aber wie komme ich jetzt auf den ganzen rest, z.B hier in der
Aufgabe?

Ok bei B und B^c Komplement kann ich mir auch noch denken
aber wieso noch A\B ?

edit: Und nich z.B nur B(vereinigt mit)A ?

aber wieso noch A\B ?

Weil das das gleiche ist wie [latex]\overline{\overline{A} \cup B}[/latex]

ja da hab ichs ja her ganz unten seite 17 da steht

1)leere Menge
2) A^c falls A element A
3) A(vereinigt mit)B

Aber wie komme ich jetzt auf den ganzen rest, z.B hier in der
Aufgabe?

Ok bei B und B^c Komplement kann ich mir auch noch denken
aber wieso noch A\B ?

Welcher ganze Rest? Lies doch mal diesen Thread hier gründlicher durch. Da steht, dass durch Abgeschlossenheit gegen Vereinigung und Komplement automatisch auch der Schnitt folgt (—>DeMorgan).

Guck dir Hüber S17 Definition 2.6 nochmal genauer an. Deine Auflistung entspricht ganz und garnicht den Axiomen. Das mit dem Schnitt steht in Worten über der Definition.

asooo ich dachte eher man rechnet das vorher aus um zu wissen
wie viele da rein gehören

Vermutung: Beobachte wieviele "isolierte" Elemente in den Mengen deines Erzeugendensystems sind, sind es [latex]n[/latex], dann sollten die erzeugte Sigma-Algebra [latex]2^{n+1}[/latex] Elemente haben.
Startest du also z.B. mit [latex] \epsilon = \left\{ \left\{1,2,3 \right\} , \left\{ 1 \right\} \right\} [/latex], so hast du als isolierte Elemente [latex] \left\{ 1 \right\} , \left\{ 2,3\right\} [/latex] . Die erzeugte Sigma-algebra wird wohl [latex]2^{2+1} [/latex] Elemente haben.

asooo ich dachte eher man rechnet das vorher aus um zu wissen
wie viele da rein gehören

Vermutung: Beobachte wieviele "isolierte" Elemente in den Mengen deines Erzeugendensystems sind, sind es [latex]n[/latex], dann sollten die erzeugte Sigma-Algebra [latex]2^{n+1}[/latex] Elemente haben.
Startest du also z.B. mit [latex] \epsilon = \left\{ \left\{1,2,3 \right\} , \left\{ 1 \right\} \right\} [/latex], so hast du als isolierte Elemente [latex] \left\{ 1 \right\} , \left\{ 2,3\right\} [/latex] . Die erzeugte Sigma-algebra wird wohl [latex]2^{2+1} [/latex] Elemente haben.

asooo ich dachte eher man rechnet das vorher aus um zu wissen
wie viele da rein gehören

Vermutung: Beobachte wieviele "isolierte" Elemente in den Mengen deines Erzeugendensystems sind, sind es [latex]n[/latex], dann sollten die erzeugte Sigma-Algebra [latex]2^{n+1}[/latex] Elemente haben.
Startest du also z.B. mit [latex] \epsilon = \left\{ \left\{1,2,3 \right\} , \left\{ 1 \right\} \right\} [/latex], so hast du als isolierte Elemente [latex] \left\{ 1 \right\} , \left\{ 2,3\right\} [/latex] . Die erzeugte Sigma-algebra wird wohl [latex]2^{2+1} [/latex] Elemente haben.

Muss ein wenig korrigiern. Gibt es [latex]n[/latex] isolierte Elemente, und ein isoliertes Komplementelement, so wird die erzeugte Algebra wohl [latex]2^{n+1}[/latex] Elemente haben, ansonsten [latex]2^n[/latex]

Es gilt:

Ist [latex]\epsilon = \left\{ A_1,…,A_n \right\} [/latex] das Erzeugendensystem, und [latex]M_w=\left\{ w' \in \Omega | \forall i=1,…,n : w \in A_i \Rightarrow w' \in A_i \right\}[/latex] die Formalisierung eines "isolierten" Elements und [latex]\Omega' = \left\{ M_w | w \in \Omega \right\} [/latex] , so gilt für die von [latex]\epsilon[/latex] erzeugte Sigma Algebra [latex] \left| \mathcal A(\epsilon) \right| = \left| 2^\Omega' \right|[/latex].

(Formal kann ich zeigen dass es einen Homomorphismus gibt, so dass [latex]h(\mathcal A(\epsilon)) = 2^\Omega' )[/latex] gilt.