함수-단사, 전사 및 역함, 비둘기집 원리

7장. 함수(1)

이산수학 및 응용

목차

7.1 일반적인 집합에서 정의된 함수

7.2 단사, 전사 및 역함수

7.3 응용: 비둘기 집의 원리

7.4 함수의 합성

7.5 카디낼러티와 계산가능성 문제

들어가며…

• 함수

– 수학에서의 함수

– 컴퓨터과학에서의 함수

• 예제

– 진리표

– 수열

– mod, div

– 천장, 마루

– …

7.1 일반적인 집합에서 정의된 함수

The theory that has had the greatest development is recent times is without any doubt the theory of functions.  Vito Volterra, 1888

함수

• 정의

– 집합 X에서 Y로의 함수 f 는(a function f from a set X to a set Y) 입력(input)인 X의 원소와 출력(output)인 Y의 원소 사이의 관계로서, 각 입력이 하나의 출력과 관계가 있는 특성을 가진다.

– f : X  Y라는 표시는 f가 X에서 Y로의 함수라는 것을 의미한다. X를 f의 정의역(domain)이라 부르고, Y를 f의 공변역(co-domain)이라 부른다.

함수

• 정의(계속)

– 주어진 입력 원소 x에 대해, f에 의해 x와 관계가 있는 Y의 유일한 출력원소 y가 존재하며, 이것을 “f는 x를 y로 대응시킨다(f sends x to y)”라 하고 f: x  y로 표기한다. 함수 f가 x를 대응시키는 유일한 원소 y를 f(x)로 표기하며, 다음과 같이 부른다.

f of x

입력 x에 대한 f의 출력

x에서 f의 값(value), f에 의한 x의 상(image)

함수

• 정의(계속)

– f가 가질 수 있는 모든 값의 집합을 f의 치역(range) 또는 f에서의 X의 상(image)이라 하며, 기호로 표시하면 다음과 같다.

f의 치역  f에서의 X의 상  {yY | y  f(x), xX}

– Y의 원소인 y가 주어졌을 때, y를 상으로 하는 X의 원소가 존재할 수 있다. f(x)  y라면 x를 y의 원상(preimage) 또는 역상(inverse image)라 한다. 기호로 표시하면 다음과 같다.

y의 역상  {xX | f(x)  y}

화살도표

• 화살도표(arrow diagram)

– X와 Y가 유한 집합일 때, 화살표를 사용하여 함수를 표현

• 예제

화살도표

• 예제

– f의 정의역, 공변역, 치역?

– s, t, v의 역상은?

– 순서쌍의 집합으로 f를 나타내면?

• f  {(1, v), (3, s), (5, v)}

함수와 비함수

• 예제

– 다음 중 함수와 함수가 아닌 것은?

함수의 정의

• 예제

– 제곱 함수(squaring function)

• f: R  R, f(x)  x2

• f: R  R, f()  2 

• f: R  R, f: x  x2

– 후속자 함수(successor function)

• g: Z  Z, g(n)  n + 1

– 상수 함수(constant function)

• h: Q  Z, g(r)  2

함수의 상등

• 정의

– 함수 f와 g가 X에서 Y로의 함수라고 할 때, “f는 g와 동등하다(f equals g)”는 f  g로 표기하며, 집합 X의 모든 원소 x에 대하여 f(x)  g(x)이다.

• 예제

– f: R  R, f(x)  |x|, g: R  R, g(x)  x2, f  g?

– F: R  R, G: R  R

• (F + G)(x)  F(x) + G(x)  for all xR

• (G + F)(x)  G(x) + F(x)  for all xR

• F + G  G + F?

항등 함수

• 예제

– 집합 X에서 X로의 함수 iX를 아래와 같이 정의

• iX(x)  x

– 집합 X의 원소 aijk와 (z)에 대하여,

• iX(aijk)?

• iX((z))?

다양한 함수

• 예제

– 함수 F: P({a, b, c})  Znonneg

• F(X)  X에 있는 원소의 개수

다양한 함수

• 예제

– Hamming 거리 함수

