'집합론'에 해당되는 글 4건

  1. 2010.04.17 Power set, again
  2. 2010.04.13 무한대와 무한대가 만났을 때 4
  3. 2010.03.15 Power Set에 대한 잡담 10
  4. 2010.01.13 무한대의 비교: 자연수와 실수

2010. 4. 17. 17:34 Mathematics

Power set, again


KP집합론이라는 녀석을 발견했다.


이 녀석에서는 멱집합 공리를 가정하지 않는다고 한다. 유한집합에 대해서 멱집합을 멱집합 공리 없이 만들어내는 방법이 있는 것이 확실해 보인다.

글을 여기에서 끝내기에는 글이 너무 짧아 좀 그러니까 내가 시도한 방법을 공개한다.

1. Axiom of Existence, Axiom of Extensionality, Axiom of Pair, Axiom of Union, Axiom schema of Replacement를 가정. 모든 자연수에 대해 그 멱집합이 존재함을 보일 것이다. 어떤 집합의 크기가 자연수라면 당연히 자연수와 일대일 대응 관계가 존재하므로 그 관계를 이용해 멱집합의 모든 원소들을 바꾸어주면 땡.

2. 자연수는 일반적으로 통용되는 정의(0={}, 1={0}, 2={0,1}, ...)를 사용한다.

3. 다음 operation을 정의한다.

4. 수학적 귀납법만 남았다.
i. 0에 대해 멱집합이 존재한다.
ii. n에 대한 멱집합이 존재한다고 가정하자. n+1에 대한 멱집합은 다음과 같다.
(증명은 생략. 헤맬 독자들을 위해 간단히 설명하자면, 전 멱집합에 마지막으로 추가된 원소 하나씩 집어넣은 녀석들을 합집합 해주는 거다.)

5. 모든 유한집합에 대해서 멱집합은 공리 없이 존재합니다! 우왕ㅋ굳ㅋ

문제는 3번이다. 저게 존재한다는 것을 어떻게 보일 수 있으려나...

'Mathematics' 카테고리의 다른 글

Involute 곡선  (10) 2010.05.01
수학의 아름다움  (2) 2010.04.24
무한대와 무한대가 만났을 때  (4) 2010.04.13
Power Set에 대한 잡담  (10) 2010.03.15
야코비 행렬(Jacobian matrix)  (12) 2010.02.24
Posted by 덱스터
자연수의 부분집합과 하나의 자연수 (Weistern)

집합론을 공부하다가 갑자기 이 글이 떠올랐다. 저 말은 바꿔 말한다면 유한수열이 자연수와 일대일 대응을 맺을 수 있음을 보이라는 소리와 똑같으니까 말이다.(그런데 두어 달도 더 지난 글을 왜 기억하고 있는 거지...)

http://www.sitmo.com/gg/latex/latex2png.2.php?z=100&eq=%7C%5Cbold%20N%7C%3D%7C%5Cbold%20N%20%5Ctimes%20%5Cbold%20N%20%7C%3D%5Caleph_0
결국 이 소리다.

그리고 다음 결과도 꽤 재미있었다.

http://www.sitmo.com/gg/latex/latex2png.2.php?z=100&eq=%7C%5Cbold%20R%7C%3D%7C%5Cbold%20R%20%5Ctimes%20%5Cbold%20R%20%7C%3D2%5E%7B%5Caleph_0%7D

실수선과 평면이 일대일 대응을 맺을 수 있다는 의미 아닌가. 난 사실 프랙탈 곡선 중 하나(힐베르트 곡선)를 생각했었는데 그거 말고 그냥 10진수 전개해서 번갈아 가면서 실수를 지정해주면 된다고 한다. 0.12345678....은 0.1357...이랑 0.2468...을 말한다는 식으로 말이다.

File:Hilbert curve.gif
힐베르트 곡선

여튼, 이렇게 원래는 수리논리쪽에 관심이 생겨서 수강하게 되었는데 이상한 방향으로 관심이 흘러가고 있는 잉여의 기록을 남겨둔다. 학부땐 원래 교양을 많이 들으려고 했는데 이상한 과(?) 흘러들어가서 전공이나 듣고 있고 뭐하는 짓이지...

'Mathematics' 카테고리의 다른 글

수학의 아름다움  (2) 2010.04.24
Power set, again  (0) 2010.04.17
Power Set에 대한 잡담  (10) 2010.03.15
야코비 행렬(Jacobian matrix)  (12) 2010.02.24
선형대수와 행렬  (0) 2010.02.04
Posted by 덱스터
ZF 집합론을 공부하는 중인데, 보다 보면 멱집합(Power set)의 공리라는 것이 있다.


