함수와 일대일·전사

사용자 ID를 넣으면 그 사용자의 프로필이 나오는 조회를 생각해 봅시다. ID 하나에 프로필이 둘 나오거나, 어떤 ID에는 아무것도 나오지 않는다면 이 조회를 믿고 쓰기 어렵습니다. "입력 하나에 출력이 정확히 하나"라는 조건을 만족하는 대응을 수학에서는 함수라고 합니다. 이 글에서는 관계의 특별한 경우로 함수를 정의하고, 함수가 출력을 겹치지 않게 내는지, 가능한 출력을 모두 내는지를 판정하는 방법을 익힙니다.

입력마다 출력이 정확히 하나

집합 A에서 집합 B로의 함수(function) $f:A\to B$는 A의 모든 원소에 B의 원소를 정확히 하나씩 대응시키는 것입니다. 관계로 보면, A의 모든 원소 a에 대해 $(a,b)$ 꼴의 순서쌍이 정확히 하나 있는 $A\times B$의 부분집합입니다. a에 대응하는 b를 $f(a)$로 씁니다. A를 정의역(domain), B를 공역(codomain)이라 하고, 실제로 나오는 출력들의 집합 $f(A)=\{f(a)\mid a\in A\}$를 치역(range)이라고 합니다. 공역은 출력이 들어갈 수 있는 집합이고, 치역은 그 가운데 실제로 나오는 출력의 집합이라 공역보다 작을 수 있습니다.

함수의 조건은 두 가지로 나누어 생각할 수 있습니다. 모든 입력에 출력이 있어야 하고, 한 입력의 출력이 둘 이상이면 안 됩니다. 반면 서로 다른 입력이 같은 출력으로 가는 것은 괜찮습니다. 아래 그림의 f는 $A=\{1,2,3\}$에서 $B=\{a,b,c\}$로, 1과 2는 a로, 3은 b로 보냅니다.

def is_function(pairs, domain):
    outputs = {}
    for x, y in pairs:
        outputs.setdefault(x, set()).add(y)
    return all(len(outputs.get(x, set())) == 1 for x in domain)


A = [1, 2, 3]
print(is_function({(1, "a"), (2, "a"), (3, "b")}, A))
print(is_function({(1, "a"), (1, "b"), (2, "a"), (3, "b")}, A))
print(is_function({(1, "a"), (2, "a")}, A))

True
False
False

is_function은 입력마다 나오는 출력의 집합을 모은 뒤, 정의역의 모든 입력에서 출력이 정확히 하나인지 봅니다. 첫째는 함수이고, 둘째는 1의 출력이 a와 b 둘이라 함수가 아니며, 셋째는 3의 출력이 없어 함수가 아닙니다. Python의 딕셔너리는 키마다 값이 하나씩이라, 키의 집합을 정의역으로 보면 그 자체로 유한한 함수를 나타냅니다.

단사, 전사, 전단사

함수가 서로 다른 입력을 늘 서로 다른 출력으로 보내면, 곧 $f(x)=f(y)$이면 $x=y$이면, 그 함수를 단사(injective) 또는 일대일 함수라고 합니다. 공역의 모든 원소가 어떤 입력의 출력으로 나오면, 곧 모든 $b\in B$에 대해 $f(a)=b$인 $a\in A$가 있으면, 전사(surjective)라고 합니다. 전사는 치역과 공역이 같다는 뜻입니다. 단사이면서 전사인 함수를 전단사(bijective)라고 하며, 정의역과 공역의 원소를 빠짐없이 하나씩 짝짓습니다.

def injective(f):
    return len(set(f.values())) == len(f)


def surjective(f, codomain):
    return set(f.values()) == set(codomain)


B = {"a", "b", "c"}
f = {1: "a", 2: "a", 3: "b"}
g = {1: "b", 2: "c", 3: "a"}
print(injective(f), surjective(f, B))
print(injective(g), surjective(g, B))

False False
True True

injective는 서로 다른 출력의 개수가 입력의 개수와 같은지, surjective는 출력의 집합이 공역과 같은지 봅니다. 그림의 f는 1과 2의 출력이 겹쳐 단사가 아니고, c가 출력되지 않아 전사도 아닙니다. g는 세 입력을 세 출력으로 겹치지 않게 보내고 공역을 모두 덮으므로 전단사입니다.

