집합(set), 이항 관계(binary relation), 동치 관계(equivalence relation), 순서 관계(order relation), 함수(function)

집합(Set): 명확히 정의된 객체들의 모임

• 원소(element): 집합의 객체

주요 개념 및 표기

• \( a \in A \): \( a \)는 집합 \( A \)의 원소이다.
• \( A \subseteq B \): \( A \)는 \( B \)의 부분집합이다.
• \( \emptyset \): 공집합
• 멱집합 \( \mathcal{P}(A) \): 집합 \( A \)의 모든 부분집합의 집합
• 곱집합 \( A \times B = \{(a, b) \mid a \in A, b \in B\} \)

집합 연산  
\[
\begin{align*}
A \cup B &= \{x \mid x \in A \text{ 또는 } x \in B\} \\
A \cap B &= \{x \mid x \in A \text{ 그리고 } x \in B\} \\
A \setminus B &= \{x \in A \mid x \notin B\}
\end{align*}
\]



이항 관계 (Binary Relations): 집합 \( A, B \) 위에서, 이항 관계 \( R \)는 순서쌍들의 집합인 \( R \subseteq A \times B \)로 정의

•  \( a R b \)는 \( (a, b) \in R \)를 의미한다.
• 보통 \( A = B \)일 때를 많이 다룬다.

이항 관계의 성질: 동치관계 또는 순서관계로 발전

• 반사성 (reflexive): \( \forall a \in A, a R a \)
• 대칭성 (symmetric): \( a R b \Rightarrow b R a \)
• 추이성 (transitive): \( a R b \land b R c \Rightarrow a R c \)
• 반대칭성 (antisymmetric): \( a R b \land b R a \Rightarrow a = b \)

 

 

동치관계 (Equivalence Relation)

집합 \( A \) 위의 이항 관계 \( \sim \subseteq A \times A \)가 다음을 만족하면, 이는 동치관계(equivalence relation)이다.
1. 반사성: \( a \sim a \)
2. 대칭성: \( a \sim b \Rightarrow b \sim a \)
3. 추이성: \( a \sim b \land b \sim c \Rightarrow a \sim c \)

 

예시: 정수의 나머지 동치 $ a \equiv b$ $ (mod n) $는 $n \mid (a - b)$를 의미

1. 임의의 정수 \( a \)에 대해 \( a - a = 0 \), 즉 \( n \mid 0 \)

2. \( a \equiv b \pmod{n} \)이면 \( n \mid (a - b) \), 그러므로 \( n \mid (b - a) \)도 성립

3. \( a \equiv b \pmod{n} \)이고 \( b \equiv c \pmod{n} \)이면 \( n \mid (a - b) \)이고 \( n \mid (b - c) \)이므로, \( (a - b) + (b - c) = a - c \)도 \( n \)의 배수

 

동치류 (Equivalance Class)

 

어떤 집합 \( A \)와 그 위의 동치관계 \( \sim \)이 있을 때, 

• \( A \)의 원소들을 (동치관계의 정의에 따라) 서로 '같은' 것으로 묶을 수 있다.
• 그 결과로 \( A \)는 겹치지 않는 부분 집합들의 모임으로 나뉘게 된다.
• \( [a] = \{ x \in A \mid x \sim a \} \): 각 부분 집합을 동치류(equivalence class)라고 부름
• \( A = \bigsqcup [a_i] \): 전체 집합 \( A \)는 이 동치류들의 분할(partition)

분할 (Partition)

 

동치관계가 주어지면, 동치류는 A를 겹치지 않게 완벽하게 나누는 방법

 

1. 포함성 (Covering): 모든 원소는 어떤 동치류에 반드시 속한다. 즉,  
   \[
   \bigcup_{a \in A} [a] = A
   \]
2. 서로소 (Disjoint): 서로 다른 동치류들은 겹치지 않는다.  
   \[
   a \not\sim b \Rightarrow [a] \cap [b] = \emptyset
   \]
3. 동일성 (Equality): 만약 \( a \sim b \)이면 \( [a] = [b] \)

 

예시: \( A = \mathbb{Z} \), \( a \equiv b \pmod{3} \)

• 이 동치관계는 '같은 나머지를 갖는 정수들'을 묶음
• 동치류:
    - \( [0] = \{ \dots, -6, -3, 0, 3, 6, \dots \} \)
    - \( [1] = \{ \dots, -5, -2, 1, 4, 7, \dots \} \)
    - \( [2] = \{ \dots, -4, -1, 2, 5, 8, \dots \} \)
• 이 세 동치류는 겹치지 않고, 모두 모으면 정수 전체가 되므로:
  \[
  \mathbb{Z} = [0] \sqcup [1] \sqcup [2]
  \]

 

 

 

부분 순서 관계 (Partial Order Relation)

집합 \( S \) 위의 이항 관계 \( \leq \subseteq S \times S \)가 다음 세 조건을 만족하면, 이는 부분순서(partial order)이다.
1. 반사성 (Reflexive)
   \[
   \forall a \in S, \quad a \leq a
   \]
   모든 원소는 자기 자신과 비교했을 때 순서가 같다.
2. 반대칭성 (Antisymmetric)
   \[
   a \leq b \land b \leq a \Rightarrow a = b
   \]
   \( a \leq b \)이고 동시에 \( b \leq a \)라면, 두 원소는 같아야 한다.
3. 추이성 (Transitive)
   \[
   a \leq b \land b \leq c \Rightarrow a \leq c
   \]
   순서가 이어지면 그 관계는 유지된다.

 

예시: 부분순서 관계

