Bijection

A bijective function, f: X → Y, where set X is {1, 2, 3, 4} and set Y is {A, B, C, D}. For example, f(1) = D.

수학(mathematics)에서, 전단사, 전단사 함수, 일-대-일 대응, 또는 역-가능 함수(bijection, bijective function, one-to-one correspondence, or invertible function)은 두 집합(sets)의 원소 사이의 함수(function)이며, 여기서 한 집합의 각 원소가 나머지 한 집합의 정확히 한 원소와 쌍을 이루고, 나머지 한 집합의 각 원소가 첫 번째 집합의 정확히 하나의 원소와 쌍을 이룹니다. 짝을 이루지 않은 원소는 없습니다. 수학적 용어에서, 전단사 함수 f: X → Y는 집합 X를 집합 Y에 일-대-일 (단사) 및 위로의 (전사) 맵핑입니다.^[1]^[2] 용어 일-대-일 대응은 일-대-일 함수 (일명 단사 함수(injective function))과 혼동해서는 안됩니다 (그림을 참조하십시오).

An injective non-surjective function (injection, not a bijection)
An injective surjective function (bijection)
A non-injective surjective function (surjection, not a bijection)
A non-injective non-surjective function (also not a bijection)

집합 X에서 집합 Y로의 전단사는 Y에서 X로의 역함수(inverse function)를 갖습니다. 만약 X와 Y가 유한 집합(finite set)이면, 전단사의 존재는 그들이 같은 숫자의 원소를 가짐을 의미합니다. 무한 집합(infinite set)에 대해, 그 그림이 보다 복잡하며, 세는-숫자(cardinal number)의 개념–다양한 크기의 무한 집합을 구별하는 방법으로 이어집니다.

집합에서 자체로의 전단사 함수는 순열(permutation)로 역시 불리고, 집합의 모든 순열의 집합은 대칭 그룹(symmetry group)을 형성합니다.

전단사 함수는 동형-사상(isomorphism), 위상-동형(homeomorphism), 미분-동형-사상(diffeomorphism), 순열 그룹(permutation group) 및 투영 맵(projective map)의 정의를 포함하여 많은 수학 영역에 필수적입니다.

Definition

전단사가 되도록 X와 Y 사이의 쌍을 이루는 것에 대해 (여기서 Y는 X와 다를 필요는 없습니다), 네 가지 속성이 유지되어야 합니다:

X의 각 원소가 Y의 적어도 하나의 원소와 쌍을 이루어야 합니다.
X의 어떤 원소도 Y의 하나보다 많은 원소와 쌍을 이룰 수 없습니다.
Y의 각 원소는 X의 적어도 하나의 원소와 쌍을 이루어야 합니다. 그리고
Y의 어떤 원소도 X의 하나보다 많은 원소와 쌍을 이룰 수 없습니다.

속성 (1)과 (2)를 만족한다는 것은 쌍을 이루는 것이 도메인(domain) X를 갖는 함수(function)임을 의미합니다. 속성 (1)과 (2)를 단일 문장으로 작성하는 것이 더 일반적입니다: X의 모든 각 원소는 Y의 정확히 하나의 원소와 짝을 이룹니다. 속성 (3)을 만족시키는 함수는 "Y 위로의(onto)"라고 말해지고, 전사(surjections) (또는 전사 함수)라고 불립니다. 속성 (4)을 만족시키는 함수는 "일-대-일 함수"라고 말해지고 단사(injections) (또는 단사 함수)라고 불립니다.^[3] 이 용어와 함께, 전단사는 전사와 단사 둘 다인 함수, 또는 다른 말을 사용하면, "일-대-일"과 "위로의" 둘 다인 함수입니다.^[1]^[4]

전단사는, f : X ⤖ Y에서 처럼, 꼬리를 가진 두-머리 오른쪽 화살표 (U+2916 ⤖ RIGHTWARDS TWO-HEADED ARROW WITH TAIL)에 의해 때때로 표시됩니다. 이 기호는 두-머리 오른쪽 화살표 (U+21A0 ↠ RIGHTWARDS TWO HEADED ARROW)의 조합이며, 때때로 전사를 나타내기 사용되고, 가시 꼬리를 가진 오른쪽 화살표 (U+21A3 ↣ RIGHTWARDS ARROW WITH TAIL)는 때때로 단사를 나타내기 위해 사용됩니다.