• Sn: 길이가 n인 0과 1로 이루어진 문자열

• H: SnSn  Znonneg

• H(s, t)  문자열 s와 t가 서로 다른 값을 가지는 자리의 개수

• H(11111, 00000)  5

• H(11000, 00000)  3

• H(00101, 01110)?

• H(10001, 01111)?

다양한 함수

• n-자리 부울 함수

– f: {0, 1}n  {0, 1}

잘 정의된 함수

• 예제: 잘 정의된 함수?

– f: R  R

– g: Q  Z, 모든 정수 m과 n에 대해(단 n  0)

7.2 단사, 전사 및 역함수

Don’t accept a statement just because it is printed.  Anna Pell Wheeler, 1883–1966

단사 함수

• 정의

– 함수 F: X  Y가 다음과 같을 때 단사 함수(injective function) 혹은 일대일 함수(one-to-one function)라 한다.

x1,x2X, if F(x1)  F(x2), then x1  x2.

또는, x1,x2X, if x1  x2, then F(x1)  F(x2).

• 어떤 함수 F: X  Y가 단사함수가 아니다

 F(x1)  F(x2)이면서 x1  x2인 x1,x2X가 존재한다.

단사 함수

• 예제: 단사 함수?

단사 함수

• 예제: 단사 함수? 증명?

– f: R  R, f(x)  4x – 1

• 임의의 실수 x1, x2가 f(x1)  f(x2)를 만족 시킨다고 가정

• f(x1)  f(x2)

 4x1 – 1  4x2 – 1

 4x1  4x2

 x1  x2

– g: Z  Z, g(n)  n2

전사 함수

• 정의

– 함수 F: X  Y가 다음과 같을 때 전사 함수(subjective function, onto function)라 한다.

yY, xX such that F(x)  y.

• 전사 함수의 부정

– yY such that xX, F(x)  y.

전사 함수

• 예제: 전사 함수?

전사 함수

• 예제: 전사 함수? 증명?

– f: R  R, f(x)  4x – 1

• y를 임의의 실수라고 두자.

• f(x)  4x – 1  y

 4x  y + 1

 x  (y + 1)/4

– h: Z  Z, h(n)  4n – 1

일대일 대응 함수

• 정의

– 함수 F: X  Y가 단사 함수이면서 전사 함수이면, 이 함수를 일대일 대응 함수(one-to-one correspondence function) 혹은 전단사 함수(bijective function)이라 한다.

일대일 대응 함수

• 예제

– 멱집합에서 문자열 집합으로의 함수

• h: P({a, b})  {00, 01, 10, 11}

역함수

• 정의

– 함수 F: X  Y를 일대일 대응 함수라 하자.

– Y의 원소 y에 대해, 함수 F–1: Y  X를 함수 F에 대한 역함수(inverse function)라 하며 다음과 같이 정의한다.

F–1(y)  F(x)가 y가 되는 집합 X의 유일한 원소 x.

– 즉,

F–1(y)  x    F(x)  y.

역함수

• 예제

– 멱집합에서 문자열 집합으로의 함수의 역함수

• h–1: {00, 01, 10, 11}  P({a, b})

역함수

• 정리 7.2.1

– 집합 X와 Y에 대해, 함수 F: X  Y가 일대일 대응 함수라면, F–1: Y  X도 일대일 대응 함수이다.

– 증명 개요

• F–1가 단사 함수임을 증명

– y1,y2Y에 대해 F–1(y1)  F–1(y2)이면 y1  y2이다.

• F–1가 전사 함수임을 증명

– xX에 대해 F–1(y)  x인 yY가 존재한다.

7.3 응용: 비둘기 집의 원리

The shrewd guess, the fertile hypothesis, the courageous leap to a tentative conclusion–these are the most valuable coin of thinker at work.  Jerome S. Bruner, 1960

비둘기 집의 원리

• 비둘기 집

비둘기 집의 원리

• 비둘기 집의 원리(pigeonhole principle)

– 유한 집합에서 더 작은 유한 집합으로의 함수는 단사일 수 없다: 공변역에 같은 상을 가지는 정의역의 원소는 적어도 두 개는 있어야 한다.

