[이산구조 개념-12] 집합의 기초 — 원소·표기·부분집합부터 데카르트 곱

1. 집합(Set)이란 무엇인가

집합(Set) 은 순서와 중복을 고려하지 않는 서로 다른 객체(Object)들의 모임이다.

주머니 비유

집합은 마치 특별한 주머니와 같다.

주머니의 특성집합과의 대응

무엇이 들어있는지가 중요	어떤 원소가 있는지가 중요
어떤 순서로 넣었는지 무관	원소 나열 순서 무관
같은 물건 여러 번 넣어도 한 종류	중복 원소는 1개로 취급

집합의 3대 특징

특징영문설명

순서 무의미	Order Irrelevant	{a,b,c} = {c,b,a}
중복 무의미	All Distinct	{a,a,b,c,c} = {a,b,c}
고유한 객체들	Unique Objects	모든 원소는 서로 다름

집합 표기 규칙

항목표기예시

집합 이름	대문자	S, T, U, A, B
원소 묶음	중괄호 { }	{1, 2, 3}
원소 구분	쉼표 ,	{a, b, c}

💡 핵심 통찰: 집합은 객체들을 분류·조직하는 가장 기본적인 수학 도구다. "어떤 요소가 존재하는가"에만 집중한다.

---

2. 원소(Element) — 집합을 이루는 단위

원소(Element 또는 Member) 는 집합에 포함된 개별 객체를 말한다.

소속 기호

기호의미예시

∈	"x는 S의 원소"	1 ∈ {1, 2, 3}
∉	"x는 S의 원소가 아님"	5 ∉ {1, 2, 3}

기호 외우기 팁

∈ 기호는 마치 포크가 원소를 콕 찍어내는 모습처럼 생겼다. 집합 안으로 들어가는 화살표라고 생각하면 쉽다.

빠른 확인

식참/거짓

3 ∈ {1, 2, 3}	참 ✅
5 ∈ {1, 2, 3}	거짓 ❌
'a' ∈ {a, b, c}	참 ✅
0 ∉ {1, 2, 3}	참 ✅

---

3. 집합을 기록하는 두 가지 방법 ⭐

집합을 표현하는 표준 방법은 두 가지다.

방법 ① 원소 나열법 (Listing)

집합의 모든 원소를 중괄호 안에 직접 나열

예시의미

{1, 2, 3, 4}	1, 2, 3, 4 네 원소를 가진 집합
{a, e, i, o, u}	영어 모음 집합
{..., −2, −1, 0, 1, 2, ...}	모든 정수의 집합

장점: 직관적, 한눈에 파악 단점: 원소가 많거나 무한할 때 부적합

방법 ② 조건 제시법 (Set Builder)

원소가 만족해야 할 조건을 제시하여 정의 형식: { x | P(x) } 의미: "조건 P(x)를 만족하는 모든 x의 집합"

기호 | 는 "such that (~를 만족하는)" 의 의미다.

예시의미

{ x | x는 정수 }	모든 정수
{ x | 0 < x < 5인 정수 }	{1, 2, 3, 4}
{ x | x는 짝수, x > 0 }	{2, 4, 6, 8, ...}

두 방법 비교

항목원소 나열법조건 제시법

표현 방식	원소 직접 나열	조건으로 정의
적합한 경우	원소 적고 유한	원소 많거나 무한
직관성	⭐⭐⭐⭐⭐	⭐⭐⭐
일반화	⭐⭐	⭐⭐⭐⭐⭐

💡 시험 빈출: 같은 집합을 두 가지 방법으로 표현하는 문제가 자주 나온다. 예: {1, 2, 3, 4} = { x | 0 < x < 5인 정수 }

---

4. 상등(Equality) — 두 집합이 같다는 것

정의

두 집합이 구성 원소가 완벽히 동일할 때 같다(Equal)고 한다. 표현 방식은 무관하다.

핵심 원리

두 집합 A, B가 같음 ⟺ A의 모든 원소가 B에 속하고, B의 모든 원소가 A에 속함

상등 판별 예시

집합 1집합 2같은가?이유

{1, 2, 3, 4}	{ x | 0 < x < 5인 정수 }	⭕	원소 동일 (표현만 다름)
{a, b, c}	{c, b, a}	⭕	순서만 다름
{1, 1, 2, 3}	{1, 2, 3}	⭕	중복은 무의미
{1, 2}	{1, 2, 3}	❌	원소 개수 다름
{1, 2, 3}	{(1, 2, 3)}	❌	후자는 원소가 1개 (순서쌍)

