Bijection, injection and surjection

	surjective	non-surjective
injective	bijective	injective-only
non- injective	surjective-only	general

수학(mathematics)에서, 단사(injections), 전사(surjections) 및 전단사(bijections)는 인수(arguments) (도메인(domain)으로부터 입력 표현(expressions)) 및 이미지(images) (코도메인(codomain)으로부터 출력 표현)가 서로 관련되거나 매핑되는 방식에 의해 구별되는 함수(functions)의 클래스입니다.

함수는 도메인의 원소로부터 그의 코도메인의 원소에 매핑(mapping)합니다. 함수 $f\colon X\to Y$ 가 주어지면:

함수는 만약 코도메인의 각 원소가 도메인의 많아야(at most) 하나의 원소에 의해 매핑되면, 또는 동등하게, 만약 도메인의 구별되는 원소가 코도메인에서 구별되는 원소로 매핑되면, 단사(injective), 또는 일-대-일(one-to-one)입니다. 단사적 함수(injective function)는 단사(injection)라고 불립니다.^[1]^[2] 표기법에서:

\forall x,x'\in X,f(x)=f(x')\Rightarrow x=x',

또는, 동등하게 (논리적 대우(logical transposition)를 사용하여),

\forall x,x'\in X,x\neq x'\Rightarrow f(x)\neq f(x').

^[3]^[4]^[5]

함수는 만약 코도메인의 각 원소가 도메인의 적어도(at least) 하나의 원소에 의해 매핑되면, 전사(surjective), 또는 위로의(onto)입니다. 즉, 함수의 이미지와 코도메인이 서로 같습니다. 전사적 함수(surjective function)는 전사(surjection)입니다.^[1]^[2] 표기법에서:

\forall y\in Y,\exists x\in X{\text{ such that }}y=f(x).

^[3]^[4]^[5]

함수는 만약 코도메인의 각 원소가 도메인의 정확히(exactly) 하나의 원소에 의해 매핑되면, 전단사(bijective) (일-대-일 및 위로의(one-to-one and onto) 또는 일-대-일 대응(one-to-one correspondence))입니다. 즉, 이 함수는 전사와 단사 둘다입니다. 전단사적 함수(bijective function)는 전단사(bijection)라고 불립니다.^[1]^[2]^[3]^[4]^[5] 즉, 단사와 전사의 정의를 결합하면,

\forall y\in Y,\exists !x\in X{\text{ such that }}y=f(x),

여기서

\exists !x

는 "정확히 하나의

x

가 존재합니다"를 의미합니다.

임의의 경우에서 (임의의 함수에 대해), 다음이 유지됩니다:

\forall x\in X,\exists !y\in Y{\text{ such that }}y=f(x).

단사 함수는 (코도메인의 모든 원소가 인수와 연관되지 않을 수도 있는) 전사일 필요는 없고, 전사 함수는 단사일 필요는 없습니다 (일부 이미지는 둘 이상의 인수와 연관될 수 있습니다). 단사 및 전사 특징의 네 가지 가능한 조합이 인접한 다이어그램에 묘사되어 있습니다.

Injection

함수는 만약 코도메인의 각 가능한 원소가 많아야 하나의 인수에 의해 매핑되면 단사 (일-대-일)입니다. 동등하게, 함수는 만약 그것이 구별되는 인수를 구별되는 이미지에 매핑하면 단사됩니다. 단사적 함수는 단사입니다.^[1]^[2] 형식적인 정의는 다음입니다.

함수

f\colon X\to Y

는, 만약 모든

x,x'\in X

에 대해,

f(x)=f(x')\Rightarrow x=x'

이면, 단사입니다.^[3]^[4]^[5]

다음은 단사와 관련된 일부 사실입니다:

함수 f : X → Y가 단사인 것과 X가 빈 것 또는 f가 왼쪽-역가능(invertible)인 것은 필요충분 조건입니다; 즉, X 위의 g o f = 항등 함수를 만족하는 함수 g : f(X) → X가 있습니다. 여기서 f(X)는 f의 이미지입니다.
모든 각 함수가 그것의 코도메인(codomain)이 그것의 이미지(image)로 제한될 때 전사이며, 모든 각 단사는 그것의 이미지 위로의 전단사를 유도합니다.^[1] 보다 정확하게, 모든 각 단사 f : X → Y는 다음처럼 포함에 따라오는 전단사로 인수화될 수 있습니다. f_R : X → f(X)를 코도메인을 그것의 이미지로 제한을 갖는 f로 놓고, i : f(X) → Y를 f(X)에서 Y 안으로의 포함 맵으로 놓습니다. 그런-다음 f = i o f_R입니다. 이중 인수-분해는 아래의 전사에 대해 제공됩니다.
두 단사의 합성은 다시 단사이지만, 만약 g o f가 단사이면, 그것은 f가 단사임을 오직 결론내릴 수 있습니다 (그림 참조하십시오).
모든 각 삽입(embedding)은 단사입니다.

Surjection

함수는 만약 각 가능한 이미지가 적어도 하나의 인수에 의해 매핑되면 전사 (위로의)입니다. 다시 말해, 코도메인에서 각 원소는 비-빈 이전-이미지(preimage)를 가집니다. 동등하게, 함수는 만약 그것의 이미지가 그것의 코도메인과 같으면 단사적입니다. 전사적 함수는 전사입니다.^[1]^[2] 형식적인 정의는 다음입니다.

함수

f\colon X\to Y

는, 만약 모든

y\in Y

에 대해,

f(x)=y

를 만족하는

x\in X

가 있으면, 전사입니다.^[3]^[4]^[5]

다음은 전사와 관련된 일부 사실입니다:

함수 f : X → Y가 전사인 것과 그것인 오른쪽-역가능인 것은 필요충분 조건입니다. 즉, Y 위의 f o g = 항등 함수를 만족하는 함수 g: Y → X가 있는 것은 필요충분 조건입니다. (이 명제는 선택의 공리(axiom of choice)와 동등합니다.)

주어진 모든 고정된 이미지에 대한 모든 인수 매핑을 축소함으로써, 모든 각 전사는 그것의 도메인의 몫에 정의된 전단사를 유도합니다. 보다 정확하게, 모든 각 전사 f : X → Y는 다음처럼 전단사를 따라오는 비-전단사로 인수화될 수 있습니다. X/~를 다음 동치 관계 아래에서 X의 동치 클래스로 놓습니다: x ~ y인 것과 f(x) = f(y)인 것은 필요충분 조건입니다. 동등하게, X/~는 f 아래에서 모든 이전-이미지의 집합(set)입니다. P(~) : X → X/~를 X에서 각 x를 그것의 동치 클래스 [x]_~로 보내는 투영 맵으로 놓고, f_P : X/~ → Y를 f_P([x]_~) = f(x)에 의해 주어진 잘-정의된 함수로 놓습니다. 그런-다음 f = f_P o P(~)입니다. 이중 인수-분해는 위의 단사에 대해 제공됩니다.

두 전사의 합성은 다시 전사이지만, 만약 g o f가 전사이면, 그것이 g가 단사임을 오직 결론내릴 수 있습니다 (그림 참조하십시오).

Bijection

함수는 만약 그것이 단사와 전사이면 전단사입니다. 전단사적 함수는 전단사 (일-대-일 대응)입니다.^[1] 함수가 전단사인 것과 모든 각 가능한 이미지가 정확히 하나의 인수에 의해 매핑되는 것은 필요충분(iff) 조건입니다.^[2] 이 동치 조건은 형식적으로 다음처럼 표현됩니다.

함수

f\colon X\to Y

는, 만약 모든

y\in Y

에 대해,

f(x)=y

를 만족하는 유일한

x\in X

가 있으면, 전단사입니다.^[3]^[4]^[5]

다음은 전단사와 관련된 일부 사실입니다:

함수 f : X → Y가 전단사인 것과 그것이 역-가능인 것, 즉, X 위의 g o f = 항등 함수 및 Y 위의 f o g = 항등 함수를 만족하는 함수 g: Y → X가 있는 것은 필요충분 조건입니다. 이 함수는 각 이미지를 그것의 고유한 이전-이미지로 매핑합니다.

두 전단사의 합성은 다시 전단사이지만, 만약 g o f가 전단사이면, 그것은 f는 단시이고 g는 전사라는 오직 결론내릴 수 있습니다 (단사와 전사에 관련하는 위의 설명과 오른쪽의 그림을 참조하십시오).

집합에서 자체로의 전단사는 합성 아래에서 그룹(group)을 형성하며, 대칭 그룹(symmetric group)이라고 불립니다.

Cardinality

우리가 두 집합이 "같은 숫자의 요소를 가짐"에 대해 무엇을 의미하는지를 정의하기를 원한다고 가정합니다. 이것을 하기 위한 한 방법은, 만약 한 집합의 모든 원소가 나머지 한 집합의 원소와 쌍을 이룰 수 있으며, 그러한 방법에서 각 원소는 정확히 한 원소와 짝을 짓게 되면 오직, 두 집합이 "같은 숫자의 원소를 가짐"이라고 말하는 것입니다. 그에 따라서, 우리는 만약 두 집합 사이에 전단사가 있으면, 두 집합이 "같은 숫자의 원소를 가짐"을 정의할 수 있습니다. 이 경우에서, 두 집합은 같은 카디널리티(cardinality)를 가지는 것으로 말합니다.

마찬가지로, 우리는 만약 $X$ 에서 $Y$ 로의 단사이면, 집합 $X$ 가 집합 $Y$ "보다 작거나 같은 숫자의 원소를 가집니다"라고 말할 수 있습니다; 우리는 역시 만약 $X$ 에서 $Y$ 로의 단사이지만, $X$ 와 $Y$ 사이의 전단사가 아니면, 집합 $X$ 는 집합 $Y$ 에서 "원소의 숫자보다 적습니다"라고 말할 수 있습니다.

Examples

각 함수의 도메인과 코도메인을 지정하는 것이 중요한데, 왜냐하면 이것을 바꿈으로써, 같은 것으로 보이는 함수가 다른 속성을 가질 수 있기 때문입니다.

단사 및 전사 (전단사): 모든 각 비-빈 집합 X에 대해 항등 함수 id_X, 및 따라서 구체적으로 $\mathbf {R} \to \mathbf {R} :x\mapsto x$ .; $\mathbf {R} ^{+}\to \mathbf {R} ^{+}:x\mapsto x^{2}$ , 및 따라서 역시 그것의 역 $\mathbf {R} ^{+}\to \mathbf {R} ^{+}:x\mapsto {\sqrt {x}}.$; 지수 함수(exponential function) $\exp \colon \mathbf {R} \to \mathbf {R} ^{+}:x\mapsto \mathrm {e} ^{x}$ (즉, 그것의 코도메인을 그것의 이미지로 제한된 것으로 갖는 지수 함수), 및 따라서 역시 그것의 역 자연 로그(natural logarithm) $\ln \colon \mathbf {R} ^{+}\to \mathbf {R} :x\mapsto \ln {x}.$

단사 및 비-전사: 지수 함수 $\exp \colon \mathbf {R} \to \mathbf {R} :x\mapsto \mathrm {e} ^{x}.$

비-단사 및 전사: $\mathbf {R} \to \mathbf {R} :x\mapsto (x-1)x(x+1)=x^{3}-x.$; $\mathbf {R} \to [-1,1]:x\mapsto \sin(x).$

비-단사 및 비-전사: $\mathbf {R} \to \mathbf {R} :x\mapsto \sin(x).$

Properties

모든 각 함수 $f$ , 도메인의 부분-집합 $X$ 및 코도메인의 부분-집합 $Y$ 에 대해, $X \subset f -1 (f (X))$ 및 $f (f -1 (Y)) \subset Y$ 입니다. 만약 $f$ 가 단사이면, $X = f -1 (f (X))$ 이고, 만약 $f$ 가 전사이면, $f (f -1 (Y)) = Y$ 입니다.
모든 각 함수 $h : X \to Y$ 에 대해, 우리는 전사 $H : X \to h (X) : x \to h (x)$ 및 단사 $I : h (X) \to Y : y \to y$ 를 정의할 수 있습니다. 그것은 $h=I\circ H$ 임을 따릅니다. 이 분해는 동형사상(isomorphism)까지(up to) 고유합니다.

Category theory

집합(sets)의 카테고리(category)에서, 단사, 전사, 및 전단사는 각각 단사-사상(monomorphism), 전사-사상(epimorphism) 및 동형(isomorphism)에 정확하게 대응합니다.^[6]

History

단사-전사-전단사 용어 (명사 및 형용사 둘 다)는 널리 채택되기 전에 프랑스 부르바키 그룹(Bourbaki group)에 의해 원래 만들어졌습니다.^[7]

References

^ ^a ^b ^c ^d ^e ^f ^g "The Definitive Glossary of Higher Mathematical Jargon". Math Vault. 2019-08-01. Retrieved 2019-12-07.{{cite web}}: CS1 maint: url-status (link)
^ ^a ^b ^c ^d ^e ^f "Injective, Surjective and Bijective". www.mathsisfun.com. Retrieved 2019-12-07.
^ ^a ^b ^c ^d ^e ^f "Bijection, Injection, And Surjection | Brilliant Math & Science Wiki". brilliant.org. Retrieved 2019-12-07.
^ ^a ^b ^c ^d ^e ^f Farlow, S. J. "Injections, Surjections, and Bijections" (PDF). math.umaine.edu. Retrieved 2019-12-06.{{cite web}}: CS1 maint: url-status (link)
^ ^a ^b ^c ^d ^e ^f "6.3: Injections, Surjections, and Bijections". Mathematics LibreTexts. 2017-09-20. Retrieved 2019-12-07.
^ "Section 7.3 (00V5): Injective and surjective maps of presheaves—The Stacks project". stacks.math.columbia.edu. Retrieved 2019-12-07.
^ Mashaal, Maurice (2006). Bourbaki. American Mathematical Soc. p. 106. ISBN 978-0-8218-3967-6.

External links

Earliest Uses of Some of the Words of Mathematics: entry on Injection, Surjection and Bijection has the history of Injection and related terms.

[:0-1] ^ ^a ^b ^c ^d ^e ^f ^g "The Definitive Glossary of Higher Mathematical Jargon". Math Vault. 2019-08-01. Retrieved 2019-12-07.{{cite web}}: CS1 maint: url-status (link)

[:1-2] ^ ^a ^b ^c ^d ^e ^f "Injective, Surjective and Bijective". www.mathsisfun.com. Retrieved 2019-12-07.

[:2-3] ^ ^a ^b ^c ^d ^e ^f "Bijection, Injection, And Surjection | Brilliant Math & Science Wiki". brilliant.org. Retrieved 2019-12-07.

[:3-4] ^ ^a ^b ^c ^d ^e ^f Farlow, S. J. "Injections, Surjections, and Bijections" (PDF). math.umaine.edu. Retrieved 2019-12-06.{{cite web}}: CS1 maint: url-status (link)

[:4-5] ^ ^a ^b ^c ^d ^e ^f "6.3: Injections, Surjections, and Bijections". Mathematics LibreTexts. 2017-09-20. Retrieved 2019-12-07.

[6] "Section 7.3 (00V5): Injective and surjective maps of presheaves—The Stacks project". stacks.math.columbia.edu. Retrieved 2019-12-07.

[7] Mashaal, Maurice (2006). Bourbaki. American Mathematical Soc. p. 106. ISBN 978-0-8218-3967-6.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Injection

Surjection

Bijection

Cardinality

Examples

Properties

Category theory

History

See also

References

External links