0. 부분집합의 정의
2화에서 다룬 부분집합을 명제를 이용해 잘 정의해 보겠습니다.
(for all a)(a in A -> a in B)일 때 A의 모든 원소가 B의 원소가 되는 것과 같으므로 A를 B의 부분집합이라 합니다. A가 B의 부분집합임은 연산자 "is subset of"를 이용해 A is subset of B라고 나타냅니다.
두 집합이 같다는 것은 A is subset of B && B is subset of A임을 의미합니다.
1. 순서쌍과 곱집합
튜플이란 순서를 가진 어떤 대상의 나열입니다. 괄호 안에 순서대로 (a,b,c)와 같은 식으로 쓰게 됩니다. 특별히 두 대상만 나열된 튜플은 순서쌍이라고 부릅니다.
새로운 집합을 정의해 보겠습니다. 집합 {(a,b)|a in A && b in B}는 잘 정의됩니다. 이 집합을 A와 B의 곱집합이라고 하고, A*B라고 씁니다. A*B는 앞 요소로 A의 원소를, 뒷 요소로 B의 원소를 가지는 순서쌍의 집합이 됩니다. 예를 들어, {1,2}*{a,b}의 원소는 (1,a), (1,b), (2,a), (2,b)로 4개가 됩니다. 자기자신을 곱한 곱집합, 예컨대 A*A는 연산자 ^를 이용해 A^2과 같이 쓸 수 있습니다.
같은 방식으로 집합 {(a,b,c)|a in A && b in B && c in C} 등, 괄호 안에 셋 이상의 요소를 가지는 튜플을 만들 수 있습니다. 이때 이 튜플들의 집합은 A*B*C와 같이 쓸 수 있습니다. 주의할 점은 A*B*C와 (A*B)*C는 다른 집합입니다. A*B*C는 크기가 3인 튜플을 원소로 가지지만, (A*B)*C는 A*B의 원소인 순서쌍과 C의 원소를 순서대로 가지는 순서쌍이 됩니다.
2. 관계와 관계의 성질
관계는 두 집합 A, B의 원소 a,b에 대해 관계 R이 있어 a와 b가 R의 관계가 있음은 aRb와 같이 쓰고, R은 A*B의 부분집합으로 정의됩니다. 즉, R is subset of A*B라면 R을 A와 B 사이에 정의되는 관계라고 할 수 있다는 것입니다. 이때 (a,b)가 R의 원소일 때 aRb라고 씁니다. 예를 들어, {1,2}*{a,b} 위에 정의된 관계 R이 { (1,a), (1,b), (2,a) }이라고 할 때, 1Ra, 1Rb, 2Ra라고 하는 것은 타당하지만, 2Rb라고 하는 것은 타당하지 않습니다. aRb는 (a,b) in R의 다른 표현이므로 in 연산자를 활용한 명제식이 됩니다.
어떤 관계 R이 reflexive:반사적이라는 것은, (for all a) aRa라는 것입니다.
어떤 관계 R이 symmetric:대칭적이라는 것은, (for all a)(for all b) aRb <-> bRa라는 것입니다.
어떤 관계 R이 transitive:추이적이라는 것은, (for all a)(for all b)(for all c) aRb && bRc -> aRc라는 것입니다.
관계 R의 Domain:정의역은 첫 번째 요소의 집합을 말하고 D(R)이라고 씁니다. D(R)은 조건 제시법으로 {x| (exist y) xRy}와 같이 정의됩니다.
관계 R의 Range:치역은 두 번째 요소의 집합을 말하고 R(R)이라고 씁니다. R(R)은 조건제시법으로 {y| (exist x) xRy}와 같이 정의됩니다. Range를 취하는 연산자 R()과 관계 R은 다른 토큰입니다.
3. 동치관계와 부분순서
동치관계란, 어떤 관계 R이 reflexive:반사적이고, symmetric:대칭적이고, transitive:추이적일 때 R을 동치관계라고 합니다. 특별히 동치관계인 관계를 = 기호를 이용해 표시합니다. 다르게 말하면 동치관계의 대표 심볼을 공연히 =로 씁니다.
예를 들어, 명제 연산자 <->는 a<->b 꼴로 나타낼 수 있고, a와 b는 각각 T 또는 F만을 취할 수 있고, <->를 집합 {T,F}*{T,F}의 부분집합이라고 할 수 있습니다. 이때 <->는 진리표를 통해 {(T,T), (F,F)}인 관계로 두는 것은 적절합니다. 이때 관계 <->는 동치관계입니다.
reflexive하고, symmetric하고, transitive한 것을 {T,F}*{T,F}의 모든 경우에 대해 직접 확인할 수 있습니다. 동치 관계의 대표 심볼로 a<->b를 a=b로 쓸 수 있습니다. 또는 두 집합이 같을 때도 동치관계라고 할 수 있습니다.
R이 antisymmetric:반대칭적이라는 것은, (for all x)(for all y) aRb && bRa -> a=b라는 것입니다.
Partial ordering:부분순서관계란, 어떤 관계 R이 reflexive:반사적이고, antisymmetric:반대칭적이고, transitive:추이적일 때 R을 부분순서관계라고 합니다. 특별히 부분순서 관계를 <= 기호를 이용해 표시합니다. (실제 표기는 ≤ 입니다.)
예를 들어 부분집합은 명제식으로 (for all x) (x in A-> x in B)일 때 A가 B의 부분집합이라고 하고 "is subset of"를 이용해 A is subset of B라고 씁니다. 이때 is subset of는 관계로 생각할 수 있고, reflexive:반사적이고, antisymmetric:반대칭적이고, transitive:추이적인 것을 증명을 통해 보일 수 있습니다. 증명 파트에서 증명을 다루겠습니다.
4. 함수
함수란, 어떤 집합 X의 원소 x에 대해 유일하게 y로 대응시키는 관계 f가 있을 때, f를 함수라고 합니다. 명제식으로 쓰면, (for all x)(for all y)(for all z)( xfy && xfz -> y=z)입니다. 명제식을 자연언어로 읽어보면, "모든 x,y,z에 대해 xfy이고 xfz이면 y=z이다"이고, xfp인 p는 모두 동치이다, 그런 p는 유일하다는 뜻과 본질적인 대상이 동일합니다. 서로 다른 p의 예시로 p1, p2가 존재한다면 p1,p2는 서로 같아야만 한다 정도로 해석해볼 수 있습니다.
함수 f에 대해 xfy일 때, 특히 f가 관계보다 함수라는 것을 강조하고 싶을 때 f(x)=y라는 표기를 사용합니다. 이때 x를 argument:변수, y를 value:함수값이라고도 합니다.
5. 관계의 중첩과 다양한 관계
어떤 관계 R의 converse(또는 inverse):역관계는 #R과 같이 표시하고 (수기에서는 위첨자로 c를 쓰는게 일반적입니다.), #R = {(y,x)|(x,y) in R}과 같이 정의됩니다.
어떤 관계가 A의 identity relation:항등관계임은 그 관계가 {(a,a)|a in A}임을 의미합니다. 이때 관계의 대표 심볼을 E로 씁니다.
어떤 관계 R (is subset of A*B), Q (is subset of B*C)가 있을 때 관계 RQ는 R과 Q의 composition:중첩이라 하고, RQ = {(x,z) | (x,y) in R && (y,z) in Q}와 같이 정의됩니다.
관계의 중첩에는 아래 성질들이 성립합니다.
1. R#R = E
2. ER = R, RE = R
관계 또한 집합으로 정의되었기 때문에 합집합과 교집합이 존재합니다. 합집합과 교집합에 대한 아래 성질들이 성립합니다.
1. (RS)T = R(ST)
2. R(S|T) = (RS)|(RT)
3. (R|S)T = (RT)|(ST)
4. R(S&T) is subset of (RS)&(RT)
5. (R&S)T is subset of (RT)&(ST)
2화에서 다룬 내용인데, 1번은 중첩에 대한 결합법칙, 2,3번은 중첩과 합집합에 대한 결합법칙입니다. 4,5는 결합법칙이 잘 성립하지 않지만 어느정도는 성립 비슷하게 한다는 것을 보여줍니다. 이후 증명 부분을 다루게 되면 1,2,3은 쉽게 증명할 수 있고, 4,5는 간단한 반례를 통해 왼쪽과 오른쪽이 항등관계가 아님을 보일 수 있습니다. 직접 반례를 찾아보세요.
6. 마치며
다음 내용을 어떤 내용을 다룰 지 고민이 많습니다. 후보는 "자연수의 정의와 실수", "증명"정도입니다. 많은 학교들이 기말고사 기간일텐데, 노력한 만큼의 성적을 모두 거둘 수 있으면 좋겠습니다. 업로드 텀이 길어진 변명이니 이해 바랍니다. 슬슬 번역도 힘들어지기 시작합니다. 영어 용어를 우리말로 번역하는 것도 제법 힘드네요.