Examples

Batting line-up of a baseball or cricket team

야구(baseball) 또는 크리켓(cricket) 팀의 타자 라인업 (또는 모든 각 선수가 라인업에서 특정 지점을 보유한 임의의 스포츠 팀의 모든 선수의 임의의 목록)을 생각해 보십시오. 집합 X는 (야구에서 크기 9의) 팀의 선수가 될 것이고 집합 Y는 타격 순서 (1, 2, 3 등)의 위치가 될 것입니다. "쌍을 이루는 것"은 선수가 순서대로 어떤 위치에 있는 것에 의해 제공됩니다. 속성 (1)은 만족되는데 왜냐하면 각 선수가 목록에서 어딘가에 있기 때문입니다. 속성 (2)는 만족되는데 왜냐하면 둘 (또는 많은) 곳에서 선수의 타석이 순서에서 없기 때문입니다. 속성 (3)은 순서대로 각 위치에 대해, 해당 위치에 어떤 선수 타자가 있음을 말하고, 속성 (4)은 두 명 이상의 선수가 목록에서 같은 위치에서 타격하지 않음을 말합니다.

Seats and students of a classroom

교실에는 특정 좌석 숫자가 있습니다. 많은 학생들이 교실에 들어오고 강사가 자리에 앉도록 요청합니다. 방을 둘러본 후, 강사는 학생의 집합과 좌석 집합 사이에 전단사가 있음을 알리며, 각 학생은 앉아있는 좌석과 쌍을 이룹니다. 강사가 이 결론에 도달하기 위해 관찰된 사항이었습니다:

모든 각 학생은 한 좌석에 앉았습니다 (서 있는 학생은 없었습니다).
학생은 한 좌석보다 많은 곳에 앉을 수 없습니다.
모든 각 좌석은 그곳에 누군가 앉았었습니다 (빈 자리는 없었습니다). 그리고
좌석은 그곳에 앉은 한 명보다 많은 학생이 없습니다.

강사는 학생 수만큼 좌석이 있다고, 두 집합을 세는 것없이, 결론지을 수 있었습니다.

More mathematical examples and some non-examples

임의의 집합 X에 대해, 항등 함수(identity function) 1_X: X → X, 1_X(x) = x는 전단사입니다.
함수 f: R → R, f(x) = 2x + 1는 전단사인데, 왜냐하면 각 y에 대해 f(x) = y를 만족하는 고유한 x = (y − 1)/2이 있습니다. 보다 일반적으로, 실수에 걸쳐 임의의 선형 함수(linear function), f: R → R, f(x) = ax + b는 전단사입니다 (여기서 a는 비-영입니다). 각 실수 y는 실수 x = (y − b)/a로부터 획득됩니다 (또는 쌍을 이룹니다).
f(x) = arctan(x)에 의해 주어진, 함수 f: R → (−π/2, π/2)는 전단사인데, 왜냐하면 각 실수 x는 tan(y) = x (즉, y = arctan(x))가 되도록 구간 (−π/2, π/2)에서 정확히 하나의 각도 y와 쌍을 이룹니다. 만약 코도메인(codomain) (−π/2, π/2)는 π/2의 정수 배수를 포함하기 위해 더 크게 만들어지면, 이 함수는 더 이상 위로의 (전사)가 아닐 것인데, 왜냐하면 이 아크 탄젠트에 의한 π/2의 배수와 쌍을 이룰 수 있는 실수이기 때문입니다.
지수 함수(exponential function), g: R → R, g(x) = e^x는 전단사가 아닙니다: 예를 들어, g(x) = −1를 만족하는 R에서 x가 없으며, g가 위로의 (전사)가 아님을 보여줍니다. 어쨌든, 만약 코도메인이 양의 실수 $\scriptstyle \mathbb {R} ^{+}\;\equiv \;\left(0,\,+\infty \right)$ 로 제한되면, g는 전단사일 것입니다; 그것의 역은 자연 로그(natural logarithm) 함수 ln입니다 (아래를 참조하십시오).
함수 h: R → R⁺, h(x) = x²은 전단사가 아닙니다: 예를 들어, h(−1) = h(1) = 1이며, h는 일-대-일 (단사)가 아님을 보여줍니다. 어쨌든, 만약 도메인(domain)이 $\scriptstyle \mathbb {R} _{0}^{+}\;\equiv \;\left[0,\,+\infty \right)$ 로 제한되면, h는 전단사일 것입니다; 그것의 역은 양의 제곱근입니다.

