이상엽 집합론 정주행 7회차 - 집합의 순서

1. 부분순서집합

들어가기에 앞서 여기에 있는 내용을 미리 숙지하고 오는 것이 좋다.

https://dafher-diary.tistory.com/45

이상엽 집합론 정주행 3회차 - 관계와 분할

 

1) 정의

① 부분순서관계: 반사적, 반대칭적, 추이적인 관계

ex1) 두 집합 A, B에 대하여 A ⊆ B

ex2) 두 실수 x, y에 대하여 x ≤ y

ex3) 두 자연수 n, m에 대하여 n이 m의 배수인 관계

 

② 부분순서집합: 집합 A상에 부분순서관계 "≤" 가 주어진 경우 A를 부분순집합이라 하고 이를 (A, ≤)로 나타내기도 한다. (굳이 "≤" 가 아니어도 되며 모든 원소가 순서관계를 가져야 하는 것은 아니다.)

ex) A = { ∅, {1}, {2}, {1, 2} } → 이 집합은 ∅, {1}, {1, 2}와 ∅, {2}, {1, 2}로 순서관계를 가지지만 {1}과 {2}는 순서관계를 가지지 않는다. 하지만 부분순서집합이다. 만약 {3}같은 것이 원소로 추가되면 부분순서집합이 아니게 된다.

 

③ 극대원소와 극소원소: A가 부분순서집합이라 할 때 ∀x ∈ A, x ≥ a → x = a를 만족하는 A의 원소 a를 극대원소, ∀x ∈ A, x ≤ b → x = b를 만족하는 A의 원소 b를 극소원소라 한다. 아래의 이미지에서 A, B가 극소원소이고 C, E가 극대원소이다.

 

④ 최대원소와 최소원소: A가 부분순서집합이라 할 때 ∀x ∈ A, x ≤ a를 만족하는 A의 원소 a를 최대원소, ∀x ∈ A, x ≥ b를 만족하는 A의 원소 b를 최소원소라 한다. 아래 이미지에서 E가 최대원소이고 B가 최소원소이다.

 

2) 상한과 하한

지금까지 극대와 극소, 최대와 최소의 개념에 대해서 다뤘는데 사실 이 개념에도 약점이 존재한다. 바로 무한집합 때문인데 (0, 1)의 실수집합이 있다고 가정하자. 만약 [0, 1]로 되어있다면 0과 1을 포함하는 집합이어서 최대, 최소가 무엇인가에 대한 답을 바로 할 수 있겠지만 (0, 1)은 0과 1을 포함하지 않기 때문에 최대, 최소를 말하는데 있어서 문제가 생길 수 밖에 없다. 이 문제를 해결하기 위해 상한과 하한에 대한 내용을 다룰 것이다.

 

① 상계와 하계: B가 부분순서집합 A의 부분집합이라 할 때 ∀x ∈ B, x ≤ a인 a ∈ A를 A에서 B의 상계, ∀x ∈ B, x ≥ b인 b ∈ A를 A에서 B의 하계라 한다.

 

그림을 잘 보면 집합 B를 기준으로 F가 최대, D와 E가 극소라는 것을 알 수 있다. 상계는 집합 B를 기준으로 모든 극대의 위에 있는 원소를 상계라고 보면 된다. 만약 극대가 단 1개인 경우 즉, 위의 이미지처럼 최대가 존재할 경우에는 최대를 포함해서 F, G, H, I가 각각 상계인 것이다. 하계는 집합 B를 기준으로 전부 밑에 있는 원소들을 의미한다. 단, C의 경우에는 집합 B에 있는 극소인 D와 비교가 불가능하기 때문에 C는 하계에서 제외되고 A, B가 하계가 되는 것이다.

 

② 상한과 하한: 부분순서집합 A의 부분집합 B에 대하여 B의 상계(하계)들의 집합이 최소(최대)원소를 가질 때, 이 원소를 A에서 B의 상한(하한)이라 하고 sup B (inf B)로 나타낸다.

 

지금 아래의 그림을 보면 상계의 집합 {F, G, H, I}가 있는데 F가 최소인 것을 알 수 있다. 바로 이 때, 집합 B의 상한으로 F가 되는 것이다. 반면 하계 A, B에서 B가 최대인 것을 알 수 있으니 하한으로 B가 나오는 것이다. 상계와 하계하고 마찬가지로 상한과 하한 역시 B의 집합일 수도, 아닐수도 있다.

 

