Moc zbioru - co to jest, oznaczenie, wzory i przykłady

Q: Co to jest moc zbioru?

Dla zbioru skończonego - liczba jego różnych elementów. Dla zbiorów nieskończonych moc mówi, które zbiory są „tak samo liczne": dwa zbiory mają równą moc, gdy ich elementy da się połączyć w pary jeden do jednego.

Q: Jak oznacza się moc zbioru?

Najczęściej |A|. Spotyka się też overlineoverlineA (dwie kreski nad literą), \#A oraz operatornamecard A.

Q: Jaka jest moc zbioru pustego?

Zero: |∅| = 0. Uwaga na zbiór \∅\ - ma jeden element (zbiór pusty), więc jego moc to 1.

Q: Ile podzbiorów ma zbiór n-elementowy?

2^n. Zbiór trzyelementowy ma 8 podzbiorów, czteroelementowy 16. Wśród nich są zawsze zbiór pusty i cały zbiór.

Q: Czy liczb wymiernych jest więcej niż naturalnych?

Nie. Choć liczby wymierne leżą „gęsto" na osi, da się je ponumerować, więc |Q| = |N| = aleph_0. Więcej jest dopiero liczb rzeczywistych.

Q: Co to jest alef zero?

aleph_0 to moc zbioru liczb naturalnych - najmniejsza moc nieskończona. Mają ją wszystkie zbiory przeliczalne, np. Z i Q.

Q: Czy podzbiór może mieć tę samą moc co cały zbiór?

Tylko gdy zbiór jest nieskończony - to wręcz jedna z definicji nieskończoności (Dedekinda). Liczby parzyste są właściwym podzbiorem liczb naturalnych, a mają tę samą moc.

Moc zbioru - najważniejsze wzory