비둘기 집의 원리

• 예제

– 13명이 모였으면 같은 달에 태어난 사람이 있다.

– 10개의 검정색 양말과 10개의 흰색 양말이 들어있는 서랍이 있다. 눈을 감고 꺼내는 경우 몇 개를 꺼내면 올바를 한 켤레를 만들 수 있는가?

– 부산에는 머리카락 개수가 같은 사람이 적어도 두 사람은 존재한다.

– n 명의 사람들이 임의로 악수하면 적어도 두 명은 같은 악수 회수를 가진다.

비둘기 집의 원리

• 예제

– {1, 2, 3, 4, 5, 6, 7, 8}에서 5개의 원소를 선택하면 합이 9가 되는 두 원소가 선택된다.

– The decimal expansion of any rational number either terminates or repeat.

• 예제: 3.625, 2.38246  2.38246246246246…

 무한집합에서 유한집합으로의 함수

비둘기 집의 원리

• 예제

– 무손실 압축(lossless compression)을 하는 알고리즘은 어떤 경우는 원본보다 더 큰 압축 파일을 만들어 낸다.

• 증명 개요: 모든 문서가 압축된다고(크기가 줄어든다고) 가정하면,

일반화된 비둘기 집의 원리

• 일반화된 비둘기 집의 원리

– 유한 집합 X에서 유한 집합 Y로의 함수 f와 양의 정수 k에 대해, N(X) > kN(Y)라면, X에 있는 적어도 k + 1 개의 서로 다른 원소의 상이 되는 yY가 존재한다.

• 예제

– In a group of 85 people, at least 4 must have the same last initial.

일반화된 비둘기 집의 원리

• 대위형태

– 유한 집합 X에서 유한 집합 Y로의 함수를 f라 두고 k를 양의 정수라 두자. 원소 yY에 대해, f–1(y)는 많아야 k 개의 원소를 가진다면, X는 많아야  kN(Y) 개의 원소를 가진다.

• 예제

– 42 명의 학생이 12 대의 컴퓨터를 공유하며, 모두 정확히 1 대의 컴퓨터만 사용한다. 적어도 5 대의 컴퓨터가 3 명 이상의 학생에의해 사용되고 있음을 보여라

• 증명 개요(모순을 사용): 4대 이하라고 가정

비둘기 집의 원리 증명

• 정의

– 어떤 집합 A가 유한(finite)이라는 것은 A가 공집합이거나 {1, 2, …, n}에서 A로 일대일 대응 함수가 존재하는 경우를 말한다. 전자의 경우 원소의 개수가 0이라 하고, 후자의 경우 n이라 한다. 유한하지 않은 집합은 무한(infinite)이라 한다.

비둘기 집의 원리 증명

• 정리 7.3.1

– 어떤 집합 X에서 유한 집합 Y로의 함수 f에 대해, N(X) > N(Y)이면 f는 단사 함수가 아니다.

– 증명(모순에 의한)

• N(Y)  m, Y  {y1, y2, …, ym}로 두자.

• 역상 집합 f–1(yi)  {xX | f(x)  yi}라 정의하면,

– N(X)  N(f–1(y1)) + N(f–1(y2)) + … + N(f–1(ym))

• f를 단사라고 가정하면 N(f–1(yi))  1이므로,

– N(f–1(y1)) + N(f–1(y2)) + … + N(f–1(ym))  m

– 따라서, N(X)  m  N(Y)가 되어 모순이다.

비둘기 집의 원리

• 정리 7.3.2: 유한 집합에 대한 단사와 전사

– X와 Y가 같은 크기의 유한 집합이고 f가 X에서의 Y로의 함수일 때, f가 단사일 때만(if, and only if) f는 전사이다.

– 증명 개요

• 단사이면 전사이다.

– Y에서 X의 상이 아닌 원소를 S라 하면,

» N(Y)  N({f(x1)}) … + N({f(xm)}) + N(S)

 m + N(S)  m

• 전사이면 단사이다.