Erzeugendensystem der trivialen Sigma - Algebra

18.10.2013, 18:13

steviehawk

Erzeugendensystem der trivialen Sigma - Algebra

Meine Frage:
Hallo Leute, ich habe die Menge:

$\begin{eqnarray*} \Omega = \left\{ 1,2,3,4\right\} \end{eqnarray*}$

dazu noch 4 Teilmengen von der Potenzmenge $\begin{eqnarray*} P(\Omega) \end{eqnarray*}$ . Nun ist die Frage, wie viele Elemente ein Erzeugendensystem der trivialen $\begin{eqnarray*} \sigma - \end{eqnarray*}$ Algebra $\begin{eqnarray*} P(\Omega) \end{eqnarray*}$ haben muss?

Meine Ideen:
Ich habe hier herrausgefunden, dass es mindestens 3 Elemente sein müssen.

Nun frage ich mich, ob es da eine allg. Regel gibt? Bzw. ob das stimmt?

Danke!

18.10.2013, 18:20

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von steviehawk
Ich habe hier herrausgefunden, dass es mindestens 3 Elemente sein müssen.

Wirklich? Wie sieht es mit

$\begin{eqnarray*} \{ \{1,2\} , \{1,3\} \} \end{eqnarray*}$

aus? Augenzwinkern

Übrigens solltest du nicht von "der trivialen $\begin{eqnarray*} \sigma \end{eqnarray*}$ -Algebra" sprechen, wenn du die Potenzmenge $\begin{eqnarray*} P(\Omega) \end{eqnarray*}$ meinst:

Gewöhnlich ist dieses Attribut "trivial" nämlich für die $\begin{eqnarray*} \sigma \end{eqnarray*}$ -Algebra $\begin{eqnarray*} \{ \emptyset, \Omega \} \end{eqnarray*}$ reserviert. Augenzwinkern

19.10.2013, 17:08

steviehawk

Auf diesen Beitrag antworten »

Gut, auf die Idee, die 3 Elemente so geschickt in 2 Menge, dass man im Endeffekt doch nur 2 Elemente braucht ist mir nicht eingefallen.

Dann sind es offensichtlich 2 Elemente.

Bleibt die Frage, ob es da etwas allg. gibt. Oder muss ich das jedes mal neu prüfen?
bzw. ist die Element Zahl vielleicht auch eine 2er Potenz?

Gruß Stevie & Danke

19.10.2013, 17:56

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von steviehawk
bzw. ist die Element Zahl vielleicht auch eine 2er Potenz?

Eher das Gegenteil (=Umkehroperation):

Ist $\begin{eqnarray*} |\Omega| = n \end{eqnarray*}$ , so kann man für $\begin{eqnarray*} P(\Omega) \end{eqnarray*}$ ein Erzeugendensystem der minimalen Mächtigkeit $\begin{eqnarray*} \left\lceil \log_2(n) \right\rceil \end{eqnarray*}$ konstruieren.

19.10.2013, 20:00

steviehawk

Auf diesen Beitrag antworten »

interessant.

Vielen Dank HAL9000

21.10.2013, 18:55

steviehawk

Auf diesen Beitrag antworten »

würde sich da ein Beweis per Induktion anbieten? Dass $\begin{eqnarray*} |P(\Omega)| = 2^n \end{eqnarray*}$ , bei $\begin{eqnarray*} |\Omega| = n \end{eqnarray*}$ zeigt man ja auch per Induktion.

Ich versuche es mal smile

Sei $\begin{eqnarray*} |\Omega| = 1 \end{eqnarray*}$ , dann ist: $\begin{eqnarray*} |P(\Omega)| = 2 \end{eqnarray*}$

es ist: $\begin{eqnarray*} log_2(1) = 0 \end{eqnarray*}$ verwirrt

aber das minimale EZS kann wohl kaum leer sein..

Hat mir jemand einen Tipp?

EDIT:

Wobei, es gilt ja für $\begin{eqnarray*} \mathcal(C) = \{ \} = \emptyset \end{eqnarray*}$ , dass:

