[해석학] Set theory: Cardinality

 

 

 

 

 

Cardinality(관계수)

 

Notes for function

 

• 어떠한 집합 A가 있을 때 원소의 개수를 관계수라고 한다. ex) A = {1,2,3,4}, then cardinality of A is 4
• 만약 집합 A와 집합 B가 1-1 대응이고 (bijection) 같은 cardinality 라면 A~B라고 표현한다.

 

 

 

• The relation "~" has the following properties (Equivalence relation):
• 1) A~A (Reflexive)
• 2) A~B and B~C => A~C (Transitive)
• 3) A~B => B~A (Symmetric)
• ex) 1) A and B are infinite sets, A~B <=> #A = #B (A와 B의 원소 개수는 같다)
•       2) N = {1,2,3,...}, 2N = {2,4,6,...}. f(n) = 2n으로 연속적으로 1-1 대응 시킬 수 있으므로 N~2N

 

 

 

 

Finite Set Definition

N_n = {1,2,3,...,n}

• A set A is finite if A~N_n for some n in N; ∅ is also considered to be finite
• A is infinite if it is not finite
• A is countable if A~N
• A is not countable if A is neither finite nor countable
• A is at most countable if it is finite or countable
• ex) N is countable. kN is countable for all k in N.

Ex) Prove that Z is countable: 

 

- Consider f: N->Z, f(n) = n/2 if n is even, -(n-1)/2 if n is odd.

 

Z is countable since all pairs 1-1 exists

 

 

 

Ex) Prove that Z*Z is countable:

 

- Consider Z*Z = {(n,m)| n,m in Z} then,

 

All pairs 1-1 are possible

 

 

 

 

Ex) Prove interval (0,1) is not countable <실수가 자연수보다 많다>

 

Cantor's diagonal argument(칸토어의 대각선 논법)을 사용

- Consider some of the bijection funtion that f:N -> (0,1), then

f(1) = 0.a11 a12 a13 a14....

f(2) = 0.a21 a22 a23 a24...

f(3) = 0.a31 a32 a33 a34...

...

f(n) = 0.an1 an2 an3 an4...

...

1-1 대응을 해놨다고 가정을 해보자.

그다음 (0,1) 범위에 있는 x를 가져올건데, ann(ex: a11 a22 a33 ....)과 다른 숫자를 가져오면,

x = 0.b1 b2 b3 .... (b1 != a11, b2 !=a22 ...) 

지금껏 대응했던 것과 완전히 다른 실수를 만들어낼수있고, 실제로 이 실수는 무한히 새로 만들 수 있다.

따라서 실수가 자연수보다 많다.

 

 

 

 

• Lemma: Every infinite subset of a countable set is countable

증명은 다음 아래의 사진과 같다.

 

countable example

 

 

 

 

 

 

 

Continuum

• Definition: We say that a set S is a continuum if S~R

countable example