순서를 보존하는 함수 찾기 풀이

수학 채널

알림 알림 중 알림 취소

구독자 1957명 알림수신 31명 @시스티나

수학에 대한 이야기를 하는 채널

순서를 보존하는 함수 찾기 풀이

ㅇㅇ (74.102)

추천 0 비추천 0 댓글 5 조회수 225 작성일 2021-03-06 18:08:41

https://arca.live/b/math/22421670

https://arca.live/b/math/21981161

Q를 유리수 집합, Z를 정수 집합이라고 하자.

QxZ={ (a, b) | a∈Q, b∈Z}이다.

그리고 QxZ의 두 원소 (a, b), (c, d)에 대해, (a, b)≤(c, d)를 ( (a＜c) 또는( a=c이면서 b≤d ) )라고 정의하자. (사전식 순서로 생각하면 된다.)

순서가 주어진 두 집합 A, B에 대해, 함수 g : A ->B 가 순서를 보존한다는 것은, 모든 A의 두 원소 a1, a2에 대해, (a1＜a2 이면, g(a1)＜g(a2) ) 라는 것을 의미한다.

그러면, f : QxZ -> Q로 가는 순서를 보존하는 단사 함수(injection)가 존재하는가?

---------------------------------------------------------------------------------------------------------------------------------------------

함수를 다음과 같은 과정으로 구성합니다.

(1) 임의의 크기가 0이 아닌 열린 구간 (a, b) (구간을 정의하는 두 실수 a, b 에 대해서 {x | a<x<b} ) 내에서 정수를 순서를 보존하면서 대응시킬 수 있음을 보입니다.

(2) 모든 유리수를 (0, 1)구간의 유리수에 대응시킬 수 있음을 보입니다.

(3) (0, 1) 구간의 유리수를 서로 겹치지 않는 열린 구간들로 대응시키는, 순서를 보존하는 함수를 구성합니다.

그러면 (1), (2), (3) 을 통해서 문제에서 요구하는 단사 함수가 존재한다는 점을 알 수 있습니다.

우선 (1), (2)는 어렵지 않기 때문에 그림으로 대신하겠습니다.

v = rc / (r+c) 로, r과 c가 모두 유리수라면 v 역시 유리수가 되지요. 음수인 구간에 대해서도 마찬가지로 대응시켜주면 됩니다.

다음은 이진법 순환소수를 이용해서 (3)의 함수를 다음과 같이 귀납적으로 구성합니다.

(진법은 이진법이 아닌 다른 진법이라도 상관없습니다. 그리고 유한소수는 어차피 순환소수로 표시할 수 있으므로 별도로 취급하지 않았습니다.)

단계 1)

(0, 1) 의 유리수 중 순환마디 앞쪽 길이와 순환마디의 길이의 합이 2인 순환소수 (길이의 합이 1인 그런 소수는 (0, 1) 구간에 없으므로 생략했습니다) 의 숫자를 n 이라고 하고 (실제로는 0.011111... 하나밖에 없기는 합니다) 이러한 순환소수들을 크기 순서로 a_1, a_2, ..., a_n 으로 배열합니다.

(0, 1) 구간을 2n+1 개의 열린 구간 iv_1, iv_2, ..., iv_(2n+1) 으로 나누고 ( iv_k = { x | (k-1)/(2n+1) < x < k/(2n+1) } ), a_j 를 iv_(2j) 에 대응시킵니다. 그러면 모든 a_j 는 열린 구간에 순서가 보존되게 대응되고, a_j 에 대응된 열린 구간 사이에는 다른 열린 구간이 존재하게 됩니다.

단계 2)

단계 1에서 나타난 순환소수들을 a_1, a_2, ..., a_n 이라고 하고 (i < j 이면 a_i < a_j) a_i 에 대응된 열린 구간을 iv_i 라고 하겠습니다.

