전사 함수

3. 성질

• 임의의 함수 $f\backslash colon\; X\backslash to\; Y$, $g\backslash colon\; Y\backslash to\; Z$가 주어졌을 때:
• * 만약 $f$와 $g$가 둘 다 전사 함수라면, $g\backslash circ\; f$ 역시 전사 함수이다.
• * 만약 $g\backslash circ\; f$가 전사 함수라면, $g$ 역시 전사 함수이다. 하지만 $f$가 전사 함수일 필요는 없다.
• 두 집합 $X$, $Y$에 대하여, 다음 두 조건은 서로 동치이다.
• * 전사 함수 $f\backslash colon\; X\backslash to\; Y$가 존재하거나, 아니면 $Y=\backslash varnothing$이다.
• * $|X|\backslash ge|Y|$이다. 여기서 $|\backslash cdot|$는 집합의 크기이다.
• 공역의 크기가 0 또는 1인 함수는 항상 전사 함수이다. (공역이 공집합이라면, 정의역 또한 공집합이어야만 함수가 존재할 수 있다.)
• 함수는 전사 함수이면서 동시에 단사 함수일 경우에만 전단사 함수이다.
• 함수를 그 그래프와 동일시한다면, 전사성은 함수 자체의 속성이 아니라 사상의 속성이다.^[7] 즉, 함수와 공역의 속성이다. 단사성과 달리, 전사성은 함수의 그래프만으로는 알 수 없다.
• 함수 g : Y → X^영어는 f(g(y)) = y^영어가 ''Y''의 모든 ''y''에 대해 성립할 경우 함수 f : X → Y^영어의 오른쪽 역함수라고 한다. 즉, ''g''와 ''f''의 합성 f o g^영어가 ''g''의 정의역 ''Y''에서 항등 함수일 경우, ''g''는 ''f''의 오른쪽 역함수이다. 함수 ''g''는 ''f''의 완전한 역함수일 필요는 없는데, 다른 순서의 합성 g o f^영어가 ''f''의 정의역 ''X''에서 항등 함수가 아닐 수도 있기 때문이다. 즉, ''f''는 ''g''를 되돌리거나 "반전"시킬 수 있지만, 반드시 ''g''에 의해 반전될 수 있는 것은 아니다.
• 오른쪽 역함수를 갖는 모든 함수는 필연적으로 전사 함수이다. 모든 전사 함수가 오른쪽 역함수를 갖는다는 명제는 선택 공리와 동치이다.
• 만약 f : X → Y^영어가 전사 함수이고 ''B''가 ''Y''의 부분 집합이면, f(f ⁻¹(B)) = B^영어이다. 따라서 ''B''는 역상 f ⁻¹(B)^영어로부터 복구될 수 있다.
• 함수 f : X → Y^영어가 전사 함수일 필요충분 조건은 함수가 오른쪽 소거 가능일 때이다.^[8] 모든 함수 g,h : Y → Z^영어에 대해, g o f = h o f^영어가 성립하면, g = h^영어이다. 이 성질은 함수와 그들의 함수 합성에 관해 공식화되며, 범주의 사상과 그들의 합성이라는 더 일반적인 개념으로 일반화될 수 있다. 오른쪽 소거 가능한 사상은 에피모피즘이라고 불린다. 구체적으로, 전사 함수는 집합 범주에서 정확히 에피모피즘이다. 접두사 ἐπί^el는 그리스어 전치사 ἐπί에서 파생되었으며, 이는 '위에', '넘어서', '위에'를 의미한다.
• 오른쪽 역을 가진 모든 사상은 에피모피즘이지만, 일반적으로 그 역은 성립하지 않는다. 사상 ''f''의 오른쪽 역 ''g''는 ''f''의 단면이라고 불린다. 오른쪽 역을 가진 사상은 분할 에피모피즘이라고 불린다.
• ''X''를 정의역, ''Y''를 공역으로 갖는 모든 함수는 전체적이고 단일 값 이진 관계인 함수 그래프로 식별하여 ''X''와 ''Y'' 사이의 이진 관계로 볼 수 있다. 정의역이 ''X''이고 공역이 ''Y''인 전사 함수는 오른쪽에서 고유하며, 전체적이고 전사적인 ''X''와 ''Y'' 사이의 이진 관계이다.
• 전사 함수의 합성은 항상 전사 함수이다. 만약 ''f''와 ''g''가 모두 전사 함수이고, ''g''의 공역이 ''f''의 정의역과 같다면, f o g^영어도 전사 함수이다. 반대로, f o g^영어가 전사 함수이면 ''f''는 전사 함수이다(그러나 먼저 적용되는 함수인 ''g''는 그럴 필요가 없다). 이러한 속성은 집합 범주의 전사 함수에서 모든 에피모피즘에 일반화된다.
• 모든 함수는 전사 함수와 단사 함수로 분해될 수 있다. 모든 함수 h : X → Z^영어에 대해, h = g o f^영어를 만족하는 전사 함수 f : X → Y^영어와 단사 함수 g : Y → Z^영어가 존재한다. 이를 보려면, ''Y''를 h(X)^영어에 속하는 ''z''에 대한 역상 h⁻¹(z)^영어의 집합으로 정의한다. 이 역상들은 상호 배타적이고 ''X''를 분할한다. 그러면 ''f''는 각 ''x''를 그것을 포함하는 ''Y''의 원소로 보내고, ''g''는 각 ''Y''의 원소를 ''h''가 해당 점들을 보내는 ''Z''의 점으로 보낸다. 그러면 ''f''는 사영이므로 전사 함수이고, ''g''는 정의에 의해 단사 함수이다.
• 사상이 전단사가 되는 것은, 그것이 단사이면서 전사일 때와 동치이다.
• 함수를 그 그래프와 동일시하여 생각할 때, 단사성과는 달리, 전사성은 함수의 그래프만으로는 파악할 수 없다. 전사성은 함수 자체의 성질이라기보다는 함수와 공역과의 관계성으로 보아야 한다.
• 사상 g': Y → X^영어가 사상 f': X → Y^영어의 오른쪽 역사상이라는 것은, 1=f'(g'(y)) = y^영어 (즉, g'^영어의 효과가 f'^영어에 의해 상쇄됨)가 Y^영어의 각 원소 y^영어에 대해 성립할 때를 말한다. 다시 말해, g'^영어와 f'^영어의 이러한 순서로의 합성 f' ∘ g'^영어가 g'^영어의 정의역 Y^영어상의 항등사상 id_Y^영어가 될 때, g'^영어가 f'^영어의 오른쪽 역이라고 한다. 역순서의 g' ∘ f'^영어가 f'^영어의 정의역 X^영어상의 항등사상이 아닐 수도 있기 때문에, 사상 g'^영어는 반드시 f'^영어의 (완전) 역사상인 것은 아니다. 즉, f'^영어는 g'^영어를 상쇄시키지만, 그 반대는 반드시 성립하지 않는다.
• 오른쪽 역을 갖는 임의의 사상은 전사이지만, "임의의 전사가 오른쪽 역을 갖는다"는 명제는 선택 공리와 동치이다.
• f': X → Y^영어가 전사이고 B^영어가 Y^영어의 부분 집합일 때, 1=f'(f' ⁻¹(B)) = B^영어가 성립한다. 즉, B^영어는 그 원상 f' ⁻¹(B)^영어으로부터 복구된다.
• 사상 f': X → Y^영어가 전사 사상이 될 필요충분 조건은, 그것이 우측 소거적이라는 것,^[9] 즉 "주어진 사상 g₁, g₂: Y → Z^영어가 1=g₁ ∘ f' = g₂ ∘ f'^영어를 만족하는 한 항상 1=g₁ = g₂^영어가 성립한다는 것"이다. 이 성질은 사상과 그 합성에 의해 정식화되어 있기 때문에, 보다 일반적으로 범주에서의 사상 (morphism)과 그 합성의 성질로 일반화할 수 있다. 즉, 우측 소거적인 사상은 에피 사상 또는 전사 사상(범주론적 전사 사상)이다. 사상이 (집합론적) 전사 함수 (surjection)이면, 그것은 정확히 집합의 범주에서의 전사 사상 (epimorphism)이 된다. 접두사 ἐπί^el는 그리스어로 '위에'를 의미하는 단어이다.
• 오른쪽 역 사상을 갖는 임의의 사상은 전사 사상이지만, 그 역은 일반적으로 성립하지 않는다. 사상 f'^영어의 오른쪽 역 g'^영어는 f'^영어에 대한 절단 (범주론)^영어이라고 불리며, 오른쪽 역을 갖는 사상을 '''분할 전사 사상''' (split epimorphism)이라고 한다.
• 정의역 X^영어 및 공역 Y^영어를 갖는 임의의 사상은 (그 그래프와 동일시함으로써) X^영어와 Y^영어 사이의 전체이며 단일 값인 이항 관계로 간주할 수 있다. 따라서 정의역 X^영어, 공역 Y^영어를 갖는 전사 함수는 X^영어와 Y^영어 사이의 전체, 단일 값 및 전사인 이항 관계라고 할 수 있다.
• 전사끼리의 합성은 항상 전사이다. 즉, f'^영어 및 g'^영어가 모두 전사이고, g'^영어의 공역이 f'^영어의 정의역과 같을 때, 합성 사상 f' ∘ g'^영어는 전사가 된다. 반대로, 합성 f' ∘ g'^영어가 전사이면 f'^영어는 전사이다(하지만 먼저 적용하는 g'^영어는 반드시 전사일 필요는 없다). 이 성질은 집합의 범주에서의 전사에서 임의의 범주에서의 임의의 전사로 일반화된다.
• 임의의 사상은, 전사와 단사의 합성 형태로 분해할 수 있다. 즉, h': X → Z^영어를 임의의 사상으로 하면, 전사 f': X → Y^영어와 단사 g': Y → Z^영어로 1=h' = g' ∘ f'^영어를 만족하는 것이 존재한다. 이것을 보려면, 집합 Y^영어는 X^영어의 부분집합족 $Y\; :=\; \backslash \{h^\{-1\}(z)=\backslash \{x\backslash in\; X\backslash mid\; h(x)=z\backslash \}\backslash mid\; z\backslash in\; h(X)\backslash \}$ 로 정의하면 된다. 여기에 나타난 원상은 서로 교차하지 않고, X^영어의 분할을 제공한다. 이때, f'^영어로 각 원소 x ∈ X^영어를 x^영어를 포함하는 Y^영어의 원소로 사상하는 사상 $f\backslash colon\; x\; \backslash mapsto\; \backslash \{x\text{'}\backslash in\; X\backslash mid\; h(x\text{'})=h(x)\backslash \}$을 취하고, g'^영어로 Y^영어의 각 원소가 포함하는 X^영어의 원소가 h'^영어에 의해 사상되는 Z^영어의 원소로 사상하는 사상 $g\backslash colon\; h^\{-1\}(z)\; \backslash mapsto\; z$로 하면, f'^영어는 사영이므로 전사이고, g'^영어는 구성 방식에 따라 단사가 되며, 1=h' = g' ∘ f'^영어가 성립한다.
• 임의의 사상은 그 공역을 치역으로 제한함으로써 전사를 유도하고, 임의의 전사는 같은 결정된 값으로 사상되는 정의역의 원소를 동일시하여 소멸시키는 몫집합 위의 전단사를 유도한다. 정확하게 말하면, 임의의 전사 f': A → B^영어는 아래에 설명하는 것처럼 전단사와 사영의 합성으로 분해된다. A/∼^영어를 1=x ∼ y ⇔ f'(x) = f'(y)^영어로 정의되는 동치 관계에 의한 A^영어의 동치류 전체의 집합으로 한다. A/∼^영어를 ''f''에 의한 원상 전체의 집합이라고 해도 같다. 사상 P_~: A ↠ A/∼^영어를 A^영어의 각 원소 x^영어를 그 동치류 [x]_~^영어로 사상하는 사영으로 하고, f'_P: A/∼ → B^영어를 $f\_P([x]\_\{\backslash sim\})\; :=\; f(x)$로 주어지는 잘 정의된 사상으로 하면 이것은 전단사이고, 1=f' = f'_P ∘ P_~^영어가 성립한다.

4. 예

• 임의의 집합 ''X''에 대해, ''X'' 상의 항등 함수 id_''X''는 전사 함수이다.
• ''f'' : '''Z''' → {0, 1}로 정의된 함수 ''f''(''n'') = ''n'' mod 2 (즉, 짝수는 0에, 홀수는 1에 매핑)는 전사 함수이다.
• ''f'' : '''R''' → '''R'''로 정의된 함수 ''f''(''x'') = 2''x'' + 1은 전사 함수(심지어 전단사)이다. 모든 실수 ''y''에 대해, ''f''(''x'') = ''y''가 되는 ''x''가 있기 때문이다. 이러한 적절한 ''x''는 (''y'' − 1)/2이다.
• ''f'' : '''R''' → '''R'''로 정의된 함수 ''f''(''x'') = ''x''³ − 3''x''는 전사 함수이다. 임의의 실수 ''y''의 역상은 삼차 다항식 방정식 ''x''³ − 3''x'' − ''y'' = 0의 해 집합이고, 실수 계수를 갖는 모든 삼차 다항식은 적어도 하나의 실근을 가지기 때문이다. 그러나 이 함수는 단사 함수가 아니므로(따라서 전단사 함수도 아님), 예를 들어 ''y'' = 2의 역상은 {''x'' = −1, ''x'' = 2}이다.
• ''g'' : '''R''' → '''R'''로 정의된 함수 ''g''(''x'') = ''x''²는 전사 함수가 '''아니다'''. ''x''² = −1인 실수 ''x''가 없기 때문이다. 그러나 ''g'' : '''R''' → '''R'''_≥0로 정의된 함수 ''g''(''x'') = ''x''² (제한된 공역을 가짐)는 전사 함수이다.
• 자연 로그 함수 ln : (0, +∞) → '''R'''는 전사 함수이고 심지어 전단사 함수이다(양의 실수의 집합에서 모든 실수의 집합으로의 매핑). 그 역인, 지수 함수는 실수 집합을 정의역과 공역으로 정의하면 전사 함수가 아니다(치역이 양의 실수의 집합이기 때문).
• 행렬 지수는 일반적으로 모든 ''n''×''n'' 행렬의 공간에서 일반 선형군 (degree ''n'')으로의 매핑으로 정의된다(즉, 모든 ''n''×''n'' 가역 행렬의 군). 이 정의 하에서, 행렬 지수는 복소수 행렬에 대해 전사 함수이다.
• 사영은 데카르트 곱에서 그 인자 중 하나로의 사영은 다른 인자가 비어 있지 않는 한 전사 함수이다.
• 3D 비디오 게임에서 벡터는 전사 함수를 통해 2D 평면 스크린에 투영된다.
• 실수 ''x''에 대해, 그 자승 ''x''²을 대응시키는 비음수 실숫값 사상 $f\; \backslash colon\; \backslash mathbb\{R\}\; \backslash ni\; x\; \backslash mapsto\; x^2\; \backslash in\; \backslash mathbb\{R\}\_+$은 전사이다. 실제로, ''x'' ≥ 0에 대해, 그 비음수 제곱근 √''x''를 취하면, ''f''(√''x'') = ''x''로 할 수 있다.
• 임의의 집합 ''X''에서, ''X'' 상의 항등 변환 $\backslash text\{id\}\_X\; \backslash colon\; X\; \backslash ni\; x\; \backslash mapsto\; x\; \backslash in\; X$는 전사이다.
• 데카르트 곱 ''A'' × ''B''의 각 성분으로의 사영 $p\_A\; \backslash colon\; A\; \backslash times\; B\; \backslash ni\; (a,b)\; \backslash mapsto\; a\; \backslash in\; A,\backslash \; p\_B\; \backslash colon\; A\; \backslash times\; B\; \backslash ni\; (a,b)\; \backslash mapsto\; b\; \backslash in\; B$는 전사이다.
• 실 2차 다항식 전체 $\backslash mathbb\{R\}\_2[x]:=\backslash \{ax^2+bx+c\backslash \; ;\backslash \; (a,b,c)\; \backslash in\; (\backslash mathbb\{R\}\; \backslash setminus\; \backslash \{0\backslash \})\; \backslash times\; \backslash mathbb\{R\}\; \backslash times\; \backslash mathbb\{R\}\backslash \}$에서 $\backslash mathbb\{R\}$로의 사상 ''D''를 $D(ax^2+bx+c):=b^2-4ac$로 정의하면, ''D''는 전사이다.
• 양의 정수 ''n''에 대해, $\backslash det\; \backslash colon\; M\_n(\backslash mathbb\{R\})\; \backslash ni\; A\; \backslash mapsto\; \backslash det\; A\; \backslash in\; \backslash mathbb\{R\}$는 전사이다. 여기서 $M\_n(\backslash mathbb\{R\})$는 실 ''n''차 정방 행렬 전체이며, $\backslash det\; A$는 행렬식을 나타낸다.
• 지수 함수 $\backslash exp\; \backslash colon\; \backslash mathbb\{R\}\; \backslash ni\; x\; \backslash mapsto\; e^x\; \backslash in\; (0,\backslash infty)$는 전사이다.
• 복소수에 대해 그 실수부, 허수부, 절댓값을 주는 사상 $\backslash Re\; \backslash colon\; \backslash Complex\; \backslash ni\; z\; \backslash mapsto\; (z+\backslash overline\{z\})/2\; \backslash in\; \backslash R,\backslash \; \backslash Im\; \backslash colon\; \backslash Complex\; \backslash ni\; z\; \backslash mapsto\; (z-\backslash overline\{z\})/2i\; \backslash in\; \backslash R,\backslash \; |\backslash cdot|\; \backslash colon\; \backslash Complex\; \backslash ni\; z\; \backslash mapsto\; \backslash sqrt\{\backslash Re(z)^2+\backslash Im(z)^2\}\; \backslash in\; \backslash R$는 모두 전사이다.

5. 역사

유럽 언어에서 쓰이는 용어 "서젝션"(surjection^영어), "쉬르젝시옹"(surjection^프랑스어) 등은 단사를 뜻하는 "인젝션"(injection^영어), "앵젝시옹"(injection^프랑스어)에서, 접두사 "인"(in^la, 안으로)을 "쉬르"(sur^프랑스어, 위로)로 치환한 것이다. 이는 수학 용어로는 니콜라 부르바키가 최초로 사용하였다.

6. 전사 함수와 관련된 집합의 기수

고정된 유한 집합 A와 B가 주어지면, 전사 함수 집합 A ↠ B를 구성할 수 있다. 이 집합의 기수는 십이중 항법의 열두 가지 측면 중 하나이며, |B|! { |A| // |B| } 로 주어지며, 여기서 { |A| // |B| }는 제2종 스털링 수를 나타낸다.^[10]

참조

_[1] 웹사이트 Injective, Surjective and Bijective https://www.mathsisf[...] 2019-12-07
_[2] 웹사이트 Bijection, Injection, And Surjection {{!}} Brilliant Math & Science Wiki https://brilliant.or[...] 2019-12-07
_[3] 간행물 Earliest Uses of Some of the Words of Mathematics http://jeff560.tripo[...] Tripod
_[4] 서적 Bourbaki https://books.google[...] American Mathematical Soc. 2006
_[5] 웹사이트 Arrows – Unicode https://www.unicode.[...] 2013-05-11
_[6] 웹사이트 Injections, Surjections, and Bijections http://www.math.umai[...] 2019-12-06
_[7] 서적 Mathematical Analysis Addison-Wesley
_[8] 서적 Topoi, the Categorial Analysis of Logic http://historical.li[...] Dover Publications 2009-11-25
_[9] 서적 Topoi, the Categorial Analysis of Logic http://historical.li[...] Dover Publications 2009-11-25
_[10] 서적 A First Course in Graph Theory and Combinatorics https://books.google[...] Hindustan Book Agency