Ordering

집합 이야기의 틀 로 돌아가기

순서 있는 집합

"내가 너를 더 사랑하는 거 같아, 안그래? 짜증나 !"

"아빠가 더 좋아, 엄마가 더 좋아?"

라는 말들을 일상에서 들을 때가 있다. 그 상황과 심정을 모르는 바 아니다. 또 이런 말들이 사랑의 심리학에 어떤 작용을 하는가 하는 설명들도 읽다만 신문지처럼 여기저기 쌓였다. 하지만 수학적인 관점에서 보면 조금은 뜬금없는 말이다. 왜냐하면 그 말을 하기 위해서 먼저 분명하게 해두야 할 것이 있기 때문이다.

사람들 이라는 모임에서 '사랑하다'라는 관계로 순서를 지을 수 있는가?

하는 문제다. (과연 가능할까?)

사람들의 삶은 항상 합리적이거나 논증적이지 않다. 논리적 관점에서 본다면 보통은 뒤죽박죽된 채 그 안에서 기쁨에 펄쩍 뛰기도 하고 노여움에 못이겨 속이 상하기도 한다. 그렇다고 마냥 불합리하는 것 같지도 않다. 어느 모임이건 그 나름의 논리가 어느정도는 있기 마련이니까. 어쨌건, 삶의 다양한 모습에 대해 수학적이고 논증적인 해결을 시도하려고 하는 것도 아니다.^[1] 수학적으로 위의 질문들에 답을 하려고 하지 않는다. 다만 그와같이 '순서있는 어떤 모임'의 성질에 대해 함께 살펴보고자 한다. 여기에서도 마침표를 쉽게 찍는 우리의 상식에 대신 물음표를 붙이는 재미있는 사실들이 등장한다. 이를 통해 우리는 집합의 세계에 대해 그리고 '수'에 대해 더 깊이 이해할 수 있으리라 기대한다. 무엇보다 빨리 달려가려는 세상에서 '머뭇거리게 하고' 생각하게 만든다.

우리는 다음의 문제를 함께 생각해볼 것이다.

어떤 모임(집합)이 순서지워질 수 있다 또는 순서 정해질 수 있는 집합 이란 무엇을 뜻할까?
"잘" 순서지워진 이라는 개념이 있다면 무엇일까?
순서 정해진 집합의 기본 성질은 무엇일까?
자연수 너머에도 수가 있을까?

순서있는 집합의 정의

가만히 보면 지금까지 우리는 집합에 대하여 이야기 하면서 집합의 원소나 크기들에 관심을 주로 가졌다. 집합을 분류해보면서 유한과 무한으로, 그리고 더 나아가 세기 개념에 기초해서 무한 집합도 '크기'가 다를 수 있다는 사실을 보았다. 그렇지만 그때 집합들은 아무런 성격없는 바로 원소들의 모임이었을 뿐이다. 이 안의 원소들끼리 어떤 성격도 갖지 않았다. 그런 '탈색'에서 벗어나 약간 채색하면서 그 색이 들어있는 것들을 따로 떼어 생각해보자. 집합의 세계로 더 깊이 탐험 떠나보자. .

우리가 만나는 수학적 대상들 중에는 순서가 있는 것들이 많다. '두 점 사이에' 다른 점이 있다. 라거나 ' 자연수 a 는 자연수 b 보다 크다' 거나. 모두 순서에 대한 말이다. 기하의 가장 기초인 직선은 '점들의 순서'에 대한 성질로 정의된다.^[2]'크기'와 '순서' 처럼 기초적인 관계가 또 있을까? 이렇듯 수학의 기초적인 대상들을 모두 포괄할 수 있을만큼 적당히 큰, 그러나 지금까지의 방법처럼 '탈색되고 너무 큰 집합' 이 아닌 집합들만 보기로 하자. 바로 '원소들의 순서가 있는' 집합을.

정의 (순서 관계) : 어떤 집합 X 에 대해 모든 원소들에 다음의 성질을 만족하는 관계를 순서 관계라고 한다.^[3]

(reflexsive) a

\leqslant

a ,

(antisymmetry) a

\leqslant

b 이고 b

\leqslant

a 면 a = b

(transitive) a

\leqslant

b 이고 b

\leqslant

c 면 a

\leqslant

c

