Search

이상엽/ 집합론/ 집합의 크기

집합의 분류

유한, 무한집합

동등

두 집합 X,YX, Y에 대하여 전단사함수 f:X→Yf : X \to Y 가 존재하면 X,YX, Y는 동등이다. (X≈YX \approx Y 또는 f:X≈Yf : X \approx Y)

유한, 무한집합

집합 XX의 적당한 진부분집합 YY가 XX와 동등하면 XX는 무한집합이다.
무한집합이 아닌 집합을 유한집합이라 한다.
ex) (0,1)≈R∴R(0, 1) \approx \mathbb{R} \therefore \mathbb{R}은 무한집합이다.

여러가지 정리

•
공집합 ∅\emptyset은 유한집합이다.
•
무한집합을 포함하는 집합은 무한이다.
•
유한집합의 모든 부분집합은 유한이다.
•
전단사함수 f:X→Yf : X \to Y에 대하여
◦
XX가 무한집합이면 YY도 무한집합이고
◦
XX가 유한집합이면 YY도 유한집합이다.
•
무한집합 XX의 부분집합 YY가 유한이면 X−YX - Y는 무한집합이다.

가부번, 비가부번 집합

가부번집합

집합 XX가 X≈NX \approx \mathbb{N} 일 때 XX 를 가부번집합이라 한다.
•
가부번집합은 번호를 붙일 수 있는 집합을 의미함.
◦
자연수 집합은 번호를 붙일 수 있으므로 가부번 집합이다. --1 다음은 2 그 다음 3이므로
◦
실수 집합은 번호를 붙일 수 없으므로 비가부번 집합이 된다. --1 다음 수를 어떤 것으로 정의할 수가 없음.

가산집합

유한집합이나 가부번집합을 가산집합이라 한다.

여러가지 정리

•
가산집합의 부분집합은 가산집합이다.
•
가부번집합들의 합집합은 가부번이다.
•
N×N\mathbb{N} \times \mathbb{N}은 가부번집합이다.
•
Q\mathbb{Q}은 가부번집합이다.
◦
가부번 집합을 합하거나 곱해도 가부번 집합이다. --지수로 올리면 얘기가 달라짐.
•
R\mathbb{R}의 부분집합 (0,1)(0, 1)은 비가부번이다.
•
모든 무리수의 집합은 비가부번집합이다.
◦
비가부번 집합인 실수 집합은 유리수와 무리수 집합의 합집합인데, 유리수 집합은 가부번 집합이므로 무리수 집합이 비가부번 집합이어야 한다.
•
C\mathbb{C}은 비가부번집합이다. (복소수 집합)

기수

기수의 개념

기수

집합의 크기를 나타내는 수. cardAcard A 또는 #A\# A
•
각 집합 AA에 대해 #A \# A는 유일하다.
•
#A\# A 에 해당하는 집합 AA는 항상 있다.
•
A=∅⇔#A=0A = \emptyset \Leftrightarrow \# A = 0
•
A {1,2,...,k}A ~ \{ 1, 2, ... , k \}이면 #A=k(k∈N)\# A = k ( k \in \mathbb{N})
•
A≈B⇔#A=#BA \approx B \Leftrightarrow \# A = \#B
•
(배열의 길이라고 생각하면 편하다)

유한기수, 초한기수

유한기수는 유한집합의 기수이고, 초한기수는 무한집합의 기수
•
대표적인 초한기수
◦
#N=ℵ0\# \mathbb{N} = \aleph_{0} 가부번집합의 기수 (알레프 제로라고 읽음)
◦
#R=ς\# \mathbb{R} = \varsigma 연속체의 기수 (시그마라고 읽음)

#A < #B

