편집토론기록

집합론

“ No one will drive us from the paradise which Cantor created for us. “
— David Hilbert (1926)

집합론(集合論, 영어: Set theory)은 집합과 집합에 관련된 것들을 다루는 학문이다. 게오르크 칸토어가 그 기틀을 세웠다.

칸토어가 처음 고안한 집합론을 소박한 집합론(naive set theory)이라고 한다. 중/고등학교에서 배우는 집합과 관련된 것들은 모두 이 소박한 집합론을 기본으로 한다. 이 집합론은 너무나 소박해서(?) 자연 언어로 정의되어 있다. 즉, 형식적인 논리로 정의되지 않았다는 것이다. 집합은 그냥 적절한 (잘 정의된) 대상들의 모임[1]으로 정의되고, 원소는 그런 대상이다. 공집합은 왜인지는 모르겠지만 어쨌든 존재하며, 무한집합 역시 존재한다. 왜냐하면, 당연히 존재할 것 같으니.


하지만 칸토어와 고틀로프 프레게의 체계는 결정적으로 단 하나의 역설에 의하여 무너지고 만다. 이것이 바로 러셀의 역설. 즉, 모든 집합을 모은 집합이 존재한다면 그 체계는 모순을 내포한다는 것이다. 이로써 소박한 집합론이 모순이 있다는 것을 알고, 버트런드 러셀은 공리적 집합론을 주장한다. 집합을 정의함에 있어 공리계가 있어야 한다는 것이다. 가장 유명(?)한 공리적 집합론 체계는 ZF(또는 ZFC[2]).

이렇게 집합을 가지고 노는 학문이 바로 집합론이다. 후술하는 것들은 집합론에서 다루는 몇 가지 개념들이다.

개요[편집 | 원본 편집]

이하의 내용은 《A Transition to Advanced Mathematics》(Douglas Smith, Maurice Eggen, Richard St. Andre 저)에서 상당수를 참조했습니다.

논리와 증명[편집 | 원본 편집]

대부분의 집합이 조건제시법(술어)으로 서술되므로, 조건에 부합하는지 아닌지를 아는 것이 매우 당연하며 중요하다. 명제논리와 술어논리, 참과 거짓을 판단하는 방법을 배우며, 기초적인 기호들을 익힌다.

여기서 간략하게나마 논리에 쓰이는 기호들을 설명하자면,

  • [math]\displaystyle{ \forall x }[/math]: 모든(임의의) [math]\displaystyle{ x }[/math]에 대하여,
  • [math]\displaystyle{ \exists x }[/math]: [math]\displaystyle{ x }[/math]가 존재하여, 어떤 [math]\displaystyle{ x }[/math]에 대하여,
  • [math]\displaystyle{ \exists !x }[/math]: [math]\displaystyle{ x }[/math]가 유일하게 존재하여,
  • [math]\displaystyle{ \neg P }[/math] 또는 [math]\displaystyle{ \sim P }[/math]: P의 부정,
  • [math]\displaystyle{ p\lor q }[/math] : p 또는 q,
  • [math]\displaystyle{ p\land q }[/math] : p 그리고 q

등이 있다.


관계[편집 | 원본 편집]

Crystal Clear app xmag.svg 이와 관련한 내용은 관계에서 볼 수 있습니다.

직관적으로 말하면 함수보다 더 일반화된 개념이다. 예를 들어, (한국, 홍길동), (한국, 김철수), (미국, Bob), (미국, John)같은 것은 각 나라에 대해 거주민을 대응시키는 것으로 볼 수 있다. 이런 것들을 관계라고 한다. 관계를 정의한 후 더 쓸모있는 관계들을 만든다.

대표적인 것들을 몇 개 추려보자면,

  • 동치관계
    • 반사성, 대칭성, 추이성을 만족하는 관계다. [math]\displaystyle{ a=a }[/math](반사성), [math]\displaystyle{ a=b\rightarrow b=a }[/math](대칭성), [math]\displaystyle{ a=b \land a=c\rightarrow\ a=c }[/math](추이성) 등호를 생각하면 쉽게 외워진다.
  • 반순서관계[3]
    • 반사성, 반대칭성, 추이성을 만족하는 관계다. [math]\displaystyle{ a\le a }[/math](반사성), [math]\displaystyle{ a\le b \land b\le a \rightarrow a=b }[/math](반대칭성), [math]\displaystyle{ a\le b \land b\le c\rightarrow a\le c }[/math](추이성) 부등호를 생각하면 쉽게 외워진다.
    • 전순서관계
      • 완전성을 만족하는 반순서관계이다. 이 때 완전성이 반사성을 내포하므로 반대칭성, 추이성, 완전성을 만족하는 관계라고 하기도 한다. [math]\displaystyle{ a\le b \land b\le a \rightarrow a=b }[/math](반대칭성), [math]\displaystyle{ a\le b \land b\le c\rightarrow a\le c }[/math](추이성) [math]\displaystyle{ a\le b \lor b\le a }[/math](완전성)

