Tag Archives: 집합

순서수

개념

  • 기수란 집합의 전단사 함수 성질을 나타냄
    • 집합 내의 대등한 것들을 같은 수로 결부시키는 것
  • 순서수란 정렬전순서 집합 중에 구조로서 같은 것들을 같은 수로 결부 시키는 것
  • 수학에서 매우 중요한 개념이 구조가 같다는 것. Isomorphic
    • 구조적으로 같은 성질을 갖고 있다.
  • 순서 동형 (order isomorphic)
    • 반순서 <A, ≤>과 <B, ≤*>에 대하여
      • <A, ≤> ≈ <B, ≤*> ⇔ ∃f : A → B
        • f : 전단사
        • a1 ≤ a2 ⇒ f(a1) ≤* f(a2)
      • (≈ 은 동형이라는 의미)
    • 두 반순서 집합이 순서 동형이라는 의미는 A 집합에서 B 집합으로 가는 전단사 함수가 존재하고, A에서의 a1, a2의 관계가 전단사 함수를 통해 B로 대응된 후에도 A에서의 a1, a2의 대응관계가 B에서도 동일하게 유지되어야 한다. 순서 보존
  • ≈ 는 반사율, 대칭율, 추이율이 성립
  • 순서수 (ordinal number) 공리
    1. 모든 정렬전순서 집합 <X, ≤>에 Ord<X, ≤>라는 순서수가 결부된다.
      • 모든 순서수 α에 대해 α = Ord<X, ≤>인 정렬전순서 집합이 존재
      • (Ord는 순서수, Ordinal라는 의미)
    2. <A, ≤> ≈ <B, ≤*> ⇔ Ord<A, ≤> = Ord<B, ≤*>
      • 두 정렬전순서가 동형이면 그 순서수는 같다.
    3. Ord<∅, ≤> = 0
      • 공집합에 대한 순서수는 0
    4. X ~ { 1, …, n } ⇒ Ord<X, ≤> = n
      • X가 1부터 n까지의 집합일 때 X의 순서수는 n
  • Ord<A, ≤> ≤ Ord<B, ≤*> ⇔ ∃Ord<C, ≤> : Lower Set of B, <A, ≤> ≈ <C, ≤*>
    • 순서수 A가 순서수 B보다 작다는 것은 정렬전순서 집합 A가 정렬전순서 집합 B의 Lower Set과 동형이라는 의미다.

정렬 원리

개념

  • 모든 집합은 정렬전순서가 존재한다.
  • 구조들 끼리의 비교. 아래와 같은 조건을 만족할 때 구조끼리 비교가 된다.
    • <X1, ≤1> ≤* <X2, ≤2> ⇔
      • X1 ⊆ X2
        • X1 이 X2 에 포함 (집합 관계)
      • 1 ⊆ ≤2
        • 1 이 ≤2 에 포함 (순서 관계)
      • a ∈ X1, b ∈ X2∖X1 ⇒ a ≤2 b
        • X1에 들어가는 원소가 X2에 들어가는 원소보다 ≤2 기준으로 작음
  • ∅ ∉ S인 집합족 ⇒ ∃f : S → ∪S ∀A ∈ S, f(a) ∈ A
    • 공집합이 들어 있지 않은 집합족 S에서, 집합족 S에서 집합족 S의 합집합으로 가는 함수 f에 대하여, f(a)가 A에 포함되는 함수가 존재한다. (선택 공리)
  • 정렬 원리, 선택 공리, 조른의 보조 정리, 하우스도르프 극대원리는 동치
    • p가 참이면 q가 참이고, q가 참이면 r이 참이고, r이 참이면 s가 참이고, s가 참이면 p가 참이면 p, q, r, s는 동치인 것을 이용하여 각 정리로 다른 정리를 증명.
  • 만일 p와 q가 동치인 것을 증명하려면 p일때 q인 것과 q일 때 p인 것을 증명해야 한다. 따라서 p, q, r, s가 동치임을 증명하려면 6번을 증명해야 하는데, 위와 같이 정리간 연결관계가 있는 경우, 한 방향으로만 증명을 해도 모두가 동치임이 자동으로 증명 되기 때문에 p, q, r, s가 동치임을 증명할 때 4번만 증명해도 된다.

정렬전순서 관계 – 2

