[Programming 질문] Injective, Surjective, Bijective

Injective, Surjective, Bijective 이해가 잘 되지 않아요.

 

Injective, Surjective, Bijective란 컴퓨터 공학 학부생이라면

Discrete Mathematics나 Calculus에서 배우는 Functions이다.

 

전공자라면 기본적으로 배우는 함수이기 때문에 알고 있지만

오랜만에 들어보거나 실제로 활용하려고 하면 헷갈리는 부분이 생기기 마련이다.

 

예를 들어 수학적 관점에서의 Injective, Surjective, Bijective functions들에 대한 문제 해결은 쉬울 수 있지만

이것을 프로그래밍 언어로 적용해서 infinite 값에 결괏값을 산출하기 위한 코딩을 한다면

"Wow"라는 생각이 든다.

 

한마디로 Functions들에 대해 알고는 있지만 명확히 100%는 아니고 한 89% 정도인 느낌인 것이다.

그래서 이번 포스트에서는 Injective, Surjective, Bijective에 대한 Functions 별 특징을 명확히 이해하고

다음 포스트 에서는 프로그래밍에서 어떤 식으로 공식화가 되는지와

infinite 값을 활용하여 응용되는 과정을 살펴보도록 하자.

 

Injective, Surjective, Bijective를 사용하는 이유

사실 사용하는 이유는 매우 간단하다.

아주 기초적인 함수이고 프로그래밍의 기본 구조 중에 하나라고도 볼 수 있기 때문이다.

프로그래밍에서 입력을 하면 계산 과정을 거쳐 결괏값이 나오는 게 기본적인 구성 형태이다.

Injective, Surjective, Bijective은 그것을 아주 잘 보여주는 함수이다.

 

그렇기에 프로그래머가 되기 위해서는 코드만 잘 쓰는게 아니라 수학을 잘해야 된다는 말이 여기에 해당한다.

함수를 알아야 기본 프로그래밍 구조를 이해할 수 있기 때문에 앞으로의 프로그램 개발에 있어 응용력이 빠르다.

다시 본론으로 돌아와서 Injective, Surjective, Bijective에 대해서

수학 수업 드는 관점이 아니라 프로그래밍 관점에서 중요한 점을 살펴보자.

왜냐하면 이미 수학 수업 시간에 배웠을 거라 생각하기 때문이다.

그리고 어렵지 않으니 가벼운 마음으로 대하기 바란다.

 

Injective function

Injective function은 다른 말로 one to one fuction이라고도 하는데 여기에 힌트가 있다.

one to one 이라는 의미처럼 Injective function은 domain과 codomain이 하나씩 일치해야 한다.

여기서 Domain이란 흔히 x값이라고 예제를 드는 정의역을 의미한다.

한마디로 많은 예시 그림에서 왼쪽에 있는 값을 Domain이라고 생각하면 된다.

Codomain은 흔히 y값이라고 하는 예제 그림에서 오른쪽에 위치한 값이라고 생각하면 된다.

 

자, 다시 본론으로 돌아와서 Function 조건이 성립되려면

하나의 Domain이 여러 개의 Codomain을 가지면 안 된다고 배웠다.

(이 부분도 잘 기억이 나지 않으면 조용히 필자에게 알려주면 Detail 하게 포스팅을 하겠다.)

 

Function의 조건을 충족하면서 Injective function이 성립되기 위해서는 각각의 Domain이

하나씩의 Codomain과 연결되어야 한다.

Function 조건에서는 여러 개의 Domain이 같은 Codomain 값을 가져도 상관없지만

Injective Function이 성립되기 위해서는 각각의 Domain이 각각의 Codomain 값을 가져야 한다.

아래 그림은 필자가 간단하게 만든 Injective Function의 예제이다.

[그림1] 각 Domain이 Codomain과 하나씩 연결되어 있다.

 

[그림2] Codomain이 짝이 없어도 Domain이 Codomain과 one to one만 이루어지면 된다.

 

여기서 유의할 점은 Codomain이 비어 있어도 상관없다는 것이다.

[그림 2]의 상황처럼 에이미가 남겨져 있어도 왼쪽 Domain 영역에 있는 친구들이 Codomain 있는 친구들과

one to one으로 연결되었기 때문에 이 역시도 Injective function 조건이 성립된다.

 

Surjective function

[그림3] 모든 Codomain이 연결되어 있어야 한다.

 

Injective funciton의 특징을 이해했다면 Surjective function을 이해하기 쉽다.

Surjective function은 on to function이라고도 불리며 Injective function과 달리

여러 개의 Domain이 하나의 Codomain에 연결돼도 무방하다.

다만, Surjective function에서는 Domain이 없는 Codomain이 있어서는 안 된다.

모든 Codomain이 Domain과 연결되어야 한다는 점이 Surjective function의 특징이다.

 

Bijective function

[그림4] Bijection = Injection + Surjection

 

Bijective function은 한마디로 Injective function의 특징과 Surjective function의 조건을 모든 충족한다.

Injective function의 조건과 Surjective function의 조건이 모두 갖고 있다면

이를 Bijective function이라고 부른다.