O mocy zbiorów raz jeszcze

Zgodnie z tym co zauważyliśmy powyżej, elementy \(A\cup B\) są trzech rozdzajów:

1. leżące w A i nie w B, czyli \(A\setminus B\),
2. leżące w B i nie w A, czyli \(B\setminus A\),
3. leżące w A i B, czyli w \(A\cap B\).

Z drugiej strony, jeśli policzymy osobno elementy w A,B, to dostaniemy:

1. Elementy w A:
   1. leżące w A i nie w B, czyli \(A\setminus B\),
   2. leżące w A i w B, czyli \(A\cap B\),
2. Elementy w B:
   1. leżące w B i nie w A, czyli \(B\setminus A\),
   2. leżące w B i w B, czyli \(A\cap B\).

Czyli \(n=|A\setminus B|+|A\cap B|\) i \(m=|B\setminus A|+|A\cap B|\). Czyli \(n+m=|A\setminus B|+|A\cap B|+|B\setminus A|+|A\cap B|=|A\setminus B|+|B\setminus A|+2|A\cap B|\). Z drugiej strony \(|A\cup B|=|A\setminus B|+|B\setminus A|+|A\cap B|\). Więc liczby n + m i \(|A\cup B|\), różnią się o \(|A\cap B|\). Czyli otrzymujemy równanie \(|A\cup B|=n+m-|A\cap B|\)!

Iloczyn

Rozważmy teraz moc zbioru \(A\times B\). Tak jak mówiliśmy, elementy występujące w tym zbiorze to pary (a,b), gdzie \(a\in A, b\in B\). Dla ustalonego \(a\in A\), par \((a,b)\in A\times B\) jest dokładnie m (czyli tyle co elementów zbioru B). Natomiast wszystkich \(a\in A\) jest n. Więc skoro dla każdego z pośród n możliwych \(a\in A\), mamy zawsze m elementów w iloczynie kartezjańskim, to cały iloczyn ma dokładnie \(n\cdot m\) elementów.

Zbiór potęgowy

Spróbujemy teraz policzyć moc zbioru P(A). Już zauważyliśmy, że \(P(\emptyset)=\{\emptyset\}\), więc \(|P(\emptyset)|=1\). Popatrzmy co się stanie, jeśli zbiór A zwiększymy o jeden element. Czyli niech \(A'=A\cup\{a\}\) i \(a\notin A\). Wtedy elementy P(A') dzielą się na dwa rodzaje:

1. te które nie zawierają a, oznaczymy je \(P_0=\{X\in P(A'):a\notin X\}\),
2. te które zawierają a, oznaczamy je \(P_1=\{X\in P(A'):a\in X\}\).

Dodatkowo zauważmy, że każdy zbiór \(X\in P(A')\) albo zawiera a, albo nie. Więc \(P_0\cap P_1=\emptyset\) i \(P(A')=P_0\cup P_1\). Czyli aby policzyć ile elementów ma zbiór P(A'), wystarczy policzyć elementy zbiorów P₀,P₁ i dodać.

• Skoro P₀ to elementy P(A') nie zawierające a, to w takim razie P₀ = P(A).
• Z drugiej strony, z każdym elementem \(X\in P_1\), można związać \(X\setminus \{a\}\in P_0\). Okazuje się, że to jest wzajemnie jednoznaczne przypisanie, ze zbioru P₁ w P₀, więc | P₀ | = | P₁ | .

Czyli \(|P(A')|=|P_0|+|P_1|=2\cdot |P_0|=2\cdot |P(A)|\). Czyli dodanie elementu do zbioru A zwiększa moc jego zbioru potęgowego dwukrotnie. Więc | P(A) | = 2ⁿ.