단사함수와 전사함수 (Injective and Surjective Function)

한 줄 정의: 단사함수는 서로 다른 입력이 항상 서로 다른 출력으로 대응되는 함수이고, 전사함수는 공역의 모든 값이 빠짐없이 함숫값으로 나타나는 함수입니다.

쉽게 풀면

학생들에게 사물함을 배정하는 상황을 생각해봅시다. 단사함수는 "한 사물함에는 한 학생만 배정되어, 서로 다른 두 학생이 같은 사물함을 쓰는 일이 없는" 경우입니다(중복 배정이 없음). 전사함수는 "학교에 있는 사물함이 하나도 빠짐없이 누군가에게 배정되는" 경우입니다(비어있는 사물함이 없음). 두 조건을 모두 만족하면, 즉 모든 사물함에 정확히 한 명씩 배정되면 이를 전단사함수(일대일대응)라고 부르며, 이때는 사물함 번호만 보고 학생을 거꾸로 찾아낼 수 있습니다(역함수 존재).

왜 중요한가

단사·전사 성질은 어떤 대응이 정보를 손실 없이 뒤집을 수 있는지, 두 집합의 크기를 비교할 수 있는지를 판단하는 기본 도구이기 때문에 순수수학뿐 아니라 암호학, 데이터 압축, 컴퓨터과학 전반에서 자주 등장합니다. 암호화나 해시 함수의 안전성, 데이터 인코딩의 복원 가능성을 증명할 때 함수가 단사인지 전사인지를 따지는 것이 논증의 출발점이 되는 경우가 많습니다.

논문에서는 이렇게 쓰입니다

"본 연구에서 제안한 인코딩 함수가 전단사임을 보임으로써, 원본 데이터를 정보 손실 없이 복원할 수 있음을 증명하였다."

이 문장은 "인코딩 함수가 단사(중복 없음)이면서 전사(빠짐없음)이기 때문에, 인코딩된 값만 보고도 원래 데이터를 정확히 되돌릴 수 있다"는 뜻입니다.

"해시 함수가 단사가 아니므로 서로 다른 두 입력이 동일한 해시값으로 대응되는 충돌(collision)이 이론적으로 발생할 수 있음을 지적하였다."

암호학 논문에서 해시 함수의 안전성을 논할 때, 단사가 아니라는 성질을 근거로 충돌 가능성을 설명하는 표현이다.

"두 유한집합 사이에 전단사함수가 존재함을 보임으로써 두 집합의 원소 개수가 같음을 증명하였다."

조합론에서 직접 원소를 세는 대신 전단사함수의 존재를 이용해 두 집합의 크기가 같음을 보이는 전형적인 증명 방식이다.

조금 더 깊게 보면

단사함수는 정의역이 유한집합일 때 정의역의 크기가 공역의 크기보다 클 수 없다는 사실과 연결되며, 이는 비둘기집 원리로 이어집니다. 무한집합에서는 전단사함수의 존재 여부를 이용해 두 무한집합의 크기(농도)가 같은지를 비교하는데, 이 방법으로 자연수 집합과 유리수 집합은 크기가 같지만 실수 집합은 그보다 더 크다는 것을 보일 수 있습니다. 논문에서 전단사를 증명할 때는 흔히 역함수를 직접 구성하거나, 단사이면서 동시에 전사임을 각각 보이는 방식을 사용합니다.

주의할 점

단사와 전사는 서로 독립적인 성질입니다. 단사이지만 전사가 아닐 수도 있고(사물함이 남는 경우), 전사이지만 단사가 아닐 수도 있습니다(한 사물함에 여러 학생이 몰리는 경우). 두 조건을 모두 만족해야만 합성함수와 역함수를 만들 수 있는 전단사함수가 됩니다.