본문으로 건너뛰기

Basic Structures: Sets, Functions, Sequences, and Sums

Discrete Mathematics and Its Applications · Kenneth H. Rosen · Ch. 2

Intuition

이산수학은 개별적인 객체들의 관계를 다루며, 집합은 이 객체들을 모으는 그릇이고 함수는 객체 사이의 연결 규칙이며 수열과 합은 이를 질서 있게 나열하고 측정하는 방법이다.

One-liner​

수학적 대상들을 체계적으로 분류(집합)하고, 연결(함수)하며, 나열(수열)하고, 정량화(합)하는 이산수학의 기본 도구 모음이다.

Prerequisites​

  • 고교 수학 수준의 기초 대수학
  • 기본적인 논리 기호 (∀,∃,∧,∨,→\forall, \exists, \wedge, \vee, \to)

Goals​

  • 집합의 정의와 부분집합, 멱집합, 데카르트 곱의 개념을 이해한다.
  • 집합 연산(합집합, 교집합, 차집합, 여집합) 및 집합 항등식을 활용한다.
  • 함수의 정의역, 공역, 치환과 단사(One-to-one), 전사(Onto), 전단사(Bijection)의 조건을 구분한다.
  • 등차수열, 등비수열의 일반항과 합의 공식을 유도하고 적용한다.
  • 집합의 크기(Cardinality)를 비교하고 가산(Countable)과 비가산(Uncountable)의 차이를 이해한다.

Core Concepts​

2.1 Sets (집합)​

Definition

Set (집합): 순서에 상관없이 서로 다른 객체들을 모아 놓은 것. 집합에 포함된 객체를 Elements (원소) 또는 Members라고 한다.

  • Set-Builder Notation (조건 제시법): O={x∈Z+∣x is odd and x<10}O = \{x \in \mathbb{Z}^+ \mid x \text{ is odd and } x < 10\} (p.112).
  • Subset (부분집합): 모든 xx에 대해 x∈A→x∈Bx \in A \to x \in B가 참이면 A⊆BA \subseteq B이다 (p.114).
  • Power Set (멱집합): 집합 SS의 모든 부분집합을 원소로 가지는 집합 P(S)P(S). 원소의 개수가 nn개이면 멱집합의 크기는 2n2^n이다 (p.116).
  • Cartesian Product (데카르트 곱): A×B={(a,b)∣a∈A∧b∈B}A \times B = \{(a, b) | a \in A \wedge b \in B\}. 순서쌍들의 집합이다 (p.118).

2.2 Set Operations (집합 연산)​

Definition
  • Union (합집합): A∪B={x∣x∈A∨x∈B}A \cup B = \{x | x \in A \vee x \in B\}
  • Intersection (교집합): A∩B={x∣x∈A∧x∈B}A \cap B = \{x | x \in A \wedge x \in B\}
  • Difference (차집합): A−B={x∣x∈A∧x∉B}A - B = \{x | x \in A \wedge x \notin B\}
  • Complement (여집합): A‾=U−A\overline{A} = U - A (단, UU는 전체집합)
  • Principle of Inclusion-Exclusion (포함-배제의 원리): ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A \cup B| = |A| + |B| - |A \cap B| (p.122).
  • Set Identities (집합 항등식): 드 모르간의 법칙 (A∩B‾=A‾∪B‾\overline{A \cap B} = \overline{A} \cup \overline{B}), 분배 법칙 등을 포함한다 (p.124).
  • Computer Representation: 전체집합 UU가 유한할 때, 비트 문자열(Bit strings)을 사용하여 집합의 원소 포함 여부를 0과 1로 효율적으로 저장할 수 있다 (p.129).

2.3 Functions (함수)​

Definition