Inverses

도메인 X를 갖는 f (함수 표기법(functional notation)에서 f: X → Y로 표시됨)는 역시 Y로 시작하고 X로 가는 전환 관계(converse relation) (화살표를 돌려서)를 정의합니다. 임의의 함수에 대해 "화살표를 돌리는" 과정은 일반적으로 함수를 산출하지는 않지만, 전단사의 속성 (3)과 (4)는 이 역 관계가 도메인 Y를 갖는 함수라고 말합니다. 게다가, 속성 (1)과 (2)는 이 역함수는 전사와 단사, 즉 역함수(inverse function)가 존재하고 역시 전단사임을 말합니다. 역 함수를 가지는 함수는 역-가능(invertible)이라고 말합니다. 함수가 역-가능인 것과 그것이 전단사인 것은 필요충분 조건입니다.

간결한 수학적 표기법으로 말하면, 함수 f: X → Y가 전단사인 것과 다음 조건을 만족시키는 것은 필요충분 조건입니다:

Y에서 모든 각 y에 대해, y = f(x)를 갖는 X에서 고유한 x가 있습니다.

야구 타격 라인-업 예제를 계속하여, 정의되고 있는 함수는 선수 중 하나의 이름을 입력하고 타격 순서에서 해당 선수의 위치를 출력하는 것으로 취합니다. 이 함수는 전단사이기 때문에, 타격 순서에서 위치를 입력으로 취하고 해당 위치에서 타격할 선수를 출력하는 역 함수를 가집니다.

Composition

두 전단사 f: X → Y 및 g: Y → Z의 합성(composition) $\scriptstyle g\,\circ \,f$ 은 전단사이며, $\scriptstyle g\,\circ \,f$ 에 의해 제공된 그것의 역은 $\scriptstyle (g\,\circ \,f)^{-1}\;=\;(f^{-1})\,\circ \,(g^{-1})$ 입니다.

반대로, 만약 두 함수의 합성 $\scriptstyle g\,\circ \,f$ 이 전단사이면, f가 단사(injective)이고 g가 전사(surjective)임을 오직 따릅니다.

Bijections and cardinality

만약 X와 Y가 유한 집합(finite set)이면, 두 집합 X와 Y 사이에 전단사가 존재하는 것과 X와 Y가 같은 숫자의 원소를 갖는 것은 필요충분(iff) 조건입니다. 실제로, 공리적 집합 이론(axiomatic set theory)에서, 이것은 "같은 숫자의 원소" (숫자의-상등성(equinumerosity))의 정의로 취해지고, 이 정의를 무한 집합(infinite set)으로 일반화하는 것은 세는-숫자(cardinal number), 다양한 크기의 무한 집합을 구별하는 방법의 개념으로 이어집니다.

Properties

함수 f: R → R가 전단사 인것과 그것의 그래프(graph)가 수평 및 수직 직선과 정확히 한번 만나는 것은 필요충분 조건입니다.
만약 X가 집합이면, X에서 자체로의 전단사 함수는, 함수의 합성 (∘)의 연산과 함께, 그룹(group), X의 대칭 그룹(symmetric group)을 형성하며, 이것은 S(X), S_X, 또는 X! (X 팩토리얼(factorial))에 의해 다양하게 표시됩니다.
전단사는 집합의 카디널리티(cardinalities)를 보존합니다: 카디널리티 |A|를 갖는 도메인의 부분-집합 A와 카디널리티 |B|를 갖는 코도메인의 부분-집합 B에 대해, 우리는 다음 상등을 가집니다:
|f(A)| = |A| 및 |f⁻¹(B)| = |B|입니다.
만약 X와 Y가 같은 카디널리티를 갖는 유한 집합(finite set)이고, f: X → Y이면, 다음은 동등합니다:
1. f는 전단사입니다.
2. f는 전사(surjection)입니다.
3. f는 단사(injection)입니다.
유한 집합 S에 대해, 원소의 가능한 전체 순서화(total ordering)의 집합과 S에서 S로의 전단사의 집합 사이의 전단사가 있습니다. 다시 말해서, S의 원소의 순열(permutation)의 숫자는 해당 집합의 전체 순서화–즉, n!과 같습니다.