💡 주의: 순서쌍(Ordered Tuple)은 순서가 바뀌면 다른 객체가 된다. 집합과는 상등의 개념이 다르다는 점을 꼭 기억하자.

---

5. 공집합(Empty Set) — 텅 빈 주머니 ⭐

정의

공집합은 원소가 단 하나도 없는 유일한(Unique) 집합이다.

표기

표기설명

∅	표준 기호 (그리스어 phi)
{ }	비어있는 중괄호

공집합의 특징

특징설명

유일성	공집합은 오직 하나만 존재
기수	|∅| = 0 (원소 0개)
모든 집합의 부분집합	∅ ⊆ S (어떤 S에 대해서도)

공집합 예시

명제결과

"날 수 있는 코끼리"의 집합	∅ (현실에 없음)
"x² = −1을 만족하는 실수 x"의 집합	∅ (해 없음)
"한국에서 키 5m 이상인 사람"의 집합	∅

⚠️ 절대 헷갈리면 안 되는 3가지

객체의미기수

0	숫자 0 (집합 아님)	—
∅	텅 빈 집합 (아무것도 없음)	0
{∅}	텅 빈 집합을 원소로 가진 집합	1

💡 시험 함정: ∅과 {∅}는 절대 같지 않다! ∅은 빈 상자, {∅}은 빈 상자를 담은 상자다.

---

6. 부분집합(Subset) ⭐

정의 — 기본 부분집합

집합 S의 모든 원소가 집합 T에 속할 때, S는 T의 부분집합이라고 한다.

S ⊆ T ⟺ S의 모든 x에 대해 x ∈ T

비유

'과일' 집합 안에 '사과' 집합이 있다고 하자. 모든 사과는 과일이므로, 사과 집합 ⊆ 과일 집합이다.

부분집합의 3대 성질

성질식의미

자기 자신 포함	S ⊆ S	모든 집합은 자기 자신의 부분집합
공집합 포함	∅ ⊆ S	공집합은 모든 집합의 부분집합
추이성	A⊆B, B⊆C → A⊆C	부분집합 관계는 사슬처럼 연결

---

7. 진부분집합(Proper Subset)

정의

S가 T의 부분집합이면서 동시에 S와 T가 같지 않을 때, S는 T의 진부분집합이라고 한다.

S ⊂ T ⟺ S ⊆ T 이면서 S ≠ T

부분집합 vs 진부분집합

구분부분집합 (⊆)진부분집합 (⊂)

자기 자신 포함 가능?	⭕ (S ⊆ S 가능)	❌ (S ⊂ S 불가능)
의미	"포함되거나 같음"	"엄격하게 포함됨"
비유	≤ (작거나 같음)	< (진짜로 작음)

비교 예시

식참/거짓이유

{1, 2} ⊆ {1, 2, 3}	참 ✅	모든 원소 포함
{1, 2} ⊂ {1, 2, 3}	참 ✅	포함 + 같지 않음
{1, 2, 3} ⊆ {1, 2, 3}	참 ✅	자기 자신 포함 OK
{1, 2, 3} ⊂ {1, 2, 3}	거짓 ❌	같으므로 진부분집합 아님

💡 상등 증명의 핵심 원리: S = T ⟺ (S ⊆ T) ∧ (T ⊆ S) — 두 집합이 서로의 부분집합이면 같다. 이건 13강의 증명 방법에서 핵심이 된다.

---

8. 기수(Cardinality) — 집합의 크기

정의

기수는 집합 S가 가진 서로 다른 원소의 개수다. 기호는 |S|.

핵심 규칙

중복은 한 번만 센다 (집합의 중복 무의미 규칙 적용)

기수 계산 예시

집합기수

∅	0
{a}	1
{1, 2, 3}	3
{1, 1, 2, 3, 3}	3 (중복 제외)
{a, b, c, d, e}	5

고난도 — 집합을 품은 집합

이 부분이 시험에서 가장 많이 틀린다.

집합원소 분석기수

{1}	원소: 1	1
{{1}}	원소: {1} (집합 1개)	1
{1, {1}}	원소: 1, {1} (서로 다른 2개)	2
{ {1, 2, 3}, {4, 5} }	원소: 두 개의 집합	2
{a, {b, c}, d}	원소: a, {b, c}, d	3

