Zbiory, relacje i funkcje: zadania z rozwiązaniami krok po kroku

1Zbiory i działania na zbiorach

Zbiór to zestaw różnych elementów: A = {1, 2, 3}. Kolejność i powtórzenia nie mają znaczenia. |A| to liczba elementów, a U to zbiór uniwersalny zawierający wszystko, o czym mowa.

• A ∪ B (suma): elementy należące do A lub B albo do obu.
• A ∩ B (iloczyn): elementy należące do obu.
• A − B (różnica): elementy A, które nie należą do B.
• A′ (dopełnienie): elementy U, które nie należą do A.

Na diagramie Venna dwa koła dzielą U na cztery obszary: tylko A, oba, tylko B i żaden. Każde wyrażenie na zbiorach jest sumą niektórych z tych obszarów, więc zawsze można je zliczyć obszar po obszarze.

Tutaj |A| = 12 + 5 = 17, |A ∩ B| = 5, |A ∪ B| = 12 + 5 + 8 = 25 oraz |(A ∪ B)′| = 15.

2Zliczanie metodą włączeń i wyłączeń

Dodanie |A| i |B| liczy część wspólną dwa razy, więc odejmij ją raz:

Dla trzech zbiorów odejmuje się części wspólne parami, ale wtedy środek został usunięty trzy razy, więc dodaje się go z powrotem:

W zadaniach tekstowych zwykle bezpieczniej jest wypełnić diagram Venna od środka na zewnątrz: najpierw elementy należące do wszystkich trzech zbiorów, potem każda para pomniejszona o środek, potem każdy pojedynczy zbiór pomniejszony o to, co już umieszczono.

Dwa inne zliczenia pojawiają się często: zbiór o n elementach ma 2ⁿ podzbiorów (jego zbiór potęgowy 𝒫(A)), a |A × B| = |A|·|B| par uporządkowanych.

3Przykład krok po kroku

Przejdź przez każdy krok. Spróbuj przewidzieć następny, zanim go odsłonisz.

4Relacje

Relacja R na zbiorze X to zbiór par uporządkowanych (x, y), gdzie x i y należą do X. Narysowana jako graf skierowany, każda para to strzałka, a (x, x) to pętla.

• Zwrotna: (x, x) ∈ R dla każdego x: pętla w każdym wierzchołku.
• Symetryczna: (x, y) ∈ R zawsze występuje razem z (y, x) ∈ R.
• Antysymetryczna: (x, y) i (y, x) należą do R jednocześnie tylko wtedy, gdy x = y.
• Przechodnia: (x, y) i (y, z) w R wymuszają (x, z) ∈ R.

Relacja zwrotna, symetryczna i przechodnia to relacja równoważności. Dzieli X na rozłączne klasy, takie jak reszty 0, 1 i 2 dla „x ≡ y (mod 3)”. Klasa o s elementach wnosi s² par uporządkowanych.

Aby obalić własność, wystarczy jeden kontrprzykład; aby ją udowodnić, sprawdź każdą parę.

5Funkcje

Funkcja f: A → B przypisuje każdemu elementowi A dokładnie jeden obraz w B.

• Różnowartościowa (injekcja): różne elementy mają różne obrazy; żaden element B nie dostaje dwóch strzałek.
• Na (surjekcja): każdy element B dostaje co najmniej jedną strzałkę.
• Bijekcja: obie własności naraz. Tylko wtedy f ma funkcję odwrotną f⁻¹.

Funkcja na rysunku jest różnowartościowa, ale nie „na”: d nie dostaje żadnej strzałki. Injekcja wymaga |A| ≤ |B|, a surjekcja |A| ≥ |B|.

Dla |A| = m i |B| = n jest nᵐ funkcji, a różnowartościowych n!/(n − m)!. Złożenie (g ∘ f)(x) = g(f(x)) stosuje najpierw f.

6Typowe błędy

• Dodanie |A| + |B| bez odjęcia części wspólnej.
• Zapomnienie o dodaniu środka w zasadzie włączeń i wyłączeń dla trzech zbiorów.
• Zapisanie mⁿ zamiast nᵐ dla liczby funkcji z m elementów w n elementów.
• Przekonanie, że relacja nie może być jednocześnie symetryczna i antysymetryczna: relacja {(1, 1)} jest obiema.
• Złożenie g ∘ f w złej kolejności: najpierw działa f.

7Jak wyglądają zadania egzaminacyjne

• Łatwe: diagramy Venna i podzbiory. Zliczasz wyrażenie na zbiorach z diagramu Venna, klikasz obszar wyrażenia albo znajdujesz liczność zbioru potęgowego, iloczynu kartezjańskiego lub rodziny podzbiorów.
• Średnie: włączenia i wyłączenia oraz relacje. Rozwiązujesz zadania na zliczanie dwóch i trzech zbiorów, zliczasz wyrażenia z sum obszarów, rozstrzygasz, jaką własność ma relacja, albo zliczasz pary potrzebne do domknięcia.
• Trudne: funkcje i zliczanie. Klasyfikujesz funkcję jako injekcję, surjekcję lub bijekcję, zliczasz funkcje, injekcje i surjekcje, obliczasz złożenia i funkcje odwrotne oraz zliczasz pary w relacjach równoważności.