상위 문서: 계산 이론 개론
개요
해당 문서에서는 함수(functions), 관계(relations)와 집합 사이의 관계에 대해 설명한다.
Functions
함수는 입력을 정의역(domain)에서 받아서 출력을 (codomain)에서 내놓는 블랙박스처럼 동작한다. 이때 중요한 것은 각 입력마다 단 하나의 출력만 존재한다는 것이다. 함수 F는 집합 A, B에 대해 데카르트 곱 [math]\displaystyle{ A \times B }[/math]의 부분집합이다. 이때 모든 [math]\displaystyle{ a \in A }[/math]에 대해 단 하나의 [math]\displaystyle{ b \in B }[/math]만 대응해야 한다. 따라서 함수의 정의를 집합을 통해서 나타내면 아래와 같다:
[math]\displaystyle{ \forall a \in A \rightarrow \exists ! b \in B \land (a, b) \in F }[/math]
Special Classes of Functions
함수는 아래와 같이 정의된다.
- 일대일 함수[1]: [math]\displaystyle{ \forall a\, a'\, b.(a,b)\in F \land (a',b)\in F \rightarrow a = a' }[/math]
- 전사[2]: [math]\displaystyle{ \forall b. b \in B \rightarrow (\exists a. (a,b)\in F) }[/math]
- 일대일 대응[3]:[math]\displaystyle{ \forall b. b \in B \rightarrow (\exists ! a.(a,b)\in F) }[/math]
Using Functions to Compare Sets
집합의 크기와 함수의 성질은 서로 밀접한 관련을 맺고 있다.
- 동수성(Equinumerous): 집합 A, B가 같은 크기[4]라면, 이는 [math]\displaystyle{ A\rightarrow B }[/math] 사이에 bijection이 존재
- 카디널리티 비교: |A|[math]\displaystyle{ \le }[/math]|B|는 A[math]\displaystyle{ \rightarrow }[/math]B 사이에 injection이 존재
- Cantor–Schröder–Bernstein 정리: |A|[math]\displaystyle{ \le }[/math]|B|이고 |A|[math]\displaystyle{ \ge }[/math]|B|이면 |A|=|B|
- 비둘기집 원리(Pigeonhole Principle): |A|[math]\displaystyle{ \le }[/math]|B|일 때 B[math]\displaystyle{ \rightarrow }[/math]A 사이의 injection은 존재할 수 없다.
Relations
이항 관계(Binary relations)란 두 집합 A, B에 대해 이항 관계는 데카르트 곱 [math]\displaystyle{ A \times B }[/math]의 부분집합을 의미한다. 이는 예를 들면,
- [math]\displaystyle{ A = \{1,2,3\}, B = \{4,5\} }[/math]
- [math]\displaystyle{ A\times B = \{(1,4),(1,5)(2,4),(2,5),(3,4),(3,5)\} }[/math]
- [math]\displaystyle{ R = \{(1,5),(3,5),(2,4)\} }[/math]
More about Binary Relations
[math]\displaystyle{ R \subseteq A\times A }[/math]를 만족하는 이항관계 R에 대해 아래와 같은 정의가 성립한다.
- reflexive: [math]\displaystyle{ \forall a. a\in A \rightarrow (a,a) \in R }[/math]
- symmetric: [math]\displaystyle{ \forall a\,\, b. (a, b) \in R \rightarrow (b,a) \in R }[/math]
- antisymmetic: [math]\displaystyle{ \forall a\,\, b. (a, b) \land (b, a) \in R \rightarrow a = b }[/math]
- transitive: [math]\displaystyle{ \forall a b c. (a, b) \land (b, c) \in R \rightarrow (a, c) \in R }[/math]
- an equivalance: 이항 관계 R이 reflexive, symmetric, and transitive
- a partial order: 이항 관계 R이 reflexive, antisymmetric, and transitive
- a total[5] order: a partial order R이 [math]\displaystyle{ \forall a b. (a, b) \in R \lor (b, a) \in R }[/math]을 추가로 만족. 즉, 모든 원소가 비교 가능하다.