이상엽/ 집합의 순서

부분순서집합

정의

부분순서관계

반사적, 반대칭적, 추이적인 관계

  • ex 1) 두 집합 A, B 에 대하여 A \subseteq B
  • ex 2) 두 실수 x, y 에 대하여 x \leq x
  • ex 3) 두 자연수 n, m 에 대하여 n m 의 배수인 관계

부분순서집합

집합 A 상에 부분순서관계 \leq 가 주어진 경우 A 를 부분순서집합이라 하고 이를 (A, \leq) 로 나타내기도 한다.

  • 집합 A \leq 관계가 부여 됐을 뿐이지, 집합 A 의 모든 원소들이 순서 관계를 가져야 하는 것은 아니다.
  • ex) A = \{ \emptyset, \{ 1 \}, \{ 2 \}, \{ 1, 2 \} \} 일 때, 
    • 다음의 관계는 성립하지만
      • \emptyset \to \{ 1 \}  
      • \emptyset \to \{ 2 \}  
      • \emptyset \to \{ 1, 2 \}  
      • \{ 1 \} \to \{ 1, 2 \}  
      • \{ 2 \} \to \{ 1, 2 \}  
    • 다음의 관계는 성립하지 않는다.
      • \{ 1 \} \to \{ 2 \}
      • \{ 2 \} \to \{ 1 \}
    • 즉 모든 원소들이 부분순서 관계를 갖지는 않는다는 것.

극대원소와 극소원소

A 가 부분순서집합이라 할 때,

  • \forall x \in A, x \geq a \Rightarrow x = a 를 만족하는 A 의 원소 a 를 극대원소,
  • \forall x \in A, x \leq b \Rightarrow x = b 를 만족하는 A 의 원소 b 를 극소원소라 한다.
  • ex) 멱집합 P(X) 에서 \emptyset, X
  • 극대, 극소 원소는 유일하지 않다. 극대, 극소는 최대, 최소와는 다르다.
  • ex) 집합 A = \{ a, b, c, d, e \} 의 관계가 다음과 같다면
    • a \to c  
    • b \to c  
    • b \to d  
    • d \to e  
    • c, e는 극대원소가 되고
    • a, b는 극소원소가 된다.

최대원소와 최소원소

A 가 부분순서집합이라 할 때,

  • \forall x \in A, x \leq a 를 만족하는 A 의 원소 a 를 최대원소,
  • \forall x \in A, x \geq b 를 만족하는 A 의 원소 b 를 최소원소라 한다.
  • 극대, 극소와 달리 최대, 최소는 유일하다.

상한과 하한

  • 극대-극소, 최대-최소를 무한집합에 적용하기 어렵기 때문에 만들어진 개념이 상계-하계, 상한-하한
  • 해당 집합을 포함하는 집합을 더 큰 정의하고 그 더 큰 집합을 이용해서 상계-하계와 상한-하한을 정의함. 

상계와 하계

B 가 부분순서집합 A 의 부분집합이라 할 때,

  • \forall x \in B, x \leq a a \in A A 에서 B 의 상계,
  • \forall x \in B, x \geq b b \in A A 에서 B 의 하계라 한다.
  • 상계-하계는 항상 존재하지 않음.

상한과 하한

부분순서집합 A 의 부분집합 B 에 대하여

  • B 의 상계들의 집합이 최소 원소를 가질 때 이 원소를 A 에서 B 의 상한이라 하고, sup B 로 나타낸다.
  • B 의 하계들의 집합이 최대 원소를 가질 때 이 원소를 A 에서 B 의 하한이라 하고, inf B 로 나타낸다.
  • ex) A = [ 0, 1 ) \subset \mathbb{R} 에서 0, 1

절편과 절단

절편

부분순서집합 A 의 원소 a 에 대하여

  • S_{a} = \{ x \in A | x < a \}
    • 집합 아래에 표시된 숫자보다 작은 숫자들을 모은 집합이라고 생각하면 된다.
  • ex 1) \mathbb{R} 의 절편 S_{0} = (- \infty, 0)
  • ex 2) \mathbb{N} 의 절편 S_{3} = \{ 1, 2 \}

절단

  1. B \cap C = \emptyset, B \cup C = A
  2. x \in B \wedge y \leq x \Rightarrow y \in B
  3. x \in C \wedge x \leq y \Rightarrow y \in C

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

  • ex) \mathbb{R} 의 두 부분집합 M = (- \infty, 0), N = [0, \infty) 에 대하여 (M, N)
  • 일종의 분할과 비슷하다.

순서동형

순서보존함수

부분순서집합 A, B 에 대하여

  • 함수 f : A \to B 가 조건 \forall x, y \in A, x \leq y \Rightarrow f(x) \leq f(y) 을 만족하면
  • f 를 순서보존함수라 한다.
  • 순서만 보장되면 되기 때문에, 집합 A와 집합 B의 크기가 달라도 무방하다.

순서동형

부분순서집합 A, B 에 대하여

  • 함수 f : A \to B 가 전단사이고 \forall x, y \in A, x \leq y \Rightarrow f(x) \leq f(y) 이면 f 를 순서동형사상이라 한다.
  • 이때 A, B 는 순서동형이라 하고 A \simeq B 로 나타낸다.
  • ex) 항등함수 I_{A} : A \to A