3) 절편과 절단

익숙한 단어가 등장했다. 절편이라고 하는 것을 학창 시절에 x절편, y절편으로 들어본 적이 있을 것이다. 이 곳에서는 아래와 같이 정의한다. 직접 보면 학창 시절에 봤던 것과 다르게 느껴질 것이다.

 

ⓛ 절편: 부분순서집합 A의 원소 a에 대하여 Sa = {x ∈ A | x < a}

ex1) R의 절편 S0 = (-∞, 0)

ex2) N의 절편 S3 = {1, 2}

 

② 절단

• B ∩ C = ∅, B ∪ C = A
• x ∈ B ∧ y ≤ x → y ∈ B
• x ∈ C ∧ x ≤ y → y ∈ C

을 만족하는 부분순서집합 A의 공집합이 아닌 부분집합들의 쌍 (B, C)

말이 어렵게 느껴질 수 있는데 B ∩ C = ∅, B ∪ C = A라는 부분을 통해 분할을 떠올리면 된다. 마치 어떤 것을 칼로 깔끔하게 잘라냈을 때, 군더더기 없이 정확하게 둘로 쪼개지는 것처럼 집합이 분할 즉, 절단되는 모습을 상상하면 되는 것이다. 예시를 들면 왼쪽은 E를, 오른쪽은 D를 기준으로 절단을 시켜서 각각 ({A, B, C}, {D, E, F})로 절단을 시킬 수 있는 것이다. 또한 E를 기준으로 절단을 시켜서 ({A, B, C, D, E}, {F})로 결과를 낼 수도 있다.

 

4) 순서동형

아래의 글에서 집합의 크기에 대해서 다룬 적이 있다.

https://dafher-diary.tistory.com/47

이상엽 집합론 정주행 5회차 - 집합의 크기

어떤 집합에서 다른 집합으로 향하는 전단사함수를 만드는 것이 가능하다면 두 집합의 크기가 같다는 것을 알 수 있었다. 마찬가지로 이제부터 다룰 내용을 통해서 어떤 집합에서 다른 집합으로 향하는 함수를 통해 어떤 정보도 존재하지 않는 다른 집합의 순서에 대해서 파악할 수 있게 된다는 것이다.

 

① 순서보존함수: 부분순서집합 A, B에 대하여 함수 f: A → B가 조건 ∀x, y ∈ A, x ≤ y → f(x) ≤ f(y)을 만족하면 f를 순서보존함수라 한다.

 

② 순서동형: 부분순서집합 A, B에 대하여 함수 f: A → B가 전단사이고 ∀x, y ∈ A, x ≤ y → f(x) ≤ f(y)이면 f를 순서동형사상이라고 한다. 이 때 A와 B는 순서동형이라고 한다.

 

 

2. 전순서집합

1) 전순서집합

① 비교가능: 부분순서집합 A의 두 원소 x, y가 x ≤ y ∨ y ≤ x이면 x와 y는 비교가능하다고 한다. (굳이 "≤" 일 필요는 없고 부분순서관계이기만 하다면 상관없다.)

 

② 전순서집합: 부분순서집합 A의 임의의 두 원소가 비교가능하면 A를 전순서집합이라고 한다. 즉, 말 그대로 어떤 원소를 뽑아와도 비교가능하다는 뜻이다.

 

2) 쇄

부분순서집합 A의 전순서 부분집합 B를 A에서의 쇄라고 한다.

위의 그림을 보면 부분순서집합 {A, B, C, D}를 볼 수 있다. 그런데 이 중에서 {A, C, D} 혹은 {B, C, D}같은 것들을 묶어서 부분집합을 만들면 그것은 전순서가 된다. 이것을 쇄라고 부른다.

 

3) 정렬집합

부분순서집합 A의 공집합이 아닌 모든 부분집합 B가 최소원소를 가지면, 그리고 그 때만 집합 A를 정렬집합이라 한다. 직관적인 이해를 위해 예시를 보자.

 

ex1) ((0, 1), ≤): 0과 1사이의 실수에 대해 "≤" 라는 관계를 보는 것인데 명백한 전순서집합이지만 정렬집합은 아닌 집합이다. 모든 부분집합이 최소원소가 있어야 하는데 부분집합으로 (0.5, 0.6)과 같은 부분집합을 잡았을 때, 0.5가 이 집합에 포함되지 않기 때문에 최소원소를 뭐라고 말할 수 없는 상태이다.

 