같은 식이라도 집합이 바뀌면 성질이 바뀐다

함수는 식만으로 정해지지 않고, 정의역과 공역까지 정해야 성질을 말할 수 있습니다. $f(x)=x^2$를 실수에서 실수로 가는 함수로 보면, $f(1)=f(-1)=1$이라 단사가 아니고, 음수는 출력되지 않으므로 전사도 아닙니다. 그런데 정의역과 공역을 모두 0 이상의 실수로 바꾸면, 0 이상인 두 수의 제곱이 같으면 두 수가 같으므로 단사이고, 0 이상의 모든 실수 y에 대해 $\sqrt y$의 제곱이 y이므로 전사입니다. 식은 그대로인데 집합을 바꾸었더니 전단사가 된 것입니다. 그래서 "제곱 함수에 역함수가 있는가"라는 질문에는 정의역과 공역을 먼저 물어야 합니다.

원소의 개수와 비둘기집 원리

정의역과 공역이 유한하면 원소의 개수가 성질을 제한합니다. 단사 함수는 서로 다른 입력을 서로 다른 출력으로 보내므로 $|A|\le|B|$여야 하고, 전사 함수는 공역의 모든 원소에 입력이 하나 이상 필요하므로 $|A|\ge|B|$여야 합니다. 그래서 $|A|>|B|$이면 어떤 함수도 단사가 될 수 없고, 반드시 두 입력이 같은 출력을 공유합니다. 비둘기 13마리가 비둘기집 12개에 들어가면 어느 집에는 두 마리 이상 들어간다는 이 사실을 비둘기집 원리(pigeonhole principle)라고 합니다. 사람이 13명 모이면 태어난 달이 같은 두 사람이 반드시 있는 것도 이 원리 때문입니다.

작은 집합이라면 가능한 함수를 모두 만들어 세어 볼 수 있습니다. 입력마다 출력을 하나씩 고르므로, $|A|=3$, $|B|=3$이면 함수는 $3^3=27$개입니다.

from itertools import product


def all_functions(A, B):
    return [dict(zip(A, outputs)) for outputs in product(B, repeat=len(A))]


def injective(f):
    return len(set(f.values())) == len(f)


def surjective(f, codomain):
    return set(f.values()) == set(codomain)


A = [1, 2, 3]
for B in (["a", "b", "c"], ["a", "b"]):
    functions = all_functions(A, B)
    print(len(functions), sum(injective(f) for f in functions), sum(surjective(f, B) for f in functions))

27 6 6
8 0 6

공역이 세 원소이면 27개 가운데 단사인 것과 전사인 것이 모두 6개인데, 이 둘은 같은 함수들입니다. 원소 수가 같은 유한집합 사이에서는 단사인 함수가 곧 전사이고, 그 반대도 성립하기 때문입니다. 공역이 두 원소이면 함수는 $2^3=8$개이고, 입력이 출력보다 많아 단사인 함수는 하나도 없습니다. 다만 개수 조건은 필요조건일 뿐이라, $|A|\le|B|$라고 해서 아무 함수나 단사인 것은 아닙니다.

더 깊이: 단사와 전사가 같아지는 것은 유한집합에서만이다

$|A|=|B|=n$인 유한집합 사이에서 단사와 전사가 같은 이유는 세어 보면 바로 나옵니다. f가 단사이면 서로 다른 n개의 입력이 서로 다른 n개의 출력을 내므로 치역의 원소가 n개이고, 이는 공역 전체이므로 f는 전사입니다. 반대로 f가 전사이면 치역이 원소 n개인 공역 전체인데, 두 입력이 같은 출력을 낸다면 n개의 입력으로 만들 수 있는 출력은 $n-1$개 이하가 되어 모순이므로 f는 단사입니다.

