부분집합

1. 개요

부분집합은 주어진 집합의 원소 중 일부 또는 전부를 포함하는 집합을 의미한다. 집합 A의 모든 원소가 집합 B의 원소일 경우, A는 B의 부분집합이며, 기호로는 A ⊆ B로 나타낸다. A가 B의 부분집합이면서 두 집합이 같지 않을 경우, A는 B의 진부분집합이며, 기호로는 A ⊊ B로 표기한다. 부분집합 관계는 반사율, 추이성, 반대칭성을 가지며, 멱집합 위에서 부분 순서를 이룬다. 멱집합은 주어진 집합의 모든 부분집합을 원소로 하는 집합이며, 포함 관계는 멱집합 위에 부분 순서 관계를 정의한다.

2. 정의, 용어, 표기법

집합 A, B가 주어졌을 때, A의 모든 원소가 B의 원소이면, 즉
:$\backslash forall\; x\; \backslash in\; A\; :\; x\; \backslash in\; B$
가 성립하면, 'A는 B에 포함된다(include, contain^영어)'. 또는 'B는 A를 포함한다'라고 한다. 기호로는
:$A\; \backslash subseteq\; B$ 또는 $B\; \backslash supseteq\; A$
로 나타낸다.

A가 B의 부분집합이지만 같지는 않은 경우, 즉 A가 B의 부분집합이고, A에 속하지 않는 B의 원소가 적어도 하나 존재하는 경우, A는 B의 진부분집합이라고 한다. 기호로는
:$A\; \backslash subsetneq\; B$ 또는 $B\; \backslash supsetneq\; A$
로 나타낸다.

때로는 부분집합, 진부분집합 관계를 각각 $\backslash subset,\; \backslash subsetneq$ 기호로 나타내거나, 각각 $\backslash subseteq,\; \backslash subset$로 나타낸다.

드물게 A가 B의 부분집합이라 하는 대신 B가 A의 상위집합(上位集合, superset^영어), A가 B의 진부분집합이라 하는 대신 B가 A의 진상위집합이라 표현하는 경우도 있다.

A가 B의 부분집합임을 A ⊆ B로 나타내고, A가 B의 진부분집합임을 A ⊂ B로 나타낸다. 부등식에서 부등호를
:x ≤ y 이고 x ≠ y일 때 x < y로 쓴다.
는 표기법에 맞춰 포함 관계에서도
: A ⊆ B 이고 A ≠ B일 때 A ⊂ B로 쓴다.
는 표기법은 자연스럽다. 하지만 이와는 다른 방식도 몇 가지 존재하며, 통일되어 있지 않다. 예를 들어, A가 B의 부분집합임을 A ⊂ B로 나타내고, A가 B의 진부분집합임을 A ⊊ B로 나타내는 방식이 있다. 이 외에도 부분집합에는 ⊆를 사용하고, 진부분집합에는 ⊂ 이고 ≠를 사용하는 경우도 있다. 진부분집합임을 명시할 수 있는 ⊊라는 기호를 준비하는 경우도 있다. 진부분집합임을 언급하는 부분이 적고 번거롭지 않다면 혼란을 피하기 위해 일일이
:A ⊆ B 이고 A ≠ B
:A ⊂ B 이고 A ≠ B
와 같이 "그리고 A ≠ B"라는 조건을 명기하는 경우도 있다.

3. 부분집합의 성질

* 공집합은 모든 집합의 부분집합이다.
* A ⊆ A (자기 자신은 자신의 부분집합이다.)
* A ⊆ B 이고 B ⊆ A 이면, A = B이다. (반대칭성)
* A ⊆ B 이고 B ⊆ C 이면, A ⊆ C이다. (추이성)
* A ⊆ (A ∪ B)
* A ⊆ C 이고 B ⊆ C 이면, (A ∪ B) ⊆ C
* A ∩ B ⊆ A
* C ⊆ A 이고 C ⊆ B 이면, C ⊆ (A ∩ B)
* 다음 명제들은 서로 동치이다.
A ⊆ B
A ∩ B = A
A ∪ B = B
A − B = ∅
** B의 여집합 ⊆ A의 여집합

4. 진부분집합의 성질

* 비반사성: 임의의 집합 A에 대해, A ⊊ A는 성립하지 않는다.
* 추이성: A ⊊ B이고 B ⊊ C이면, A ⊊ C이다.
* 비대칭성: A ⊊ B이면 B ⊊ A는 성립하지 않는다.

5. 멱집합

모든 집합은 공집합과 자기 자신을 부분집합으로 갖는다. 어떤 집합의 부분집합을 모두 모아놓은 집합을 그 집합의 멱집합이라고 하는데, 이는 자연히 적어도 공집합과 그 집합을 원소로 둔다. 부분집합 관계는 집합의 멱집합 위에서 자주 다루어지며, 이는 부분순서의 전형적인 예이다.

