countably infinite

집합이 countable 이라는 것이 어떤 함수를 통해서

자연수의 집합과 1:1로 대응되는 경우라고 하던데요,

실수의 범위 부터는 uncountable 이라고 하더군요.

다시 말해서 유리수의 범위 까지는 countable 이라는 말인데,

어떻게 자연수와 유리수를 1:1로 매칭 시키나요?

자연수와 정수의 경우에는

f(x) = -x / 2   (x = even)
       0        (x = 1)
       (x - 1) / 2 (x = 1이 아닌 odd)

이런식으로 함수를 정의하게되면 -무한대 ~ 무한대 까지의 모든 정수를 표현
할 수 있다고 하더군요. (기억이 안나서 방금 그냥 생각한거라 맞는지는 모름
여튼 이런 식)

그런데 유리수와는 어떤 함수를 정의해야 자연수와 매치를 시킬 수 있는지

모르겠습니다. 앨지럼 캐고수님들 도와주세여

잡담 | 2239명이 읽었어요. 3.138.204.208

비공개 손님 … 2007-04-30 15:03:12

이건, 약간 그림이 추가 되면 좋은데 -_-
일단, 유리수 = 분수꼴로 나타낼수 있다. (기약분수)

라고가정을 하고 생각해보면

1/1 1/2 1/3 1/4 1/5 ....

2/1 2/2 2/3 2/4 2/5 ....

3/1 3/2 3/3 3/4 3/5 ....

4/1 4/2 4/2 4/4 4/5 ....

5/1 5/2 5/3 5/4 5/5 ....

이런식으로 유리수를 나타 내고

여기에다 자연수를 1:1 대응을 시킵니다.

1 -> 1/1

2 -> 1/2

3 -> 2/1

4 -> 3/1

5 -> 2/2

6 -> 1/3

7 -> 1/4

8 -> 2/3

9 -> 3/2

10 -> 4/1

11 -> 5/1

....

이런식으로요,

이렇게보면, 대각선으로 계속 대응이 되게 되는데

그러면 하나의 유리수 ex) 1/1, 2/2, 3/3.. (다 1을 나타내죠)

에 여러 자연수가 대응되게 되는데, 이런것들은 빼면 됩니다.

그러면 모든 유리수에 대해

자연수가 대응이 되게 되는거죠.

함수로는 잘... ㅈㅅ

비공개 손님 … 2007-04-30 17:42:47

저도 처음에 생각 할 때는 유리수가 분수의 꼴로 표현이 될 수 있다는 것으로 부터 생각을 해 보려고 했는데 그게 좀 꼬이더라구요.

음. 명확하게 함수를 보고싶은데..

비공개 손님 … 2007-05-02 18:30:43 x

답3/ 2변수 함수인건가요?

비공개 손님 … 2007-05-04 01:40:31

informally, 임의의 유리수에 번호를 매길 수 있으면 유리수가 셀 수 있는 집합이 되겠죠? (임의의 유리수에 번호를 매긴다는 것 자체가, 임의의 유리수에 대해서 그 유리수로 대응되는 유일한 자연수 n을 지정할 수 있음을, 즉 자연수에서 유리수로 가는 전단사함수가 존재함을 뜻합니다)
그럼 이제 다음과 같이 (음이 아닌) 유리수를 나열해보세요.
0, 1/1, 1/2, 2/1, 1/3, 2/2, 3/1, 1/4, 2/3, 3/2, 4/1, 1/5, 2/4, 3/3, 4/2, 5/1, ...
그리고 여기서 중복되는 목록들은 다 제거합니다. 그러면 아래와 같은 목록을 얻겠죠?
0, 1, 1/2, 2, 1/3, 3, 1/4, 2/3, 3/2, 4, 1/5, 5, ...
이러한 목록을 만들었다는 것 자체가, 이미 임의의 음이 아닌 유리수를 '세었다'는 것을 뜻합니다. 즉, 위와 같이 나열된 목록의 n번째 수를 함수값으로 갖는 함수 f는 (비록 explicit한 공식을 제시하진 않았지만) 자연수에서 음이 아닌 유리수로 가는 전단사함수가 됩니다. 그러므로 유리수는 셀 수 있습니다 (음의 유리수는 정수와 자연수를 일대일 대응시킬때처럼 부호를 번갈아가면서 끼워넣으면 또한 셀 수 있음을 알 수 있겠죠?
대부분의 책에서는 그림으로 나와있는 경우가 많구요~ 함수로 표현할 수는 있지만 시도해본결과 무지 복잡하다는.. 제가 실력이 부족해서 그럴 수도 있겠지만.. 책에 함수로 나와있지 않은걸 보면 아마도 쉬운 표현은 아닐 것 같습니다. 아님 말고;

비공개 손님 … 2007-05-04 01:41:42

글구 첫번째 올렸던건 2변함수아닙네다;

댓글을 작성하실 수 없습니다.
(권한이 없는 회원레벨)

목록으로

△ 이전글: [질문] 자바로 지하철노선과 소요시간... [5]

▽ 다음글: 프로그래밍 C++ 중고수이상님들만..헬프!! [4]

TOP arrow_upward