Bijections and category theory

전단사는 집합(sets)과 집합 함수의 카테고리(category) 집합(Set)에서 정확하게 동형-사상(isomorphism)입니다. 어쨌든, 전단사가 보다 복잡한 카테고리에 대해 항상 동형-사상은 아닙니다. 예를 들어, 그룹(groups)의 카테고리 Grp에서, 사상은 준동형(homomorphism)이어야 하는데 왜냐하면 그들은 그룹 구조를 보존해야 하므로, 동형은 전단사 준동형인 그룹 동형입니다.

Generalization to partial functions

일-대-일 대응의 개념은 부분 함수(partial functions)로 일반화되며, 여기서 그들은, 비록 부분 전단사가 오직 단사인 것을 요구할지라도, 부분 전단사로 불립니다. 이 느슨함에 대해 이유는 (적절한) 부분 함수가 그것의 도메인의 일부에 대해 이미 비-정의된 것이라는 것입니다; 따라서 그것의 역을 전체 함수(total function), 즉 도메인의 어디에나 정의되도록 제한할만한 강제적인 이유가 없습니다. 주어진 기본 집합에 대한 모든 부분 전단사의 집합은 대칭 역 준그룹(symmetric inverse semigroup)이라고 불립니다.^[5]

같은 개념을 정의하는 또 다른 방법은 A에서 B 로의 부분 전단사가 R이 전단사 f:A′→B′의 그래프(graph)라는 속성을 갖는 임의의 관계 R (이것은 부분 함수임이 밝혀집니다)임을 말하는 것이며, 여기서 A′는 A의 부분-집합(subset)이고 B′는 B의 부분-집합입니다.^[6]

부분 전단사가 같은 집합에 있을 때, 일-대-일 부분 변환(one-to-one partial transformation)이라고 때때로 불립니다.^[7] 한 예제는 확장 복소 평면에 대한 그것의 완비가 아니라, 복소 평면에 대한 간단히 정의된 뫼비우스 변환(Möbius transformation)입니다.^[8]

Contrast with

Multivalued function

Notes

^ ^a ^b "The Definitive Glossary of Higher Mathematical Jargon — One-to-One Correspondence". Math Vault. 2019-08-01. Retrieved 2019-12-07.{{cite web}}: CS1 maint: url-status (link)
^ "Injective, Surjective and Bijective". www.mathsisfun.com. Retrieved 2019-12-07.
^ There are names associated to properties (1) and (2) as well. A relation which satisfies property (1) is called a total relation and a relation satisfying (2) is a single valued relation.
^ "Bijection, Injection, And Surjection | Brilliant Math & Science Wiki". brilliant.org. Retrieved 2019-12-07.
^ Christopher Hollings (16 July 2014). Mathematics across the Iron Curtain: A History of the Algebraic Theory of Semigroups. American Mathematical Society. p. 251. ISBN 978-1-4704-1493-1.
^ Francis Borceux (1994). Handbook of Categorical Algebra: Volume 2, Categories and Structures. Cambridge University Press. p. 289. ISBN 978-0-521-44179-7.
^ Pierre A. Grillet (1995). Semigroups: An Introduction to the Structure Theory. CRC Press. p. 228. ISBN 978-0-8247-9662-4.
^ John Meakin (2007). "Groups and semigroups: connections and contrasts". In C.M. Campbell; M.R. Quick; E.F. Robertson; G.C. Smith (eds.). Groups St Andrews 2005 Volume 2. Cambridge University Press. p. 367. ISBN 978-0-521-69470-4. preprint citing Lawson, M. V. (1998). "The Möbius Inverse Monoid". Journal of Algebra. 200 (2): 428. doi:10.1006/jabr.1997.7242.

References

This topic is a basic concept in set theory and can be found in any text which includes an introduction to set theory. Almost all texts that deal with an introduction to writing proofs will include a section on set theory, so the topic may be found in any of these:

