Topology- Set Theory, Fundamental Concepts

in Math

참고
[1] Topology 2e, James Munkres

Introduction

  • Set Theory에서 Set에 대한 기본 개념과 간단한 operation에 대해서 알아본다.

property

  • property \(P(x)\)는 참과 거짓을 다루는 함수이다. 파라미터를 가질 수 있다.
  • Set을 이루는 element들을 제한하는데 사용한다.
\[B = \{x|x\text{ is integer greater than 5}\}\]
  • 위의 Equation은 말로 풀어 쓰면 “B is the set of all \(x\) such that \(x\) is integer greater than 5”을 의미한다.
  • \(\{\}\)은 Set의 정의, \(x\)|은 모든 x를 의미, \(x \text{ is integer greater than 5}\)는 property를 의미한다.
  • 위의 Equation에서 Property \(P(x, 5) = x > 5 \text{ and x is integer}\) 을 의미한다.

Union, Intersection and Empty Set

  • union of \(A\) and \(B\) :
\[A \cup B = \{x|x\in A \text{ or } x\in B \}\]
  • intersection of \(A\) and \(B\) :
\[A \cap B = \{x|x\in A \text{ and } x\in B \}\]
  • 만약에 \(x\in A \text{ and } x\in B\) 을 만족하는 x가 하나도 존재하지 않을 시에는 \(A \cap B = \varnothing\) 이라고 한다. 그리고 이런 경우 \(A\) 와 \(B\)는 disjoint하다고 한다.
  • empty set은 element를 하나도 가지지 않는 set을 의미한다.
  • empty set의 개념은 어려울 수 있다. element를 가지지 않는게 Set이라고 부를 수 있는가. 이것은 수체계에서 0을 수로 인정하는 것과 같다. 0을 처음 수로 인정하는게 어려웠나보다. Convention 하게 empty set을 도입할 경우, 여러 이론과 증명이 정확히 떨어지는 경우가 많기에 직관상 이상하지만 수학적으로 사용하는 개념이라 볼 수 있다.
\[\begin{aligned} A \cup \varnothing = A \quad \text{ and } \quad A \cap \varnothing = \varnothing \quad \quad \text{for every set A} \end{aligned}\]

Vacuous Truth

  • \(\varnothing \subset A\) 이것은 참일까, 거짓일까
  • 그전에 “if P, then Q”의 Statement를 보자. 만약에 P를 만족시키는 event가 하나도 존재하지 않다면 어떻게 될까.
  • Set Theory에서는 가정이 잘못되면 그 Statement는 참으로 본다. 이것을 Vacuous Truth라고 부른다.
  • 아래의 Statement는 참이다. if 문을 만족시키는 x가 없기 때문이다.
\[\text{if } x^2 < 0, \text{then } x = 23\]
  • 다시 \(\varnothing \subset A\)를 보자. 이것을 문자로 풀어보면 \(\text{if } x \in \varnothing \text{, then } x \in A\) 이다. if 문을 만족시키는 x가 없기 때문에 vacuous truth에 의해 이 명제는 참이다. 심지어 \(\varnothing \subset \varnothing\) 또한 참이다. 하지만 \(\varnothing \in \varnothing\)은 참이 아니다.
  • vacuous truth는 직관적인 이해보다는 수학적 논리에의해 정의된 convention에 가깝다. 예를들면 vacuous truth는 contrapositive가 성립한다.
\[\begin{aligned} \text{if } x^2 < 0&, \text{then } x = 23 \\[1em] \text{if } x \neq 23 &, x^2 >= 0 \end{aligned}\]
  • 다음은 vacuous truth의 조건들이다.
\[\begin{cases} \forall x: P(x) \Rightarrow Q(x), \text{where it is the case that} \forall x: \neg P(x) \\[1em] \forall x \in A : Q(x), \text{where the set A is empty} \end{cases}\]
  • 좀 더 직관적인 이해를 해보자. \(\text{if P,then Q}\) 를 Set의 개념으로 생각해보면, P를 만족시키는 event의 set을 \(P\)라고 하고, Q를 만족시키는 event의 set을 \(Q\)라고 하자. 앞의 statement를 set operation으로 바꾸면 \(P \subseteq Q\) 으로 표현될 수 있다. 만약에 \(P\)가 empty set이라면 Q에 포함된다는 의미니까 앞의 statement는 참이 된다. contrapositive를 보면 \(\neg P\) 는 모든 element를 담은 set이기 때문에 모든 set Q에 대해서도 명제는 참이된다.