개념

  • Lower Set
    • 반순서 <X, ≤>, A ⊆ X, <A, ≤> : Lower Set of <X, ≤> ⇔ ∀x ∈ X, y ∈ A, x ≤ y ⇒ x ∈ A
    • A가 X의 Lower Set이라는 것은 A가 X의 부분집합이고, A의 임의의 원소 y 이하인 X의 모든 원소는 A에 속한다는 뜻. (엄밀하진 않지만 A가 X의 가장 작은 원소를 포함하는 집합이라고 생각하면 쉽다.)
  • <X, ≤> : 정렬전순서일 때
    • Lower Set 들의 교집합, 합집합도 Lower Set
    • Lower Set 의 Lower Set도 Lower Set
    • Proper Lower Set 은 { x ∈ X | x < a } 로 표현 할 수 있다.
      • Proper면 진 이라는 뜻. 진부분집합, 진 Lower Set 등. 자기 자신은 원소로 포함하지 않는 집합
  • 표기법
    • <A, ≤>에 대하여, Aa = { x ∈ A | x < a } 로 표기.
      • 이를 initial segment라고 한다.
  • <A, ≤> 정렬전순서, 집합족 F = { X | <X, ≤> : lower set of <A, ≤> } 이고, 집합족 S ⊆ F 에 대하여
    • (집합족 F가 A의 모든 lower set을 모은 집합이고, 집합족 S는 F의 부분집합일 때)
      • Ax ∈ S ⇒ A∪ { x } ∈ S (Ax ≠ A)
        • Ax가 S의 원소일 때, Ax와 x를 합집합 한 것도 S의 원소이다. 단, Ax는 Proper Lower Set
      • T ⊆ S ⇒ ∪T ∈ S
        • 집합족 S의 부분집합들의 합집합은 S의 원소이다.
      •  위 2가지 조건을 다 만족한다면 S = F이다.
  • 초한귀납법
    • <X, ≤> 정렬전순서, P(x) : 명제 함수 일 때
    • ∀x ∈ X, P(x) ⇔ ∀x, y ∈ X (y < x), P(y) ⇒ P(x)
      • 모든 x에 대하여 P(x)가 참이 성립하면, X에 속하는 임의의 원소 x, y에 대하여 (y < x), P(y)가 참이면 P(x)가 참이다.
      • 수학적 귀납법과 달리 자연수를 넘어서 정렬전순서 집합에 대해 모두 적용 가능한 귀납법.
      • 1번째 조건과 증가 조건을 정의해야 하는 수학적 귀납법과 달리 1개의 조건으로 성립
      • 임의의 두 원소에 대하여 작은 원소에 대해 성립하면 그 다음 원소에 대해 성립한다.

정렬전순서 관계 – 1

개념

  • 전순서 <X, ≤> : 정렬 ⇔ ∀S(≠∅) ⊆ X, ∃minS
    • 전순서 집합의 공집합이 아닌 모든 부분 집합이 최소 원소를 가질 때 정렬전순서 집합이라고 부른다.
  • X : 정렬전순서가 존재 ⇔ ∃≤*, <X, ≤*> : 정렬전순서
    • 전순서가 아닌 일반 집합에 대해서도 정렬전순서가 존재하는지를 말할 수 있는데,
    • 집합 X에 어떤 순서가 있어서 그것을 정렬전순서로 만들 수 있으면 집합에 대해서도 정렬전순서가 존재한다고 말할 수 있음
  • 자연수 집합은 정렬전순서이지만, 정수, 유리수는 최소값이 없기 때문에 정수, 유리수 집합은 정렬전순서가 아니다.
    • 하지만 그 안에 정렬전순서가 존재는 한다.
  • X : 유한 or 가산 ⇒ X : 정렬전순서
    • X가 유한이나 가산 잡합이면 X는 정렬전순서가 존재한다.
  • <A, ≤> : 정렬전순서 부분 집합 of <X, ≤>이고 <B, ≤> : 정렬전순서 부분 집합 <A, ≤> ⇒ <B, ≤> : 정렬전순서 부분 집합 <X, ≤>
    • A가 X의 정렬전순서 부분집합이고 B가 A의 정렬전순서 부분집합이면, B는 X의 정렬전순서 부분집합이다.

선택공리로 증명하는 문제들

개념

  • Card A ≤ Card B ∨ Card A ≥ Card B 일 때
    • T = { (Aα, fα) | Aα ⊆ A, ∃fα : Aα → B 단사 }
  • ∀집합 A에 대하여, ∃전단사 f : A → A, f(x) ≠ x
    • 모든 집합에 대하여 자신의 집합으로 가면서, 원소와 그 값이 다른 함수가 존재한다.

하우스도르프 극대원리, 조른 보조정리

개념

  • 하우스도르프 극대원리
    • 반순서 <A, ≤>, T = { X | X ⊆ <A, ≤> 사슬 } ⇒ ∃<T, ⊆>의 극대원
    • 반순서 <A, ≤>의 사슬만 모아 놓은 집합에 대하여, <T, ⊆>의 극대원이 존재한다.
  • 조른의 보조정리
    •  반순서 <A, ≤>의 모든 사슬의 상계가 A에 있으면,  ⇒ ∃<A, ≤>의 극대원

선택 공리

