Function
1. Function
1-1. Definition
Definition 1
A와 B를 set라고 할 때, $\forall x \in A$에 대해 unique한 $y \in B$가 있는 경우 A relation f from A to B를 function이라고 부른다.
$f \subseteq A \times B$ 이다.
모든 x에 대한 함숫값이 있어야 하고,
그 함숫값은 하나만 존재해야 한다.
1-2. Terminology
f : $A \rightarrow B$ 그리고 f(a) = b일 때,
A = the domain of f
B = the codomain of f
b = image of a under f
a = pre-image of b under f
The range R = $\{b|(a, b) \in f$ for some a $\}$
$R \subseteq B$
Definition 2
f : $A \rightarrow B$ and $S \subseteq A$일 때, S의 image의 집합을
$f(S) = \{f(w) | w \in S\}$ 로 표시 가능하다.
$f(A) = R /subseteq B$
1-3. Operators
Definition 3
An n-ary operator $O_n$ over the set S is a function from the set of ordered n-tuples of elements of S to S itself
연산을 해도 codomain은 S로!
$O_n : S^n /rightarrow S$
1-4. Function Operators
Definition 4
아무 binary operator에 대해 ($\bullet$ : $B \times B \rightarrow B$) and two functions $f : A \rightarrow B$ 그리고 $g : A \rightarrow B$라면 function $f \bullet g$ 는
$\forall a \in A, (f \bullet g)(a) = f(a) \bullet g(a)$
f와 g는 같은 domain과 codomain을 가져야 한다!
1-5. Function Composition
Definition 5
$g : A \rightarrow B, f : B \rightarrow C$인 두 함수에 대해서 $f \circ g$는
$f \circ g = \{<x,z>|(\exists y \in B)(<x, y> \in g\ \land <y,z> \in f)\}$
$(f \circ g)(x) = z = f(g(x))$
Theorem 1
Composition of function은 associative하지만 commutative하지는 않음!!
1-6. Restiction and Extension
Definition 6
만약 $f : X \rightarrow Y and A \subseteq X$ 그리고 $f \cap (A \times Y)$가 A to Y일 때, the restriction of f to A라고 부르고 f/A로 표기한다.
$f \subseteq X \times Y$, the restriction $f/A \subseteq A \times Y$
1-7. Partial Function
Definition 7
X와 Y가 set일 때, partial function f with domain X and codomain Y는 $X' \subseteq X$인 X'에 대해 X' to Y의 함수 관계를 가질 때를 말한다. X'는 domain of definition of f이다.
ex)
$f : \mathbb{Z} \rightarrow \mathbb{R}$ 일 때, $f(n) = \sqrt{n}$은 partial function from $\mathbb{Z}$ to $\mathbb{R}$이다. the domain of definition은 the set of non-negative integer다.
2. Type of function
2-1. Injective Functions & Surjective Function
Definition 8(Injective Functions)
Injectove function은 one-to-one(일대일) 함수라고도 불리는데, range에 존재하는 모든 원소가 단지 하나의 pre-image를 가지는 함수를 말한다. 즉 $f(x) = f(y),\ then \ x = y$이다.
Definition 9(Surjective Functions)
$f : A \rightarrow B$가 surjective 또는 onto 함수이려면, $\forall b \in B, \exists a \in A(f(a) = b)$이어야 한다. 모든 codomain에 있는 원소가 하나 이상의 pre-image를 가져야 한다!
2-2. Bijective Functions
Definition 10
A function $f : A \rightarrow B$가 bijective이려면 injective하고 surjective 해야 한다!
Theorem 2
$f \circ g : A \rightarrow C$가 composite function이고, $g : A \rightarrow B and f : B \rightarrow C$일 때,
(1) f와 g가 surjective라면 $f \circ g$는 surjective이다.
(2) f와 g가 injective라면 $f \circ g$는 injective이다.
(3) f와 g가 bijective라면, $f \circ g$는 bijective이다.
(4) $f \circ g$가 surjective라면, f는 surjective이다.
(5) $f \circ g$가 injecrive라면, g는 injective이다.
(6) $f \circ g$가 bijective라면, f는 surjective이고, g는 injective이다.
proof) (만약 f와 g가 surjective라면 $f \circ g$는 surjective이다.)
$f \circ g : A \rightarrow C$는 g와 f의 composition function이다.
(1) : f는 surjective이기 때문에, $\forall z \in C$에 대해 $<y, z> \in f$인 $y \in B$가 존재한다. f(y) = z
(2) : g는 surjective이기 때문에, 주어진 $y \in B$에 대해 $<x, y> \in g$인 $x \in A$가 존재한다. g(x) = y
위의 두 문장을 이용하여 f(g(x)) = z는 $\forall z \in C$에 대해 $\exists x \in A$이다.
따라서 $f \circ g$는 surjective이다.
2-3. Constant Fuctions & Identity Functions
Definition 11 (Constant Functions)
function $f : X \rightarrow Y$는 constant function이려면 $(\exists y \in Y)(\forall x \in X)(f(x) = y)$이어야 한다.
Definition 12 (Identity Functions)
Identity function $I_A : A \rightarrow A$는 $\forall a \in A$에 대해 I(a) = a인 함수이다. 해당 함수는 unique하다.
Identity 함수는 bijective이다!
2-4. Inverse Function
Definition 13
$f : X \rightarrow Y$가 bijection일 때, inverse function은 $f^{-1}$로 표시하고 f의 inverse relation이다.
Theorem 3
(1) f가 bijective function이면 $f^{-1}$도 bijective function이다.
(2) f가 bijective라면 $(f^{-1})^{-1} = f$이다.
만약 f가 bijective가 아니라면,
f가 injective가 아닐 경우 : $f^{-1}$은 하나의 pre-image에 두 개의 image가 매칭될 수 있다. => 함수의 정의에 위배
f가 surjective가 아닐 경우 : $f^{-1}$은 image를 가지지 않는 pre-image가 있을 수 있다, => 함수의 정의에 위배
2-5. Left Inverse & Right Inverse
Definition 14
$h : A \rightarrow B$ and $g : B \rightarrow A$일 때, $g \circ h = I_{A}$라면, g는 h의 left inverse이고, h는 g의 right inverse이다.
Theorem 4
$f : A \rightarrow B$이고 $A \neq \varnothing$일 때,
(1) f는 left inverse를 가진다. $\iff$ f는 injective일 때
(2) f는 right inverse를 가진다 $\iff$ f는 surjective일 때
(3) f는 left와 right inverse를 가진다. $\iff$ f는 bijective일 때,
(4) f가 bijective라면, left inverse와 right inverse는 동일하다.
proof) (f는 left inverse를 가진다. $iff$ f는 injective일 때)
(only if \Rightarrow) $g : B \rightarrow A$일 때, left inverse of $f : A \rightarrow B$이다. for some $x_1, x_2 \in A$에 대해
$$(g \circ f = I_A) \land (f(x_1) = f(x_2) \ Rightarrow (x_1 = x_2)) $$
을 보여야 한다.
$f(x_1) = f(x_2) = y$라고 하면, $g \circ f = I_{A}$에 의해 $(g \circ f)(x_1) = x_1$ and $(g \circ f)(x_2) = x_2$이다.
$$\exists u \in B <x_1, u> \in f, <u, x_1> \in g$$
$$\exists v \in B <x_2, v> \in f, <v, x_2> \in g$$
이다.
위의 가정을 다시 한 번 불러오면
$$y = u \because <x_1, y> \in f \land <x_1, u>$$
$$y = v \because <x_2, y> \in f \land <x_2, v>$$
인데, 하나의 pre-image에는 다수의 image를 가질 수 없기 때문에, $y = u = v$이고, $x_1 = x_2$가 된다.
$$x_1 = x_2 \because <u, x_1> \ in g, <v, x_2> \in g$$이다.
따라서 $f(x_1) = f(x_2) = u = v$일 때, $x_1 = x_2$인 것을 알 수 있다. f는 injective이다.
(if \Leftarrow) $f : A \rightarrow B$
우리는 f가 injective일 때, left inverse가 존재한다는 것을 보여줘야 한다.
$\forall y \in B일 때, either y \in f(A) or y \notin f(A)$이다. $f(A) \neq B$일 수 있기 때문이다.
따라서 $g : B \rightarrow A$인 함수 g를 정의하자.
$g(y) = x$ 만약 y가 range라면, f(x) = y일 때의 x가 g(y)의 값이다.
$g(y) = z$ 만약 y가 range가 아니라면 z는 임의의 값이다.
g는 모든 pre-image에 대해 단 하나씩의 값을 가지고 있고 때문에 valid한 함수이다.
$\forall y \in f(A), Unique\ \exists x \in A$이다. 왜냐하면 f는 injective이기 때문이다!
이는 $\forall y \in f(A), g(y) = x$라는 말로 쓸 수있다. $g \circ f$는 valid한 함수이기 때문에 $\forall a \in A, g(f(a)) = a$이다.
그러므로 g는 f의 left inverse이다.
Remark 1(An injection has a left inverse)
f(x) = x/2 : [0,1] -> [0.1] 라고 하면
$g(x) = 2x if x \in [0, 1/2]$
$g(x) = 0.9 otherwise$
라고 하면
g는 left inverse가 된다.
이는 injection fuctions f가 left inverse g를 가진다는 것을 알 수 있다.
proof) (f는 right inverse를 가진다. $iff$ f는 surjective일 때)
(only if \Rightarrow) $h : B \rightarrow A$에 대해 $f : A \rightarrow B$라고 한다면, $f \circ h = I_B$이다.
이것은
$$\forall b \in B, \exists a = h(b) \in A \ such \ that\ f(a) = b$$
을 의미한다. codomain B의 모든 원소에 대해서 pre-image 값을 가지기 때문에 f는 surjective이다.
(if \leftarrow) surjective한 함수 $f : A \rightarrow B$에 대해 right inverse를 가진다는 것을 보여야 한다.
$h : B \rightarrow A$f를 모든 $y \in B$에 대해
$$h(y) = x \ where\ f(x) = y$$
(하나의 image y에 대해 pre-image x는 여러개일 수 있지만, h(y)의 값을 정할 때 x를 이러한 pre-image 중 임의의 한개로 지정해주면 된다.)
$$\forall y \in B, f(h(y)) = f(x) = y,\ for \ some \ x \in A$$
라고 정의하면 h(y)는 right inverse가 된다.
Remark 2 (A surjection has a right inverse)
$f : \mathbb{Z} \rightarrow \{0, 1\}$ f(n) = n%2인 surjective function을 생각해보자
h(x) = x, $h : {0, 1} \rightarrow {0, 1}$ 이면 $f \circ h = I_{\{0,1\}}$ 이다.
하지만 f가 bijective하지는 않기 때문에 $f^{-1}$이 존재하지는 않는다!
여기선 내가
(proof) f has a left and a right inverse $\iff$ f는 bijective
(only if $\Rightarrow$)
f가 injective, surjective임을 보이면 됨.
위의 증명 이용
(if $\Leftarrow$)
injective일 때 left inverse가, surjective일 때 right inverse가 나오는 것을 구하면 됨.
(proof) f는 bijective $\Rightarrow$ f has a left and a right inverse
$f : A \Rightarrow B$일 때,
left inverse g는
$g(y) = x, if f(x) = y$일 때,
$g(y) = z if y \notin range of f(x)$일 때,
근데, bijection이기 때문에 $\forall y \in B \land y \in range of f(x)$이다.
따라서 $\forall y \in B, g(y) = x$이다.
surjective 또한 똑같이 정의 가능.
2-6. Permutation
Definition 15
set A의 permutation은 A 원소들의 순서를 갖춘 정렬을 의미한다.
모든 permutation은 bijection이다.
따라서 composite of two permutations도 permutation이다.
permutation은 composite operation에 대해 닫혀있다고(close) 표현할 수도 있다.
ex) Identity fuction 은 A의 permutation이다.