AA는 BB의 한 부분집합과 동등이고, BB는 AA의 어떠한 부분집합과도 동등이지 않다.
•
#A≤#A\# A \leq \# A
•
AA가 BB의 부분집합과 동등이고, BB도 AA의 부분집합과 동등이면 AA와 BB는 동등이다. (#A=#B\# A = \# B) - 칸토어-번슈타인 정리
•
#A≤#B\# A \leq \# B이고 #B≤#C\# B \leq \# C이면 #A≤#C\# A \leq \# C이다.

기수의 연산

기수 합

서로소인 두 집합 A,BA, B의 기수를 각각 a,ba, b 라고할 때, a+b=#(A∪B)a + b = \# (A \cup B)

기수 곱

집합 A,BA, B의 기수를 각각 a,ba, b 라고할 때, ab=#(A×B)ab = \# (A \times B)

연산 법칙

임의의 기수 x,y,zx, y, z에 대하여 다음이 성립한다.
•
교환법칙
◦
x+y=y+xx + y = y + x
◦
xy=yxxy = yx
•
결합법칙
◦
(x+y)+z=x+(y+z)(x + y) + z = x + (y + z)
◦
(xy)z=x(yz)(xy)z = x(yz)
•
분배법칙
◦
x(y+z)=xy+xzx(y+z) = xy + xz
•
(기수 자체는 숫자인데, 기수의 연산은 그 숫자의 값이 위의 결과를 만족한다고 보는게 아니라, 그 기수가 대응되는 집합과의 관계가 위 조건을 만족한다는 의미)

여러가지 정리

•
ℵ0+ℵ0=ℵ0\aleph_{0} + \aleph_{0} = \aleph_{0}
•
ς+ς=ς\varsigma + \varsigma = \varsigma
•
ℵ0+ς=ς\aleph_{0} + \varsigma = \varsigma
•
ℵ0ℵ0=ℵ0\aleph_{0} \aleph_{0} = \aleph_{0}
•
ςς=ς\varsigma \varsigma = \varsigma
•
ℵ0ς=ς\aleph_{0} \varsigma = \varsigma

기수의 지수

집합 A,BA, B에 대하여 #A=m,#B=n\# A = m, \# B = n 일 때
•
BA={f∣f:A→B}B^{A} = \{ f | f : A \to B \}
◦
A에서 B로 가는 함수를 끌어 모은 집합. 지수에서 밑으로 가는 모습
◦
ex) A={1,2,3},B={4,5}A = \{ 1, 2, 3 \}, B = \{ 4, 5 \} 일 때, f:A→BXf : A \to BX의 총 개수
▪
2×2×2=8=23=#B#A2 \times 2 \times 2 = 8 = 2^{3} = \#B^{\#A}
•
#(BA)=nm\# (B^{A}) = n^{m}
•
B={0,1}B = \{ 0, 1 \} 일 때, BA={0,1}A=2AB^{A} = \{ 0, 1 \}^{A} = 2^{A}

여러가지 정리

•
집합 XX에 대하여 #X=x\# X = x 일 때 #P(X)=2x\# P(X) = 2^{x}
◦
ex) X={1,2,3}X = \{ 1, 2, 3 \} 일 때
▪
P(X)={∅,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}P(X) = \{ \emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\} \}
▪
#P(X)=8\# P(X) = 8
•
기수 x,y,zx, y, z 에 대하여
◦
xyxz=xy+zx^{y} x^{z} = x^{y+z}
◦
(xy)z=xyz(x^{y})^{z} = x^{yz}
◦
(xy)z=xzyz(xy)^{z} = x^{z} y^{z}
•
ς=ℵ0ℵ0=ςℵ0\varsigma = \aleph_{0}^{\aleph_{0}} = \varsigma^{\aleph_{0}}
◦
ℵ0\aleph_{0} 끼리의 합이나 곱은 여전히 ℵ0\aleph_{0}지만, 지수로 올리면 ς\varsigma가 된다.
◦
ς\varsigma에 ℵ0\aleph_{0}를 지수로 올려도 ς\varsigma 가 된다.
•
2c=ℵ0c=ςc2^{c} = \aleph_{0}^{c} = \varsigma^{c}
◦
2c2^{c}는 실수집합의 멱집합
Made with