$\begin{eqnarray*} \sigma(\mathcal(C) = P(\Omega) \end{eqnarray*}$ und $\begin{eqnarray*} \mathcal(C) \end{eqnarray*}$ hat keine Elemente.

Sei die Aussage also für ein $\begin{eqnarray*} n \in \mathbb N \end{eqnarray*}$ gezeigt.

mhh Induktionsschluss bekomme ich nicht hin! Aber vielleicht gehts auch ohne Induktion!

21.10.2013, 19:48

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von steviehawk
aber das minimale EZS kann wohl kaum leer sein..

Doch, kann es: Bei leerem EZS ist die Sigma-Algebra die wirklich triviale $\begin{eqnarray*} \{\emptyset,\Omega\} \end{eqnarray*}$ .

Ich hatte nicht an Induktion gedacht, sondern an die direkte konstruktive Angabe eines solchen Erzeugendensystems. Zunächst mal können wir o.B.d.A.

$\begin{eqnarray*} \Omega = \{ 0, 1, 2, \ldots, n-1 \} \end{eqnarray*}$

annehmen, alles andere lässt sich durch passend bijektives Mapping erledigen. Sei nun $\begin{eqnarray*} d = \left\lceil \log_2(n) \right\rceil \end{eqnarray*}$ , d.h., es ist dann $\begin{eqnarray*} 2^{d-1} < n\leq 2^d \end{eqnarray*}$ . Jetzt definieren wir die $\begin{eqnarray*} d \end{eqnarray*}$ Mengen des EZS:

$\begin{eqnarray*} A_k = \left\{ m=\sum_{j=0}^{d-1} b_j2^j \in \Omega \biggm| b_j\in\{0,1\}\,\wedge\, b_k=1 \right\} \end{eqnarray*}$ für $\begin{eqnarray*} k=0,1,\ldots,d-1 \end{eqnarray*}$ ,

d.h. in Worten: $\begin{eqnarray*} A_k \end{eqnarray*}$ enthält alle diejenigen Zahlen aus $\begin{eqnarray*} \Omega \end{eqnarray*}$ , die in ihrer Binärdarstellung an der $\begin{eqnarray*} k \end{eqnarray*}$ -ten Stelle eine 1 haben (von hinten gezählt ab Index 0).

Der Effekt dieser Konstruktion ist, dass man über die Auswahlfunktion

$\begin{eqnarray*} M_k(b) = \begin{cases} A_k^c & \; \mbox{für}\; b=0 \\ A_k & \; \mbox{für}\; b=1 \end{cases} \end{eqnarray*}$

für $\begin{eqnarray*} m\in \Omega \end{eqnarray*}$ mit Binärdarstellung $\begin{eqnarray*} m=\sum_{j=0}^{d-1} b_j2^j \end{eqnarray*}$ die Einermenge

$\begin{eqnarray*} \bigcap\limits_{k=0}^{d-1} M_k(b_k) = \{ m \} \end{eqnarray*}$

erhält. Aus allen Einermengen kann man nun offensichtlich durch Vereinigungen auch die ganze Potenzmenge $\begin{eqnarray*} P(\Omega) \end{eqnarray*}$ erzeugen.

------------------------------------------

Beispiel $\begin{eqnarray*} n=6 \end{eqnarray*}$ mit $\begin{eqnarray*} \Omega = \{ 0, 1, 2, 3, 4, 5\} \end{eqnarray*}$ und $\begin{eqnarray*} d=3 \end{eqnarray*}$

$\begin{eqnarray*} A_0 = \{ 1, 3, 5 \} \end{eqnarray*}$
$\begin{eqnarray*} A_1 = \{ 2, 3 \} \end{eqnarray*}$
$\begin{eqnarray*} A_2 = \{ 4, 5 \} \end{eqnarray*}$

------------------------------------------

Damit ist gezeigt, dass es ein Erzeugendensystem der Größe $\begin{eqnarray*} d = \left\lceil \log_2(n) \right\rceil \end{eqnarray*}$ gibt. Was man noch zeigen müsste, dass es nicht noch ein kleineres gibt. Aber das ist auch möglich.

Neue Frage »

Antworten »

Erzeugendensystem der trivialen Sigma - Algebra

Verwandte Themen