Tag Archives: 수학

배우기

순서수 비교

BY suyeongpark

개념

• 정렬전순서 <A, ≤> 위에 순서동형함수는 IdA 뿐이다.

배우기

순서수

BY suyeongpark

개념

• 기수란 집합의 전단사 함수 성질을 나타냄
  • 집합 내의 대등한 것들을 같은 수로 결부시키는 것
• 순서수란 정렬전순서 집합 중에 구조로서 같은 것들을 같은 수로 결부 시키는 것
• 수학에서 매우 중요한 개념이 구조가 같다는 것. 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과 동형이라는 의미다.

배우기

정렬 원리

BY suyeongpark

개념

• 모든 집합은 정렬전순서가 존재한다.
• 구조들 끼리의 비교. 아래와 같은 조건을 만족할 때 구조끼리 비교가 된다.
  • <X₁, ≤₁> ≤* <X₂, ≤₂> ⇔
    • X₁ ⊆ X₂
      • X₁ 이 X₂ 에 포함 (집합 관계)
    • ≤₁ ⊆ ≤₂
      • ≤₁ 이 ≤₂ 에 포함 (순서 관계)
    • a ∈ X₁, b ∈ X₂∖X₁ ⇒ a ≤₂ b
      • X₁에 들어가는 원소가 X₂에 들어가는 원소보다 ≤₂ 기준으로 작음
• ∅ ∉ 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

BY suyeongpark

개념

• 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, ≤>에 대하여, A_a = { x ∈ A | x < a } 로 표기.
    • 이를 initial segment라고 한다.
• <A, ≤> 정렬전순서, 집합족 F = { X | <X, ≤> : lower set of <A, ≤> } 이고, 집합족 S ⊆ F 에 대하여
  • (집합족 F가 A의 모든 lower set을 모은 집합이고, 집합족 S는 F의 부분집합일 때)
    • A_x ∈ S ⇒ A_x  ∪ { x } ∈ S (A_x ≠ A)
      • A_x가 S의 원소일 때, A_x와 x를 합집합 한 것도 S의 원소이다. 단, A_x는 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

BY suyeongpark

개념

• 전순서 <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의 정렬전순서 부분집합이다.

배우기

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

BY suyeongpark

개념

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

배우기

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

BY suyeongpark

개념

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

배우기

선택 공리

BY suyeongpark

개념

• 선택 공리
  • ∅ ∉ 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 = Id_B)

배우기

고정점 정리

BY suyeongpark

개념

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

배우기

순서 관계 – 2

BY suyeongpark

개념

• <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의 하계가 된다.