[집합] 기본 개념
Math/Logic/Set/Func.2008. 11. 20. 00:34 |전체집합 ( Universal Sets )
Domain of discourse 를 나타내는 집합을 전체집합 U 로 놓고, 특별한 언급이 없더라도 논의되는 모든 집합들은 원소를 U에서 취한다.
집합의 원소의 개수 ( Number of elements )
집합 A의 원소의 개수를 |A| 로 표기하기로 한다.
원소의 개수가 유한개인 집합을 유한집합(finite set) , 무한개인 집합을 무한집합(infinite set) 이라고 한다.
이후에, 무한집합들에 대해서 까지 원소의 개수 개념을 확장하여 카디널리티(cardinality)를 정의하고 마찬가지로 |A| 로 표기한다.
특히, 유한집합에 대한 카디널리티는 원소의 개수이다.
집합의 상등 ( Equality of sets )
A=B ≡ ∀x ( x∈A ⇔ x∈B )
부분집합 (Subsets)
A⊂B ≡ ∀x ( x∈A ⇒ x∈B )
A를 B의 부분집합, B를 A의 super set 이라고 부른다.
모든 집합은 자기자신의 부분집합이고, 공집합은 모든집합의 부분집합이다. 이것은 정의를 통해 간단히 증명되는 정리이므로 증명을 생략한다.
특히, 자기자신이 아닌 부분집합을 proper subset 이라고 칭하기로 한다.
또한, 상등과 부분집합의 정의로 부터 다음의 정리는 자명하다.
A=B ≡ A⊂B ∧ A⊃B
진리집합 (truth sets)
the truth set of the propositional function p(x) is the set P = { x | p(x) }
교집합 (Intersections)
A∩B = { x | x∈A ∧ x∈B }
A∩B = φ 일때, A와 B를 서로 disjoint 라고 한다.
합집합 (Unions)
A∪B = { x | x∈A ∨ x∈B }
여집합 (Complements)
relative complement of A in B : A ＼ B = { x | x∈A ∧ x !∈ B } 단, !∈ 는 속하지 않는다의 기호로 사용했다.
A ＼ B 을 A - B 로도 쓴다.
특히, Ac = U ∖ A 로 쓰기로 한다.
따라서, A ＼ B = A ∩ Bc 으로 쓸 수 있다.
다음의 정리는 모두 자명하다. ( 모두 논리식으로 간단히 증명가능함 )
(Ac)c = A
A ∩ Ac = φ , A ∪ Ac = U
φc = U , Uc = φ
A ⊂ B ⇔ Ac ⊃ Bc
(A∪B)c = (Ac∩ Bc) , (A∩B)c = (Ac∪Bc) : De Morgan's Laws
디스조인트 셋과 여집합에 대한 다음의 정리가 성립한다.
A∩B = φ ⇔ A ⊂ Bc ⇔ Ac ⊃ B
따라서 다음의 정리도 참이다.
A ⊂ B ⇔ A ∩ Bc = φ ⇔ A ＼ B = φ
멱집합 (Power sets)
P(A) = { x | x ⊂ A }
멱집합에 대한 다음의 정리는 자명하다.
A⊂B ⇒ P(A) ⊂ P(B)
또한 다음의 정리들이 성립한다.
P(A) ∩ P(B) = P(A∩B)
P(A) ∪ P(B) ⊂ P(A∪B)
유한 멱집합의 카디널리티
|A| = n 이면, |P(A)| = 2 n 이다.
컴비네토리얼 프루프로 간단히 증명된다. A의 각 원소를 부분집합에 포함시킬까 말까라는 두가지 선택권으로 부터 위의 정리는 자명하다.
또한 이것으로 부터 이항계수에 대한 다음의 정리도 증명할 수 있다.
역시 컴비네토리얼 프루프로 간단히 증명되는데, 부분집합을 원소가 0 개인것, 1개인것, ... , n개인것들의 개수를 모두 더한것은 전체부분집합의 개수와 같고, 원소의 개수가 r 개인 부분집합의 수는, n개의 원소에서 r개를 추출한 것이므로 nCr 이되어, 위의 증명이 완료된다.
무한집합의 경우에도, 멱집합의 카디널리티가 원래의 집합보다 크다 ( Cantor's theorem) 는 것을 증명할 수 있는데, 이것은 나중에 살펴본다.