개념

  • 선택 공리
    • ∅ ∉ S인 집합족 S에 대하여
    • ⇒ ∃f : S → ∪S, ∀A ∈ S, f(A) ∈ A
    • 집합족 S에서 집합족 S의 합집합으로 가는 함수 f에 대하여, S의 부분집합 A에 대하여 f(A)는 A를 만족하는 함수 f가 존재한다.
  • 선택 공리를 이용하여 아래와 같은 명제를 증명
  • ∅ ∉ T인, X의 분할 집합인 T에 대하여
    • ⇒ ∃B ⊆ X, ∀A ∈ T, | A ∩ B | = 1
    • T의 모든 부분 집합들과 교집합 할 때 원소가 1개만 존재하는 X의 부분집합 B가 존재한다.
  • f : A → B 전사 ⇒ Card A ≥ Card B
  • 관계 R : A → B, Dom R = A ⇒ ∃f : A → B, f ⊆ R
  • f : A → B 전사
    • ⇔ (f : A → B ⇒ ∃g : B → A, f ⚬ g = IdB)

고정점 정리

개념

  • 고정점 정리
    • 반순서 <A, ≤>의 모든 사슬의 최소상계가 A에 있을 때, f : A → A, f(x) ≥ x ⇒ ∃p ∈ A, f(p) = P
    • 모든 사슬이 최소상계가 존재하면, f(x) ≥ x 인 함수는 고정점을 가진다.

순서 관계 – 2

개념

  • <A, ≤> 반순서 일 때
    • ∃x : A의 최대원소 ⇔ ∃x ∈ A ∀a ∈ A, a ≤ x
      • 집합 내에 x보다 큰 원소가 없을 경우 x가 최대원소
    • ∃x : A의 극대원소 ⇔ ∃x ∈ A ∀a ∈ A, x ≤ a ⇒ x = a
      • 집합 내에 x보다 같거나 큰 원소가 있을 경우, 그 원소와 x가 같을 때 x가 극대원소
    • ∃x : A의 최소원소 ⇔ ∃x ∈ A ∀a ∈ A, x ≤ a
      • 집합 내에 x보다 작은 원소가 없을 경우 x가 최소원소
    • ∃x : A의 극소원소 ⇔ ∃x ∈ A ∀a ∈ A, a ≤ x ⇒ x = a
      • 집합 내에 x보다 같거나 작은 원소가 있을 경우, 그 원소와 x가 같을 때 x가 극소원소
  • 최대/최소 원소는 유일하다
    • x가 <A, ≤>의 최대 원소 ⇔ x = max<A, ≤>
    • x가 <A, ≤>의 최소 원소 ⇔ x = min<A, ≤>
  • 전순서 집합에서
    • 최대원소 ⇔ 극대원소
    • 최소원소 ⇔ 극소원소
  • 상계란 최대값을 찾을 수 없는 집합에서 그 상위의 집합을 이용해 최대값을 찾는 것
    • (0, 1) 집합에는 최대값이 없으므로, 그 상위 집합인 실수 집합 ℝ을 이용하여 최대값을 찾는다.
  • 상계, 최소상계, 하계, 최대하계
    • 반순서 <A, ≤>, <B, ≤> ⊆ <A, ≤> 일 때
    • ∃x : B의 상계 ⇔ ∃x ∈ A, ∀b ∈ B, b ≤ x
      • 집합 A에 속하는 원소 중 B의 모든 원소 보다 큰 원소를 상계라고 한다.
      • 단순히 상계를 위와 같이 정의하면 값이 무한히 많으므로, 그 중에 가장 작은 값인 최소 상계를 구한다.
    • ∃x : B의 최소상계 ⇔ ∃x ∈ A, ∀y : B의 상계, x ≤ y ⇔ x = sup<B, ≤>
      • B의 상계 중에서 가장 작은 상계를 최소 상계라고 한다.
    • ∃x : B의 하계 ⇔ ∃x ∈ A, ∀b ∈ B, x ≤ b
      • 집합 A에 속하는 원소 중 B의 모든 원소 보다 작은 원소를 하계라고 한다.
    • ∃x : B의 최대하계 ⇔ ∃x ∈ A, ∀y : B의 하계, y ≤ x ⇔ x = inf<B, ≤>
      • B의 하계 중에서 가장 큰 상계를 최대 상계라고 한다.
  • 집합족 S에 대하여 F ⊆ S 일 때,
    • ∪F ∈ S ⇒ ∪F : <F, ⊆> 의 상계
      • S에 속하는 F에 대하여 그 합집합이 S의 원소가 되면 F 합집합이 F의 상계가 된다.
    • ∩F ∈ S ⇒ ∩F : <F, ⊆> 의 하계
      • S에 속하는 F에 대하여 그 교집합이 S의 원소가 되면 F 교집합이 F의 하계가 된다.