Kardinalität zweier Mengenfamilien F,G so dass |A cup B| ungerade für alle A in F und B in G

02.12.2016, 15:06

stultus

Kardinalität zweier Mengenfamilien F,G so dass |A cup B| ungerade für alle A in F und B in G

Meine Frage:
Den folgenden Satz habe ich schon gewiesen. Der Satz, mit dem ich Schwierigkeiten habe ist der zweite, ohne Beweis.

Satz: Angenommen, wir haben zwei Mengensysteme $\begin{eqnarray*} F,G \subset P(n) \end{eqnarray*}$ , sodass für jedes $\begin{eqnarray*} A \in F \end{eqnarray*}$ und $\begin{eqnarray*} B \in F \end{eqnarray*}$ gilt: $\begin{eqnarray*} |A \cup B| \end{eqnarray*}$ ist gerade. Dann ist $\begin{eqnarray*} |F||G| <= 2^n \end{eqnarray*}$ .

Beweis: Wir arbeiten in $\begin{eqnarray*} \mathbf{F}_2 \end{eqnarray*}$ . Betrachte die charakteristischen Vektoren der Mengen in $\begin{eqnarray*} F \end{eqnarray*}$ und $\begin{eqnarray*} G \end{eqnarray*}$ im Vektorraum $\begin{eqnarray*} \mathbf{F}_2^n \end{eqnarray*}$ . Dann bilden die char. Vektoren in $\begin{eqnarray*} F \end{eqnarray*}$ bzw. $\begin{eqnarray*} G \end{eqnarray*}$ jeweils einen Untervektorraum. Sei $\begin{eqnarray*} U \end{eqnarray*}$ der Unterraum bzgl. $\begin{eqnarray*} F \end{eqnarray*}$ und $\begin{eqnarray*} V \end{eqnarray*}$ der Unterraum bzgl. $\begin{eqnarray*} G \end{eqnarray*}$ . Dann sind $\begin{eqnarray*} U \end{eqnarray*}$ und $\begin{eqnarray*} V \end{eqnarray*}$ orthogonal. Wir wissen, dass $\begin{eqnarray*} dim(U) + dim(V) <= n \end{eqnarray*}$ . Also folgt aus $\begin{eqnarray*} |U| = 2^k \end{eqnarray*}$ direkt $\begin{eqnarray*} |V| <= 2^(n-k) \end{eqnarray*}$ und wir erhalten $\begin{eqnarray*} |U||V| <= 2^n \end{eqnarray*}$ .

Ich würde gerne eine Variation desselben beweisen, bei der 'gerade' durch 'ungerade' ersetzt wurde:

Satz: Angenommen, wir haben zwei Mengensysteme $\begin{eqnarray*} F, G \subset P(n) \end{eqnarray*}$ , sodass für jedes $\begin{eqnarray*} A \in F \end{eqnarray*}$ und $\begin{eqnarray*} B \in F \end{eqnarray*}$ gilt: $\begin{eqnarray*} |A \cup B| \end{eqnarray*}$ ist ungerade. Dann ist $\begin{eqnarray*} |F||G| <= 2^n \end{eqnarray*}$ .

Meine Ideen:
Beweisidee: Ich würde gerne den gleichen Ansatz verfolgen wie im Beweis des ersten Satzes, allerdings bleibe ich bei dem Unterraumargument stecken (weil dies offensichtlich nicht stimmt). Ich würde mich freuen, wenn mir jemand auf die Sprünge helfen könnte.

02.12.2016, 15:10

HAL 9000

Auf diesen Beitrag antworten »

Vielleicht kann sich ein Moderator erbarmen, und alle LaTeX-Tags in das korrekte [latex]...[/latex] umwandeln - danke.

EDIT: Ach Moment, du bist ja registriert und kannst editieren - dann kannst du es natürlich selbst tun.

02.12.2016, 15:15

stultus

Auf diesen Beitrag antworten »

Hallo HAL 9000. Ich kann selber editieren ja, aber ich bin mir nicht sicher was da falsch ist?

02.12.2016, 15:18

HAL 9000

Auf diesen Beitrag antworten »

Das schließende Tag muss [/latex] lauten, nicht [\latex].

02.12.2016, 15:19

stultus

Auf diesen Beitrag antworten »

danke! Hab's jetzt korrigiert.

EDIT: einen Fehler habe ich noch gefunden, den ich aber nicht mehr korrigieren kann weil das Forum mir das nicht erlaubt. In der ersten Zeile vom ersten Satz sollte es heißen:

