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

개념

  • 하우스도르프 극대원리
    • 반순서 <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의 하계가 된다.

순서 관계 – 1

개념

  • 수학의 가장 근간을 이루는 분야인 집합과 논리에서 가장 가까운 수학 분야가 대수와 위상
  • 순서 관계란, 관계 R : A → A에 대하여
    • aRa (반사율)
    • aRb ∧ bRa ⇒ a = b (반대칭)
    • aRb ∧ bRc ⇒ aRc (추이율)
      • 위 3가지 조건을 만족하는 경우 R : 반순서
    • aRb ∨ bRa
      • 위 4가지 조건을 모두 만족하는 경우 R : 전순서
  • <A, R> : 반순서 집합
    • (A 자리에 집합, R 자리에 관계 기호를 쓰면 된다.)
  • 오해의 소지가 없다면, 반순서관계 R을 ≤로 표기
  • <A, ≤> : 반순서 일 때
    • a ≤ b ⇔ a < b ∨ a = b
    • a < b ⇒ ¬(a ≥ b)
      • 반대 방향은 성립 안 함
  • <ℝ, ≤> : 전순서 관계
  • <F, ⊆> : 반순서 관계
  • <ℕ, | > : 반순서 관계
    • | 기호는 다음과 같이 정의
    • n | m ⇔ ∃k ∈ ℕ,  m = nk
    • (n은 m의 약수, m은 n의 배수 관계라는 의미)
  • <ℝ2, ≤> : 반순서 관계
  • <ℝ, ℝ> : 반순서 관계
  • 반순서 <A, ≤>, B ⊆ A 일 때
    • <B, ≤> : <A, ≤>의 반순서 부분집합 ⇔ <B, ≤> : A의 반순서
    • <B, ≤> : <A, ≤>의 전순서 부분집합 (사슬) ⇔ <B, ≤> : A의 전순서
    • A 가 반순서 집합이고 B가 A의 부분집합일 때 B는 A의 반순서 집합이거나 A의 사슬이다.
  • 전순서 <A, ≤>, B ⊆ A 일 때 ⇒ <B, ≤> : A의 전순서 (사슬)
    • A가 전순서 집합이고 B가 A의 부분집합일 때 B는 A의 사슬이다.

기수의 지수 – 3

개념

  • Card (C1(ℝ, ℝ)) = ℵc
    • C1(ℝ, ℝ) = { 미분가능 f : ℝ → ℝ } (미분 가능한 함수들의 집합)
    • 미분 가능한 함수들의 집합은 연속인 함수들의 부분집합이다.
  • n ~ (0, 1)
    • cn = (2ℵ0)n = 2ℵ0 × n = 2ℵ0 = ℵc = Card (0, 1)
    • 유클리드 공간은 실수 집합과 대등하다.
  • ℍ = { f : ℕ → ℝ | Σi=1 f(i)2 = 수렴 } 일 때, ℍ ~ ℝ
  • 0ℵ0 = ℵc
  • 연속체 가설
    • ∃x, ℵ0 < x < ℵc 가 존재하는가?
    • 자연수 집합과 실수 집합 사이에 존재하는 무한 집합이 존재하는가?
    • 반증도 증명도 안되는 문제.
      • 괴델이 ZFC 공리계와 모순되지 않는다고 증명
      • 코헨이 ZFC 공리계로 증명불가능함을 증명

기수의 지수 – 2

개념

  • 2ℵ0 = ℵc
    • 2의 자연수집합은 실수 집합과 같다.
  • 0 < ℵc
    • 0 = Card ℕ < Card P(ℕ) = Card (2) = 2ℵ0 = ℵc
  • c × ℵc = ℵc
    • c × ℵc = 2ℵ0 × 2ℵ0 = 2ℵ0 + ℵ0 = 2ℵ0 =  ℵc (∵ ℵ0 + ℵ0 = ℵ0)
  • cℵc = 2ℵc
    • cℵc = (2ℵ0)ℵc = 2ℵ0 × ℵc = 2ℵc (∵ ℵ0 × ℵc = ℵc)
  • C(A, B) = { 연속 f : A → B }, K(A, B) = { 상수 f : A → B } 일 때,
    • C(ℝ, ℝ) ~ C(ℚ, ℝ) ~ K(ℝ, ℝ) ~ ℝ

기수식

  • (Card X × Card Y)Card Z = (Card X)Card Z × (Card Y)Card Z
    • (xy)z = xzyz와 같다.
  • Card P(X) = 2Card X
    • 임의의 집합의 멱집합의 개수는 2의 임의의 집합 원소 개수와 같다

