Basic Structures:Sets, Functions, Sequences, and Sums

2장은 기본적인 구조에 대해서 나온다.



Sets
집합은 정렬되지 않은 object의 collection이다. 집합 내의 object는 element, member로 불린다.
어떠한 집합 A의 모든 멤버가 다른 집합 B의 멤버일 경우 A는 B의 부분집합이다.
subset에서 equal을 제외한 것을 proper subset이라고 한다.

아.. 기호가 많은데 글로만 쓸려니 힘들다 'ㅁ'

어떠한 집합 S에 대해 |S|를 S의 cardinality 라고 하며 집합 S의 멤버의 갯수를 의미한다.
어떤 집합의 카디날리티가 유한하면, 유한집합이라고 하고..
카디날리티가 무한하면, 무한집합이라고 한다.

Power Set P(S)는 집합 S의 모든 부분집합을 원소로 가지는 특이한 집합이다.

Cartesian product는 카티션 곱이라고도 불리며
A×B는 집합 A의 원소 a와 집합 B의 원소 b에 대하여 (a,b)의 집합으로 정의된다.
뒤에서 나올 relation, function 등등의 기본이 된다.

R⊆A×B일때, R은 A로부터 B로 대응되는 relation으로 정의된다.
relation은 두 가지의 의미로 정의될 수 있다.
첫째로는 위에서 언급하였듯이 카디션 곱의 부분집합이고,
둘째로는 infix binary boolean operator이다. aRb가 있을 때, True, False 값을 반환해 주는 operator라고 생각할 수 있다.
이 부분은 매우 중요하다! 기억하자!

앞에서의 로직과 마찬가지로 집합도 연산들을 가지며 다 아는 것이기 때문에 생략..(Union 등등)

 

Functions
A에서 B로의 Function은 중학교, 고등학교때 배워서 너무나도 잘 알고 있듯이,
A의 모든 element에 대해서 B의 element가 정확하게! 하나만 대응되는 것이다.
그러므로, A에서 B로의 function은 A에서 B로의 relation의 subset이 된다.

함수에 있어서도 중학교 고등학교때 흔히 배웠던 개념이 나온다.
One-to-One Function과 Onto Function이다.
단사, 전사, 전단사로 배웠을 내용이다. 내가 학교다닐땐 일대일함수, 일대일대응 함수 등등으로 배웠던 것 같다;;

One-to-one Function은 injective function이라고도 하는데,
∀a∈A∀b∈B(a≠b⇒f(a)≠f(b))를 만족하는 것을 의미한다.
즉, 어떠한 function이 injection이면, A의 카디날리티보다 B의 카디날리티가 크거나 같다.

Onto Function은 surjective function이라고도 하며,
∀b∈B∃a∈A(f(a) =b)를 만족시키는 함수를 의미한다.
즉 range가 B 전체가 되는 것을 의미하며
어떠한 function이 surjection이면 B의 카디날리티보다 A의 카디날리티가 크거나 같다.

둘다 만족하는 것을 bijection이라고 하며, A와 B의 카디날리티는 같게 된다.
one-to-one correspondence라고도 불린다!

bijection일 경우 f의 inverse function이 존재하게 된다.


Sequence는 생략.. 자세히 나와있지가 않다.

마지막으로 set에 대해 약간 어렵고 중요한 개념이 나온다.
어떠한 집합이 유한집합이거나, Z+(양의 정수 집합)와 카디날리티가 같을 경우 countable하다고 한다.
countable 안하면 당연하게도 uncountable이다.

처음 이 개념을 배웠을 때, finite 개념과 헷갈렸었는데 유의해야 할 것 같다. countable의 경우에는 무한집합이더라도 Z+와 카디날리티가 같을 경우 countable로 취급한다는 점이 중요하다.
ㅎㅎ 참 흥미롭다. 우리가 어떤 수를 셀 때 하나, 둘, 셋 세니까 Z+만큼 센다면(카디날리티가 같다면) countable하다고 여기는 것이다. 누가 정의했는지 몰라도 참 신기하고 재밌다.

이 정의를 이용해 어떤 집합이 countable한가 안한가를 증명할 수 있어야 한다.
2진수를 셀 수 있는 지 정도는 증명을 알아두도록 하자. 2진수는? 셀수 없다.ㅋ


여기까지는 대학교 과정 이전의 내용들보다 약간 심화된 내용을 수학적으로 정의해 놓은 것 같다.