Dla zbiorów skończonych moc to liczba elementów: $|A|$ (także $\overline{\overline{A}}$ , $\#A$ , $\operatorname{card} A$ ).

$|\varnothing| = 0 \qquad |A \cup B| = |A| + |B| - |A \cap B|$

$|A \times B| = |A| \cdot |B| \qquad |\mathcal{P}(A)| = 2^{|A|}$

Zbiory nieskończone: $|\mathbb{N}| = |\mathbb{Z}| = |\mathbb{Q}| = \aleph_0$ (przeliczalne), $|\mathbb{R}| = \mathfrak{c} = 2^{\aleph_0}$ (continuum).

Co to jest moc zbioru

Moc zbioru (inaczej liczba kardynalna) to uogólnienie pojęcia liczby elementów. Dla zbioru skończonego moc to po prostu liczba jego elementów. Dla zbiorów nieskończonych liczenie nie działa, więc moc definiuje się przez porównywanie: dwa zbiory mają tę samą moc (są równoliczne), gdy ich elementy da się połączyć w pary - każdy element pierwszego zbioru z dokładnie jednym elementem drugiego, bez żadnych pominiętych. Taka funkcja nazywa się bijekcją (funkcją wzajemnie jednoznaczną).

Moc zbioru $A$ oznacza się najczęściej $|A|$ . W starszych podręcznikach spotyka się zapis z dwiema kreskami nad literą $\overline{\overline{A}}$ , a także $\#A$ i $\operatorname{card} A$ (od angielskiego cardinality).

Moc zbioru skończonego - przykłady

Przy zbiorach skończonych wystarczy policzyć różne elementy:

$A = \{2, 4, 6, 8\}$ , więc $|A| = 4$ ;
$B = \{x \in \mathbb{Z} : -2 \le x < 3\} = \{-2, -1, 0, 1, 2\}$ , więc $|B| = 5$ ;
zbiór rozwiązań równania $x^2 = 9$ to $\{-3, 3\}$ , więc ma moc $2$ ;
$\{1, 1, 2\} = \{1, 2\}$ - powtórzony element liczy się raz, moc wynosi $2$ ;
zbiór pusty $\varnothing$ nie ma elementów, więc $|\varnothing| = 0$ ;
$\{\varnothing\}$ to zbiór, którego jedynym elementem jest zbiór pusty - jego moc to $1$ , nie $0$ .

Moc sumy zbiorów

Moc sumy nie jest sumą mocy - elementy wspólne policzylibyśmy dwa razy. Dlatego odejmujemy część wspólną:

$|A \cup B| = |A| + |B| - |A \cap B|.$

To najprostszy przypadek zasady włączeń i wyłączeń. Gdy zbiory są rozłączne ( $A \cap B = \varnothing$ ), wzór upraszcza się do $|A \cup B| = |A| + |B|$ .

Przykład. W klasie jest $30$ uczniów. Matematykę lubi $18$ z nich, fizykę $15$ , a oba przedmioty $8$ . Ilu uczniów nie lubi żadnego z nich?

Uczniów lubiących co najmniej jeden przedmiot jest $|M \cup F| = 18 + 15 - 8 = 25$ , więc żadnego nie lubi $30 - 25 = 5$ uczniów.

Dla różnicy zbiorów działa podobny wzór: $|A \setminus B| = |A| - |A \cap B|$ . W przykładzie tylko matematykę (bez fizyki) lubi $18 - 8 = 10$ uczniów.

Moc iloczynu kartezjańskiego i zbioru potęgowego

Iloczyn kartezjański $A \times B$ to zbiór wszystkich par $(a, b)$ , gdzie $a \in A$ , $b \in B$ . Każdy z $|A|$ elementów łączymy z każdym z $|B|$ elementów, więc $|A \times B| = |A| \cdot |B|$ . Na przykład dla $A = \{1, 2, 3\}$ i $B = \{x, y\}$ par jest $3 \cdot 2 = 6$ .

Zbiór potęgowy $\mathcal{P}(A)$ to zbiór wszystkich podzbiorów zbioru $A$ (łącznie ze zbiorem pustym i samym $A$ ). Jeśli $|A| = n$ , to podzbiorów jest $2^n$ - przy każdym elemencie decydujemy niezależnie „bierzemy albo nie bierzemy”, czyli mamy $n$ wyborów po dwie możliwości.

Przykład. Zbiór $\{a, b, c\}$ ma $2^3 = 8$ podzbiorów: $\varnothing$ , $\{a\}$ , $\{b\}$ , $\{c\}$ , $\{a, b\}$ , $\{a, c\}$ , $\{b, c\}$ , $\{a, b, c\}$ .

Zbiory nieskończone przeliczalne - alef zero

Zbiór nazywamy przeliczalnym, gdy jest równoliczny ze zbiorem liczb naturalnych - czyli gdy jego elementy da się ustawić w ciąg (ponumerować) bez pomijania żadnego. Moc takiego zbioru oznacza się $\aleph_0$ (alef zero, od pierwszej litery alfabetu hebrajskiego); oznaczenie wprowadził Georg Cantor.

Przy zbiorach nieskończonych intuicja „część jest mniejsza od całości” zawodzi:

Liczby parzyste mają tyle samo elementów co wszystkie liczby naturalne: pary $n \leftrightarrow 2n$ łączą $0, 1, 2, 3, \ldots$ z $0, 2, 4, 6, \ldots$ Ten paradoks zauważył już Galileusz.
Liczby całkowite są przeliczalne, bo da się je ponumerować naprzemiennie: $0, 1, -1, 2, -2, 3, -3, \ldots$
Liczby wymierne też są przeliczalne, choć między każdymi dwiema leży ich nieskończenie wiele - ułamki można ustawić w tablicę i przejść ją „po przekątnych”.

Stąd $|\mathbb{N}| = |\mathbb{Z}| = |\mathbb{Q}| = \aleph_0$ . Obrazową wersję tych faktów opowiada historia hotelu Hilberta - zobacz cytat o raju Cantora.

Moc continuum - zbiory nieprzeliczalne

W 1874 roku Cantor udowodnił, że liczb rzeczywistych nie da się ponumerować. Najsłynniejszy dowód tego faktu, metoda przekątniowa, pochodzi z 1891 roku: z dowolnej listy liczb z przedziału $(0, 1)$ da się zbudować liczbę, której na liście nie ma. Moc zbioru liczb rzeczywistych nazywa się mocą continuum i oznacza $\mathfrak{c}$ ; zachodzi $\mathfrak{c} = 2^{\aleph_0} > \aleph_0$ .

Moc continuum mają nie tylko wszystkie liczby rzeczywiste, ale też:

każdy przedział, np. $(0, 1)$ - tyle samo punktów co cała prosta;
zbiór liczb niewymiernych (gdyby był przeliczalny, to $\mathbb{R}$ jako suma dwóch zbiorów przeliczalnych też byłby przeliczalny);
płaszczyzna $\mathbb{R}^2$ - wynik, który zaskoczył samego Cantora.

Czy istnieje zbiór o mocy pośredniej, większej niż $\aleph_0$ , a mniejszej niż $\mathfrak{c}$ ? To hipoteza continuum. Kurt Gödel (1940) i Paul Cohen (1963) pokazali, że na gruncie standardowych aksjomatów teorii mnogości nie da się jej ani udowodnić, ani obalić.

Nie ma największej mocy

Twierdzenie Cantora mówi, że zbiór potęgowy zawsze ma większą moc niż sam zbiór: $|\mathcal{P}(A)| > |A|$ . Dla zbiorów skończonych to oczywiste ( $2^n > n$ ), ale twierdzenie działa także dla nieskończonych. Stosując je raz za razem, dostajemy nieskończoną drabinę coraz większych nieskończoności: $|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < \ldots$ Szczegóły i dowód: twierdzenia Cantora.

Najczęstsze pytania

Co to jest moc zbioru? Dla zbioru skończonego - liczba jego różnych elementów. Dla zbiorów nieskończonych moc mówi, które zbiory są „tak samo liczne”: dwa zbiory mają równą moc, gdy ich elementy da się połączyć w pary jeden do jednego.

Jak oznacza się moc zbioru? Najczęściej $|A|$ . Spotyka się też $\overline{\overline{A}}$ (dwie kreski nad literą), $\#A$ oraz $\operatorname{card} A$ .

Jaka jest moc zbioru pustego? Zero: $|\varnothing| = 0$ . Uwaga na zbiór $\{\varnothing\}$ - ma jeden element (zbiór pusty), więc jego moc to $1$ .

Ile podzbiorów ma zbiór $n$ -elementowy? $2^n$ . Zbiór trzyelementowy ma $8$ podzbiorów, czteroelementowy $16$ . Wśród nich są zawsze zbiór pusty i cały zbiór.

Czy liczb wymiernych jest więcej niż naturalnych? Nie. Choć liczby wymierne leżą „gęsto” na osi, da się je ponumerować, więc $|\mathbb{Q}| = |\mathbb{N}| = \aleph_0$ . Więcej jest dopiero liczb rzeczywistych.

Co to jest alef zero? $\aleph_0$ to moc zbioru liczb naturalnych - najmniejsza moc nieskończona. Mają ją wszystkie zbiory przeliczalne, np. $\mathbb{Z}$ i $\mathbb{Q}$ .

Czy podzbiór może mieć tę samą moc co cały zbiór? Tylko gdy zbiór jest nieskończony - to wręcz jedna z definicji nieskończoności (Dedekinda). Liczby parzyste są właściwym podzbiorem liczb naturalnych, a mają tę samą moc.

Podsumowanie

Moc zbioru skończonego to liczba jego różnych elementów, oznaczana $|A|$ ; $|\varnothing| = 0$ .
Moc sumy: $|A \cup B| = |A| + |B| - |A \cap B|$ ; moc iloczynu kartezjańskiego: $|A \times B| = |A| \cdot |B|$ .
Zbiór $n$ -elementowy ma $2^n$ podzbiorów.
Zbiory równoliczne to takie, między którymi istnieje bijekcja.
$\mathbb{N}$ , $\mathbb{Z}$ i $\mathbb{Q}$ są przeliczalne (moc $\aleph_0$ ), a $\mathbb{R}$ ma większą moc continuum $\mathfrak{c}$ .
Nie ma największej mocy: zawsze $|\mathcal{P}(A)| > |A|$ .
Więcej o zbiorach liczbowych: zbiory liczbowe.