절대 헷갈리면 안 되는 관계

1 ≠ {1} ≠ {{1}}

객체정체기수

1	숫자 (집합 아님)	—
{1}	1을 원소로 가진 집합	1
{{1}}	집합 {1}을 원소로 가진 집합	1

💡 시험 함정: 바깥 중괄호의 원소를 셀 때, 중괄호 안의 또 다른 중괄호는 하나의 원소로 본다. 절대 안쪽 원소까지 풀어서 세지 말 것.

---

9. 멱집합(Power Set) ⭐⭐⭐ 시험 빈출

정의

집합 S의 모든 부분집합을 원소로 가지는 집합을 멱집합이라 한다.

표기

표기의미

P(S)	집합 S의 멱집합
2^S	같은 의미 (왜 2^S인지는 아래 설명)

핵심 공식 ⭐

|P(S)| = 2^|S|

집합 S의 원소가 n개라면, 멱집합의 원소는 2ⁿ개다.

왜 2ⁿ인가?

각 원소마다 포함하거나(O) / 포함하지 않거나(X) 의 2가지 선택지가 있기 때문이다.

원소 개수각 원소의 선택지부분집합 총 수

1개	O 또는 X	2¹ = 2
2개	OO, OX, XO, XX	2² = 4
3개	(8가지 조합)	2³ = 8
n개	2ⁿ가지 조합	2ⁿ

멱집합 계산 예제

S = {a, b}일 때 P(S)는?

모든 부분집합 나열

번호a 포함?b 포함?부분집합

1	❌	❌	∅
2	⭕	❌	{a}
3	❌	⭕	{b}
4	⭕	⭕	{a, b}

결과: P(S) = { ∅, {a}, {b}, {a, b} }

검증: |S| = 2 → |P(S)| = 2² = 4 ✅

멱집합 빠른 계산표

| |S| | |P(S)| = 2^|S| | |---|---| | 0 | 1 (P(∅) = {∅}) | | 1 | 2 | | 2 | 4 | | 3 | 8 | | 4 | 16 | | 5 | 32 | | 10 | 1,024 | | 20 | 1,048,576 |

💡 응용 분야: 데이터베이스 스키마 설계, 권한 관리(누가 어떤 기능에 접근할 수 있는가), 조합론, 의사결정 분석 등 모든 가능한 경우의 수를 다룰 때 멱집합이 등장한다.

---

10. 순서쌍(Ordered n-tuples) — 순서가 중요한 리스트

정의

집합과 비슷해 보이지만, 순서와 중복이 매우 중요한 리스트다.

표기

표기형태

길이 n의 순서쌍	(a₁, a₂, ..., aₙ)
괄호	소괄호 ( ) ← 집합과 결정적 차이

비유

좌표 (3, 5)와 (5, 3)은 다른 위치를 가리킨다. 비밀번호 1234와 4321은 다른 비밀번호다. 순서쌍은 마치 '주소' 처럼 순서가 결정적이다.

집합 vs 순서쌍 결정적 비교 ⭐

구분일반 집합순서쌍

괄호 기호	{ a, b }	( a, b )
순서 변경	영향 없음 ({a,b} = {b,a})	완전 다름 ((a,b) ≠ (b,a))
중복 요소	의미 없음 ({a,a} = {a})	의미 있음 ((a,a) ≠ (a))
핵심 속성	무질서한 덩어리	순서가 정해진 목록

실생활 예시

상황순서쌍 표현

좌표계 점	(3, 5)
사람 이름 (성, 이름)	(김, 철수)
함수 입력	f(2, 3)
비밀번호	(1, 2, 3, 4)

💡 시험 핵심: { } 와 ( )를 헷갈리지 말 것. 중괄호는 집합(순서·중복 무의미), 소괄호는 순서쌍(순서·중복 중요).

---

11. 데카르트 곱(Cartesian Product) ⭐ 함수와 관계의 기초

정의

두 집합 A와 B에서 각각 원소를 뽑아 만든 모든 순서쌍의 집합.

A × B = { (a, b) | a ∈ A ∧ b ∈ B }

비유

두 개의 서로 다른 주머니에서 하나씩 물건을 꺼내, 모든 가능한 짝을 만드는 작업.

데카르트 곱 핵심 공식

|A × B| = |A| × |B|

A의 원소 개수 × B의 원소 개수 = 데카르트 곱의 원소 개수