그러니까, 어떤 집합이 있으면 항상 그 부분집합 전체를 원소로 갖는 집합(멱집합이라고 부른다)이 존재한다는 것이다. 그런데 이게 공리여야 할 필요가 있나 싶다. 먼저 부분집합은 당연히 존재한다.(제한된 내포공리꼴-Axiom Schema of Restricted Comprehension을 이용하면 된다.) 그리고, 이 부분집합들을 자기 자신과 짝을 맺어 다시 집합으로 만드는 것이 가능하다(짝공리-Axiom of Pair; 집합에 중괄호{}를 한번 더 씌워줄 수 있다는 의미). 그리고 이렇게 만들어 낸 집합들의 합집합을 만들어낼 수 있는데(이건 짝공리와 합집합 공리-Axiom of Union를 꼬으면 된다), 이렇게 얻을 집합이 바로 멱집합이 되기 때문이다. 따라서 공리로 채택하기보다는 정리(Theorem)으로 유도해도 될 것 같다는 느낌이 든다. 물론 이건 유한집합에서의 이야기이지만.

생각해보면 무한집합에서 멱집합을 정의해줄 필요가 있어서 이런 공리를 택하는 것 같다. 무한차원에서의 선형대수학도 기저(base)를 정당화하기보다는 그렇다고 정의해버리니까 말이다.(제대로 공부해본 적은 없어서 확실하다고는 못 하겠지만.) 나중에 교수님께 질문해보지 뭐.

'Mathematics' 카테고리의 다른 글

Power set, again  (0) 2010.04.17
무한대와 무한대가 만났을 때  (4) 2010.04.13
야코비 행렬(Jacobian matrix)  (12) 2010.02.24
선형대수와 행렬  (0) 2010.02.04
루빅스로 배우는 군론  (0) 2010.01.27
Posted by 덱스터
당장 수중에 책이 없어서 확인하지는 못하겠지만, 동화(?) 『수학귀신』의 9번째 장에는 아픈 아이의 방에 무한히 많은 숫자들이 몰려드는 이야기가 나온다. 이때 수학귀신이 한마디 던진다. '여기 중에서 제일 많은 숫자는 누구일까?'

이제 와서 돌이켜보면 무한히 많은 원소를 가지는 집합들의 크기를 비교하는 방법을 다룬 이야기였다. 1부터 5까지의 범위 안에 있는 자연수의 수와 홀수의 수는 확실히 비교할 수 있다. 하지만 우리가 다루는 구간이 무한히 나아간다면 어떨까? 얼핏 생각한다면 홀수가 더 적어 보인다. 홀수의 집합은 자연수의 집합의 부분집합이기 때문이다. 그런데 문제는 무한이라는 수(?)는 그 자체로 대소를 비교할 수 없다는 것이다.

문제를 조금 바꾸어서, 셋까지만 셀 수 있는 사람이 수만명으로 이루어진 두 집단의 크기를 비교하는 것으로 바꾸어 보자. 어떤 방법을 쓰면 두 집단을 비교할 수 있을까? 가장 간단한 방법은 서로 다른 집단의 한 사람과 손을 잡도록 시킨 후, 손이 빈 사람이 있는지 살펴보는 것이다. 두 집단을 편의상 갑과 을이라고 부른다면, 갑 집단의 사람이 많다면 갑 사람 중 손이 을 사람을 찾아 헤메는 사람이 있을 것이고 을 집단의 사람이 많다면 그 반대일 것이다.

물론 우리는 꽤 큰 숫자까지 셀 수 있다. 하지만 그 수를 무한과 비교해본다면, 수만 중 셋조차도 되지 못한다. 따라서 숫자 집합의 크기를 비교할 때에는 고민할 수 밖에 없다. 어떻게 해야 그 둘을 비교할 수 있을까? 앞선 문제에서 이미 눈치를 챈 독자도 있겠지만 나처럼 눈치가 매우 없는 사람들을 위해서 설명하자면, 그 숫자를 서로 묶어주는 것이다. 한 집단의 모든 원소에 대해 다른 집단의 원소를 묶어줄 수 있다면, 두 집단의 크기는 동일하다. 간단하게 자연수와 홀수를 비교해보자.


우리의 직관은 이렇게 홀수(아랫줄)구간에 빈 자리가 생기기 때문에 홀수가 당연히 더 적을 것이라고 생각한다. 하지만 과연 그럴까? 이번에는 이렇게 줄세워보자.


이번엔 자연수(윗줄)이 적어 보인다. 보이는 것이 전부는 아닌 것이다. 어떻게 해야 크기를 제대로 비교할 수 있을까? 답은 이렇다. '어떻게 줄을 세우더라도 한 쪽이 남는다면, 그 쪽이 크다' 자연수와 홀수는 이렇게 줄세우면 양쪽이 하나도 남지 않게 할 수 있다.


