[Section 2] 집합들의 관계

대수학 목차 보기

[INTRO] 대수학 미리보기

0. INTRO

칸토어는 1845년에 태어나 1918년에 생을 마감한 독일의 수학자이다. 그는 무한에 매료되어, 집합론이라는 수학 체계를 완성하는데, 그 당시 그의 이론은 당대의 수학자들에게 환영받지 못하였다. 위대한 수학자 가우스 또한 무한을 셈하려는 것에 반대하였다고 한다. 하지만 집합론은 인간의 인식체계를 자연스럽게 확장시켜주는 계기가 되었고, 그의 집합론은 현대 수학의 근간을 이루고 있다. 현대 수학의 근간인 집합론을 이해하기 위해 집합 간의 관계를 나타내는 집합을 정의해보자.

1. 집합 간의 관계

집합론에서 가장 중요한 개념은 집합끼리의 관계이다. 이는 순서론적 개념을 이해하는데 선행되어야 할 개념임이 틀림없기에 집합 간의 관계를 다음과 같이 A, B, C 순서로 정의하자.

A. 집합의 관계(relation) , <A,B>

일반적인 비교 연산자 '<'와 '>'는 ~보다 작다, 혹은 ~보다 크다는 의미를 가지는 술어 연산자이다. 이러한 술어 관계는 수학적으로 <A, B> 쌍으로 나타낸다. 집합의 관계에 있어서 <A, B>는 2-place 관계이다(자연수에 대해서). 3-place 관계를 'x+y=z'의 방정식에서 알 수 있지만, 보통 관계는 2-place 관계를 의미한다.

 

수학적으로 관계는 순서 쌍들의 집합을 의미한다. 다시 말해서, x가 어떤 관계에 대해 y를 만족한다는 것은 순서쌍 <x, y>가 집합 r의 원소이며, 다음의 xry 대응관계가 성립한다는 것이다. 

 

"xry ⇔ <x, y>∈r"

 

이 순서쌍 집합 r의 원소들은 고정된 기본 집합(fixed ground set), M에 속한다고 가정한다. 여기서 r 등의 알파벳으로 표기한 변수는 관계를 나타낸다. 예를 들어, 어떤 집합 M과 자연수 집합 N이 각각의 집합에 원소를 나타내는 변수 m과 n에 대해서 <m, n>이 관계 ≤에 속하면, m≤n 관계를 만족하는 순서쌍 <m, n>이 집합 r에 속하게 된다.

 

정의에 따라서 관계 m≤n을 나타내는 순서쌍 집합은 <0,0>, <0,1>, <1,1>, <1,2>... 를 원소로 가지는 집합이 된다. 

 

B. 관계(relation)의 영역(domain)

관계 집합 r을 위의 자연수 집합에서 정의한 바와 같이,  xry 혹은 yrx 관계를 만족하는 x와 y의 원소 집합을 영역(domain)이라고 정의한다. 예를 들어 자연수 집합에서 어떤 관계 r 이 '<'의 관계를 만족하는 <x, y>의 집합이라고 할 때, 첫 번째 영역(the first domain)은 ⋁yxry에 의해서 정의된 집합 θ₁(r)= {0,1,2...}으로 정의한다. 그리고 두 번째 영역(the second domain)은 ⋁_yyrx θ₂(r)= {1,2...}으로 정의한다. 따라서 어떤 관계, r에 있어서 영역(domain)은 집합 θ1(r)∪θ2(r)으로 나타내는 것이 가능하다. 

C. 항등 관계, I

 항등(Identity) 관계는 I로 표시하고 xIy 관계식은 다음의 명제와 동치이다.

 

"xIy ⇔ x=y"

 

* 빈(empty or void) 관계

빈 관계를 나타내는 순서쌍은 존재하지 않는다. 하지만 그 관계를 나타내는 집합은 다음과 같이 표기한다. 

 