Wolf (1998). Proof, Logic and Conjecture: A Mathematician's Toolbox. Freeman.
Sundstrom (2003). Mathematical Reasoning: Writing and Proof. Prentice-Hall.
Smith; Eggen; St.Andre (2006). A Transition to Advanced Mathematics (6th Ed.). Thomson (Brooks/Cole).
Schumacher (1996). Chapter Zero: Fundamental Notions of Abstract Mathematics. Addison-Wesley.
O'Leary (2003). The Structure of Proof: With Logic and Set Theory. Prentice-Hall.
Morash. Bridge to Abstract Mathematics. Random House.
Maddox (2002). Mathematical Thinking and Writing. Harcourt/ Academic Press.
Lay (2001). Analysis with an introduction to proof. Prentice Hall.
Gilbert; Vanstone (2005). An Introduction to Mathematical Thinking. Pearson Prentice-Hall.
Fletcher; Patty. Foundations of Higher Mathematics. PWS-Kent.
Iglewicz; Stoyle. An Introduction to Mathematical Reasoning. MacMillan.
Devlin, Keith (2004). Sets, Functions, and Logic: An Introduction to Abstract Mathematics. Chapman & Hall/ CRC Press.
D'Angelo; West (2000). Mathematical Thinking: Problem Solving and Proofs. Prentice Hall.
Cupillari. The Nuts and Bolts of Proofs. Wadsworth.
Bond. Introduction to Abstract Mathematics. Brooks/Cole.
Barnier; Feldman (2000). Introduction to Advanced Mathematics. Prentice Hall.
Ash. A Primer of Abstract Mathematics. MAA.

External links

[:0-1] "The Definitive Glossary of Higher Mathematical Jargon — One-to-One Correspondence". Math Vault. 2019-08-01. Retrieved 2019-12-07.{{cite web}}: CS1 maint: url-status (link)

[2] "Injective, Surjective and Bijective". www.mathsisfun.com. Retrieved 2019-12-07.

[3] There are names associated to properties (1) and (2) as well. A relation which satisfies property (1) is called a total relation and a relation satisfying (2) is a single valued relation.

[4] "Bijection, Injection, And Surjection | Brilliant Math & Science Wiki". brilliant.org. Retrieved 2019-12-07.

[Hollings2014-5] Christopher Hollings (16 July 2014). Mathematics across the Iron Curtain: A History of the Algebraic Theory of Semigroups. American Mathematical Society. p. 251. ISBN 978-1-4704-1493-1.

[Borceux1994-6] Francis Borceux (1994). Handbook of Categorical Algebra: Volume 2, Categories and Structures. Cambridge University Press. p. 289. ISBN 978-0-521-44179-7.

[Grillet1995-7] Pierre A. Grillet (1995). Semigroups: An Introduction to the Structure Theory. CRC Press. p. 228. ISBN 978-0-8247-9662-4.

[Campbell2007-8] John Meakin (2007). "Groups and semigroups: connections and contrasts". In C.M. Campbell; M.R. Quick; E.F. Robertson; G.C. Smith (eds.). Groups St Andrews 2005 Volume 2. Cambridge University Press. p. 367. ISBN 978-0-521-69470-4. preprint citing Lawson, M. V. (1998). "The Möbius Inverse Monoid". Journal of Algebra. 200 (2): 428. doi:10.1006/jabr.1997.7242.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Function
$x \mapsto f (x)$
History of the function concept
Examples of domains and codomains
$X$ → $\mathbb {B}$ , $\mathbb {B}$ → $X$ , $\mathbb {B} ^{n}$ → $X$ $X$ → $\mathbb {Z}$ , $\mathbb {Z}$ → $X$ $X$ → $\mathbb {R}$ , $\mathbb {R}$ → $X$ , $\mathbb {R} ^{n}$ → $X$ $X$ → $\mathbb {C}$ , $\mathbb {C}$ → $X$ , $\mathbb {C} ^{n}$ → $X$
Classes/properties
Constant Identity Linear Polynomial Rational Algebraic Analytic Smooth Continuous Measurable Injective Surjective Bijective
Constructions
Restriction Composition λ Inverse
Generalizations
Binary relation Partial Multivalued Implicit Space
v t e