졌다고 하자.
의 선형부분순서집합들을 모두 나열하면 다음과 같다.∅, , , , , , , , , ,
이 집합들을 모두 원소로 갖는 집합을
라고 하자. 그리고
에 순서관계 ⊆이 주어졌다고 하자.
의 원소들 의 순서관계를 그림으로 나타내면 다음과 같다.이때
는 과 을 극대원소로 가진다. □보기
1.6.3 앞의 보기 1.6.2에서 집합
은 정렬집합이 아니다. 왜냐하면 은
의 공집합이 아닌 부분집합이지만 극소원소가 와 으로서 유일하지 않기 때문이다. 그러나
에 자연순서를 부여하면
는 정렬집합이 된다. □집합
에 적절한 순서관계를 정의하여
가 정렬집합이 되도록 할 수 있으면 ‘
는 정렬 가능하다’라고 말한 다. 정렬 정리에 의하면 임의의 집합은 정렬 가능하다. 그러나 정렬 정리는 집합의 정렬 가능성을 보장할 뿐, 실제로 그 집합에 어떠한 순서관계를 부여해야 정렬집합이 되는지에 대한 정보를 주지는 않는다. 예를 들어 정 렬 정리에 의하여 실수 집합 ℝ는 정렬 가능하지만 어떠한 순서관계가 ℝ를 정렬집합이 되도록 하는지는 알려 져 있지 않다.1.7 집합의 크기
두 집합
,
가 유한집합일 때에는 각각의 원소의 개수를 세어 어느 것이 더 많은 원소를 가지고 있는지 비 교할 수 있다. 그러나 무한집합의 경우에는 원소의 개수를 직접 세는 방법으로 비교할 수 없다. 대신 두 집합 사이에 원소를 하나씩 대응시켜 어느 쪽이 더 많은지 비교할 수 있다.두 집합
,
에 대하여 일대일대응
→
가 존재할 때 ‘
와
는 대등하다(equinumerous)’라고 말하고 이것을 기호로
≈
로 나타낸다. 대등하다는 것을 ‘크기가 같다’ 또는 ‘농도가 같다’라고 표현하기도 한다.일대일대응의 성질에 의하여 대등관계는 다음을 만족시킨다.
∙ 임의의 집합
에 대하여
≈
이다.∙ 집합
,
에 대하여
≈
이면
≈
이다.∙ 집합
,
,
에 대하여
≈
이고
≈
이면
≈
이다.이러한 관점에서 대등관계는 임의의 집합족의 동치관계이다.
집합
에 대하여 이상인 정수 이 존재하여
≈ ⋯ 을 만족시키거나
∅이면
를 유한집합이라고 부른다. ≔ ∈ℤ ≥ , ≔ ∈ℤ ≤ 이라고 하자. 그러면
가 유한집 합이라는 것은∃∈
≈ 인 것과 동치이다. 유한집합이 아닌 집합을 무한집합이라고 부른다.ℕ이 자연수 집합이고
가 무한집합이라고 하자.
는 공집합이 아니므로 ∈
가 존재한다.
∖
은공집합이 아니므로 ∈
∖
이 존재한다.
∖
는 공집합이 아니므로 ∈
∖
가 존 재한다. 일반적으로 , , ⋯, 이
의 서로 다른 원소일 때 ∈
∖
⋯
이 존재한다. 이와 같은 방법으로 구성된 집합
∈ℕ
은 명백히 ℕ과 대등한 집합이다. 즉 임의의 무한집합은 자 연수 집합과 대등한 부분집합을 가진다.자연수 집합과 대등한 집합을 가부번집합(enumerable set)이라고 부른다. 가부번집합은 무한집합 중에서 가장 작 은 집합이다. 즉
가 무한집합이면
는 자연수 집합과 대등한 부분집합을 가진다. 유한집합과 가부번집합을 통틀어 가산집합(countable set)이라고 부른다.다음은 유한집합과 무한집합에 관련된 몇 가지 성질이다.
∙
가 무한집합일 필요충분조건은 가부번인 부분집합을 갖는 것이다.∙
가 무한집합이고
가 유한집합이면
≈
∖
이다.∙
가 무한집합이고
⊆
이면
도 무한집합이다.∙
와
가 유한집합이면
×
도 유한집합이다.∙
와
가 가산집합이면
×
도 가산집합이다.∙
가 유한집합이면 ℘
도 유한집합이다.∙ 정의역이
이고 공역이 인 함수들의 모임을 로 나타내자. 이때 ≈ ℘
이다.∙ 집합족
∈ℕ
의 모든 원소
가 가산집합이면
∈ ℕ
도 가산집합이다.정수 집합 ℤ는 가산집합이다. 왜냐하면 ℤ의 모든 원소를
, , , , , , , , , ⋯
와 같이 빠짐없이 한 줄로 나열할 수 있기 때문이다. 한 줄로 나열할 수 있다는 것은 순서대로 자연수를 하나 씩 대응시킬 수 있다는 것을 의미한다. 따라서 ℤ는 ℕ과 대등하다. 마찬가지로 유리수 집합 ℚ도 가산집합이 다. 유리수를 기약분수로 나타내었을 때 분모와 분자의 절댓값의 합이 작은 것부터 차례대로 쓰면
,
,
,
,
,
,
,
,
,
,
,
,
,
,
, ⋯
와 같이 모든 유리수가 빠짐없이 나열된다.
35
1.7 집합의 크기
그러나 실수 집합 ℝ는 가산집합이 아니다. 만약 ℝ가 가산집합이라면 부분집합인 열린구간
도 가 산집합이다. 그러면
의 모든 원소를, , , , ⋯
와 같이 빠짐없이 나열할 수 있다. 각 은 보다 크고 보다 작은 실수이므로 정수부분이 인 소수로 나타 낼 수 있다. 특히 이 유한소수인 경우에는 마지막 자리에서 을 빼고 그 뒤에 를 무한히 이어 써서 동일한 수를 나타낼 수 있다. 이제 의 소수점 아래 번째 자리 수를 이라고 하면,
의 원소를 ⋯
⋯
⋯
⋯
⋮ 와 같이 나열할 수 있다. 이때 자연수 에 대하여 를
≔
if ≠
if 이라고 정의하고 소수 를
≔ ⋯
라고 정의하자. 명백히 는 보다 크고 보다 작은 수이므로
의 원소이다. 그러나 임의의 자연수 에 대하여≠ 이므로 ≠ 이다. 즉 는 어떠한 와도 같지 않다. 이것은
의 모든 원소를 꼴로 나열했다는 것에 모순이다. 따라서
는 가산집합이 아니다.
는 ℝ의 부분집합이므로 ℝ도 가산집합이 아니다. 이와 같이 가산집합이 아닌 집합을 비가산집합(uncountable set)이라고 부른다.열린구간
은 ℝ와 대등하다. 왜냐하면 함수
→ ℝ를 tan
또는
로 정의하면 는
로부터 ℝ로의 일대일대응이 되기 때문이다.두 집합
,
에 대하여 일대일함수
→
가 존재할 때 ‘
가
보다 크거나 또는 둘의 크기가 같다’라고 말하고
≼
로 나타낸다. 그리고
≼
이면서
≉
인 것을
≺
로 나타낸다. 칸토어-베른슈타인 (Cantor-Bernstein) 정리에 의하면 두 집합
,
에 대하여
≼
이면서 동시에
≼
이면
≈
가 성립한다.[문제 27 참조] 이러한 의미에서 ≼는 임의의 집합족의 순서관계이다.
이제
과
이 대등함을 보이자.
의 원소 가 임의로 주어졌다고 하자. 의 좌표와 좌표를 각각 무한소수로 표현한 순서쌍을 ⋯ ⋯
으로 나타내자. 그리고
⋯
으로 정의하자. 이때 를 에 대응시키는 함수 ↦ 는
으로부터
로의 일대일함수이다. 따라서
≼
이다. 한편 명백히
≼
이다. 그러므로 칸토어-베른슈타인 정리에 의하여
≈
이 성립한다.[참고로 임의의 무한집합
와 자연수 에 대하여
≈
이 성립한다.]복소수 집합 ℂ는 ℝ와 대등하다. 즉, 임의의 복소수 에 대하여 를 만족시키는 실수 , 가 각 각 유일하게 존재한다. 이때 를 순서쌍 에 대응시키면 ℂ는 ℝ와 대등하다는 것을 알 수 있다.
한편 ℝ는
과 대등하고 ℝ은
과 대등하므로 ℝ ≈
≈
≈ ℝ≈ ℂ를 얻는다.지금까지 살펴본 바에 의하면
ℕ ≈ ℤ ≈ ℚ ≺ ℝ ≈ ℂ 이다. 그렇다면 ℝ보다 더 큰 집합이 존재할까?
칸토어의 정리(Cantor’s theorem)에 의하면 임의의 집합
에 대하여 멱집합 ℘
는
보다 크다. 이것을 증명 해 보자. 만약
≈ ℘
라면 일대일대응
→ ℘
가 존재한다.
∈
∉ 라고 하면
⊆
이다. 따라서
인 ∈
가 존재한다. ∈라고 가정하면 ∉
이므로 ∉ 가 되어 모순이다. ∉ 라고 가정하면 ∈
이므로 ∈가 되어 모순이다. 어느 경우에나 모순이므로 일대일 대응
→ ℘
는 존재할 수 없다. 따라서
≺ ℘
이다.이로써 칸토어의 정리에 의하여 다음을 얻는다.
ℝ ≺ ℘ ℝ ≺ ℘ ℘ ℝ ≺ ℘ ℘ ℘ ℝ ≺⋯
즉 무한집합의 종류는 무한히 많다.
한편 ℝ ≈ ℘ ℚ 가 성립한다. 이것은 연속함수의 성질을 이용하여 증명되는데, 여기서는 그 증명을 간단히 살펴보자. 함수 ℝ → ℘ ℚ 를 ∈ℚ 라고 정의하자. 명백히 는 일대일함수이다. 즉 ℝ≼℘ ℚ 이다. 다음으로 함수 ℕ→ ℝ를 임의의 ∈ ℕ에 대하여
∞
으로 정의하자. 즉 정수부분이 이고 소수점 아래 번째 자리의 숫자가 인 소수를 의 값으로 정의 한다. 그러면 는 일대일함수이다. 즉 ℝ≽℘ ℚ 이다. 따라서 칸토어-베른슈타인 정리에 의하여 ℝ는
℘ ℚ 와 대등하다.
이제 또 하나의 의문이 생긴다. ℚ ≺
≺ ℝ인 집합
가 존재하는가? 일반화시켜 생각해보면 임의의 무한집합
에 대하여
≺
≺ ℘
인 집합
가 존재하는가?라는 의문이 생긴다. 20세기 초까지 많은 수학자들이 그러한 집합
는 존재하지 않을 것이라고 추측하였는데, 이러한 추측을 연속체 가설(continuum hypothesis)이라고 부른다. 1938년 괴델(Kurt Gödel)은 연속체 가설이 집합 론의 공리에 모순이 되지 않는다는 것을 증명하였으며, 1963년 코헨(Paul Cohen)은 연속체 가설이 기존의 집합 론의 공리와 독립적임을 증명하였다. 즉 연속체 가설은 선택 공리와 마찬가지로 그것을 참으로 받아들이든 그 것을 부정하든 전혀 모순이 발생하지 않는다.참고로 괴델(Kurt Gödel)은 자연수를 다룰 수 있는 모든 수학 공리계[즉 페아노 산술을 포함하는 일차논리 공리계]에는 참 또는 거짓 여부를 증명할 수 없는 명제가 존재함을 증명하였는데 이것을 불완전성 정리(incompleteness theorem) 라고 부른다.
이처럼 연역적 사고와 논리적 추론을 통한 진리를 추구하는 수학에서도 참 또는 거짓 여부를 증명할 수 없는 명제가 항상 존재하는데, 세상에는 모든 것의 옳고 그름을 지나치게 따지는 사람들이 있다는 사실이 참 안타깝다. 심지어는 자신과 생각이 다르면 둘 중 하나는 옳고 하나는 틀리다고 믿는 사람들도 있다. 우리는 살아가면서 옳고 그름만을 따 지기보다는 서로를 이해하고 더 나은 방향으로 나아가기 위하여 노력해야 할 것이다.
37
단원 마무리 문제
개념 이해하기
1. 다음 논리식의 진리표를 작성하여라.
(1) ∧ ∧ (2) ∧ ∧
(3) ∨ ∼ ∧ (4) ∼ ∧ ∨
(5) ↔ (6) ∧ ∨ ∼ ∧ ∼
2. 가 ‘나는 고양이다’, 가 ‘나는 가볍다’일 때, 다음 식을 자연스러운 문장으로 만들어라.
(1) ∨ (2) ∧
(3) → (4) ∼ → ∼
(5) ∼ → ∼ (6) ∼ ∧
3. 가 ‘나는 동물이다’, 가 ‘나는 개미이다’일 때, 다음 문장을 기호를 사용하여 나타내어라.
(1) 나는 동물이지만 개미는 아니다.
(2) 나는 개미이므로 동물이다.
(3) 내가 개미이려면 나는 동물이어야 한다.
(4) 동물은 개미가 아니다.
4. 다음 문장의 부정을 말하여라.
(1) 토끼는 하얗지도 않고 귀엽지도 않다.
(2) 비가 내리면 우산이 잘 팔린다.
(3) 애인이 생기면 학업 성적이 좋아진다.
(4) 부업을 하면 돈은 벌지만 여유는 줄어든다.
5. 다음 문장의 부정을 말하여라.
(1) 모든 개미핥기는 파충류이다.
(2) 말 중에는 온순한 것도 있다.
(3) 수학자 중에는 사교적인 사람이 있다.
(4) 모든 강아지는 귀엽거나 똑똑하다.
(5) 헤엄치지 못하는 돌고래는 없다.
(5) 헤엄치지 못하는 돌고래는 없다.