(0, 1) 의 유리수 중 순환마디 앞쪽 길이와 순환마디의 길이의 합이 3인 순환소수들 중 a_i 보다 크고 a_(i+1)보다 작은 수의 집합을 B_i 라 하겠습니다. 그러면 B_i = { b_i1, b_i2, ..., b_in } (j < k 일 때 b_ij < b_ik) 로 정렬할 수 있습니다.

iv_i = (l_i, u_i), iv_(i+1) = (l_(i+1), u_(i+1)) 이라고 하면, (u_i, l_(i+1))에 2n+1 개의 다음과 같은 열린 구간들을 설정할 수 있습니다.

ivi_k = (u_i + (k-1) / (2n+1) * (l_(i+1) - u_i), (u_i + k / (2n+1) * (l_(i+1) - u_i) )

그리고 b_ij 를 ivi_(2k) 에 대응시킵니다.

글로 써놓으니 눈이 어지러운데, 아래 그림과 같은 이야기입니다.

이렇게 되면 임의의 b_ij 가 순서가 대응되고 겹치는 열린 구간 하나에 대응되고, 각 열린 구간 사이에는 공간이 남게 됩니다.

a_1 보다 작은 수들과 a_n 보다 큰 수들도 마찬가지로 구간을 할당할 수 있으므로 생략합니다.

단계 k) (k ≥ 3)

단계 2에서와 마찬가지로, (0, 1) 의 유리수 중 순환마디 앞쪽 길이와 순환마디의 길이의 합이 k+1인 순환소수들을, 단계 k-1 까지에서 할당된 열린 구간들 사이에 집어넣고 마찬가지로 열린 구간들을 하나씩 할당합니다.

이렇게 되면 임의의 유리수가 열린 구간 하나에 대응되며, 열린 구간들은 서로 겹치지 않고 또 유리수의 순서를 보존합니다.

따라서 (3)의 함수를 구성할 수 있으므로 문제의 조건을 만족하는 대응관계를 만들 수 있습니다.

댓글 글쓰기

ㅇㅇ (74.102)

2021-03-06 21:03:01 삭제 수정 답글

이 풀이에서는 "순환마디 앞쪽 길이와 순환마디의 길이의 합"을 이용해서 유리수를 분류했지만, 사실 분류만 되면 어떤 기준이건 상관없습니다. 생각해보니 "기약분수로 나타냈을 때의 분모"를 이용해서 분류하는 편이 훨씬 간단했겠네요.

펼쳐보기▼

ㅇㅇ (110.11)

2021-03-07 05:59:05 삭제 수정 답글

(0,1)을 열린 구간들로 disjoint하고 dense하게 나누는 방법에 대해 감은 잡으신 것 같은데, 


(a b)에 정수를 순서를 보존하게 대응시키려면 
양의 정수는 n -> 1-1/(n+1) ,  0은 0으로, 음의 정수는 n -> -1-1/(n-1)  로 대응시키면 (-1, 1)에 순서를 보존하면서 대응이 되고,   (-1, 1)을  2/(b-a) 배로 압축 혹은 확장시킨 뒤에 b-2/(b-a) 만큼 평행이동시켜주면 되긴 하죠. 

유리수를 열린 구간으로 disjoint하게 나눠야 하는 건 맞는데, 

단계 1에서, 
(0, 1) 의 유리수 중 순환마디 앞쪽 길이와 순환마디의 길이의 합이 2인 순환소수인 경우는,

0.010101...  , 0.0111111...,   0.10101010.... 으로 3가지가 있지 않나요?

그리고 a1, a2, ..., an 중 하나가 k/(2n+1),  (k는 0이상, 2n+1 이하의 정수)인 경우에는 a1, a2, ..., an 중 한 개는  iv_1, iv_2, ..., iv_(2n+1) 의 원소가 아닐 수 있어요.   



단계 2에서,
의도된 것인지는 모르겠지만, B_i의 원소의 개수(=n)랑 단계 1의 순환소수의 개수(=n)이랑 같다고 보신 건가요?

의도된 게 아니시라면, B_i의 원소의 개수가 2개 이상이어야 그 다음 단계에서도 문제가 안 생길 것 같습니다. (이 부분은 가능할 거라고 봅니다.)