위에서 = 은 같음 관계를 뜻한다. 자연수 집합은 '크다'라는 개념으로 $\leqslant$ 를 표시하지만, 여기서는 위의 성질을 만족하기만 하는 '순서' 관계가 있으면 되는 것이지 꼭 크다 아니다라는 개념이 아니라는 데 주의하라. 다시 말해 자연수 집합에서 흔히 쓰는 '대소관계' $\leq$ 는 순서 관계의 특수한 하나의 경우일 뿐이다. 그에 비해 우리의 순서 관계 $\leqslant$ 는 그저 '앞'과 '뒤'를 뜻할 뿐이다. 무엇이 앞에 올 것인지는 그때그때 정해줄 수 있다. { 1, 2 ,3, 4, 5 } 라는 집합을 보자. 아직 어떤 순서도 없다. 이를 순서지워서 쓴다면

{ 1, 2, 3, 4, 5 }

\qquad

'작은 것을 앞에 큰 것을 뒤에' 순서, 이때

\leqslant :=\leq

{ 5, 4, 3, 2, 1 }

\qquad

'큰 것을 앞에 작은 것을 뒤에' 순서 , 이때

\leqslant :=\geq

{ 1, 3, 5, 2, 4 }

\qquad

'홀수 먼저, 작은 것 먼저' 다음에 '짝수 작은 것에서 큰 것으로' 순서.

{ 2, 3, 1, 3, 5 }

\qquad

'짝수 먼저, 작은 것 먼저' 다음에 '홀수 작은 것에서 큰 것으로' 순서.

{ 5, 3, 1, 4, 2 }

\qquad

'홀수 먼저, 큰 것 먼저' 다음에 '짝수 큰 것에서 작은 것으로' 순서.

.....

정할 수 있는 방법은 여럿이다. 그렇다면 질문.

어떤 집합의 원소가 n 개 일 때, 서로 다른 순서 관계는 몇개날 될까 ?

그렇듯, { 엄마, 아빠, 할머니, 할아버지 } 라는 집합은

{ 엄마, 아빠, 할머니, 할아버지 }

{ 아빠, 엄마, 할머니, 할아버지 }

{ 엄마, 할머니, 아빠, 할아버지 }

{ 할머니, 할아버지, 아빠, 엄마 }

..... 로 다양하게 순서 지울 수 있다. 어떤 것이 그 가족의 '사랑'의 관계라고 이름 붙일 수 있을지 ?

자연수 집합도 보통은 { 1, 2, 3, 4, 5, ... } 라고 쓰지만, 그것은 특수한 경우일 뿐이다.

{ ... , 3, 2, 1 }

{ 1, 3, 5, ... , 2, 4, 6, ... }

{ ..., 6, 4, 2, ... , 5, 3, 1 }

로 할 수도 있고 얼마든지 다른 방법을 생각할 수 있다. 원소가 같아도 순서 때문에 다른 집합이라고 볼 수 있다.

이제 우리는 '순서 있는 집합'을 정의할 수 있다.

정의(순서있는 집합) : 어떤 순서 관계가 주어진 집합을 순서 있는 집합 이라고 한다.

어떤 집합 X 가 순서 $\leqslant$ 가 주어졌다면, 순서있는 집합을 기호로

< X,

\leqslant

>

쓰기로 하자. 그렇다면 순서 있는 집합의 예를

<\mathbb {N} ,\ \leq >

<{\mathcal {P}}(X),\ \subset >

<\mathbb {N} ,\ \mid \ >

, 여기서 'a | b' 관계는 'a 는 b 를 나눌 수 있음' 을 뜻함.

어떤 집합이 순서가 있다고 해서 모든 원소들을 비교할 수 있다는 것은 아직 장담할 수 없다. 비교할 수있다는 것을 정의하면

정의 (비교가능) : 순서 있는 집합 X 의 원소 a, b 에 대해 a

\leqslant

b 거나 b

\leqslant

a 이면 a 와 b 는 비교 가능하다고 한다.

정의 (선형으로 순서 있는 집합) : 어떤 순서 있는 집합의 원소들이 모두 비교 가능하면, 우리는 이를 '선형으로 순서 있은 집합' 이라고 한다.

다시 말해 한줄로 순서 있는 집합이란 어떤 집합의 순서를 앞에 든 대부분의 예에서 보듯 '한줄로' 늘여놓을 수 있다는 뜻이다. 한줄로 순서 있는 집합은 순서 있는 집합의 특수한 모임이다. 모든 순서 있는 집합은 한줄로 늘여놓을 수 있을까? 아니다.

앞에 여러 예들 중 '한줄로 늘여놓을 수 없는 순서있는 집합'을 찾아보라. 그리고 다른 예를 몇 개 생각해보라.