집합 S의 모든 부분집합의 집합을 멱집합이라고 하며, P(S)로 표기한다.

이항 관계인 포함 관계 ⊆는 A ≤ B ⇔ A ⊆ B로 정의된 집합 P(S)에 대한 부분 순서 관계이다. 또한, A ≤ B if and only if B ⊆ A로 정의하여 멱집합 P(S)를 역 집합 포함 관계에 의해 부분적으로 순서를 정할 수도 있다.

집합 S의 멱집합 P(S)에 대해, 포함 부분 순서 관계는 k = |S| (S의 기수)개 복사본의 데카르트 곱이며, 0 < 1에 대해 {0, 1}에 대한 부분 순서 관계이다. 이는 S = {s₁, s₂, ..., s_k}를 열거하고 각 부분집합 T ⊆ S (즉, 2^S의 각 원소)를 {0, 1}^k의 k-튜플과 연관시킴으로써 설명할 수 있는데, 여기서 i번째 좌표는 s_i가 T의 멤버인 경우에만 1이다.

6. 포함 관계의 기타 성질

모든 집합은 공집합과 자기 자신을 부분집합으로 갖는다. 어떤 집합의 부분집합을 모두 모아놓은 집합을 그 집합의 멱집합이라고 하는데, 이는 자연히 적어도 공집합과 그 집합을 원소로 둔다. 부분집합 관계는 집합의 멱집합 위에서 자주 다루어지며, 이는 부분순서의 전형적인 예이다.

* 반사율: 임의의 집합 $A$에 대해, $A\; \backslash subseteq\; A$이다.
* 추이성: 만약 $A\; \backslash subseteq\; B$이고 $B\; \backslash subseteq\; C$이면, $A\; \backslash subseteq\; C$이다.
* 반대칭성: 만약 $A\; \backslash subseteq\; B$이고 $B\; \backslash subseteq\; A$이면, $A\; =\; B$이다.
* 집합 A는 교집합이 A와 같을 때 B의 부분 집합이다. 형식적으로 다음과 같다.
::$A\; \backslash subseteq\; B\; \backslash text\{\; if\; and\; only\; if\; \}\; A\; \backslash cap\; B\; =\; A.$
* 집합 A는 합집합이 B와 같을 때 B의 부분 집합이다. 형식적으로 다음과 같다.
::$A\; \backslash subseteq\; B\; \backslash text\{\; if\; and\; only\; if\; \}\; A\; \backslash cup\; B\; =\; B.$
* 유한 집합 A는 교집합의 기수가 A의 기수와 같을 때 B의 부분 집합이다. 형식적으로 다음과 같다.
::$A\; \backslash subseteq\; B\; \backslash text\{\; if\; and\; only\; if\; \}\; |A\; \backslash cap\; B|\; =\; |A|.$
* 부분 집합 관계는 집합에 대한 부분 순서를 정의한다. 사실, 주어진 집합의 부분 집합은 부분 집합 관계 아래에서 불 대수를 형성하며, 여기서 결합 및 만남은 교집합과 합집합으로 주어지고, 부분 집합 관계 자체는 불 대수 포함 관계이다.
* 포함 관계는 정규 부분 순서이며, 이는 모든 부분 순서 집합 $(X,\; \backslash preceq)$가 포함 관계에 의해 정렬된 집합 모음에 동형이라는 의미이다. 서수는 간단한 예이다. 각 서수 n이 n 이하의 모든 서수 집합 $[n]$으로 식별되면 $a\; \backslash leq\; b$ if and only if $[a]\; \backslash subseteq\; [b].$가 성립한다.

다음은 S, T, U를 집합으로 한다.

* S = T와 S ⊆ T 이고 T ⊆ S는 동치이다([집합#외연성 공리|외연성 공리]]).
* 공집합 ∅는 모든 집합의 부분집합이다.
* S ⊆ S
* S ⊆ T 이고 T ⊆ U이면 S ⊆ U이다.
* S ⊆ S ∪ T
* S ⊆ T이면 S ∪ U ⊆ T ∪ U이다.
* S ⊆ U 이고 T ⊆ U이면 S ∪ T ⊆ U이다.
* S ∩ T ⊆ S
* S ⊆ T이면 S ∩ U ⊆ T ∩ U이다.
* S ⊆ T 이고 S ⊆ U이면 S ⊆ T ∩ U이다.
* S - T ⊆ S
* S ⊆ T이면 S - U ⊆ T - U이다.
* S ⊆ T 이고 S ⊆ U^C이면 S ⊆ T - U이다.
* 다음은 동치이다.
* S ⊆ T
* S ∩ T = S
* S ∪ T = T
* S − T = ∅
* S와 T가 모두 U의 부분집합일 때, S ⊆ T와 U - T ⊆ U - S는 동치이다.