기수의 지수 1

개념

  • BA := { f | f : A → B 함수 }
    • A에서 B로 가는 모든 함수를 모아 놓은 집합
    • 그럼 함수들의 개수가 BA개가 된다.
    • A가 3개, B가 2개의 원소를 가진 집합이라면 A에서 B로 가는 함수의 개수는 23개가 되어서 8개가 된다.
  • (Card B)Card A := Card (BA)
  • A ~ A1, B ~ B1 이면
    • Card (BA) = Card (B1A1)

기수식

  • (Card X)Card Y × (Card X)Card Z = (Card X)Card Y + Card Z
    • xyxz = xy+z 와 같다.
  • ((Card X)Card Y)Card Z = (Card X)Card Y × Card Z
    • (xy)z = xy × z 와 같다.

기수의 곱


개념

  • Card A × Card B = Card A × B
  • A ~ A1, B ~ B1 일 때, Card (A × B) = Card(A1 × B1)
  • Card X × Card Y = Card Y × Card X
    • 기수의 곱에 대하여 교환법칙이 성립
  • Card X × (Card Y × Card Z) = (Card X × Card Y) × Card Z
    • 기수의 곱에 대하여 결합법칙이 성립
  • Card Y ∩ Card Z = ∅ 일때,
    • Card X × (Card Y + Card Z) = Card X × Y + Card X × Z
    • 기수의 곱에 대하여 분배법칙이 성립
  • Card X ≤ Card Y ⇒ Card X × Card Z ≤ Card Y × Card Z
  • Card X × Card Y = 0 ⇒ Card X = 0 ∨ Card Y = 0

기수식

  • 1 × Card X = Card X
    • 기수의 곱에 대하여 항등원이 존재. 항등원은 1
  • 0 × Card X = 0
  • 0 × ℵ0 = ℵ0
    • 자연수 집합과 자연수 집합의 곱은 자연수 집합
  • c × ℵc = ℵc
    • 실수 집합과 실수 집합의 곱은 실수 집합

기수의 합

개념

  • A ~ B, A ⊆ X ⊆ B ⇒ X ~ A
    • A와 B가 대등한 조건이었으므로 X ~ B 도 성립
  • A ⊆ B ⇒ Card A ≤ Card B
  • ∃단사 f : A → B ⇔ Card A ≤ Card B
  • (칸토어 정리) Card X < Card P(X)
    • P(X)는 멱집합. X의 부분집합들을 모은 집합
  • 가장 큰 기수는 존재하지 않는다
    • Card A를 가장 큰 기수로 가정할 때, 칸토어의 정리에 따라 Card A < Card P(A)가 되어야 하므로 Card A가 가장 큰 기수가 될 수는 없음. 가정이 모순
  • Card (ℕ) = ℵ0 라고 표기. Card (ℝ) = ℵc 라고 표기.
  • Card X + Card Y = Card Y + Card X
    • 기수의 합에 대하여 교환법칙이 성립
  • Card X + (Card Y + Card Z) = (Card X + Card Y) + Card Z
    • 기수의 합에 대하여 결합법칙이 성립
  • Card X + 0 = Card X
    • 기수의 합에 대하여 항등원이 존재. 항등원은 0
  • Card X ≤ Card Y ⇒ Card X + Card Z ≤ Card Y + Card Z
    • Card X < Card Y ⇒ Card X + Card Z < Card Y + Card Z 는 성립하지 않는데, Card Z가 무한집합(ℵ0)인 경우가 반례가 된다.
    • 같은 맥락에서 Card X + Card Z = Card Y + Card Z 일 때 Card X = Card Y 도 성립하지 않는다. Card Z가 무한집합(ℵ0)인 경우

기수식

  • A ∩ B = ∅ 일때
    • Card A + Card B = Card (A ∪ B)
  • A ~ A1, B ~ B1, A ∩ B = ∅, A1 ∩ B1 = ∅ 일 때
    • Card (A ∪ B) = Card (A1 ∪ B1)
  • 0 + ℵ0 = ℵ0
    • 자연수 집합과 자연수 집합의 합은 자연수 집합
  • c + ℵc = ℵc
    • 실수 집합과 실수 집합의 합은 실수 집합
  • 0 + ℵc = ℵc
    • 자연수 집합과 실수 집합의 합은 실수 집합
  • n + ℵ0 = ℵ0
    • 자연수와 자연수 집합의 합은 자연수 집합
  • n + ℵc = ℵc
    • 자연수와 실수 집합의 합은 실수 집합