등이 있다.

함수[편집 | 원본 편집]

Crystal Clear app xmag.svg 이와 관련한 내용은 함수에서 볼 수 있습니다.

함수는 관계의 특별한 종류 중 하나다. 함수가 갖는 큰 특징은 관계는 정의역에 대응하는 치역이 여러 개일 수 있지만, (위의 예에 있는 (한국, 홍길동), (한국, 김철수)처럼) 함수는 정의역의 각 원소에 대해 절대 두 개 이상이 대응되지 않는다.

즉, 우리가 잘 아는 그 함수가 되어 좋은 성질들을 가지게 된다.

농도(cardinality)[편집 | 원본 편집]

Crystal Clear app xmag.svg 이와 관련한 내용은 농도 (수학)에서 볼 수 있습니다.

집합의 크기라고도 한다. 농도는 직관적으로 집합이 얼마나 많은 원소를 가지고 있는지를 보여주는 척도다. 집합 [math]\displaystyle{ A }[/math]의 농도는 절대값 표기와 같이 [math]\displaystyle{ |A| }[/math]로 표기한다. 절대값과 표기가 똑같아서 종종 [math]\displaystyle{ \operatorname{card}(A) }[/math]...등등의 다른 표현을 사용해 혼동을 피하기도 한다.

집합 [math]\displaystyle{ A }[/math]가 집합 [math]\displaystyle{ B }[/math]보다 농도가 크다는 얘기를 할 수 있다. 농도가 곧 원소가 얼마나 많은가라서 집합 [math]\displaystyle{ A }[/math]와 집합 [math]\displaystyle{ B }[/math]의 원소를 짝지었더니 [math]\displaystyle{ A }[/math]쪽 원소가 남으면 [math]\displaystyle{ A }[/math]의 농도가 작지 않다. 원소를 비교하는 것은 함수를 통해 할 수 있다. 그래서 단사함수 [math]\displaystyle{ f : A \rightarrow B }[/math]가 존재하면 [math]\displaystyle{ |A| \leq |B| }[/math]라고 정의한다. 선택공리를 받아들인다면, 두 집합의 농도를 항상 비교할 수 있다. 두 집합 [math]\displaystyle{ A, B }[/math]에 대해, [math]\displaystyle{ |A|\lt |B|, |A|=|B|, |A|\gt |B| }[/math]중 하나를 만족한다.

유한집합, 무한집합[편집 | 원본 편집]

무한집합의 예로 자연수 집합을 들 수 있다. 자연수에서 자연수로 가는 함수 중에서, [math]\displaystyle{ f(n) = n+1 }[/math]를 생각해 보자. 이 함수는 단사인데, 이 함수의 상(image)는 2 이상의 자연수로, 자연수의 진부분집합이다. 또 다른 예는 [math]\displaystyle{ f(n) = 2*n }[/math]. 이 함수의 상은 짝수인 자연수이다. 이로부터 무한집합을 정의할 만한 아이디어를 얻을 수 있다.

어떤 집합 [math]\displaystyle{ X }[/math]가 어떤 진부분집합 [math]\displaystyle{ Y }[/math]과 일대일 함수가 존재하면 [math]\displaystyle{ X }[/math]는 무한이라고 한다. 자연수집합은 무한집합이 된다.

가산집합, 비가산집합[편집 | 원본 편집]

Crystal Clear app xmag.svg 이와 관련한 내용은 가산집합, 비가산집합에서 볼 수 있습니다.

가산집합은 말 그대로 셀 수 있으면 가산집합이다. 하나, 둘... 하고 모든 원소를 셀 수 있으면 된다. 만약 세다가 더이상 셀 원소가 없다면 유한집합이고, 멈추지 않고 계속 세야 한다면, 가산무한집합이 된다.

