surjekcja

Surjekcja, w matematyce, to funkcja f: A → B, dla której każdy element zbioru B ma przynajmniej jeden odpowiednik w A. Formalnie: f jest surjekcją wtedy i tylko wtedy, gdy dla każdego b ∈ B istnieje a ∈ A z f(a) = b. Innymi słowy, obraz f jest całym zbiorem B, czyli f(A) = B. Termin ten często tłumaczony jest jako „onto”.

Własność i znaczenie: surjekcja oznacza, że każdy element codomainu ma przynajmniej jeden element źródłowy, który go odwzorowuje. W kontekście skończonych zbiorów, jeśli A i B są finite i f: A → B jest surjekcją, to |A| ≥ |B|; jeśli dodatkowo |A| = |B|, surjekcja jest także bijekcją. Zależność ta daje praktyczne kryteria oceny kartografii między zbiorami.

Własności operacyjne: składanie surjekcji jest surjekcją. Jeśli f: A → B i g: B → C są surjekcjami, to g ∘ f: A → C jest surjekcją. Ponadto, jeśli f jest surjekcją, to funkcja postkompozycji g ∘ f jest surjekcją wtedy i tylko wtedy, gdy g jest surjekcją. Pod pewnymi warunkami (np. przy założeniu aksjomatu wyboru) każda surjekcja ma prawy odwrotność s: B → A z f ∘ s = id_B.

Przykłady: f: {1, 2, 3} → {a, b} z definicją f(1) = a, f(2) = a, f(3) = b jest surjekcją. Przykład nie-surjekcyjny: f: {1, 2} → {a, b, c} z f(1) = a, f(2) = b nie pokrywa elementu c.

Zobacz także: iniekcja, bijekcja, funkcja odwrotna.