B_i의 원소들이 언제나 v_ik들 중 하나의 원소이다. 라는 부분도 설명이 필요할 것 같습니다. v_ik를 m등분하는 방법은 까다로울 수 있겠네요. 


결론 부분에서, 
임의의 유리수가 열린 구간 하나에 대응된다는 부분에서,
v=rc/(r+c)   (r과 c는 양의 정수)라고 대응을 잡으신 것 같은데, 양의 유리수만 생각해도 되긴 하는데, 저렇게 잡으면 단사 함수가 되나요?  그리고 rc/(r+c)들이 disjoint한 열린 구간들 중에 대응되는 게 있다면, 하나만 대응되어야겠지만 언제나 존재한다고 볼 수 있나요?

펼쳐보기▼

ㅇㅇ (74.102)

2021-03-07 13:53:19 삭제 수정 답글

*수정됨

0.10101010.... 도 앞쪽 길이와 순환마디의 길이의 합이 2가 맞네요. 감사합니다. 하나 빠뜨렸네요. 하지만 풀이에서는 개수가 n인 일반적인 경우로 풀었으니 개수가 1이건 2이건 마찬가지로 됩니다. (010101... 는 앞쪽 길이와 순환마디의 길이의 합이 3입니다.)

a1, a2, ..., an 중 한 개는 iv_1, iv_2, ..., iv_(2n+1) 의 원소가 아닐 수 있다는 말씀은 의미를 모르겠습니다. 여기서는 각각의 유리수를 열린 구간 하나에 대응시키는 것이 목적입니다. 열린 구간 하나가 대응되면 정수들을 전부 그 구간 안의 유리수들에 순서가 보존되게 대응시킬 수 있으니까요. 그 목적으로 a_i 라는 유리수를 iv_(2i) 라는 구간 하나에 대응시키는 것입니다. 따라서 a_i 가 iv_j 의 원소일 필요는 없습니다. 마찬가지로 B_i 의 원소들이 ivi_ik 의 원소일 필요도 없습니다.

n 을 중복해서 사용한 것은 단순히 사용할 알파벳이 부족해서였고 두 n 이 같은 숫자라는 뜻은 아닙니다. 공연히 혼란스럽게 만든 것 같군요. n_1, n_2, ... 하는 식으로 구분해서 써주는 편이 나았겠습니다.

v=rc/(r+c) 는 (3)이 아닌 (1), (2) 부분에 대한 것입니다. 그러니까 v를 구간에 대응시키는 것이 아니라, 모든 유리수 (혹은 정수) r 이 열린 구간 내의 유리수 v 에 대응된다는 점을 보인 것입니다. 그림에서 (-c, c) 가 열린 구간을 나타냅니다. (열린 구간의 lower bound 는 꼭 -c 가 아니어도 상관없기 때문에 그림에서는 표시하지 않았습니다.) 단사함수가 된다는 점은 v는 r에 대해서 단조증가한다는 점으로 설명됩니다.

펼쳐보기▼

ㅇㅇ (110.11)

2021-03-07 17:40:43 삭제 수정 답글

*수정됨

아, 유리수 집합에서 (0, 1)로 가는 순서를 보존하는 bijection을 잡고,  (0, 1)의 모든 유리수를 dense한 disjoint open set들에 대응시켜준다는 의미였군요.

그러면 맞겠네요.


풀이를 살짝 일반화하고 좀 더 엄밀하게 풀어 쓰자면,

유리수 집합을 서로 disjoint한 non-empty finite set들의 합집합으로 표현한 뒤에,
Q=UF_i  (i는 양의 정수)

base case로 F_1의 원소들 a1, a2, .... , an  (a1<a2<a3< ... <an)에 대해서 

v_(1, k) = (k/(2n+1), k/(2n+1))  for k=1, 2, ... , n 이라고 하고, 

O1= { v_(i, 2k) |  k∈{1, 2, ... , n} } 이라고 정의하고, 

함수 g_1 : F_1 -> O1 such that g_1(ak)=v_(i, 2k) 라고 정의.