전순서집합

전순서집합

비교가능

부분순서집합 A 의 두 원소 x, y x \leq y \vee y \leq x 이면 x, y 는 비교가능하다고 한다.

  • ex) 집합 A = \{ a, b, c, d \} 의 관계가 다음과 같을 때
    • a \to c  
    • b \to c  
    • c \to d  
    • 다른 원소들 간에는 비교가 가능하지만 a와 b는 비교가 불가능하다.

전순서집합

부분순서집합 A 의 임의의 두 원소가 비교가능하면 A 를 전순서집합이라고 한다.

  • 집합 내의 모든 원소가 비교 가능한 상태이면 전순서집합이 된다.

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

  • ex) 집합 A = \{ a, b, c, d \} 의 관계가 다음과 같을 때
    • a \to c  
    • b \to c  
    • c \to d  
  •  A 는 전순서 집합이 아니지만, 만일 A 의 부분집합을  B = \{ a, c, d \} 로 잡으면 B 는 전순서집합이 되고, 이 때 B A 의 쇄라고 한다.

정렬집합

부분순서집합 A 의 공집합이 아닌 모든 부분집합 B 가 최소원소를 가지면, 그리고 그 때에만 집합  A 를 정렬집합이라 한다.

  • ex)
    • ((0, 1), \leq) 는 전순서집합이긴 하지만, 최소 원소를 갖고 있지 않기 때문에 정렬집합은 아니다.
    • (\mathbb{N}, \leq) 는 전순서집합이기도 하고 정렬집합이기도 하다.
  • 따라서 정렬집합이면 전순서집합이다. 그 역은 성립하지 않는다.

서수

서수의 개념

서수

집합의 길이를 나타내는 수

  1. 모든 정렬집합 A 에 대하여 서수가 존재하며, 모든 순서수 \alpha 에 대하여, o(A) = \alpha 인 정렬집합 A 가 존재한다.
    • 책에 따라 ord(A) 라고 표기하기도 함.
  2. A \approx B \Leftrightarrow o(A) = o(B)
  3. A = \emptyset \Leftrightarrow o(A) = 0
  4. A \approx \{ 1, 2, ... , k \} \Leftrightarrow o(A) = k
  • 기수와 서수의 가장 큰 차이는 구조가 들어가느냐 하는 것.

유한서수와 초한서수

유한서수란 유한정렬집합의 기수이고, 초한서수란 무한정렬집합의 서수이다.

  • <대표적인 초한서수>
    • \omega = o(\mathbb{N})

서수의 순서

정렬집합 A, B 에 대하여 o(A) = \alpha, o(B) = \beta 일 때,

  • A B 의 절편과 순서동형이면 \alpha \beta 보다 작거나 같다고 하며 \alpha \leqslant \beta 로 나타낸다.
  • 이때 특히 \alpha \neq \beta 이면 \alpha < \beta 로 나타낸다.

서수의 연산

서수 합

서로소인 두 집합 A, B 의 서수를 각각 \alpha, \beta 라고 할 때 \alpha + \beta = o(A \cup B)

  • ex) A = \{ 1 \}, B = \{ a, b \} 라면 
    • B B_{1} = \{ 2, 3 \} 로 변환한 후에
    • 그 둘을 합하여 A \cup B = \{ 1, 2, 3 \}   을 만든다.

서수 곱

서로소인 두 집합 A, B 의 서수를 각각 \alpha, \beta 라고 할 때\alpha \beta = o(B \times A)

  • 순서쌍의 순서는 앞의 것을 먼저, 뒤의 것을 그 다음에 보는 것이 자연스럽다 –사전식 순서
  • 뒤의 것을 앞으로 놓고 곱하는 것이 사전식 순서 결과를 만들 수 있기 때문에 서수곱은 뒤의 것을 먼저두는 식으로 한다. 이것은 일종의 수학적 약속.

연산 법칙

임의의 서수 \alpha, \beta, \gamma 에 대하여 다음이 성립한다.

  • 결합법칙
    • (\alpha + \beta) + \gamma = \alpha + (\beta + \gamma)
    • \alpha (\beta \gamma) = (\alpha \beta) \gamma
  • 분배법칙
    • \alpha (\beta + \gamma) = \alpha \beta + \alpha \gamma
    • 단 (\alpha + \beta) \gamma \neq \alpha \gamma + \beta \gamma
      • 좌측 분배 법칙은 성립하지만, 우측 분배 법칙은 성립하지 않는다.
      • 2 \cdot (\omega + 1) = 2 \cdot \omega + 2
      • (\omega + 1) \cdot 2 \neq \omega \cdot 2 + 2
  • 일반적으로 서수는 합과 곱에 대하여 교환법칙이 성립하지 않는다.
    • 1 + \omega \neq \omega + 1
    • 2 \cdot \omega \neq \omega \cdot 2
  1.  
[ssba]

The author

지성을 추구하는 사람/ suyeongpark@abyne.com

댓글 남기기

This site uses Akismet to reduce spam. Learn how your comment data is processed.