Set Theory

이것저것 공부/확률과 통계

Set Theory

해피밀세트 2024. 9. 15. 00:29

Set 이란?

수학적인 대상 중 가장 기본이 되는건 Set
Set은 어떠한 대상들이 모여있는 Collection이라고 할 수 있음

https://www.geeksforgeeks.org/set-theory/

Set의 기본

Set

객체의 집합
중괄호({})로 표현하고, 콤마(,)로 원소들을 구분함 (e.g., {1,2,3,4,5})
set은 다른 set을 포함할 수 있는가? => 가능
* 하지만 이것으로 여러가지 패러독스가 발생하기도 함 (러셀의 패러독스, 불확실성의 원리)

Element

set 안에 있는 멤버를 표현하는 말
∈로 표현함 (e.g., 1 ∈ {1,2,3} = 1은 set의 element이다)
포함 관계는 ⊂로 표현

Subset (부분 집합)

set안에 있는 모든 element 중에 일부로 만들어지는 다른 set
{a,b}는 {a,b,c}의 subset 이다

Universal set (전체 집합)

고려하는 모든 subset의 모임
{a,b}와 {b,c}의 universal set은 {a,b,c} 이다

Disjoint sets (서로소 집합)

어떤 set 간의 intersection(교집합)이 공집합인 관계
서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합
A ∩ B = ∅

Partition of Set

Disjoint sets의 Union set이 Universal set인 경우
example: set A = {1,2,3,4}, Partition of A: {{1,2},{3},{4}}

Cartesian product

두 개의 Set의 원소를 받는데 첫번째 원소는 첫번째 Set에서 가져오고, 두번째 원소는 두번째 Set에 가져오는 관계
example 1
· A = {1,2}, B = {3,4,5}
· A x B = {(1,3), (1,4), (1,5), (2,3), (2,4), (2,5)}
example 2
· $ \mathbb{R} $ : 실수의 집합
· $ \mathbb{R}^{2} $ : 2차원 변수의 집합
· $ \mathbb{R}^{d} $ : d차원 변수의 집합
· $ (x,y)\in\mathbb{R}^{2}=\mathbb{R}\times\mathbb{R} $
· 위의 식이 Cartesian product와 동일함. 각각의 실수에서 값을 가져왔기 때문
example 3
· 가우시안 분포는 $ N(\mu ,\sigma ^{2}) $ 로 정의됨
· $ \mu $ (평균)과 $ \sigma^{2} $ (분산)의 파라미터들이 살고 있는 공간은 $ \mathbb{R}\times \mathbb{R}_{\geq 0} $ 로 정의할 수 있다
· $ \mu $ 은 실수의 모든 값을 가질 수 있고, $ \sigma^{2} $ 는 양수의 모든 값을 가질 수 있는데 여기서 각각 한개씩 가져오기 때문· Cartesian product을 했을때 Cartesian product를 한 원소의 개수는 각각의 set의 원소의 개수를 곱한 것과 같다

Power set

set의 원소들로 만들 수 있는 집합
A라는 set이 있을때, A의 원소로 만들 수 있는 집합의 개수는 $ 2^{A} $
example
· A = {1,2,3}
· $ 2^{A} $ = { $ \varnothing $, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3} }

Set의 원소의 개수 계산 (Cardinality)

Cardinality: 원소의 개수
절대값으로 표현함
· |A| = set A의 원소의 개수
Cardinality의 구분: Finite, Infinite, Countable, Denumerable, Uncountable
|A| = m, |B| = n 일때, |AxB| = mn (Cartesian product)
|A| = n 일때, |$ 2^{A} $| = $ 2^{n} $ (Power set)
어떤 두개의 set 사이에서 일대일 대응을 할 수 있으면 같은 Cardinality를 갖는다고 표현할 수 있다

Finite

유한한 set
{1,2,3}

Infinite

무한한 set
자연수의 집합, 실수의 집합
* 자연수의 집합의 무한과 실수의 무한이 같을까?
Finite과 Infinte을 구분할때 자연수로 줄세우기를 사용할 거임
자연수와 one-to-one 매칭이 된다면 Finite이라고 함

Countable

유한함와 자연수로 유한하다는 특성을 갖추고 있음. 즉, 셀 수 있음
자연수의 집합과 같은 Cardinality를 갖고 있다면 Countable이라고 함
자연수 전체의 집합과 one-to-one 매칭이 되거나, 자연수 전체의 집합의 Subset과 one-to-one 매칭이 됨
정수는 자연수의 집합과 one-to-one 매칭이 되므로 Countable set이다
{1,2,3}, 자연수의 집합($ \mathbb{N} $), 정수의 집합, 유리수의 집합 등

Denumerable

Countable와 Uncountable의 경계
셀 수는 있지만 무한함 (Countably infinite)
자연수 전체의 집합과 같은 Cardinality를 갖는 set
모든 Denumerable set은 같은 집합의 원소의 수를 가지고 있다
* 자연수의 집합, 정수의 집합, 유리수의 집합은 모두 같은 원소의 수를 가지고 있다
$ \aleph_{0} $(aleph null)로 표현됨
체계화 되어 있는 Infinite