제대로 된 정의는, 어떤 집합 [math]\displaystyle{ X }[/math]에서 자연수 [math]\displaystyle{ \mathbb{N} }[/math]로의 단사함수가 존재하면 가산집합이라 하고, 그렇지 않으면 비가산집합이다. 당연히 유한집합은 가산집합이다.

특히 앞의 논리에 의해 어떤 집합[math]\displaystyle{ X }[/math]은 [math]\displaystyle{ |X|\lt |\mathbb{N}| }[/math]이거나 [math]\displaystyle{ |X|=|\mathbb{N}| }[/math]이거나 [math]\displaystyle{ |X|\gt |\mathbb{N}| }[/math]인데 이런 집합을 차례대로, 유한집합, 가산무한집합, 비가산집합이다.

자연수[math]\displaystyle{ \mathbb{N} }[/math], 정수[math]\displaystyle{ \mathbb{Z} }[/math], 유리수[math]\displaystyle{ \mathbb{Q} }[/math] 집합은 가산집합인 반면, 실수[math]\displaystyle{ \mathbb{R} }[/math]는 불가산집합이다. 실수집합이 불가산집합인 것은 칸토어의 대각선 논법에 의해 보일 수 있다. 또한 이 대각선 논법을 이용하면 어떤 집합의 멱급수의 농도는 그 집합의 농도보다 항상 크다는 것도 보일 수 있다.

농도의 연산[편집 | 원본 편집]

서로소인 두 집합 [math]\displaystyle{ A }[/math]와 [math]\displaystyle{ B }[/math]가 있을 때, 농도의 합은 두 집합의 합집합의 농도이다. [math]\displaystyle{ a = |A|, b = |B| }[/math]일 때, [math]\displaystyle{ a+b = |A \cup B| }[/math]인 것이다. 예로, [math]\displaystyle{ \aleph_0+\aleph_0 = \aleph_0 }[/math] . [4]

곱셈의 경우는 서로소일 필요는 없고 곱집합의 농도이다. 즉, [math]\displaystyle{ ab = |A \times B| }[/math]이다. [math]\displaystyle{ \aleph_0 \aleph_0 = \aleph_0 }[/math][5] 더해도 곱해도 같은게 나오는 신기한 세계

[math]\displaystyle{ B }[/math]에서 [math]\displaystyle{ A }[/math]로 가는 함수들의 집합의 농도를 [math]\displaystyle{ a^b }[/math]로 표시한다. 특별히 [math]\displaystyle{ 2^b }[/math]는 농도가 [math]\displaystyle{ b }[/math]인 집합[math]\displaystyle{ B }[/math]의 멱집합의 농도와 같다.

순서수(Ordinal Numbers)[편집 | 원본 편집]

Crystal Clear app xmag.svg 이와 관련한 내용은 서수에서 볼 수 있습니다.

정의[편집 | 원본 편집]

앞의 기수는 한 개, 두 개……라면, 순서수는 첫 번째, 두 번째……와 같은 것이다. "영 번째"는 공집합, "첫 번째"는 원소가 1개 있는 집합들 등등 이런 식이다. 만약 집합의 원소 개수가 유한하다면, 기수나 순서수나 똑같다. 그런데 무한이라면? 기수와 순서수는 전혀 다른 이야기가 된다.

순서수에 대해 고려하기 위해서는 단순히 집합만 고려하면 안되고 정렬집합이 필요하다. 즉, 완전순서[6]가 있어야 하고, 이 완전순서가 모든 공집합이 아닌 부분집합에 대해 극소원소가 있어야 한다. 표시는 집합 [math]\displaystyle{ A }[/math]와 정렬 [math]\displaystyle{ \le_A }[/math]에 대해 [math]\displaystyle{ (A,\le_A) }[/math]라고 표시한다.