D. 관계 대수(Algebra of Relations)

관계를 집합으로 정의하면, 임의의 관계 집합 R과 r을 다음과 같은 교집합(intersection)과 합집합(union), 그리고 보어(complement) 관계를 정의할 수 있다. 

 

교집합, 합집합, 보어 관계를 나타내는 기호들

 

 그리고 R과 r 집합의 부분(the inclusion) 관계, r⊆R을 다음의 기호로 간단히 나타낼 수 있다.

 

 "⋀_x⋀_y(xry⟶xRy)"

 

역(converse) 관계와 관계 곱(relative product)을 다음과 같이 정의할 수 있다.

 

역관계와 관계곱

 

* 관계곱은 교환 법칙이 성립하지 않는다.

하지만 같은 관계인 r과 r의 관계곱은 r²으로 나타내는 것이 일반적이다.

 

2. 관계 집합의 성질

관계를 집합으로 정의함으로써, 관계 집합은 다음의 A. 동일성(idenity), B. 반사성(reflexive), C. 추이성(transive), D. 연결성(connex)의 성질들을 갖는다.

A. 동일성(idenity)

역관계가 성립하는 관계 집합은 모두 대칭성(symmetric)을 갖는다. 만약 대칭성을 갖는 관계 r이 ⋀_x⋀_y(xry∧yrx⟶x=y)을 만족하면, 관계 r은 동일성을 가진다. 따라서 동일성은 두 집합 x, y 간의 같은 원소를 지칭하는 관계 원소가 존재하는 성질을 의미한다. 

B. 반사성(reflexive)

항등 관계를 포함하는 관계 집합은 반사성을 갖는데, 재귀성이라고도 불리는 이 성질은 첫 번째 영역의 원소와 동일한 원소가 두 번째 영역에도 있다는 것을 말한다.

C. 추이성(transive)

추이 성이라 함은 모든 x, y, z 원소에 대해서 xry이고 yrz 관계를 만족하는 r은 xrz에 대해서도 그 관계를 만족한다는 성질을 의미한다. 

D. 연결성(connex)

연결성을 가지는 관계 집합, r은 모든 x, y 원소에 대해서 xry이거나 yrx이다. 따라서 연결성이라 함은 관계 집합 r이 xry 혹은 yrx에 대해서 반드시 하나를 만족하는 성질을 의미한다. 

 

*  배열(orderings)에 대해서...

위에서 정의한 4가지 성질을 모두 만족하는 관계 집합 '≤'을 배열(orderings)이라고 부른다. '<' 관계로도 배열(orderings)을 정의할 수 있는데, 이 경우 동일성과 연결성은 다음으로 재정의함에 따라 4가지 성질을 모두 만족하는 관계 집합이 된다.

 

"⋀_x¬xrx and ⋀_x⋀_y(x≠y⟶xry∨yrx)"  

3. 집합론에서의 함수(function)

함수라 불리는 관계로 이루어진 모임은 다음의 유일성의 조건(the requirement of uniquness)에 따라서 정의된다. 

 

"⋀x⋀y⋀z((xry∧xrz)⟶y=z)"

 

일반적으로 함수는 'f(x) = y' 표기법으로 잘 알려져 있지만, 집합론 체제에서 위의 조건을 만족하고  xfy의 관계를 가지는 모든 집합을 f로 나타낸다. 이 f는 첫 번째 영역이 두 번째 영역으로 이동한다는 점에서 사상(mapping)이라고도 불린다. 함수 관점에서 역관계를 가지는 함수는 역함수가 된다. 역함수가 존재하는 함수는 가역적(invertible) 성질을 가진다. 

 

한편, 함수의 영역들(domains)이 자연수 체제를 따르게 되면, 그 함수를 수열(sequence)이라고 부른다. 그리고 앞서 언급한 서로 같은 집합의 정의에 따라서 같은 함수는 모든 영역의 원소에 같은 값을 갖게 된다. 

 