빈집합

\emptyset

은 순서 있는 집합일까 아닐까?

순서 있는 집합의 성질

순서 있는 집합은 집합들 중 특수한 성격을 가지면서도 수학 세계 안에서나 현실 세계에서 만날 수 있는 상당히 많은 집합을 포괄하기 충분하다. 물론 이렇게 '적당히' 범위를 한정시키면 과연 어떤 비밀을 밝혀낼 수 있는 것일까?

먼저 이 울타리 안에서 적용될 수 있는 '관계'를 지정해보자. 이 울타리 안의 집합들끼리 비교할 수 있는...

정의 (같은 꼴 관계(isomorphism) ) : 두 순서있는 집합 사이에 순서가 안바뀌는 일대일 대응이 있으면 그 두 집합은 같은 꼴 관계 라고 한다.^[4]

이것을 기호로 하면 보다 분명해진다. 아래의 집합 X 에서 Y 로 대응하는 f 가 일대일 일 때, 두 집합은 같은꼴인 것이다.

a

\leqslant

b 이면 f(a)

\leqslant

f(b) 이고 그 역도 성립.

이런 관계에 있을 때 기호로 이렇게 나타내기로 하자.

X

\approx

Y

이 관계도 '같음' 이나 '같은 세기'처럼 아래 세 성질을 갖는다는 것을 분명하다. (증명해보라.)

X

\approx

X.

X

\approx

Y 이면 Y

\approx

X.

X

\approx

Y 이고 Y

\approx

Z 면, X

\approx

Z.

