2) 함수와 관계

함수: 한 집합의 원소를 각각 다른 집합의 단일 원소로 배정하는 규칙

f가 한 함수라 한다면 첫번째 집합을 함수 f의 정의역이라 하며, 두번째 집합을 치역이라 한다. 이러한 함수를 아래와 같이 표기한다.

$$f:S_1→S_2$$

 

전체 함수, 부분함수: 함수 f의 정의역이 S_1과 같은경우 f를 "전체함수"라 하고, 그렇지 않을경우 "부분함수"라한다.

 

순위: f(n)과 g(n)을 정의역이 양의 정수들의 부분집합인 함수라 했을때, 충분히 큰 모든 n에 대해 

 

$$f(n)<=c|g(n)|$$을 만족하는 상수 c가 존재할 시 f의 순위가 g의 순위보다 높지 않다고 한다. 이를 아래와 같이 표기한다.

$$f(n)=O(g(n))$$

그리고  $$|f(n)|>=c|g(n)|$$이 성립하는 상수 c가 존재할 시 f의 순위가 g의 순위보다 낮지 않다고 한다. 이를 아래와 같이 표기한다.

$$f(n)=Ω(g(n))$$

그리고

$$c_1|g(n)|<= |f(n)| <= c_2|g(n)|$$이 성립하는 c_1,c_2가 존재한다면, f와 g는 같은 크기 순위를 같는다고 하며 이를

$$f(n)=O(g(n))$$

으로 표기한다. 상수계수와 낮은순위의 항들은 무시한다. n이 커짐에 따라 그 값들은 전체 값에 비하면 아무것도 아니기 때문이다.

 

관계 : 함수는 {(x_1,y_1),(x_2,y_2),....}같이 표현 할 수 있으며 x_i는 정의역의 원소이고 y_i는 치역의 대응값이다. 함수를 순서쌍으로 나타내기 위해서는 각 x_i가 집합내에서의 순서쌍에서 첫번째 위치에 한번만 나타나야 한다. 이를 만족하지 않을경우 이를 함수라 부를수 없으며, 이를 관계라 한다.

 

동치관계: 관계의 한종류, 동치의 개념을 일반화. 하나의 순서쌍이 동치관계에 있음을 표기할때는 "x≡y"로 표기한다.