Uncountable

자연수 전체의 집합보다 더 큰 무한한 집합 (예. 실수의 집합)
1874년 Georg Cantor가 증명함
0에서 1사이에 있는 모든 실수들의 집합, 혹은 실수 전체를 Uncountable set이라고 함
Cardinality 차원에서는 0~1 사이의 실수의 집합과 실수 전체의 집합이 같다. (두 집합 사이의 매핑을 만들 수 있기 때문)
이런걸 Continuum이라고 함
Continuum: c = $ 2^{\aleph_{0}} $
|$ \mathbb{N} $| < |$ \mathbb{R} $|을 증명하는 과정에서 위의 식이 쓰임

Mapping

https://ics.uci.edu/~alspaugh/cls/shr/correspondence.html

random variable의 정의가 어떤 sample space에서 observation space로 가는 매핑이다.
어느 한 점에서 다른 한 점으로 모이는 것을 매핑이라고 한다
Function (혹은 Mapping)은 두 개의 set 사이에서 정의됨

Domain (정의역)

함수에서 입력값이 될 수 있는 모든 값들의 집합을 의미함
함수에 넣을 수 있는 값들이 모여 있는 범위

Codomain (공역)

함수의 결과값이 들어갈 수 있는 값들의 집합을 의미함
즉, 함수가 출력될 수 있는 값들이 속하는 범위
다만, Codomain에 속하는 모든 값이 실제로 함수의 결과로 나오는 것은 아님

Image

Domain에 있는 subset이 매핑을 통해 얻어지는 Codomain 속의 subset을 의미함
Codomain에 속하는 원소
f(A) = {f(x) ∈ V : x ∈ A} where A ⊆ U
x가 A에 속하는 모든 원소일때, f라는 매핑을 통해서 V라는 공간에서 모이는 모든 점들을 모아놓은 set
A는 Domain U의 subset
* Image는 Element에서 Element 로 가는것이 아니라 Set에서 Set으로 가는 것임 (Set Function)

Range

Domain의 Image
* Domain U를 다 집어 넣었을 때 Codomain V의 어디에 속하는지
U의 모든 원소들을 가지고 매핑을 통과했을 때 V를 다 채울 수 도 있지만, 채우지 못할 수도 있음

☆ Inverse image or Pre-image

함수에서 결과값에 대응하는 입력값
$ f^{-1} $(B) = {x ∈ U : $ f(x) $ ∈ B} where B ⊆ V
확률은 Pre-image로 정의된다
Codomain에 속하는 원소가 만들어지기 위해 입력으로 들어간 Domain에 속한 원소가 무엇인지 가리킴
머신러닝이나 생성모델의 Inverse Problem 풀 때 사용되는 개념
일반적으로 Mapping이 만족되는 조건은 Domain의 점이 Codomain의 한 점으로 간다
Domain의 점이 Codomain의 두 점으로 가지 않는다
Inverse image를 계산하기 어려운 이유
· Codomain에 속하는 하나의 원소가 Domain의 여러개의 원소에서 왔을 수 있기 때문
· Domain에 있는 Image가 Codomain을 모두 커버하지 않을 수 있기 때문에 특정 원소는 Inverse image가 존재하지 않을 수 도 있기 때문
* Random variable를 어떤 Set 사이의 매핑으로 정의한다면, 확률은 observation space에서의 Inverse image로 얻어지는 Sample space의 measure가 될 것이다

Mapping의 종류

https://www.cs.csub.edu/~eddie/cmps2120-s19/material/ch2_sets_funcs/ch2.3.notes.html

onto (or surjective)

f(U) = V
Domain의 모든 점들이 Codomain으로 매핑되었을 때, Codomain의 모든 점들이 포함될 때

one-to-one (or injective)

f(a) = f(b) → a = b
Domain의 원소가 각각 Codomain의 하나의 원소와 매핑됨

invertible (or bijective)

one-to-one과 onto가 모두 성립함
역함수가 존재하는 것의 정의
Domain과 Codomain의 원소 개수가 같다
생성모델 중 Normalizing Flow와 관련된 논문엔 항상 Invertible mapping 이 나옴
· Invertible mapping을 통해 Latent space에서 Image space로 가는 것이 Normalizing Flow이다.
Invertible 하려면 데이터의 cardinality가 같아야 하고 차원이 똑같다는 의미

neither

위의 3개 중 아무것도 아니지만 함수임
우리가 보는 대부분의 Mapping

not a function

Domain에 커버되지 않은 원소가 있음
Domain에 있는 하나의 원소가 Codomain의 원소 두 개로 매핑됨

Axiom of extensionality (외연성 공리)

