SmileCat

Coding The Matrix를 보다보면 후반부에 갈수록 앞서 본 용어들에 대해서 잊어버려 찾는 것을 반복하게 되어 정리해보며 읽어나가고자 한다.

집합(Set)

1 \in \{ 1, 2, 3, 4 \}

수학 객체를 모아 놓은 것으로, 집합에 속하는 각 객체는 많아야 한 번 그 집합에 나타나는 것으로 간주한다. 집합은 원소들 사이에 순서가 없으므로 집합 내 원소의 순서는 중요하지 않다.

S_1 \subseteq S_2

집합의 포함 관계는 위와 같이 나타내며, 두 집합이 같다는 것은 다음 두 단계를 사용하여 증명한다.

첫 번째 집합이 두 번째 집합에 포함됨을 증명한다.
두 번째 집합이 첫 번째 집합에 포함됨을 증명한다.

\mid S \mid

집합 S가 유한집합이면, |S|를 사용하여 집합의 크기(원소의 개수)를 나타낸다.

Ref

Ch1 - 1p

집합 - 위키백과

카테시안 곱(Cartesian product)

A \times B = \{ (a, b) \mid a \in A, b \in B \}

두 집합 A와 B의 카테시안 곱(데카르트 곱)은 a ∈ A 와 b ∈ B 의 모든 쌍 (a, b)으로 이루어진 집합이다.

Ref

Ch1 - 1p

곱집합 - 위키백과

함수(Function)

Ref

Ch1 - 2p

함수 - 위키백과

비공식

가능한 입력 집합 D의 각 원소에 대해 가능한 출력을 할당하는 규칙이다.

출력 : 함수에 의한 입력의 상(image), 함수값
입력 : 출력의 원상(pre-image)
정의역 : 가능한 입력 집합
공역 : 함수값이 선택되는 집합, 모든 원소가 함수값이 되어야하는 것은 아님
치역 : 모든 정의역 원소들에 대한 함수값들의 집합, 공역의 원소들 중 실제로 함수값이 되는 공역 원소들의 집합

공식

쌍 (a, b)들의 집합(무한 집합도 가능)이다.

예

정의역 {1, 2, 3,...} × {1, 2, 3,...}을 가지는 곱셈 함수는 아래와 같이 나타낼 수 있다.

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

매핑

함수 f에 대해, f에 의한 q의 상을 f(a)로 나타낼때,

r = f(a)

이면, q는 f에 의해 r로 매핑된다고 한다. (q ↦ r)

`D`에서 `F`로의 함수 or `D`를 `F`로 매핑하는 함수

f : D \to F

f : 함수
집합 D : 정의역
집합 F : 공역

주어진 정의역과 공역을 가지는 함수들의 집합에 대한 표기법

집합 D와 F에 대해, D에서 F로의 모든 함수는 아래와 같이 나타낸다.

F^D

Fact 1.3.9

임의의 유한 집합 D와 F에 대해,

\mid F^D \mid = {\mid F \mid}^{\mid D \mid}

Ref

Ch1 - 5p

함수 - 위키백과

항등함수

임의의 정의역 D에 대해, 아래를 만족하면 함등함수라 한다.

id_D : D \to D

모든 d ∈ D 에 대해, 항등함수는 다음과 같이 정의된다.

id_D (d) = d

Ref

Ch1 - 5p

항등함수 - 위키백과

함수의 합성

두 개의 함수를 결합하여 하나의 새로운 함수를 얻는 것이다.

f : A \to B\\ g : B \to C\\

위와 같이 주어진 함수 f와 g에 대해,

g \circ f : A \to C\\ x \in A 에 대해, (g \circ f)(x) = g(f(x))\\

합성 함수 g∘f는 정의역 A, 공역 C인 함수가 된다.(반드시, 함수 f의 치역이 함수 g의 정의역에 포함되어야 한다.)

Ref

Ch1 - 5p

함수의 합성 - 위키백과

함수 합성의 결합법칙

함수를 합성할 때 결합법칙이 성립한다.

Proposition 1.3.12

h \circ (g \circ f) = (h \circ g) \circ f

Ref

Ch1 - 6p

단사함수, 전사함수(Definition 1.3.14)

단사함수

함수 f : D ⟶ F 일때, 모든 x, y ∈ D에 대해, f(x) = f(y)는 x = y이면 단사함수이다.

전사함수

함수 f : D ⟶ F 일때, 모든 z ∈ F에 대해, f(x) = z를 만족하는 x ∈ D가 존재하면 전사함수이다.

Ref

Ch1 - 7, 8p

단사함수 - 위키백과

전사함수 - 위키백과

역함수(Definition 1.3.13)

다음 두 조건을 만족하면 함수 f와 g는 서로의 역함수이다.

g∘f가 정의되고, g의 정의역에 대해 항등함수이다.
f∘g가 정의되고, f의 정의역에 대해 항등함수이다.

모든 함수가 역함수를 가지는 것은 아니며, 역함수를 가지는 함수를 가역적이라고 한다.

가역함수는 단사함수이다. (Lemma 1.3.16)
가역함수는 전사함수이다. (Lemma 1.3.17)
함수가 가역적이 될 필요충분조건은 그 함수가 단사함수이며 동시에 전사함수인 경우이다.(전단사함수, Theorem 1.3.18)
모든 함수는 많아야 하나의 역함수를 가진다. (Lemma 1.3.19)

Ref

Ch1 - 7~9p

역함수 - 위키백과

가역함수를 합성한 함수의 가역성(Lemma 1.3.20)

만약 f와 g가 가역함수이고 f∘g가 존재하면, f∘g는 가역함수이고,

(f \circ g)^{-1} = g^{-1} \circ f^{-1}

이다.

Ref

Ch1 - 9p

프로시저(Procedure)

입력(매개변수)을 받아들여 출력(리턴값)을 생산하는 계산 절차에 대한 정확한 기술이다.

예

def mul(p, q): return p*q

Ref

Ch1 - 3p

프로시저 - 위키백과

계산 문제(Computational problem)

프로시저가 필요할 수도 있는 입력-출력에 대한 사양(스펙)(input-output specification)이다.

예

- input: 1보다 큰 정수의 쌍 (p, q)
- output: 곱 pq

Ref

Ch1 - 4p

프로시저, 계산 문제, 함수의 연관 관계

프로시저와는 달리, 함수 또는 계산 문제는 입력을 사용하여 출력을 어떻게 계산하는지에 대한 정보를 주지 않는다.
- 동일한 입출력 사양을 만족하거나 동일한 함수를 구현하는 많은 다른 프로시저가 존재한다.
때로는 동일한 프로시저가 다른 함수를 위해 사용될 수 있다.
함수와는 달리, 계산 문제는 모든 입력에 대해 하나의 유일한 출력을 명시할 필요는 없다.
함수와 계산 문제는 다르게 정의되지만 서로 연관되어 있다.
정의역 각 원소에 대해 프로시저를 적용하여 출력을 확인하는 방법으로 원상 문제를 풀면 비용이 클 수 있지만, 모든 함수에 적용 가능한 더 나은 방법은 없다.
원상 문제를 임의의 함수가 아니라 특정 종류의 함수에 적용하는 방법을 사용하면, 원상 문제를 풀기위한 빠른 프로시저가 존재하여도 실질적인 문제를 해결하는데 도움이되지 않을 수 있다.
계산산의 어려움과 가능성 사이에서 길을 찾는 것이 필요하다.
선형 함수들을 사용하여 실질적인 문제를 모델링하고 이 함수들을 사용하여 원상 문제를 풀 수 있다.