Functions and Relations 문서 원본 보기

[[분류:계산 이론 개론]]
[[분류:컴퓨터 공학]]
상위 문서: [[계산 이론 개론#Mathematical Objects|계산 이론 개론]]

==개요==
해당 문서에서는 함수(functions), 관계(relations)와 집합 사이의 관계에 대해 설명한다.

==Functions==
함수는 입력을 정의역(domain)에서 받아서 출력을 (codomain)에서 내놓는 블랙박스처럼 동작한다. 이때 중요한 것은 각 입력마다 단 하나의 출력만 존재한다는 것이다. 함수 F는 집합 A, B에 대해 데카르트 곱 <math>A \times B</math>의 부분집합이다. 이때 모든 <math>a \in A</math>에 대해 단 하나의 <math>b \in B</math>만 대응해야 한다. 따라서 함수의 정의를 집합을 통해서 나타내면 아래와 같다:
 <math>\forall a \in A \rightarrow \exists ! b \in B \land (a, b) \in F</math>

===Special Classes of Functions===
함수는 아래와 같이 정의된다.
* 일대일 함수<ref>단사, one-to-one, injective라고도 한다.</ref>: <math>\forall a\, a'\, b.(a,b)\in F \land (a',b)\in F \rightarrow a = a'</math>
* 전사<ref>onto, surjective라고도 한다.</ref>: <math>\forall b. b \in B \rightarrow (\exists a. (a,b)\in F)</math>
* 일대일 대응<ref>one-to-one correspondence, bijective라고도 한다.</ref>:<math>\forall b. b \in B \rightarrow (\exists ! a.(a,b)\in F)</math>

===Using Functions to Compare Sets===
집합의 크기와 함수의 성질은 서로 밀접한 관련을 맺고 있다.
* 동수성(Equinumerous): 집합 A, B가 같은 크기<ref><math>|A|=|B|</math></ref>라면, 이는 <math>A\rightarrow B</math> 사이에 bijection이 존재
* 카디널리티 비교: |A|<math>\le</math>|B|는 A<math>\rightarrow</math>B 사이에 injection이 존재
* Cantor–Schröder–Bernstein 정리: |A|<math>\le</math>|B|이고 |A|<math>\ge</math>|B|이면 |A|=|B|
* 비둘기집 원리(Pigeonhole Principle): |A|<math>\le</math>|B|일 때 B<math>\rightarrow</math>A 사이의 injection은 존재할 수 없다.

==Relations==
이항 관계(Binary relations)란 두 집합 A, B에 대해 이항 관계는 데카르트 곱 <math>A \times B</math>의 부분집합을 의미한다. 이는 예를 들면, 
* <math>A = \{1,2,3\}, B = \{4,5\}</math>
* <math>A\times B = \{(1,4),(1,5)(2,4),(2,5),(3,4),(3,5)\}</math>
* <math>R = \{(1,5),(3,5),(2,4)\}</math>

===More about Binary Relations===
<math>R \subseteq A\times A</math>를 만족하는 이항관계 R에 대해 아래와 같은 정의가 성립한다.
* reflexive: <math>\forall a. a\in A \rightarrow (a,a) \in R</math>
* symmetric: <math>\forall a\,\, b. (a, b) \in R \rightarrow (b,a) \in R</math>
* antisymmetic: <math>\forall a\,\, b. (a, b) \land (b, a) \in R \rightarrow a = b</math>
* transitive: <math>\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<ref>or linear</ref> order: a partial order R이 <math>\forall a b. (a, b) \in R \lor (b, a) \in R</math>을 추가로 만족. 즉, 모든 원소가 비교 가능하다.

==각주==