데카르트 곱 계산 예제

A = {1, 2}, B = {x, y, z}일 때 A × B는?

모든 짝 만들기

A의 원소B의 원소순서쌍

1	x	(1, x)
1	y	(1, y)
1	z	(1, z)
2	x	(2, x)
2	y	(2, y)
2	z	(2, z)

결과: A × B = { (1,x), (1,y), (1,z), (2,x), (2,y), (2,z) }

검증: |A| × |B| = 2 × 3 = 6 ✅

교환법칙 성립 안 함 ⚠️

A × B ≠ B × A (일반적으로)

순서쌍이라 순서가 중요하기 때문이다.

식결과

A × B	{ (1,x), (1,y), (1,z), (2,x), (2,y), (2,z) }
B × A	{ (x,1), (x,2), (y,1), (y,2), (z,1), (z,2) }

→ 두 결과는 다른 집합!

실생활 응용

상황데카르트 곱 적용

2차원 좌표계	ℝ × ℝ (모든 (x, y) 점)
메뉴 조합	(한식 메뉴) × (음료) → 모든 식사 조합
학생 시간표	(요일) × (교시) → 모든 시간 슬롯
데이터베이스 JOIN	두 테이블의 모든 조합 행

💡 다음 단원 예고: 데카르트 곱은 함수와 관계(Functions & Relations) 단원의 직접적인 기초가 된다. 함수란 결국 A × B의 부분집합이다.

---

📌 한눈에 보는 핵심정리

개념핵심

집합	순서·중복 무의미한 객체들의 모임
원소	∈ (포함), ∉ (포함되지 않음)
표기법 ①	원소 나열법 — {1, 2, 3}
표기법 ②	조건 제시법 — { x | P(x) }
상등	원소 동일하면 같음 (표현 무관)
공집합	∅,
부분집합	S ⊆ T (S의 모든 원소가 T에 속함)
진부분집합	S ⊂ T (S ⊆ T이고 S ≠ T)
기수
멱집합	P(S) = 모든 부분집합의 집합,
순서쌍	(a, b), 순서·중복 중요, 소괄호 사용
데카르트 곱	A × B = 모든 (a, b) 순서쌍,
상등 증명 원리	S = T ⟺ S ⊆ T ∧ T ⊆ S

---

🧠 예상문제 2제

문제 1. 기수 계산 — 집합 속 집합

다음 집합의 기수 |S|로 옳은 것은?

S = { ∅, {1}, {1, 2}, {{1, 2}}, 1 }

① 3 ② 4 ③ 5 ④ 6

👉 정답: ③

각 원소를 분석하면 5개의 서로 다른 객체다.

번호원소정체

1	∅	공집합
2	{1}	1을 원소로 가진 집합
3	{1, 2}	1, 2를 원소로 가진 집합
4	{{1, 2}}	집합 {1, 2}를 원소로 가진 집합
5	1	숫자 1

이들은 모두 서로 다른 객체다. 특히 다음 4가지를 헷갈리지 말자:

• 1 (숫자) ≠ {1} (집합) ≠ {1, 2} (다른 집합) ≠ {{1, 2}} (집합을 원소로 가진 집합)

따라서 |S| = 5.

💡 시험 함정 회피: 집합 안의 또 다른 중괄호는 하나의 원소로 카운트한다. 안쪽 원소까지 풀어서 세면 안 된다.

---

문제 2. 멱집합과 데카르트 곱 결합

집합 A = {a, b}, B = {1}일 때, |P(A) × B| 의 값은?

① 3 ② 4 ③ 6 ④ 8

👉 정답: ②

단계별 풀이

1단계 — P(A) 구하기

A = {a, b}의 멱집합:

부분집합

∅
{a}
{b}
{a, b}

→ P(A) = { ∅, {a}, {b}, {a, b} }, |P(A)| = 2² = 4

2단계 — P(A) × B의 기수 계산

데카르트 곱 공식 적용:

|P(A) × B| = |P(A)| × |B| = 4 × 1 = 4

실제 P(A) × B

순서쌍

(∅, 1)

({a}, 1)

({b}, 1)

({a, b}, 1)

→ 정확히 4개 ✅

💡 고난도 시험 패턴: 멱집합과 데카르트 곱이 결합된 문제는 공식만 정확히 알면 한 줄로 해결된다. |P(A) × B| = 2^|A| × |B| = 4 × 1 = 4.