집합 AA에서 BB로의 Function ff는 AA의 모든 원소에 대해 BB의 원소를 정확히 하나씩 대응시키는 규칙이다.

  • Injective (단사/One-to-one): f(a)=f(b)→a=bf(a) = f(b) \to a = b (p.136).
  • Surjective (전사/Onto): 공역의 모든 원소가 치역에 포함됨 (∀b∈B∃a∈A(f(a)=b)\forall b \in B \exists a \in A (f(a) = b)) (p.137).
  • Bijective (전단사/One-to-one correspondence): 단사이며 동시에 전사인 함수. 역함수가 존재할 필요충분조건이다 (p.138).
  • Composition (합성): (f∘g)(a)=f(g(a))(f \circ g)(a) = f(g(a)). gg의 치역이 ff의 정의역의 부분집합이어야 한다 (p.140).
  • Floor and Ceiling Functions: ⌊x⌋\lfloor x \rfloor는 xx보다 작거나 같은 최대 정수, ⌈x⌉\lceil x \rceil는 xx보다 크거나 같은 최소 정수이다 (p.143).

2.4 Sequences and Summations (수열과 합)​

  • Geometric Progression (등비수열): a,ar,ar2,…a, ar, ar^2, \dots 형태의 수열 (p.150).
  • Arithmetic Progression (등차수열): a,a+d,a+2d,…a, a+d, a+2d, \dots 형태의 수열 (p.151).
  • Summation: ∑j=mnaj\sum_{j=m}^n a_j로 표기하며, 인덱스 이동(shifting)을 통해 계산을 단순화할 수 있다 (p.153).
  • Cardinality of Infinite Sets: 자연수 집합과 일대일 대응이 가능하면 Countable (가산)이라고 한다. 유리수 집합은 가산 집합이지만, 실수 집합은 칸토어의 대각선 논법(Diagonalization argument)에 의해 Uncountable (비가산)임이 증명되었다 (p.158-160).

Notation​

기호의미
∈,∉\in, \notin원소이다 / 원소가 아니다
∅\emptyset공집합 (원소가 없는 집합)
Z,N,Q,R\mathbb{Z}, \mathbb{N}, \mathbb{Q}, \mathbb{R}정수, 자연수, 유리수, 실수 집합
$S
A⊆BA \subseteq BAA는 BB의 부분집합
A⊂BA \subset BAA는 BB의 진부분집합 (A⊆BA \subseteq B 이고 A≠BA \ne B)
f:A→Bf: A \to BAA에서 BB로 가는 함수 ff
ℵ0\aleph_0자연수 집합의 기수 (Aleph null)

Key Theorems & Formulas​

Theorem (Sum of a Geometric Series)

조건: aa와 rr은 실수이고 r≠0r \ne 0이다.

결론:

\sum_{j=0}^n ar^j = \begin{cases} \frac{ar^{n+1}-a}{r-1} & \text{if } r \ne 1 \\ (n+1)a & \text{if } r = 1 \end{cases} $$ (p.155)
Theorem (De Morgan's Laws for Sets)

결론:

  1. A∪B‾=A‾∩B‾\overline{A \cup B} = \overline{A} \cap \overline{B}
  2. A∩B‾=A‾∪B‾\overline{A \cap B} = \overline{A} \cup \overline{B} (p.124)

Intuitions​

  • 멱집합과 이진수: 원소가 nn개인 집합의 부분집합을 결정하는 것은 각 원소를 '포함할지(1)' '말지(0)' 선택하는 nn번의 이진 결정과 같다. 따라서 총 개수는 2n2^n이다.
  • 함수의 종류 비유:
    • Injective: "화살을 쏘는 사람이 각자 다른 과녁을 맞힘."
    • Surjective: "모든 과녁이 최소 하나의 화살을 맞음."
    • Bijective: "모든 사람이 각자 다른 과녁을 맞혔고, 빈 과녁도 없음."
  • 가산성의 직관: 집합의 원소들을 "첫 번째, 두 번째..." 하며 빠짐없이 번호를 매겨 나열할 수 있다면 가산 집합이다. 유리수는 지그재그 경로를 통해 나열 가능하므로 가산적이다.

Worked Examples​

Example 1: Set Builder Notation (p.112)​

문제: Q+Q^+ (양의 유리수 집합)를 조건 제시법으로 나타내라. 해석: 유리수는 정수의 비율로 표현되는 수이다. 답: Q+={x∈R∣x=p/q for some p,q∈Z+}\mathbb{Q}^+ = \{x \in \mathbb{R} \mid x = p/q \text{ for some } p, q \in \mathbb{Z}^+\}

Example 2: Composition of Functions (p.141)​

문제: f(x)=2x+3,g(x)=3x+2f(x) = 2x + 3, g(x) = 3x + 2 일 때 (f∘g)(x)(f \circ g)(x)를 구하라. 핵심 단계:

  1. f(g(x))=f(3x+2)f(g(x)) = f(3x + 2)
  2. 2(3x+2)+3=6x+4+32(3x + 2) + 3 = 6x + 4 + 3 답: 6x+76x + 7 (참고: g∘f=6x+11g \circ f = 6x + 11로 교환법칙이 성립하지 않음)

Example 3: Shifting Indices in Summation (p.155)​

문제: ∑j=15j2\sum_{j=1}^5 j^2의 인덱스를 0부터 4까지로 변경하라. 핵심 단계:

  1. k=j−1k = j - 1로 치환하면 j=k+1j = k + 1이다.
  2. j=1→k=0j=1 \to k=0, j=5→k=4j=5 \to k=4가 된다. 답: ∑k=04(k+1)2\sum_{k=0}^4 (k + 1)^2

Common Pitfalls​

Pitfall

공집합 vs 공집합을 원소로 가지는 집합: ∅\emptyset과 {∅}\{\emptyset\}은 다르다. ∅\emptyset은 원소가 0개인 빈 폴더이고, {∅}\{\emptyset\}은 내부에 빈 폴더 하나가 들어있는 폴더이다 (p.114).

Pitfall

역함수의 존재 조건: 함수가 단순히 '전사'이거나 '단사'이기만 해서는 역함수가 정의되지 않는다. 반드시 Bijection (일대일 대응)이어야만 거꾸로 가는 규칙이 유일하게 확정된다.

Connections​

  • 선행 개념: Ch. 1 기초 논리 - 집합의 포함 관계와 함수의 조건을 명제로 표현하는 데 사용됨.
  • 후속 개념: Ch. 4 수학적 귀납법 - 수열의 합 공식을 증명하는 핵심 도구. Ch. 8 관계 - 함수가 관계의 특수한 형태로 일반화된다.
  • 응용 분야:
    • 컴퓨터 과학: 데이터 타입(Datatype)은 집합과 그 위의 연산으로 정의된다 (p.113).
    • 알고리즘 분석: 복잡도를 나타내는 Big-O 표기법은 함수와 수열의 성장 속도를 다룬다 (Ch. 3).

Critical Notes​

교재가 강조하는 것

  • 집합론의 엄밀한 공리적 구성보다는 직관적인 Naive Set Theory (소박한 집합론)를 사용하되, 러셀의 역설(Russell's Paradox)과 같은 한계를 언급하며 주의를 환기한다 (p.111).
  • 수학적 대상을 비트 문자열로 변환하여 컴퓨터가 처리하기 쉬운 형태로 바꾸는 관점을 강조한다.

실제로 중요한 것

  • 함수에서 정의역과 공역을 명확히 정의하는 습관. 같은 규칙 f(x)=x2f(x)=x^2이라도 정의역이 실수 전체인지 양의 실수인지에 따라 함수의 성질(단사성 등)이 완전히 달라진다.
  • 가산성 개념은 컴퓨터로 계산 가능한 것과 불가능한 것을 구분하는 이론적 기초가 된다.

교재가 생략하거나 얼버무리는 것

  • 공리적 집합론(ZFC 등)의 복잡한 내용은 연습문제나 심화 읽기로 돌리고, 학습자가 집합을 '도구'로서 바로 사용할 수 있도록 서술되어 있다.

Open Questions​

이해하지 못한 것

  • 칸토어의 대각선 논법이 '모든' 비가산 집합의 크기를 비교하는 데 어떻게 확장될 수 있는지 (연속체 가설 등).