함수와 무한대2


Functions and Infinity

여태까지 추상적인 이야기만 했기 때문에 예를 한번 들어보겠다. 집합 \( A = \{ a,b,c \} \) 와 집합 \( B = \{ 1, 2, 3 \} \)이 있다. 함수 \( f: A \rightarrow B \)를 다음과 같이 정의 하자.
\[ f(a) = 1, f(b) = 2, f(c) = 3 \]
수학자들은 \( f \)를 반복해서 쓰는 대신 다음과 같은 표현도 쓴다.
\[ a \mapsto 1, b \mapsto 2, c \mapsto 3 \]
여기서 우리는 모든 A의 원소가 유일한 B의 원소와 쌍이 되는 것을 볼 수 있다. 집합의 두 개의 크기를 비교하는 것은 이 방법을 적용시킨것이라고 생각하면 된다. 만약 \( A \)에 있는 모든 원소를 \( B \)에 있는 원소와 겹치지 않게 쌍을 지었는데 \( B \)의 원소가 남았다면 우리는 당연히 \( B \)가 더 크다고 이야기 할 것이다. 반대의 경우로는 \( A \)에 있는 모든 원소와 \( B \) 원소와 쌍을 지으려고 했지만  \( B \)의 원소가 모자라는 경우에는 \( A \)가 더 크다고 이야기 한다. 이를 수학적으로 다시 이야기를 하게 된다면,

\( f \)에서 \( f(a) = f(b) \Rightarrow a = b \)가 성립할 경우 우리는 \( f \)를 단사함수(Injective Function)이라고 부른다. 모든 \( b \in B \)에 대하여 \( f(a) = b \)인 \( a \in A \)가 존재할 경우, 우리는 \( f \)를 전사함수(Surjective Function)이라고 부른다.

엄밀하지 않게 \( |A| \)를 집합 \( A \)의 크기 혹은 농도라고 정의 하자. 이 글의 맨 처음 예에서는 직관적으로 두 집합의 크기가 똑같은 것을 알 수 있다. 만약 단사 함수 \( f: A \rightarrow B \)가 존재하게 된다면 우리는 \( |A| \leq |B| \)라고 표현한다. 반대로, 전사 함수 \( f: A \rightarrow B \)가 존재하게 된다면 \( |B| \leq |A| \)가 성립한다.

만약 \( f: A \rightarrow B \)가 단사함수이자 전사함수이면 \( f \)를 단전사함수(Bijective function)이라고 부른다. 이 경우에는 \( |A| = |B| \)라고 표현한다. 여태까지 우리가 알고 있는 지식에 의하면 \( |A| \leq |B| \) 이고 \( |B| \leq |A| \)이면 \(|A| = |B| \)은 당연한 것인데, 지금 우리가 사용하는 부등호는 숫자에서 사용하는 부등호가 아니기 때문에 이를 확인할 필요가 있다.

하지만 상당한 논리 과정을 걸쳐서 증명이 이루어지기 때문에 이를 증명하는 칸토어-번슈타인(Cantor-Berstein) 정리에 관해 여기서 읽어봐라.

이로써 무한대의 집합의 크기는 함수가 존재하냐 존재하지 않느냐에 의해서 결정된다. 다행히도 두 집합 \( A \)와 \( B \)에 관련해서 단사함수 \( f: A \rightarrow B \) 혹은 전사함수 \( f: A \rightarrow B \)가 존재한다. 다시 말해서, 두 집합의 크기는 무조건 비교할 수 있다는 소리다. 이에 관련해서는 순서수(Ordinal Numbers)에 관해 여기서 읽어봐도 나쁘지 않을 것 같다.

Comments

Post a Comment

Popular posts from this blog

The topology of the p-adic numbers 3