• 집합 \( \mathbb{N} = \{0, 1, 2, 3, \dots\} \) 위의 '작거나 같다' 관계 \( \leq \)
• 집합 \( \mathcal{P}(A) \) (어떤 집합 \( A \)의 멱집합) 위의 포함 관계 \( \subseteq \)
  예) \( \mathcal{P}(\{1,2\}) = \{\emptyset, \{1\}, \{2\}, \{1,2\}\} \) 위의 \( \subseteq \)
  - \( \emptyset \subseteq \emptyset \) → 반사성  
  - \( \{1\} \subseteq \{1,2\} \)이고 \( \{1,2\} \not\subseteq \{1\} \) → 반대칭성  
  - \( \emptyset \subseteq \{1\} \), \( \{1\} \subseteq \{1,2\} \) → \( \emptyset \subseteq \{1,2\} \) → 추이성
  이 관계는 부분순서이지만, 모든 원소가 서로 비교 가능한 건 아님 (예: \( \{1\}, \{2\} \)는 비교 불가)

전순서 관계 (Total Order Relation 또는 Linear Order Relation): 부분순서 관계 \( \leq \)가 모든 원소 쌍에 대해 비교 가능한 경우

4. 전순서성 (Totality / Comparability)
   \[
   \forall a, b \in S, \quad a \leq b \quad \text{또는} \quad b \leq a
   \]

예시: 전순서 관계

• 사전식 순서(lexicographic order): 알파벳 단어들 사이의 사전 순 비교
• \( \mathbb{N} \) 위의 \( \leq \)
  - 반사성: \( a \leq a \)
  - 반대칭성: \( a \leq b \)이고 \( b \leq a \)이면 \( a = b \)
  - 추이성: \( a \leq b \), \( b \leq c \)이면 \( a \leq c \)
  - 전순서성: 임의의 두 자연수 \( a, b \)에 대해 반드시 \( a \leq b \) 또는 \( b \leq a \)
  따라서 \( \leq \)는 전순서 관계를 만족하며, \( \mathbb{N} \)은 선형 정렬(linearly ordered)된다.

 

 

함수 (Function): 특별한 이항 관계 (입력 하나당 결과 하나)

• \( f \subseteq A \times B \)가 함수이기 위한 조건:
  \[
  \forall a \in A, \exists! b \in B \text{ such that } (a, b) \in f
  \]
• \( A \): 정의역 (domain)
• \( B \): 공역 (codomain)
• \( f(A) = \{ b \in B \mid \exists a \in A, f(a) = b \} \): 치역 (range, image)
• 즉, 정의역의 각 원소에 대해 오직 하나의 출력만 존재해야 한다.

함수의 분류: 정의역과 공역 사이의 대응 방식에 따라 나뉨

• 단사 함수 (Injective): 서로 다른 입력은 서로 다른 출력을 가진다(\( a_1 \ne a_2 \Rightarrow f(a_1) \ne f(a_2) \)).
  \[
  f(a_1) = f(a_2) \Rightarrow a_1 = a_2 
  \]
• 전사 함수 (Surjective): 공역의 모든 원소가 치역에 포함된다.
  \[
  \forall b \in B, \exists a \in A \text{ such that } f(a) = b
  \]
• 전단사 함수 (Bijective): 일대일 대응. 단사 + 전사

역함수

• \( f: A \to B \)가 전단사일 때 역함수 \( f^{-1}: B \to A \)가 존재  
  \[
  f^{-1}(f(a)) = a, \quad f(f^{-1}(b)) = b
  \]

합성 함수: 함수 연쇄 작용을 표현하며, 구조적 계산의 핵심 도구

• \( f: A \to B, \quad g: B \to C \)
• 합성: \( g \circ f: A \to C \), 정의: \( (g \circ f)(x) = g(f(x)) \)

범주론적 관점에서의 함수: 더 추상적인 구조인 사상(morphism)이라 부르며,  단순한 입력-출력 대응 이상으로 수학적 구조 전체를 보존하고 변환하는 도구임을 강조

• 객체(object): 집합, 군, 벡터공간, 위상공간 등
• 사상(morphism): (일반) 함수, 군 준동형, 선형변환, 연속 함수 등
• 보존되는 구조: X, 군 연산, 선형 연산, 위상 등

범주에서 함수는 다음을 만족해야 함:
1. 항등 사상의 존재: \( \text{id}_A: A \to A \)
2. 합성의 결합성: \( h \circ (g \circ f) = (h \circ g) \circ f \)



지시 함수 (Indicator Function): 집합 \( A \subseteq X \)에 대해, 어떤 원소가 \( A \)에 속하는지를 0 또는 1로 나타내는 함수

•  정의:  
  \[
  \chi_A(x) = \begin{cases}
  1 & \text{if } x \in A \\
  0 & \text{if } x \notin A
  \end{cases}
  \]
• 수학에서의 표기: \( \chi_A(x),\ \mathbf{1}_A(x) \)  
• 확률·통계에서의 표기: \( \mathbf{1}_{\{X \in A\}},\ \mathbb{I}_A(X) \)  
  → 확률 변수의 사건 발생 여부를 나타내는 도구로 사용됨

성질

1.  두 지시 함수의 곱은 교집합의 지시 함수와 같다.
   \[
   \chi_A(x) \cdot \chi_B(x) = \chi_{A \cap B}(x)
   \]
2. 여러 집합 \( A_i \)에 대한 지시 함수 \( \chi_{A_i}(x) \)의 합: \( x \)가 포함된 집합의 개수를 세는 함수
   \[
   \sum_{i=1}^n \chi_{A_i}(x) = \text{원소 } x \text{가 속한 } A_i \text{들의 개수}
   \]