(richtig) sodass für jedes $\begin{eqnarray*} A \in F \end{eqnarray*}$ und $\begin{eqnarray*} B \in G \end{eqnarray*}$ gilt.

nicht

(falsch) sodass für jedes $\begin{eqnarray*} A \in F \end{eqnarray*}$ und $\begin{eqnarray*} B \in F \end{eqnarray*}$ gilt.

02.12.2016, 15:24

HAL 9000

Auf diesen Beitrag antworten »

Dann habe ich zunächst mal eine Frage zu deinem Originalbeweis:

Zitat:

Original von stultus
Betrachte die charakteristischen Vektoren der Mengen in $\begin{eqnarray*} F \end{eqnarray*}$ und $\begin{eqnarray*} G \end{eqnarray*}$ im Vektorraum $\begin{eqnarray*} \mathbf{F}_2^n \end{eqnarray*}$ . Dann bilden die char. Vektoren in $\begin{eqnarray*} F \end{eqnarray*}$ bzw. $\begin{eqnarray*} G \end{eqnarray*}$ jeweils einen Untervektorraum.

Wieso das? Es ist nur von Mengensystemen $\begin{eqnarray*} F \end{eqnarray*}$ und $\begin{eqnarray*} G \end{eqnarray*}$ die Rede, d.h., beliebige Mengen von Teilmengen aus $\begin{eqnarray*} P(n) \end{eqnarray*}$ . Daher sind die zugehörigen charakteristischen Vektoren m.E. auch nur irgendwelche Teilmengen von $\begin{eqnarray*} \mathbf{F}_2^n \end{eqnarray*}$ , die nicht notwendig die Unterraumeigenschaft haben - oder verstehe ich hier was falsch? verwirrt

Vielleicht meinst du den von diesen charakteristischen Vektoren erzeugten Unterraum?

02.12.2016, 15:35

stultus

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Dann habe ich zunächst mal eine Frage zu deinem Originalbeweis:

Zitat:

Wieso das? Es ist nur von Mengensystemen $\begin{eqnarray*} F \end{eqnarray*}$ und $\begin{eqnarray*} G \end{eqnarray*}$ die Rede, d.h., beliebige Mengen von Teilmengen von $\begin{eqnarray*} P(n) \end{eqnarray*}$ . Daher sind die zugehörigen charakteristischen Vektoren m.E. auch nur irgendwelche Teilmengen von $\begin{eqnarray*} \mathbf{F}_2^n \end{eqnarray*}$ , die nicht notwendig die Unterraumeigenschaft haben - oder verstehe ich hier was falsch? verwirrt

Du hast Recht! Es stimmt nur unter der folgenden Bedingung. Angenommen, F und G sind maximal sodass die Voraussetzungen erfüllt sind.

Wir wählen zwei Vektoren $\begin{eqnarray*} \chi_{A_1}, \chi_{A_2} \end{eqnarray*}$ in $\begin{eqnarray*} U \end{eqnarray*}$ . Dann ist $\begin{eqnarray*} \chi_{A_1}+ \chi_{A_2} = \chi_{A_1 \triangle A_2} \end{eqnarray*}$ und $\begin{eqnarray*} |A_1 \triangle A_2 \cap B| = |A_1 \cap B| + |A_2 \cap B| + 2|A_1 \cap A_2 \cap B| = 0 (mod 2) \end{eqnarray*}$ für jedes $\begin{eqnarray*} B \in G \end{eqnarray*}$ . Also ist U ein Untervektorraum.

02.12.2016, 15:42

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von stultus
Dann sind $\begin{eqnarray*} U \end{eqnarray*}$ und $\begin{eqnarray*} V \end{eqnarray*}$ orthogonal.

Versteh ich ebenfalls nicht. Wenn ich mir das Standardskalarprodukt in $\begin{eqnarray*} \mathbf{F}_2^n \end{eqnarray*}$ anschaue, dann bedeutet Orthogonalität doch eher, dass $\begin{align*} |A{\color{red}\cap}B| \end{align*}$ gerade ist, d.h. Durchschnitt statt Vereinigung - oder?

02.12.2016, 15:45

stultus

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000

Zitat:

Original von stultus
Dann sind $\begin{eqnarray*} U \end{eqnarray*}$ und $\begin{eqnarray*} V \end{eqnarray*}$ orthogonal.

Stimmt. Überall wo ich im Originalpost \cup geschriebe habe, sollte ein \cap hin. Dumm von mir. Hammer

Sorry!

Kann das vielleicht ein Moderator ändern?

Neue Frage »

Antworten »

Kardinalität zweier Mengenfamilien F,G so dass |A cup B| ungerade für alle A in F und B in G

Verwandte Themen