이 논증은 원소의 개수를 셀 수 있다는 데 기대므로 무한집합에서는 성립하지 않습니다. 자연수에서 자연수로 가는 $f(n)=n+1$은 서로 다른 수를 서로 다른 수로 보내 단사이지만 0이 출력되지 않아 전사가 아니고, n을 2로 나눈 몫, 곧 n/2 이하의 가장 큰 정수를 돌려주는 $g(n)=\lfloor n/2\rfloor$는 모든 자연수를 출력하지만 $g(0)=g(1)=0$이라 단사가 아닙니다. 실제로 무한집합은 자기 자신의 진부분집합과 짝을 지을 수 있다는 성질로 정의하기도 하며, $f(n)=n+1$이 바로 자연수 전체와 0을 뺀 자연수 사이의 그런 짝입니다.

공역이 더 작을 때 전사인 함수의 수는 포함·배제로 셉니다. 원소 n개에서 원소 k개로 가는 함수 $k^n$개 가운데 출력에 빠진 원소가 있는 것을 빼고, 두 번 뺀 것을 다시 더하는 식으로 정리하면 전사 함수는 $\sum_{j=0}^{k}(-1)^j\binom kj(k-j)^n$개입니다. 앞의 실행에서 공역이 두 원소일 때의 6은 $2^3-2\cdot1^3+0=6$이고, 공역이 세 원소일 때의 6은 $27-3\cdot8+3\cdot1-0=6$입니다. 포함·배제의 원리는 11장에서 자세히 다룹니다.

역함수는 전단사에서만 있다

$f:A\to B$의 역함수(inverse function) $f^{-1}:B\to A$는 f의 출력을 원래 입력으로 되돌리는 함수입니다. 역함수도 함수이므로, B의 모든 원소에 대해 되돌릴 입력이 정확히 하나 있어야 합니다. f가 단사가 아니면 두 입력이 같은 출력을 내서 되돌릴 입력이 둘이 되고, 전사가 아니면 출력되지 않는 원소에는 되돌릴 입력이 없습니다. 그래서 역함수는 f가 전단사일 때만 있습니다.

앞의 g의 역함수는 딕셔너리의 키와 값을 뒤집어 만들 수 있습니다. {v: k for k, v in g.items()}는 {'b': 1, 'c': 2, 'a': 3}이 되어, b를 1로, c를 2로, a를 3으로 되돌립니다. 역관계는 순서쌍의 방향을 뒤집은 것이라 어떤 함수에나 만들 수 있지만, 그것이 함수가 되는 것은 원래 함수가 전단사일 때뿐입니다.

정리

• 함수 $f:A\to B$는 정의역 A의 모든 원소에 공역 B의 원소를 정확히 하나씩 대응시키며, 서로 다른 입력이 같은 출력으로 가는 것은 허용됩니다. 치역은 실제로 나오는 출력의 집합입니다.
• 단사는 서로 다른 입력이 늘 서로 다른 출력으로 가는 것, 전사는 치역이 공역과 같은 것, 전단사는 둘 다인 것입니다.
• 같은 식이라도 정의역과 공역에 따라 단사, 전사 여부가 달라지므로 집합부터 정해야 합니다.
• 유한집합에서 단사이면 $|A|\le|B|$, 전사이면 $|A|\ge|B|$이고, $|A|>|B|$이면 비둘기집 원리에 따라 출력이 겹칩니다.
• 역함수는 전단사인 함수에만 있으며, 역관계는 늘 있지만 함수가 아닐 수 있습니다.

연습 문제

1. 전단사와 역함수

$A=\{1,2,3\}$, $B=\{a,b,c\}$에서 $f(1)=b$, $f(2)=c$, $f(3)=a$인 함수의 단사, 전사 여부를 판정하고 역함수를 쓰세요.

2. 두 배 하는 함수

정수에서 정수로 가는 함수 $g(n)=2n$은 단사인가요, 전사인가요? 공역을 바꾸면 어떻게 될까요?

3. 비둘기집 원리 쓰기

1부터 10까지의 정수 가운데 6개를 고르면, 합이 11이 되는 두 수가 반드시 들어 있음을 비둘기집 원리로 보이세요.

판정하기 전에 정의역, 공역, 치역을 먼저 적어 보세요. 함수를 이어서 적용하는 합성과 자주 쓰는 함수들은 다음 글 함수의 합성과 종류에서 다룹니다.