이런 식으로 끝까지(?) 나아갈 때, 나오지 않는 자연수와 홀수는 존재하지 않는다. 따라서 자연수와 홀수 집합의 크기는 동일하다. 이런 식으로 모든 소수의 집합과 모든 정수의 집합, 모든 유리수의 집합과 모든 제곱수의 집합 등이 전부 자연수 집합과 동등한 크기를 갖는다는 것을 증명할 수 있다.

유리수를 세는 방식. 2/2는 지워야 하겠지만 규칙성을 볼 수 있도록 놓아두었다.
분모와 분자의 합을 일정하게 하고 분모를 하나 뺀 뒤 분자를 하나 더하는 방식이다.

하지만 실수가 출동하면 어떨까?

나는 구식이다 OTL

실수 전체와 자연수를 비교하려면 힘이 매우 많이 든다. 먼저 0과 1 사이에 존재하는 모든 실수에 대해서만 자연수와 비교하도록 하자. 시작할때는 널럴하게 아무 실수나(전에 나온 것을 빼고) 골라서 자연수와 연결해준다. 다음처럼 말이다.


이대로라면 모든 실수를 연결해 줄 수 있을것만 같다는 기분이 든다. 과연 그럴까? 다음 실수가 자연수와 연결되었는지 확인해보자.

소수점 첫 째 자리는 1과 연결된 실수의 소수점 첫 째 자리와 다르고
소수점 둘 째 자리는 2와 연결된 실수의 소수점 둘 째 자리와 다르고
소수점 셋 째 자리는 3과 연결된 실수의 소수점 셋 째 자리와 다르고
소수점 넷 째 자리는 4와 연결된 실수의 소수점 넷 째 자리와 다르고
[...]
위에서의 예: 0.32436....

실수는 소수점 아래 무한한 자리의 숫자가 있고, 위의 실수는 지금 연결된 모든 실수와 최소한 한 자리는 차이가 나기 때문에 자연수와 전혀 연결되지 않았다. 그렇다면 이 수를 먼저 연결해주면 될 것 아닌가? 그런데 그러면 위와 같은 방법으로 구한 또 다른 수가 생길 것이고, 결국 어떤 방법을 쓰더라도 실수와 자연수를 연결하면 실수가 남는다는 것을 알 수 있다.(지금 실수는 0과 1 사이에서만 생각하고 있었다는 것을 생각하면 까마득하다.) 더군다나 이런 방식을 응용해서 찾을 수 있는 소수는 무수히 많다. 어떻게 연결해 주더라도 실수 중에서는 자연수 짝을 찾지 못한 솔로부대가 존재해야만 한다는 것이다.(그것도 매우 많이) 우리는 결국 실수의 집합은 자연수의 집합보다 크다는 결론을 내릴 수 밖에 없다.[각주:1]

우리는 지금까지 무한대의 크기를 비교했다. '실수 집합의 원소의 수'라는 무한과 '자연수 집합의 원소의 수'라는 무한 사이에는 같은 무한이더라도 분명한 크기 차이가 존재한다는 것을 보였다. 그렇다면 두 무한 사이에 존재하는 무한도 있을 수 있을까? 이 문제는 힐베르트의 난제중 하나(1번)이다. 이미 그 해답은 얻어졌지만, 공부를 안해서귀찮은 관계로 이 문제는 기약없는 다음으로 미루어두기로 한다.



20100304 추가
이 정리는 칸토르의 작품이었다고 한다. 좀 더 엄밀한 정리.
  1. 첨언하자면 무리수의 집합 중 근(root)으로 나타낼 수 있는 수들의 집합은 자연수의 집합과 같은 크기를 갖는다. 왜 그런지는 독자들의 몫으로 남겨둔다. 힌트: 모든 근으로 이루어진 수들은 정수를 계수로 갖는 다항식의 해이다. [본문으로]

'Mathematics' 카테고리의 다른 글

선형대수와 행렬  (0) 2010.02.04
루빅스로 배우는 군론  (0) 2010.01.27
Laplace 변환을 이용한 미분방정식 풀이  (2) 2009.12.17
각종 변환들  (0) 2009.12.15
Fourier 변환의 고유함수  (0) 2009.12.15
Posted by 덱스터
이전버튼 1 이전버튼

블로그 이미지
A theorist takes on the world
덱스터
Yesterday
Today
Total

달력

 « |  » 2024.3
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31

최근에 올라온 글

최근에 달린 댓글

글 보관함