Let \( G \) be a topological space and let \( H \) be a subspace of \( G \) endowed with the subspace topology. Then \( H \times H \) endowed with the product topology is same as the subspace topology of \( H \times H \subset G \times G \) with \(G \times G \) endowed with the product topology due to: \[ (U_1 \cap H) \times (U_2 \cap H) = (U_1 \times U_2) \cap (H \times H) \] Let \( G \) be a topological group with a subgroup \( H \). We would like to show that \( H \) endowed with the subspace topology is also a topological group. Let \( p_G \) denote the product map. in \( G \) and \( p_H \) denote the product map in \( H \). We want to show that \( p_H \) is continuous. Let \( U \) be an open set in \( H \), then \(U = U_G \cap H \) for some open set \( U_G \) in \( G \). \[ \begin{array}{lcl} p_H^{-1}(U) & = & \{ (h_1, h_2) \in H \times H ~|~ h_1h_2 \in U \} \\ & = & \{ (g_1, g_2) \in G \times G ~|~ g_1g_2 \in U_G \} \cap H \times H \\ & = & p_G^{-1}(U_G) \
Read more

함수와 무한대 1

중학생에 수학을 배울 당시에는 함수는 단지 \( y=f(x) \)에 불과했다. 그저 뭔가를 집어넣으면 뭔가 튀어나오는 자동판매기였지만 두 가지의 수학적 물체 사이의 관계를 나타내 준다는 것을 깨달았다. 함수를 관계로 보는 시각은 범주론(Category Theory)를 배우다보면 더욱 명확해 진다. 집합(Set)은 원소(Elements)의 모임이다. 보통 대문자 \( A, B, C \)를 사용해 집합을 표현하고 원소 \( a \)가 집합 \( A \)에 있을 경우 \( a \in A \)라고 쓰고 \( a \) 는 \( A \)안에 있다라고 말한다. 집합 \( A \) 와 \( B \)가 있을 때, 모든 \( a \in A \) 에 대하여 유일한 \( b \in B \)가 있을 경우 이 "법칙"을 \( f \)라고 부르고 \( f(a) = b \)라고 쓴다. 여기서 좀 더 들어가게 되면, 집합 \( A, B \)를 이용해서 다음과 같은 집합을 정의할 수 있다. \[ A \times B  \{ (a,b) ~|~ a \in A, b \in B \} \] 함수 \( f \) 는 \( A \times B \)의 부분집합인데, 다음이 성립한다. 만약 \( (a, b_1), (a, b_2) \in A \times B~\) 이면  \(~b_1 = b_2 \) 함수는 위에서 말했던 관계의 일종인데, 관심있는 사람들은 여기 를 참고하자. 위가 성립을 하게 되면 우리는 \( f(a) = b \)라고 쓸 수 있다. 만약 \( f \)가 \( A \times B \)의 부분집합이면 이를 우리는 \( f: A \rightarrow B \)라고 쓴다. 후에 함수를 정의할때 중요한것은 well-defined를 보여주는 것이다. 직역을 하자면 정정(正定)인데 함수가 "말이 된다"라는 것을 보여주는 것이다. 일반적으로 두 가지 정도를 체크해줘야된다. 그 전, 만약 \( f \)가  \( A \rightarrow B \)일 경우에 우리는 \( A \)를 정
Read more

RSA 암호 1. 개요

수학자들 중에서 정수론을 전문적으로 공부하는 사람을 정수론자라고 한다. 워낙 추상적인 개념을 많이 다루는 직업이기에 매번 "그래서 정수론을 배워서 뭐에 써먹는데?" 라는 질문을 자주 받게 된다. 솔직히 말하면 정수론이 실생활에 응용되어 쓰여지는 일은 드물다. 하지만 컴퓨터의 등장 이후, 모듈러 산술을 이용해 암호론에 정수론에 적용되기 시작되었다. 그 중에서 RSA 암호에 대해서 설명해보려고 한다. 정수론에 대해서 이야기 하기 전에 먼저 암호에 대해서 이야기 해보자. 다음 용어를 숙지해두자. 용어정리 평문 : 보호해야 할 메세지 암호문 : 평문을 특정 대상 외에는 이해하지 못하게 변환한 메세지 암호화 : 평문을 암호문으로 바꾸는 과정 복호화 : 암호문을 평문으로 바꾸는 과정 기본적으로 우리는 다음을 하고 싶다. 김씨가 박씨에게 비밀 메세지를 보내고 싶다고 하자. 1. 김씨는 평문을 암호화 하여 암호문을 만든다. 2. 김씨는 암호문을 박씨에게 넘긴다. 3. 박씨는 김씨의 암호문을 받아 복호화를 하여 평문을 읽는다. 두 사람이 다른 사람에게 들키지 않고 비밀 메세지를 주고 받는 방법에 대해서 생각해보자. 일단 가장 간단한 방법은 두 사람이 같은 "키"를 가지고 있는 것이다. 대칭키 암호 (Symmetric-Key Cryptography) 예시 1 자물쇠가 달린 상자로 비유해보자. 김씨와 박씨는 다른 사람은 보지 못하게 비밀 메세지를 교환하고 싶다. 이를 위해서 그들은 자물쇠가 달린 상자를 구매했고 서로 같은 키를 구매했다. 1. 김씨는 비밀 메세지 (평문)을 상자에 넣어 자물쇠를 채운다 (암호화). 2. 김씨는 상자 (암호문)을 박씨에게 넘긴다. 3. 박씨는 김씨의가 보낸 상자를 키를 이용해서 자물쇠를 연다 (복호화). 이와 같이 김씨와 박씨가 같은 키를 쓰는 것을 대칭 키 암호 (Symmetric-Key Algorithm) 이라고 부른다. 만약 박씨가
Read more