수학적 귀납법으로 

가정 : 
O_n은 disjoint open interval들의 집합이고,
함수 g_n : UF_x  (x=1 ~ n) -> U O_x (x=1~n)이 순서를 보존하는 단사 함수이고, 
g_n의 정의역의 임의의 서로 다른 두 원소 a＜b 에 대해, g_n(a)의 모든 원소보다 크고, g_n(b)의 모든 원소보다 작은 유리수가 2개 이상 존재하고
g_n은 순서를 보존하는 단사 함수임을 가정,

F_(n+1)의 원소들 b1, b2, ...., bm,  (b1<b2< ... <bm) 에 대해서
UF_x  (x=1 ~ n)의 원소들 c_1, c_2, ...., c_z에 대해, c_0=0, c_(z+1)=1이라고 하면,

for k= 0, 1, 2, 3, ..., z,  C_k={ b∈F_(n+1) | c_k<b<c_(k+1)} = {d_1, d_2, ... , d_o}에 대해, 
    F_(n+1)=UC_x (x=1~z)  가 성립하고, 
    C_k가 공집합인 경우에는 O_(k, n+1)= 공집합으로, 
    C_k가 공집합이 아닌 경우에는
        열린 구간 (c_k, c_(k+1))을 (2o+1)개로 나눈 뒤에, 
         가령, x=1, 2, 3, ... , 2o+1에 대해 v_(n+1, k, x) = (c_k+ (x-1)/(c_(k+1)- c_k), c_k+ x/(c_(k+1)- c_k)  )라 
          는 열린 구간으로 잡고,    
         O_(n+1, k) = { v_(n+1, k, 2j) | j∈ { 1, 2, ... , o} }라고 정의한 뒤에,
         g_(n+1, k) : C_k -> O_(n+1, k) s.t. g_(n+1, k) ( d_j ) = v_(n+1, k, 2j) for j=1, 2, .. , o 라고 정의.


O_(n+1) =U O_(n+1, x)  (x=1 ~ z) 라고 정의,
UF_x  (x=1 ~ n)와 F_(n+1)은 서로소이므로  F_(n+1)=UC_x (x=0 ~ z) 이 성립,
함수 g_(n+1) : UF_x  (x=1 ~ n+1) -> U O_x (x=1~n+1) s.t. 임의의 bk∈F_(n+1)에 대해 bk∈C_y인 유일한 양의 정수 y가 존재하고, g_(n+1) (bk) = g_(n+1, y) (bk) 이고,  임의의 a∈UF_x  (x=1 ~ n) 에 대해, 
g_(n+1)(a) = g_n(a)라고 정의.

이후 O_(n+1)과 g_(n+1)이 가정의 성질들을 여전히 만족하는 것을 증명.


그 다음에 O=UO_n  (n=1에서 무한) 이라고 정의하고, 
g : Q -> O s.t. 임의의 q∈Q에 대해, q∈F_x 인 유일한 양의 정수 y가 존재하고, g(q)=g_y(q)라고 정의하고 최종적으로 g가 순서를 보존하는 단사 함수임을 증명한다는 방식이네요.

펼쳐보기▼

ㅇㅇ (74.102)

2021-03-07 21:46:24 삭제 수정 답글

예, 이런 식으로 정리하는 게 더 깔끔하네요. 감사합니다.

그리고 올려주신 풀이를 읽어보다가 문득 떠오른 건데, F_i 는 어쨌든 "유한이고 서로 disjoint 하고 F_i 의 합집합이 유리수 전체의 집합이면" 되는 것이니까, 각 F_i 의 원소는 단 한 개라도 상관없을 것입니다. 그렇다면 F_i 라는 집합들을 늘어세우는 대신 그냥 유리수들을 일렬로 늘어세우고 open interval 을 차례대로 하나씩 대응시키는 것도 괜찮을 것 같습니다. 그렇게 하면 (본질적으로 같은 이야기겠지만) 풀이의 길이는 조금 더 짧아질 수 있겠네요.

펼쳐보기▼