Negation

  • negation of statement \(P\)는 not \(P\)를 의미한다.
  • 대부분의 경우에서 not \(P\)를 구하는 것은 쉬울 것이다. 하지만 “for every”, “for at least one” 같은 logical quantifiers에서는 혼동이 올 수 있다.
\[\text{For every } x \in A, \text{statement P holds}\]
  • 위의 statement의 negation은 다음과 같다. “for every“의 negation은 “for at least one“인 것에 주의하자.
\[\text{For at least one } x \in A, \text{statement P does not hold}\]
  • 반대로 “for at least one“의 negation은 “for every” 이다.

Distributive law

  • Set의 \(\cup, \cap\) 은 distribute law를 만족한다.
  • \(\cup, \cap\) 모두 만족시킬 수 있다는 것에 주의하자.
\[\begin{aligned} A \cup (B \cap C) = (A \cup B) \cap (A \cup C) \\[1em] A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \end{aligned}\]
  • 다음의 equation을 DeMorgan’s laws 라고 부른다.
\[\begin{aligned} A - (B \cup C) = (A - B)\cap(A - C) \\[1em] A - (B \cap C) = (A - B)\cup(A - C) \end{aligned}\]

Collections of Sets

  • Set은 Set을 element로 가질 수 있다.
  • Set의 모든 element가 Set으로 이루어졌으면 그 Set을 Collection of Set 이라 부른다.
  • 대표적으로 the power set of \(A\)이 있다.
  • power set of \(A\)는 \(A\)의 모든 Subset을 element로 가지고 있는 Set을 의미한다. \(\mathcal{P}(A)\)로 표시한다.
\[\begin{aligned} A &= \{a, b, c\} \\[1em] a &\in A, \\[1em] \{a\} &\subset A, \\[1em] \{a\} &\in \mathcal{P}(A) \end{aligned}\]

Arbitrary Unions and Intersections

  • union과 intersection을 꼭 두개의 Set에 대해서만 할 필요는 없다. 여러개를 같이 할 수도 있다.
  • Collection \(\mathcal{A}\) 이 있을때, the union of the elements of \(\mathcal{A}\) 은 다음과 같이 정의한다.
\[\bigcup_{A \in \mathcal{A}} A = \{x|x \in A \text{ for at least one } A \in \mathcal{A}\}\]
  • 그리고 the intersection of the elements of \(\mathcal{A}\) 은 다음과 같이 정의한다.
\[\bigcap_{A \in \mathcal{A}} A = \{x|x \in A \text{ for every } A \in \mathcal{A}\}\]
  • 만약에 \(\mathcal{A}\) 가 empty set이라면 어떻게 될까.
  • Union의 경우 생각해보자. Property 부분만 따로 떼어내보면, x가 존재하기 위해서는 적어도 하나 이상의 \(A\)가 있어야 한다. 하지만 \(A\)는 empty이기 때문에 적어도 하나의 \(A\)는 존재하지 않기에 Property를 만족시키는 \(x\)는 없다.
  • Intersection의 경우를 생각해보자. 위의 Property를 문장으로 표현하면 \(\forall A \in \mathcal{A}, x \in A\) 이다. vacuous truth 두번째 조건을 보면 Intersection의 Property와 동일한 구조이다. 그렇기에 어떠한 \(x\) 인지 상관없이 위의 statement는 참이 된다.
  • 하지만 많은 수학자가 위의 논리를 인정하지 않기에 Intersection of collection은 collection이 empty set일 때 정의하지 않는다.

Cartesian Product

  • Cartesian product Set \(A \times B\) 는 다음과 같이 정의된다.
\[A \times B = \{(a, b)\text{ }|\text{ } a \in A \text{ and } b \in B\}\]
  • \((a, b)\) 는 ordered pair라고 부른다.
  • 대부분의 ordered pair는 단순히 \(a\) 와 \(b\) 를 element로 가지는 Set으로 여겨지지만, ordered pair의 정의에 따라 다를 수 있다.
  • Cartesian product로 생성된 Set들 간에 Cartesian product를 수행할 수도 있다.
\[(A \times B) \times (C \times D) = \{(a, b, c, d)\text{ }|\text{ } a \in A, b \in B, c \in C, d \in D \}\]