Functions and Relations

상위 문서: 계산 이론 개론

개요

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

Functions

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

$\mathrm{\forall }a\in A\to \mathrm{\exists }!b\in B\wedge (a,b)\in F$

Special Classes of Functions

함수는 아래와 같이 정의된다.

• 일대일 함수: $\mathrm{\forall }a{a}^{\prime }b.(a,b)\in F\wedge (a^{\prime },b)\in F\to a=a^{\prime }$
• 전사: $\mathrm{\forall }b.b\in B\to (\mathrm{\exists }a.(a,b)\in F)$
• 일대일 대응:$\mathrm{\forall }b.b\in B\to (\mathrm{\exists }!a.(a,b)\in F)$

Using Functions to Compare Sets

집합의 크기와 함수의 성질은 서로 밀접한 관련을 맺고 있다.

• 동수성(Equinumerous): 집합 A, B가 같은 크기라면, 이는 $A\to B$ 사이에 bijection이 존재
• 카디널리티 비교: |A|$\le$|B|는 A$\to$B 사이에 injection이 존재
• Cantor–Schröder–Bernstein 정리: |A|$\le$|B|이고 |A|$\ge$|B|이면 |A|=|B|
• 비둘기집 원리(Pigeonhole Principle): |A|$\le$|B|일 때 B$\to$A 사이의 injection은 존재할 수 없다.

Relations

이항 관계(Binary relations)란 두 집합 A, B에 대해 이항 관계는 데카르트 곱 $A\times B$의 부분집합을 의미한다. 이는 예를 들면,

• $A=\{1,2,3\},B=\{4,5\}$
• $A\times B=\{(1,4),(1,5)(2,4),(2,5),(3,4),(3,5)\}$
• $R=\{(1,5),(3,5),(2,4)\}$

More about Binary Relations

$R\subseteq A\times A$를 만족하는 이항관계 R에 대해 아래와 같은 정의가 성립한다.

• reflexive: $\mathrm{\forall }a.a\in A\to (a,a)\in R$
• symmetric: $\mathrm{\forall }ab.(a,b)\in R\to (b,a)\in R$
• antisymmetic: $\mathrm{\forall }ab.(a,b)\wedge (b,a)\in R\to a=b$
• transitive: $\mathrm{\forall }abc.(a,b)\wedge (b,c)\in R\to (a,c)\in R$
• an equivalance: 이항 관계 R이 reflexive, symmetric, and transitive
• a partial order: 이항 관계 R이 reflexive, antisymmetric, and transitive
• a total order: a partial order R이 $\mathrm{\forall }ab.(a,b)\in R\vee (b,a)\in R$을 추가로 만족. 즉, 모든 원소가 비교 가능하다.