두 개의 Set의 Cardinality가 같고, 두 개의 Set의 Element가 일대일 대응이 되는 매핑을 찾을 수 있으면, 두 개의 Set은 같다고 말할 수 있다.
example 1
· x ∈ A = [1,2], y ∈ B = [1,4] 라면 B가 A보다 3배 많을 것 같지만, y=2x라는 매핑을 만들면 둘은 같다고 할 수 있다.
example 2
· 자연수의 집합과 정수의 집합도 2배 차이가 나는 것 같지만 매핑을 해보면 둘은 같다

https://blog.naver.com/duxogn08/221154831584?photoView=5

A = {t | 0 ≤ t ≤ 1 }, B = {(x,y) | 0 ≤ x ≤ 1, 0 ≤ y ≤ 1 } 이러한 두 개의 Set이 있다면 A와 B의 Cardinality는 같은가?
→ 같다
· 어떻게하면 Inverible한 매핑을 찾을 수 있는가? → 보통은 이진법을 사용함
· A는 0~1 사이의 집합이니까 $ A = 0.x_{1}x_{2}x_{3}\cdots $ 이런 식으로 쓸 수 있고,
B는 $ B = (0.x_{1}x_{2}x_{3}\cdots, 0.y_{1}y_{2}y_{3}\cdots) $ 이렇게 쓸 수 있다.
· 여기서 $ x_{1}x_{2}x_{3}\cdots $ 와 $ y_{1}y_{2}y_{3}\cdots $는 무한으로 갈 수 있고, 각각을 0또는 1로 표현함
· 이것으로 $ t=0.x_{1}y_{1}x_{2}y_{2}x_{3}y_{3}\cdots $라는 또다른 무한한 집합을 만들 수 있다
· 여기서 t는 항상 0~1사이에 있는 값이므로 A와 같다
0~1 사이의 1차원과 0,1,0,1 2차원 점들도 다 같은 Cardinality를 갖는다
0~1 사이 모든 실수들의 개수와 임의 d차원의 Euclidean space($ \mathbb{R}^{d} $)가 같은 Cardinality를 갖는다
* 실수의 집합보다 더 큰 Cardinality를 갖는 Set은 존재하는가?

응용 문제

1. 모든 정수의 집합과 모든 유리수의 집합은 같은가?
→ Yes

정수의 집합과 유리수의 집합의 관계는 denumerable

2. A = [0,1], B = $ \mathbb{R_{\geq 0}} $ 일때 이들의 관계는 어떻게 찾을 수 있나?
→ 아크탄젠트를 사용

3. C=[0,1]의 cardinality가 uncountable(셀 수 없음)을 보여라(Cantor's diagonal argument)
1) 목표: 실수 집합 [0,1] 사이의 모든 수가 countable(가산 무한)하지 않음을 증명하고 싶습니다.
2) 가정: 우선, [0,1] 구간의 실수들이 가산 무한하다고 가정합니다. 즉, 모든 실수를 리스트로 나열할 수 있다고 생각하는 겁니다.
3) 리스트 만들기: 각 실수를 소수점 이하의 무한 소수로 표현해서 리스트로 나열합니다.
4) 대각선 방식: Cantor는 이 리스트에 존재하지 않는 새로운 실수를 만들어냅니다. 이를 위해, 각 소수의 첫 번째 자리에서 첫 번째 숫자, 두 번째 자리에서 두 번째 숫자, 세 번째 자리에서 세 번째 숫자, ...를 고릅니다. 그런 다음 각 숫자를 바꿔서 새로운 숫자를 만들어요.
5) 결론: 이렇게 새로 만들어진 숫자는 리스트의 어느 실수와도 일치하지 않습니다. 즉, 가정했던 "리스트로 모든 실수를 나열할 수 있다"는 것이 틀렸다는 결론에 도달하게 됩니다.
→ 결론: 이 방법을 통해 [0,1] 구간의 실수들이 countable이 아님을 증명할 수 있습니다. [0,1] 구간의 실수는 uncountable입니다.

4. 그렇다면, 0과 1 사이의 실수는 몇 개인가? (증명 개요)
1) Cantor의 대각선 논법을 사용하면, 0과 1 사이의 실수를 모두 나열하는 것은 불가능하다는 것을 알 수 있습니다. 이 논리로 인해, 0과 1 사이의 실수들은 가산 무한 집합이 아니라는 결론에 도달하게 됩니다.
2) 수학적으로, 0과 1 사이의 실수 집합의 cardinality는 c = $ 2^{\aleph_{0}} $로 나타내며, 이는 자연수나 정수의 집합보다 더 큰 크기의 무한입니다.
→ 결론: 0과 1 사이의 실수의 개수는 uncountable이며, 자연수나 정수의 집합보다 훨씬 더 많은 수가 존재합니다.

5. * 한 마을에 이발사가 있다. 이발사는 스스로 이발할 수 없는 사람들을 모두 이발해준다. 마을의 모든 사람들이 깨끗해져야 한다고 할때, 이발사는 누가 이발해주는가? (Barber paradox)
→ 왜 이런문제가 생겼는지 생각해보자 → Set 안에 Set이 존재하기 때문에 발생 → Subset과 Set이 같은 층위에 존재함