jebae's dev blog

코딩 더 매트릭스 - 1장 함수 (1)

집합과 함수

2018년 11월 10일

필립 클라인의 저서 코딩 더 매트릭스 1장 함수 중 집합과 함수

  1. 집합과 함수를 되새겨 봅니다.
  2. 단사 함수와 전사 함수를 알아보고 단사, 전사 함수와 역함수의 관계를 알아봅니다.





집합

고등학교 수학 가장 처음 대목이기도 한 집합은 수학 객체를 모아 놓은 것입니다. 몇가지 성질을 다시 한번 떠올려 봅시다.

  1. 집합에 속하는 각 객체는 많아야 한 번 그 집합에 나타납니다.
  2. 집합 내 순서는 중요하지 않습니다.
  3. 집합의 크기 Cardinality   ∣S∣\mid S \mid
  4. 원소가 집합에 속한다는 수식은 고등학교에서 배웠듯 아래와 같이 씁니다. a∈{a,b,c}a \in \{a,b,c\}





카테시안 곱 Cartesian product

두 집합 AA 와 BB 가 있다면 두 집합의 카테시안 곱은 두 집합에 속한 모든 원소의 쌍으로 이루어 집니다. 예를 들어 A={1,2,3}A = \{1, 2, 3\} B={a,b,c}B = \{a, b, c\} 일때 두집합의 카테시안 곱은

A×B={(1,a),(1,b),(1,c),(2,a),(2,b),(2,c),(3,a),(3,b),(3,c)}A \times B = \{(1,a), (1,b), (1,c), (2,a), (2,b), (2,c), (3,a), (3,b), (3,c)\}

각각의 집합과 카테시안 곱한 집합의 크기를 생각하면 어렵지 않게

∣A×B∣=∣A∣⋅∣B∣\mid A \times B \mid = \mid A \mid \cdot \mid B \mid

가 성립합니다.





함수

쌍 (a, b) 들의 집합이며 이때 각 쌍의 첫번째 원소는 다릅니다. 하나의 정의역 원소에서 하나의 공역 원소에만 매핑되므로 각 쌍의 첫번째 원소가 다르다고 말할 수 있습니다. 이 집합은 무한 집합도 가능합니다. 정의역 자체도 숫자들의 쌍으로 구성될 수 있습니다. 예를 들어 정의역 {1,2,3,...}×{1,2,3...}\{1,2,3,...\} \times \{1,2,3...\} 을 가지는 곱셈 함수는 다음과 같이 나타낼 수 있습니다.

{((1,1),1),((1,2),2),((2,1),2),((2,2),3)...}\{((1,1), 1), ((1,2), 2), ((2,1), 2), ((2,2), 3)...\}

고등학교에서 배웠듯 우리는 정의역 DD과 공역 FF, 매핑의 의미를 보기 쉽게 다음과 같이 표현합니다. DD에서 FF로의 함수 또는 DD를 FF로 매핑하는 함수 f:D→Ff : D \rightarrow F





항등 함수

임의의 정의역 DD에 대해 함수 idD:D→Did_D : D \rightarrow D 를 DD 에 대한 항등함수라 합니다. 모든 d∈Dd \in D 에 대해 항등함수는 다음과 같이 정의합니다. idD(d)=did_D(d) = d





합성 함수

두 함수 f:A→Bf : A \rightarrow B 와 g:B→Cg: B \rightarrow C 에 대해 함수 g∘fg \circ f 는 gg 와 ff 의 합성함수라 하며 정의역은 AA, 공역은 CC 입니다. 다음처럼 쓸 수 있습니다. (g∘f)(x)=g(f(x))(g \circ f)(x) = g(f(x)) 만약 함수 ff의 치역이 함수 gg 의 정의역에 포함되지 않는다면 g∘fg \circ f 처럼 쓸 수 없습니다. 합성 함수는 결합법칙이 성립합니다. h∘(g∘f)=(h∘g)∘fh \circ (g \circ f) = (h \circ g) \circ f 합성 함수의 계산 순서는 오른쪽에서 왼쪽으로 진행되기 때문에 굳이 함수의 합성에 괄호를 사용할 필요가 없습니다. 단순히 h∘g∘fh \circ g \circ f 라 써도 무방합니다.





단사 함수, 전사 함수, 역함수

단사 함수는 공역 VV의 원소 v 에 대해 매핑되는 하나의 정의역 원소만 가지는 경우입니다. 좀 더 수학적으로 정의하면 함수 f:D→Ff : D \rightarrow F 가 있다고 할 때 모든 x,y∈Dx, y \in D 에 대해 f(x)=f(y)f(x) = f(y) 가 x=yx = y 를 의미하면 ff 는 단사함수(one to one)라 합니다.
전사 함수는 공역이 모두 치역이 되는 경우입니다. 역시 좀 더 수학적으로 정의하면 위의 함수 ff 에서 만약 모든 z∈Fz \in F 에 대해 f(x)=zf(x) = z 를 만족하는 x∈Dx \in D 가 존재하면 ff 는 전사함수(onto)라 합니다.
역함수는 말그대로 원래의 함수를 뒤집은 경우입니다. 함수 ff 와 gg 가 있다고 할때 ff 는 {A,...,Z}\{A, ..., Z\} 에서 {1,...,26}\{1, ..., 26\} 로의 함수, gg 는 {1,...,26}\{1, ..., 26\} 에서 {A,...,Z}\{A, ..., Z\} 로의 함수입니다. ff는 A...ZA ... Z 까지 각각의 알파벳을 그 순서 1...261 ... 26 에 매핑하고 gg 는 그 반대로 숫자를 알파벳에 매핑합니다. 각 함수는 서로를 거꾸로 뒤집는 함수입니다. 여기서 g∘fg \circ f 는 항등함수고 f∘gf \circ g 도 항등함수입니다. gg 는 ff 의 역함수, ff 는 gg 의 역함수입니다. 따라서 다음과 같이 정의할 수 있습니다.

다음 조건이 만족하면 함수 ff 와 gg 는 역함수이다.

  • f∘gf \circ g 가 정의되고 gg 의 정의역에 대해 항등함수다.
  • g∘fg \circ f 가 정의되고 ff 의 정의역에 대해 항등함수다.
  • 모든 함수가 역함수를 가지지는 않고 역함수를 가지는 함수는 가역적이라고 합니다.

  • 역함수는 단사함수이자 전사함수입니다.

    역함수
  • 모든 함수는 많아야 하나의 역함수를 가집니다. 함수 f:U→Vf: U \to V에 대해 역함수 g1g_1, g2g_2가 존재한다고 가정하겠습니다. f(u)=v (v∈V)f(u) = v \text{ }(v \in V)일때 g1g_1, g2g_2는 ff의 역함수이므로 g1(v)=ug_1(v) = u, g2(v)=ug_2(v) = u입니다. 따라서 g1(v)=g2(v)g_1(v) = g_2(v)로 역함수 g1g_1과 g2g_2는 같습니다.
  • 만약 ff 와 gg 가 가역함수이고 f∘gf \circ g 가 존재하면 f∘gf \circ g 는 가역함수이고 (f∘g)−1=g−1∘f−1(f \circ g)^{-1} = g^{-1} \circ f^{-1} 입니다. ∵(f∘g)∘(g−1∘f−1)=f∘id∘f−1=f∘f−1=id\because (f \circ g) \circ (g^{-1} \circ f^{-1}) = f \circ id \circ f^{-1} = f \circ f^{-1} = id
선형대수학
# 코딩 더 매트릭스# python