순서쌍 는 , , 를 순서대로 각각 , , 에 대응시키는 함수로 생각할 수 있다. 이러한 관점에서 임의 개수의 집합의 데카르트 곱을 정의해보자.
두 집합
,
에 대하여, 정의역이
이고 공역이
인 모든 함수들의 모임을
로 나타낸다. 그리고 집합족
∈
와
∈
에 대하여
의 데카르트 곱을
∈
≔
∈
∀∈
∈
로 정의한다. [
는 ‘product’라고 읽는다.]즉 데카르트 곱
∈
는 정의역이
이고 공역이
∈
인 함수들 중에서 각 ∈
를
의 원소에 대응시키는 함수들의 모임이다.참고
1.4.8 집합론에서 이상의 정수는 다음과 같이 정의된다.
≔ ∅, ≔ , ≔ , ≔ , ≔ , ⋯
따라서 ℝ는 정의역이 이고 공역이 ℝ인 함수들을 모두 모은 집합이라고 생각할 수 있다. 이것은 앞서 언급한 것처럼 순서쌍 를 ↦ , ↦ , ↦ 인 함수로 생각하는 것과 일치한다. □
1.5 순서집합
반사적이고 반대칭적이며 추이적인 관계를 순서관계라고 부른다. 예를 들어 ≤는 ℝ에서의 순서관계이다. 순 서관계 ≤가 주어진 집합
를 순서집합(ordered set)이라고 부르고 〈
≤〉로 나타낸다. 혼동할 염려가 없을 때에는 〈
≤〉를 그냥
로 나타낸다.순서집합
의 원소 , 에 대하여 ≤ 또는 ≤ 가 성립할 때 ‘와 는 비교 가능하다(comparable)’라고 말한다. 순서집합
의 임의의 두 원소가 비교 가능할 때
를 전순서집합(totally ordered set) 또는 선형순서집합 (linearly ordered set)이라고 부른다.보기
1.5.1 실수의 크기를 비교할 때 사용하는 부등호 ≤는 ℝ에서의 순서관계이다. 이 순서관계를
자연순서 (natural order, canonical order)라고 부른다.
⊆ ℝ이고 ≤≔ ∈
×
≤ 이면 ≤는
에서의 순서관계가 된다. 이러한 관점에서 순서집합의 부분집합은 순서집합이다. □
보기
1.5.2 정수론에서는 두 정수 , 에 대하여 이 의 약수일 때 으로 나타낸다.
[ 은 ‘이 을 나눈다’라고 읽는다.] 이때 는 자연수 집합에서의 순서관계가 된다. 왜냐하면∙ 임의의 자연수 에 대하여 이다,
∙ 자연수 , , 에 대하여 이고 이면 이다,
∙ 자연수 , 에 대하여 이고 이면 이다
가 모두 성립하기 때문이다. 그러나 는 자연수 집합에서 전순서관계가 아니다. 왜냐하면 과 는 서로 약수이
거나 배수인 관계가 아니므로 비교 가능하지 않기 때문이다. □
보기
1.5.3
가 집합족이라고 하자. 이때 부분집합관계 ⊆는
에서의 순서관계가 된다. 왜냐하면∙ 임의의 집합
에 대하여
⊆
이다,∙ 집합
,
,
에 대하여,
⊆
이고
⊆
이면
⊆
이다,∙ 집합
,
에 대하여,
⊆
이고
⊆
이면
이다가 모두 성립하기 때문이다.
가 어떤 집합인지에 따라서 ⊆는 전순서관계가 될 수도 있고 그렇지 않을 수도 있다. 예를 들어
∅ 이면 ⊆는
에서의 전순서관계이다. 그러나 만약
∅ 이면 ⊆는
에서의 전순서관계가 아니다. □위 보기에서 보다시피 특정한 집단에서는 모든 대상을 한 줄로 세울 수 있는 기준일지라도 집단이 달라지면 동 일한 기준으로 대상을 한 줄로 세울 수 없는 경우가 있다. 따라서 우리는 세상을 살면서 얻은 자신의 기준으로 모든 것을 비교하려고 하지 말아야 한다.
보기
1.5.4 사전에는 단어가 순서대로 정렬되어 있다. 두 단어의 첫 글자가 다르면 첫 글자에 따라 단어의
순서가 정해지지만, 첫 글자가 같으면 두 번째 글자에 따라 단어의 순서가 정해진다. 두 순서쌍의 순서를 비교 할 때에도 비슷한 방법을 사용할 수 있다.순서집합 〈
≤〉, 〈
≦〉가 주어졌다고 하자. 이제 집합
×
에 다음과 같은 관계를 주자.
⩽
⇔
≤ ∧ ≠
∨
∧ ≦
이러한 순서관계 ⩽를 사전식 순서(lexicological order)라고 부른다. □
순서집합의 구조를 그림으로 나타낼 수 있다. 예를 들어 집합
,
,에 보기 1.5.2에서와 같은 순서관계 가 주어졌다고 하자. 이때 순서집합
,
의 구조를 그림으로 나타내면 다음과 같다.위 그림에서 관계가 있는 모든 원소가 직접 연결되어 있는 것은 아니다. 예를 들어 은 의 약수이지만
를 통해 연결되어 있으므로 과 는 직접 연결하지 않는다.
29
1.5 순서집합
앞의 그림에서
는 전순서집합이 아니지만 부분집합
는 전순서집합이다. 이렇게 순서집합의 전순서부분집합 을 사슬(chain) 또는 쇄라고 부른다. 즉
는
의 사슬이다.순서집합 〈
≤〉, 〈
≦〉에 대하여∀ ∈
≤ → ≦ 를 만족시키는 함수
→
를 순서보존함수 또는 증가함수라고 부른다. 만약
→
가 일대일대응 이고 와 가 모두 순서를 보존하면 를 순서동형사상(order-isomorphism)이라고 부르고 이때 ‘
와
는 순 서동형(isomorphic)이다’라고 말한다. 두 집합
,
가 순서동형인 것을
≅
로 나타낸다. 순서집합들을 모은 집합족에서 순서동형관계는 동치관계이다.보기
1.5.5 집합
,
에 순서관계가 다음과 같이 정의되었다고 하자.이때
와
는 서로 다른 원소를 가진 집합이지만, 서로 동일한 순서구조를 가지고 있다. 즉
로부터
로의 함수
→
를 , , ,
이라고 정의하면 는
로부터
로의 순서동형사상이 된다. 따라서
와
는 순서동형이다. □직관적으로 동형이란 두 집합의 구조가 동일한 것을 의미한다. 위 보기에서 집합
,
는 다른 원소를 가지고 있지만 순서집합이라는 관점에서는 서로 같다고 할 수 있다. 특히
의 원소 는
의 원소 과 동일한 역 할을 한다고 볼 수 있다. 문학에서 사용하는 비유도 동형인 두 집단에서의 동일한 역할을 하는 두 원소를 대응 시키는 함수라고 생각할 수 있다.다음으로 순서집합의 원소와 관련된 용어를 살펴보자.
전체집합 과 두 집합
,
에 다음 그림과 같은 순서 관계가 주어졌다고 하자.이때 은
의 원소 중에서 가장 큰 원소이고 은
의 원소 중에서 가장 작은 원소이다. 이러한 원소를 각각 최대원소, 최소원소라고 부른다.즉
이 순서집합
의 원소이고 ∀∈
≤
이 성립하면
을
의 최대원소 또는 끝 원소라고 부른 다. 또한 이 순서집합
의 원소이고 ∀∈
≤ 가 성립하면 을
의 최소원소 또는 첫 원소라고 부른다.한편 집합
는 최대원소나 최소원소를 갖지 않는다. 은
의 최대원소처럼 보이지만 와 은 비교 가능하지 않기 때문에 어느 쪽이 더 크다고 할 수 없다. 그러나
의 원소 중에는 보다 큰 원소도 없고 보다 큰 원소 도 없다. 이러한 원소를 극대원소라고 부른다. 즉 가 순서집합
의 원소이고∀∈
≤ → 가 성립하면 를
의 극대원소라고 부른다. 위 명제는 ‘
의 원소 중에서 이상인 원소는 자신밖에 없다’라는 의미이다. 마찬가지로 가 순서집합
의 원소이고∀∈
≤ → 가 성립하면 를
의 극소원소라고 부른다.정의에 의하여 최대원소와 최소원소는 각각 극대원소와 극소원소가 된다. 즉 집합
에서 은 최대원소인 동시 에 극대원소이며 은 최소원소인 동시에 극소원소이다.보기
1.5.6
실수 집합 ℝ에 자연순서가 주어져 있고
ℝ × ℝ에 사전식 순서가 주어져있다고 하자. 그 리고 집합
≤
이 주어졌다고 하자. 즉
는 좌표평면에서 원점을 중심으로 하고 반지 름이 인 원의 내부와 경계를 포함하는 집합이다. 이때 은
의 최대원소이며 은
의 최소원소이다. □
가 순서집합이고
⊆
라고 하자. 만약 가
의 원소이고 ∀∈
≤ 가 성립하면 를
의 상계 라고 부른다. 또한 가
의 원소이고 ∀∈
≤ 가 성립하면 를
의 하계라고 부른다. 상계를 갖는 집합을 위로 유계인 집합이라고 부르며 하계를 갖는 집합을 아래로 유계인 집합이라고 부른다. 상계 중 가장 작 은 것을 최소상계 또는 상한이라고 부르며 하계 중 가장 큰 것을 최대하계 또는 하한이라고 부른다.보기
1.5.7 집합
,
에 다음 그림과 같은 순서관계 가 주어졌다고 하자.이때
의 상계는 이고 하계는 , , , 이다. 은
에 속하는 하계이지만 , , 은
에 속하지 않는하계이다.
의 상한은 이고 하한은 이다. □31
1.5 순서집합 보기
1.5.8 집합
,
에 다음 그림과 같은 순서관계가 주어졌다고 하자.이때
의 상계와 상한은 존재하지 않는다. 즉
는 위로 유계가 아니다. □위 두 개의 보기를 통해 다음 사실을 알 수 있다.
∙ 상계와 하계가 항상 존재하는 것은 아니다.
∙ 상계와 하계는 각각 하나씩 존재할 수도 있고 여러 개가 존재할 수도 있다.
∙ 상계와 하계는 그 집합에 속할 수도 있고 속하지 않을 수도 있다.
∙ 동일한 집합일 지라도 그것을 포함하는 전체집합이 달라지면 상계와 하계가 달라질 수 있다.
보기
1.5.9 자연순서가 주어진 실수 집합 ℝ의 반열린구간 은 유계이다. 이 집합의 하한은 이고 상
한은 이다. 이 집합의 최솟값은 이지만 최댓값은 존재하지 않는다. □
순서집합
에 대하여,
의 공집합 아닌 모든 부분집합이 단 하나의 극소원소를 가지면
를 정렬집합(well- ordered set)이라고 부른다.보기
1.5.10 자연순서가 주어진 자연수 집합 ℕ은 정렬집합이다. 왜냐하면 자연수만으로 이루어지고 공집합
아닌 집합은 항상 최소원소를 갖기 때문이다. 반면 정수 집합 ℤ는 정렬집합이 아니다. 왜냐하면 모든 음의 정 수의 집합은 ℤ의 부분집합이고 공집합이 아니지만 극소원소를 갖지 않기 때문이다. □보기
1.5.11 모든 양의 실수의 집합 ℙ에 자연순서가 주어져 있을 때 ℙ는 정렬집합이 아니다. 왜냐하면 반
열린구간 ≤ 는 ℙ의 부분집합이고 공집합이 아니지만 극소원소를 갖지 않기 때문이다.□
참고로 모든 정렬집합은 전순서집합이다. 즉 〈
≤〉가 정렬집합이라고 하자. 그리고 , 가
의 임의의 원 소라고 하자. 그러면 는
의 공집합 아닌 부분집합이다. 만약 와 가 비교 가능하지 않다면 와 는 모두 의 극소원소가 된다. 그런데
는 정렬집합이므로 의 극소원소는 유일하다. 이것은 모 순이므로 와 는 비교 가능하다.그러나 모든 전순서집합이 정렬집합인 것은 아니다. 예를 들어 자연순서가 주어진 집합 ℤ, ℝ는 전순서집합 이지만 정렬집합이 아니다.