ex2) (N, ≤): 자연수 전체의 집합이다. 이 경우는 어떤 범위를 잡아도 적어도 1은 최소원소로 보장이 가능하다. 다른 자연수 a, b를 가지고 범위를 잡아도 어차피 최소원소로 a혹은 a + 1을 잡을 수 있기 때문에 정렬집합인 것이다.

 

ex3) (Z, ≤): 정수 전체의 집합인데 이 경우는 상황이 다르다. 수직선을 그렸을 때, 음수의 방향으로 무한히 나아가기 때문에 최소원소를 구할 수 없는 것이다. 따라서 전순서집합이지만 정렬집합은 아닌 것이다.

 

 

3. 서수

사실 강의에서 서수의 정의를 설명할 때, 다른 곳과 좀 다르게 정의를 했다. 원래 서수라는 것이 순서를 나타내는 수라고 정의를 하는데 이 강의는 순서가 아니라 길이를 나타내는 수라고 했다. 앞서 우리는 집합의 크기를 기수라고 부른다고 배웠고 기수에 대해서 다뤘는데 막상 서수를 보면 기수와 다를 것이 없어보이다. 강의에서는 그 차이가 구조를 띄고 있냐 그렇지 않냐에 대한 차이를 이야기했는데 그럼 서수에 대해서 알아보자.

 

1) 서수의 개념: 집합의 길이를 나타내는 수

① 모든 정렬집합 A에 대하여 서수가 존재하며, 모든 순서수 a에 대하여 o(A) = a인 정렬집합 A가 존재한다.

② A = B ↔ o(A) = o(B)

③ A = ∅ ↔ o(A) = 0

④ A = { 1, 2, 3, ... , k } ↔ o(A) = k

 

여기서 o(A)는 집합 A의 서수를 의미하며 오로지 정렬집합에서만 서수에 대해 이야기할 수 있다. 이것은 기수와의 차이를 보이는 부분이다.

 

2) 유한서수, 초한서수

ⓛ 유한서수: 유한정렬집합의 기수(오타아님)

② 초한서수: 무한정렬집합의 서수

 

< 대표적인 초한서수 >

ω(오메가) = o(N) 자연수 집합의 서수

자연수 집합의 서수와 구조가 동일한 무한정렬집합이 있다면 그 또한 서수가 ω이다.

 

3) 서수의 순서와 연산

정렬집합 A, B에 대하여 o(A) = a, o(B) = b일 때, A가 B의 절편과 순서동형이면 a는 b보다 작거나 같다고 한다. 다만 이 글에서는 원래 쓰는 기호를 찾는 것이 힘들어서 그냥 a ≤ b, a < b로 대체하고자 한다.

 

① 서수 합: 서로소인 두 집합 A, B의 서수를 각각 a, b라고 할 때, a + b = o(A ∪ B)라고 한다.

② 서수 곱: 집합 A, B의 서수를 각각 a, b라고 할 때, ab = o(B × A)라고 한다.

 

여기서 주의할 점은 o(A × B)가 아니라 o(B × A)라는 것이다. 왜 그렇냐고 하면 이게 그냥 수학자들이 한 정의라서 딱히 이유는 없다... o(A × B)가 좀 더 편해 보이겠지만 o(B × A)가 정의라서 일단은 이렇게 할 것이다.

 

4) 연산법칙

임의의 서수 a, b, c에 대하여 다음이 성립한다.

 

① 결합법칙: (a + b) + c = a + (b + c)

② 분배법칙: a(b + c) = ab + ac (단, (a + b)c ≠ ac + bc)

 

생각했던 것과는 결과가 많이 다르게 나오는 것일지도 모르겠다. 이런 결과가 나오는 이유는 서수의 연산은 합과 곱에서 교환법칙이 성립하지 않기 때문에 이런 현상이 나온다. 왜 교환법칙이 성립하지 않는지에 대한 증명은 아래의 링크에서 1:08:27부터 시청해보자.

https://www.youtube.com/watch?v=I_btU_4dQyU&list=PL127T2Zu76FveA8TGXZU-PSSt7GTMhKp6&index=9