A. 전단사 함수(bijective function)

전단사 함수란, 두 집합에서 원소를 서로 일대일 대응(one to one correspondence)시키는 함수를 말한다. 만약 어떤 두 집합 A와 B가 전단사 함수를 통해서 일대일 대칭이 성립한다고 하면, 두 집합 A와 B는 같은 집합이다. 이를 간단히 A~B로 표기한다. 전단사 함수를 통해서 한 가지 명시해야 할 중요한 점은 두 집합의 원소는 중요하지 않다는 점이다. 따라서 전단사 함수를 통해서 드러낸 두 집합 A~B는 기수(cardinal number)의 관점에서만 동치이다.

 

B. 기수(cardinal number), x

기수는 집합의 크기를 나타내는 수를 의미한다. 예를 들어, A={0,1}이고 B= {1,2}라고 하자. 두 집합의 기수는 2로 같다. 즉, 기수가 같으면 전단사 함수이고 이를 기호 A~B로 나타낸다.

 

전단사 함수 예시

 

칸토어는 어떤 유한한 집합의 농도(cardinality)를 도입했다. 이 농도(cardinality) 개념의 도입은 유한한 집합에서 기수를 무한한 집합으로까지 확장하는 것을 가능케한다. 예를 들어, 자연수 집합 N과 자연수의 제곱을 원소로 가지는 N^2 집합은 다음과 같이 서로 일대일 대응 관계가 가능하다.  

 

N과 N^2 집합 관계

 

* 칸토어가 사용한 무한 집합은 데데킨트(Dedekind)의 무한 집합 정의를 따르는 것으로 알려져 있다.

 

칸토어에 의해, 무한 집합까지 확장한 기수(cardinal number) 개념은 어떤 집합 x에 있어서, x와 동등한 모든 집합들에  공통인 원소를 가지는 집합을 의미한다. 동등한 집합은 칸토어-번슈타인 정리에 의해서 정의된다. 

 

따라서 집합 x의 기수는 일대일 관계가 성립하는 임의의 모든 집합을 의미하고, 일반적으로 어떤 집합의 크기 성질을 나타내는 데 사용한다.

C. 칸토어-번슈타인 정리(Cantor-Bernstein equivalence theorem)

번슈타인은 모든 집합에서 유한하든, 무한하든 다음이 성립합을 증명하였다. 

 

"만약 A 집합이 B집합에 포함되고, B집합이 C집합에 포함되고, A와 C가 전단사 관계가 성립하면,

B와 C도 전단사 관계가 성립한다."

 

위의 정리는 번슈타인의 집합 동등의 정리이며, 기호로 다음과 같이 표시한다.

 

번슈타인의 동등 정리

 

D. 셀 수 있는 집합

(1) 자연수 체제를 따르는 어떤 집합의 기수를 다음과 같이 명시하고, (2) 초한수(transfinite), (3) 가산(countable)과 (4) 가산 이하(at most countable) 집합을 다음과 같이 정의한다.

 

기수와 셀수있는 집합의 정의

 

자세히 말하자면, (1)은 자연수 집합 N의 크기를 의미하고 '알레프-제로(aleph-zero)'라고 읽는다. 그리고 어떤 기수 X̃가 알레프-제로 보다 작을 때, 유한하다고 말한다. 이 정의에 따라서, 모든 유한한 집합은 (3) 가산이거나 (4) 가산 이하인 조건을 만족하게 된다. 반면, 초한수는 (2)의 조건으로 정의된다. 초한수는 무한 집합의 상대적인 크기를 나타내기 위해서 정의하였다. 

 

위의 조건들에 따라서, 어떤 유한한 기수 X̃는 유한 집합과 초한수 그리고 무한 집합까지 각각의 원소를 대응(비교)할 수 있다. 

 

 

 

* 다음 강의는 서수의 개념입니다.

[Section 2] 서수의 개념