그렇다면 이 울타리 안에는 '같음' (=) , 같은 세기( $\sim$ ), 같은꼴 ( $\approx$ ) 이라는 관계들이 있다. 같음은 너무 뻔하고, $\approx$ 인 관계에 있는 두 집합은 $\sim$ 관계도 된다는 것은 정의에 따라 명확하다. 그렇다면 그 역도 성립할까? 다시 말해 두 관계는 같은 뜻의 다른 표현일까? 그럴 것 같지는 않다. 그 예를 보자. 무한집합에 대하여 그 역도 성립한다고 할 수는 없다. (유한집합에 대해서는 어떻게 될까?^[5]

정리 : 유한 집합 중 순서 있는 집합 X , Y 는 X

\sim

Y

\Leftrightarrow

X

\approx

Y

< { 1, 2, 3, 4, 5 , ... } , $\leq$ > 와 < { ... 5, 4, 3, 2, 1 } , $\leq$ > : 첫번째 순서 있는 집합의 첫번째 원소는 두번째 집합으로 대응할 수가 없다.
< [0,1] , $\leq$ > 와 < $\mathbb {R}$ , $\leq$ > : 첫번째 집합의 가장 큰 원소는 두번째 집합으로 대응할 수 없다.
< $\mathbb {Z}$ , $\leq$ > 와 < $\mathbb {Q}$ , $\leq$ > (왜 그럴까?)

다시 말해, 어떤 순서있는 두 집합 X, Y 에 대해

정리 1 : X $\sim$ Y 면 일반적으로 X $\approx$ Y 라고 할 수 없다. ^[6]

가장 자연스러워보이는 자연수 집합과 유리수 집합에 대해 '크기 관계'가 정해졌다면, 그 관계가 유지되면서 일대일로 대응시킬 수 없다니. 무언가 갑갑하다. 예쁘지 않다. 혹시 순서 있는 집합 안에 어떤 특별한 울타리를 치면 그 울타리 안의 집합들은 이런 상황이 안일어날 수 있을까?

잘 순서지워진 집합과 ordinal number

우리는 앞에서 집합 전체를 '순서'라는 울타리를 쳐서 그 안의 집합들을 보았다. 그리고 우리는 다시 그 안에 울타리를 더 치고 싶다. 칸토르는 '잘 순서지워진 집합' 이라는 개념을 생각해내었다.

정의 (잘 순서지워진 집합) : 어떤 순서 있는 집합이 가장 처음 원소가 있고 선형으로 순서지워져 있으면 잘 순서지워진 집합이라 부른다.

인공적이거나 이상한 정의가 결코 아니다. 예를들어 익숙한 자연수 집합을 보라. 모두 그 시작 지점이 있고 나머지 원소들은 한줄로 차례차례 늘어놓게 된다. 그리고 수학적 귀납의 원칙 을 생각해보라.

시작지점에서 참이고
차례차례 늘어선 중간에 어느 이웃하는 것을 잡았을 때 앞의 원소에 성립하는 성질이 뒤의 것에도 성립하면
무한 집합의 모든 원소에 대해서도 참이다.

라는 원칙 아니었던가. ^[7] 위의 정의는 이렇게도 바꿀 수 있다. (정말 그럴까?)

정의 (잘 순서지워진 집합) : 어떤 순서 있는 집합 X 의 어떤 빈집합 아닌 부분집합도 처음 원소를 가지면 X 는 잘 순서지워진 집합이라 부른다.

그렇다면 어떤 집합이 잘 순서지워진 집합일까?

자연수 집합
자연수 집합 $\cup$ { -3, -2, -1 , 0 }
자연수 집합 $\cup$ n 개의 원소로 된 선형으로 순서 지워진 집합

자, 이제 잘 순서지워진 두 집합, 자연수 집합과 (0,1) 구간에 대해 대응을 시킨다고 생각해보자.

1

\mapsto a_{1}

, 2

\mapsto a_{2}

, 3

\mapsto a_{3}

,...

모든 자연수를 다 써서 이 구간의 부분집합인

{

a_{1},\ a_{2},\ a_{3},\ a_{4}

... }

와 자연수는 1 대 일로 대응한다. 그런데 실수 집합에서 1을 대응시킬 자연수가 없다. 1을 대응시킬 '새로운 수'를 정해주자. 이 수는 이미 자연수를 넘어선 어떤 수다. 이 수를 보통 $\omega$ 로 쓴다. 다시 말해

1,2, 3, .... 모든 자연수를 '넘어' 있는 첫번째 수를

\omega

다. 그런데 (1, 2) 까지 더 세어야 한다면 ? 1 다음에 또 세어가기를 계속한다. (1,2) 사이에 어떤 수 하나

b_{1}

를 보탰다.

{

a_{1},\ a_{2},\ a_{3},\ a_{4},\ \dots ,a_{\omega },b_{1}

}

이 집합은 '잘 순서 지워진 집합이다' (왜 그런가?) 이어서 ( $b_{1}$ , 2) 에서 또 그 다음 수 또 다음수를 '뽑아서' 집합을 정의해보자.

{

a_{1},\ a_{2},\ a_{3},\ a_{4},\ \dots ,a_{\omega },b_{1},\ b_{2},\ b_{3},\dots

}

로 세어갈 것이다. 이 집합도 모두 잘 순서지워진 집합이다. 그런데 $a_{\omega }$ 바로 '다음 수' $b_{1}$ 에 어떤 수를 대응시켜 '세어가기'를 계속 했단 말인가? 꼬리표를 하나씩 하나씩 붙여갔는데 자연수 꼬리표는 다 썼고, 자연수 바로 다음 수인 새로운 $\omega$ 까지 가져와서 써버렸으니. 하나씩 더해가고 있으니 그 다음 수에 대응하는 수는 '당연히' $\omega +1$ 일 것이다. 그래서 새로 얻은 집합에 꼬리표를 붙인 채로 다시 보면

{

a_{1},\ a_{2},\ a_{3},\ a_{4},\ \dots ,a_{\omega },a_{\omega +1},\ a_{\omega +2},\ a_{\omega +3},\dots

}

자, 그렇다면 이런 수는 계속 어디까지 갈까? 이에 대해 더 깊이 들어가지는 않겠다. 결론만 말하면,

\omega ^{\omega ^{\omega ^{.^{.}}}}

로 계속 커져간다. 지금까지 우리가 새로 도입한 이 수를 'transfinite 수' 또는 'ordinal number' 라고 부른다. 그렇다면 새로운 수학이 생겼다. 새로운 수집합에 대한 연산은 어떻게 정의할까?

몇 가지 사항에 대해서만 이야기하고 끝맺기로 하자.

이렇게 잘 순서지워진 집합들만 한 울타리에 모았을 때 모두 비교할 수 있을까? ^[8]
위에서 자연수와 어떤 구간을 대응시켜 나갈 때 도대체 '뽑아서'란 무슨 말인가? 어떻게 뽑는다는 말인가? 도대체 이것은 무언가? 이것에 대해서는 심각한 이야기가 있다. 따로 보지 않을 수 없는... 지나칠 수 없는 개념들은 아래와 같다.

선택공리 : 어떤 집합들을 원소로 갖는 집합이 있다고 하자. 모든 원소들인 집합에서 하나씩 원소를 뽑을 수 있다.

타르스키-바나흐 파라독스 : 하나의 공은 같은 크기의 같은 모양의 공 두개가 될 수 있다.