순서수는 [math]\displaystyle{ \operatorname{ord}(A, \le_A) }[/math]로 표시한다. 우리가 다 아는 그 대소 관계에 따른 자연수[math]\displaystyle{ (\mathbb{N}, \le) }[/math]집합의 순서수는 특별히 오메가 [math]\displaystyle{ \omega }[/math]라고 표시한다. [math]\displaystyle{ \omega =\operatorname{ord}(\mathbb{N}, \le) }[/math] 완전순서가 필요한 이유는 순서를 어떻게 정하냐에 따라 순서수가 또 달라질 수 있다. 익숙한 대소 관계에서는 0이 가장 작은 자연수지만, 제가 새로 만든 대소 관계에서는 "0이 가장 큰 수고 나머진 똑같아요!" 하면, 즉, [math]\displaystyle{ 1 \le' 2 \le' ... \le' n \le' ... \le' 0 }[/math]라고 하면 [math]\displaystyle{ \omega }[/math]와 순서수가 달라진다.

덧셈[편집 | 원본 편집]

순서수끼리 덧셈이 가능하다. 교집합이 공집합인 두 정렬집합 [math]\displaystyle{ (A,\le_A) }[/math]와 [math]\displaystyle{ (B,\le_B) }[/math]이 있다고 하자. 합집합 [math]\displaystyle{ (A \cup B, \le_{ab}) }[/math]에 대해

  • [math]\displaystyle{ x, y \in A }[/math]일 때 [math]\displaystyle{ x \le_{ab} y \iff x \le_A y }[/math]이고,
  • [math]\displaystyle{ x, y \in B }[/math]일 때 [math]\displaystyle{ x \le_{ab} y \iff x \le_B y }[/math]이고,
  • [math]\displaystyle{ x \in A, y \in B }[/math]이면, [math]\displaystyle{ x \le_{ab} y }[/math](즉 모든 [math]\displaystyle{ B }[/math]의 원소는 모든 [math]\displaystyle{ A }[/math]의 원소보다 크다)

이 세 가지 조건을 만족할 때, [math]\displaystyle{ \operatorname{ord} ( A \cup B, \le_{ab} ) }[/math] [math]\displaystyle{ =\operatorname{ord}(A,\le_A)+\operatorname{ord}(B,\le_B) }[/math]라고 표기한다. 그냥 [math]\displaystyle{ B }[/math]를 [math]\displaystyle{ A }[/math] 뒤에 갖다 붙인 거라고 생각하면 된다.

놀랍게도... 이 덧셈은 교환법칙이 성립하지 않는다. 뭐요? 덧셈이 덧셈이 아니야 [math]\displaystyle{ 1+\omega = \omega }[/math][7]이지만, [math]\displaystyle{ \omega + 1 \neq \omega }[/math]이다. [math]\displaystyle{ \omega + 1 }[/math]는 앞에서 예로 든 0이 가장 큰 수고 나머진 똑같은 그 정렬집합의 순서수이다.

곱셈[편집 | 원본 편집]

곱셈도 가능하다. 두 정렬집합 [math]\displaystyle{ (A, \le_A), (B, \le_B) }[/math]이 있을 때, [math]\displaystyle{ (A \times B, \le_{ab}) }[/math]에 대해

  • [math]\displaystyle{ (x, u) \le_{ab} (y, v) \iff x \le_A y \lor (x = y \land u \le_B v) }[/math]일 때,

[math]\displaystyle{ \operatorname{ord}(A \times B, \le_{ab}) = \operatorname{ord}(A, \le_A) \times \operatorname{ord}(B, \le_B) }[/math]이다.

쉽게 직관적으론 사전정렬을 생각하면 된다. 이 곱셈 역시 교환법칙이 성립하지 않는데, 예로, [math]\displaystyle{ 2 \omega = \omega }[/math]인데, [math]\displaystyle{ \omega 2 \neq \omega }[/math]이다.

응용[편집 | 원본 편집]

추가바람

같이 읽을 거리[편집 | 원본 편집]

이 외에도 추가바람

각주

  1. ↑ 참고로 이 모임은 그냥 모여있는 것(collection)이며 집합론의 다른 개념(class)을 뜻하는 것은 아니다. 물론 집합은 모임(class)이다.
  2. ↑ ZF에 선택공리(AC)를 추가한 것이다.
  3. ↑ 부분 순서 관계라고도 한다. 임의의 두 원소의 비교가능성이 항상 보장되지 않으므로 이렇게 부른다.
  4. ↑ 짝수 집합과 홀수 집합의 농도는 [math]\displaystyle{ \aleph_0 }[/math]이고, 저 두 집합의 합인 자연수 집합의 농도도 [math]\displaystyle{ \aleph_0 }[/math]이다.
  5. ↑ \mathbb{N}\times\mathbb{N}와 \mathbb{N} 사이에 일대일대응 함수를 만들 수 있다.
  6. ↑ 모든 두 원소가 대소비교가 가능한 부분순서
  7. ↑ 간단히 수식을 설명하면, 0보다 더 작은 원소 하나를 더 추가해도 순서수는 바뀌지 않는다.