Tag Archives: 집합

데코수학/ 정수, 유리수 만들기

개념

  • 0과 자연수로 정수 만들기
    • 이전에 정의한 자연수 체계를 확장해서 정수를 정의
    • 기존 구조를 포함하고 추가로 역원을 만들면 가능
    • 자연수를 이용하여 동치류를 정의하고 동치류 사이의 연산을 정의
  • 0을 포함하는 자연수 집합을 이용하여 정수 집합을 정의
    • 0을 포함하는 자연수 집합을 다음과 같이 카테시안 형태로 정의
      • ( { 0 } ∪ ℕ ) × ( { 0 } ∪ ℕ )
        • (0, 0), (0, 1), (0, 2)… (1, 0), (2, 1)..
    • 다음과 같은 관계를 정의
      • (a, b) ~ (c, d) ⇔ a + d = b + c
      • Ex)
        • (0, 0) ~ (1, 1) ~ (2, 2) ~ (3, 3) ~…
        • (0, 1) ~ (1, 2) ~ (2, 3) ~ …
        • (1, 0) ~ (2, 1) ~ (3, 2) ~ …
      • 즉 모든 원소들은 (0, 0), (0, 1), (0, 2)…와 대등하거나 (1, 0), (2, 0), (3, 0)…과 대등한 것들로 나뉜다.
    • 위 동치류들의 집합에서 연산을 다음과 같이 정의
      • (a, b)/~ +* (c, d)/~ = (a+c, b+d)/~
        • (a, b)의 동치류들과 (c, d)의 동치류들의 덧셈은 (a+c, b+d)의 동치류들과 같다.
      • (a, b)/~ ⋅* (c, d)/~ = (ac+bd, ad+bc)/~
        • (a, b)의 동치류들과 (c, d)의 동치류들의 곱셈은 (ac+bd, ad+bc)의 동치류들과 같다.
      • 덧셈 예시
        • (2, 0)/~ +* (1, 7)/~ = (3, 7)/~ = (0, 4)/~
      • 곱셈 예시
        • (3, 2)/~ ⋅* (2, 3)/~ = (12, 13)/~ = (0, 1)/~
    • 위의 식을 다음과 같이 표기하고 이런 체계를 정수 집합으로 정의함
      • (0, 0)/~ 는 ±0이라 부른다.
      • (0, n)/~ 는 +n이라 부른다.
      • (n, 0)/~는 -n이라 부른다.
      • +*는 정수 덧셈으로 부른다.
      • ⋅*는 정수 곱셈이라 부른다.
  • 정수 구조를 이용하여 유리수 구조를 직접 구성
    • 정수를 다음과 같은 카테시안 형태로 정의
      • ℤ × (ℤ ∖ {±0})
    • 다음과 같은 관계를 정의
      • (a, b) ≈ (c, d) ⇔ a ⋅* d = b ⋅* c (이것은 동치 관계가 된다)
    • 위 동치류들의 집합에서 연산을 다음과 같이 정의 ((a, b)/≈ 는 a / b로 표기)
      • a / b +’ c / d = (ad + bc) / bd
      • a / b ⋅’ c / d = ac / bd

데코수학/ 자연수 만들기

개념

  • 페아노 공리 – 아래 구조를 만족하면 자연수 구조가 됨
    • 집합 X에 대하여
      • ∃m ∈ X
      • ∃S : X → X 함수
      • ∀x ∈ X, S(x) ≠ m
      • S(x) = S(y) ⇒ x = y (S: 단사)
      • (Y ⊆ X, m ∈ Y, ∀x ∈ Y, S(x) ∈ Y) ⇒ Y = X
    • 이때 X를 0을 포함한 자연수 집합, m을 0, S를 ‘다음 수’ 함수라고 부르면 이것이 바로 자연수 구조가 된다.
  • 논리와 집합을 이용하여 수 체계를 만들 수 있음
  • 자연수 덧셈 연산 정의
    • 페아노 공리를 만족하는 구조 X에 대하여 함수 + : X × X → X를 다음으로 정의한다.
      • a, b ∈ X
      • (b = m) ⇒ +(a, b) = a
      • (b ≠ m) ⇒ ∃c, b = S(c) ⇒ +(a, b) = S(+(a, c))
    • +(a, b) 표기는 a + b로 쓸 수 있음. 위의 내용을 아래와 같이 요약
      • a + m = a
      • a + S(b) = S(a+b)
    • 덧셈 예시
      • m + S(m) = S(m+m) = S(m)
      • S(S(S(m))) + S(m) = S(S(S(S(m))) + m) = S(S(S(S(m))))
      • S(m) + S(S(m)) = S(S(m) + S(m)) = S(S(S(m) + m)) = S(S(S(m)))
    • 위의 정의에 따른 덧셈은 교환 법칙, 결합 법칙, 항등원을 만족
      • a + b = b + a
      • a + (b + c) = (a + b) + c
      • a + m = m + a = a
  • 자연수 곱셈 연산 정의
    • 페아노 공리를 만족하는 구조에 대하여 함수 ⋅ : X × X → X를 다음으로 정의한다.
      • a, b ∈ X
      • a ⋅ m = m (⋅(a, b)를 a ⋅ b로 표기)
      • a ⋅ S(b) = a + (a ⋅ b) (⋅(a, b)를 a ⋅ b로 표기)
    • 곱셈 예시
      • S(m) ⋅ S(S(m)) = S(m) + (S(m) ⋅ S(m)) = S(m) + (S(m) + (S(m)⋅m)) = S(m) + S(m) = S(S(m) + m) = S(S(m))
    • 위의 정의에 따른 곱셈은 교환 법칙, 결합 법칙, 항등원, 분배 법칙을 만족
      • a ⋅ b = b ⋅ a
      • a ⋅ (b ⋅ c) = (a ⋅ b) ⋅ c
      • a ⋅ S(m) = a
      • a ⋅ (b + c) = a ⋅ b + a ⋅ c
  • 자연수 순서 관계 정의
    • 페아노 공리를 만족하는 구조에 대하여 관계 ≤ : X → X를 다음으로 정의한다.
      • a, b ∈ X
      • a ≤ b ⇔ ∃c, b = a + c
    • 관계 ≤ 는 정렬전순서 관계이다.
  • 동형사상
    • 페아노 공리를 만족하는 X1, X2에 대하여, φ : X1 ≈ X2인 함수가 존재한다.

데코수학/ 순서수의 폰노이만 정의

개념

  • Ord <{ x : 순서수 | x < α }, ≤순서수> = α
    • α라는 순서수 보다 작은 순서수 집합의 순서수는 α이다.
  • 모든 순서수를 모은 집합은 존재하지 않는다.
  • 순서수의 폰노이만 정의
    • 순서수를 집합 형태로 정의
    • 순서수 α := { x : 순서수 | x < α }
    • 어떤 순서수의 다음 순서수는 그 전의 순서수를 모두 모아 놓은 순서수
    • 예)
      • 순서수 0 := ∅
      • 순서수 1 := { 0 } = { ∅ }
      • 순서수 2 := { 0, 1 } = { ∅, { ∅ } }
      • 순서수 3 := { ∅,  { ∅ }, { ∅, { ∅ } } }
      • 순서수 4 := { ∅,  { ∅ }, { ∅, { ∅ } }, { ∅,  { ∅ }, { ∅, { ∅ } } } }
      • ω := { 0, 1, 2, 3, 4, … }
      • ω+1 := { 0, 1, 2, 3, 4, …, ω }
      • ω+2 := { 0, 1, 2, 3, 4, …, ω, ω+1 }
  • 집합 X의 초기순서수
    • | X | = min { x : 순서수 | x ~ X }
      • X의 초기순서수란 X와 대등한 모든 집합들 가운데 가장 작은 순서수를 의미
  • 폰노이만 순서수 정의에서 기수는 초기순서수를 의미 함.
  • 기수와 순서수 연산의 의미가 다르므로 주의
    • 기수 연산에서 ℵ0 + ℵ0 = ℵ0 이지만, 순서수 연산에서 ω + ω > ω 이다.
      • 0 ω는 같지만
  • 폰노이만 정의에서는 다음이 성립
    • α =순서수 β ⇔ α =집합 β
      • 순서수로서 동일하면 집합으로서 동일
    • α < β ⇔ α ∈ β ⇔ α ⊂ β
      • 순서수로서 작다는 것은 원소이면서 부분집합
  • 지수자리가 유한순서인 경우 αn 형태로 정의 가능
  • 지수자리가 유한이 아닌 경우 최소 원소가 존재하지 않기 때문에 정의가 까다로움

데코수학/ 순서수 곱

개념

  • <A, ≤>, <B, ≤•> 일 때 두 정렬전순서의 곱은 다음과 같이 로 정의 한다.
    • <A, ≤> × <B, ≤•> = <A × B, ≤*>
    • ≤*
      • (a, b), (c, d) ∈ A×B에 대하여
      • a ≤ c ⇒ (a, b) ≤* (c, d)
      • a = c ⇒ ((a, b) ≤* (c, d) ⇔ b ≤* d)
      • 두 정렬전순서를 카테시안으로 만들고, 앞의 원소가 빠른 것을 먼저 쓰고, 앞의 원소가 같으면 그 다음 원소가 빠른 것을 먼저 쓰는 식으로 정렬한다. (마치 사전에서 단어 정렬하는 것과 같다. ab, ac, ba 3글자는 첫번째 글자가 빠른 것, 그 다음 글자가 빠른 것으로 정렬된다)
      • 이렇게 하면 ≤* 는 정렬전순서가 된다.
  • Ord<B, ≤> ⋅ Ord<A, ≤•> = Ord<A×B, ≤*>
    • 두 순서수의 곱셈은 위와 같이 정의한다.
    • 곱셈은 순서가 중요하다. 먼저 쓴 것이 뒤에 들어가야 함.
  • Ord<A1, ≤1> = Ord<A2, ≤2>, Ord<B1, ≤•1> = Ord<B2, ≤•2> 일 때,
    • Ord<B1, ≤•1> ⋅ Ord<A1, ≤1> =  Ord<B2, ≤•2> ⋅ Ord<A2, ≤2>
  • Ord<2, ≤> ⋅ Ord<ℕ, ≤> = Ord<ℕ, ≤> (Ord<2, ≤>는 두 원소 집합)
    • 순서수와 자연수 순서수를 곱하면 자연수 순서수와 같다.
  • Ord<ℕ, ≤> ⋅ Ord<2, ≤> > Ord<ℕ, ≤> (Ord<2, ≤>는 두 원소 집합)
    • 자연수 순서수와 순서수를 곱하면 자연수 순서수 보다 크다.
  • 순서수 곱에는 곱하는 순서가 중요하다. 뒤에 곱해지는 것이 카테시안에서 앞에 나오기 때문.
    • Ord<2, ≤> ⋅ Ord<ℕ, ≤> < Ord<ℕ, ≤> ⋅ Ord<2, ≤>
    • 고로 순서수 곱에는 교환법칙이 성립하지 않는다.
    • 하지만 결합법칙은 성립한다.
      • (Ord A ⋅ Ord B) ⋅ Ord C = Ord A ⋅ (Ord B ⋅ Ord C)
  • Ord<n, ≤> ⋅ Ord<ℕ, ≤> = Ord<ℕ, ≤> (Ord<n, ≤>는 유한 순서수)
    • 유한 순서수와 자연수 순서수의 곱은 자연수 순서수와 같다.

순서수식

  • Ord A ⋅ Ord 1 = Ord A = Ord 1 ⋅ Ord A (Ord 1은 한 원소 집합)
    • 순서수 곱에는 항등원이 존재한다.
  • Ord A ⋅ ∅ = ∅ = ∅ ⋅ Ord A
    • 순서수와 공집합의 곱은 공집합이다.
  • Ord A ⋅ (Ord B + Ord C) = (Ord A ⋅ Ord B) + (Ord A ⋅ Ord C)
    • 순서수에는 분배법칙이 성립한다. (왼쪽에 곱할 경우만)
    • (Ord B + Ord C) ⋅ Ord A ≠ (Ord B ⋅ Ord A) + (Ord C ⋅ Ord A)
  • Ord A = Ord B ⇔ Ord C ⋅ Ord A = Ord C ⋅ Ord B (Ord C ≠ ∅)
  • Ord A < Ord B ⇔ Ord C ⋅ Ord A < Ord C ⋅ Ord B (Ord C ≠ ∅)
  • Ord A = Ord B ⇒ Ord A ⋅ Ord C = Ord B ⋅ Ord C (Ord C ≠ ∅)
    • 반대방향은 성립하지 않음
  • Ord A ⋅ Ord C < Ord B ⋅ Ord C ⇒ Ord A < Ord B (Ord C ≠ ∅)
    • 반대방향은 성립하지 않음
  • Ord A ⋅ Ord B = ∅ ⇔ Ord A = ∅ or Ord B = ∅
    • 두 순서수의 곱이 공집합이면 두 순서수 중 하나는 공집합

데코수학/ 순서수 합 – 2


개념

  • 모든 순서수는 바로 다음 순서수를 갖는다.

순서수식

  • (Ord A + Ord B) + Ord C = Ord A + (Ord B + Ord C)
    • 순서수에 대하여 결합법칙은 성립한다.
  • Ord A + ∅ = Ord A = ∅ + Ord A
    • 순서수 덧셈에 대한 항등원이 존재한다.
    • 순서수 덧셈에 대한 역원은 존재하지 않는다.
  • Ord B < Ord C ⇔ Ord A + Ord B < Ord A + Ord C
  • Ord B = Ord C ⇔ Ord A + Ord B = Ord A + Ord C
    • 왼쪽 소거법. 역원이 없기 때문에 두 식을 비교할 때 중요.
  • Ord B + Ord A < Ord C + Ord A ⇒ Ord B < Ord C
    • 오른쪽에 같은 것을 제거한 경우는 같지만 그 반대는 성립 안 함
  • Ord B = Ord C ⇒ Ord B + Ord A = Ord C + Ord A
    • 오른쪽에 같은 것을 더한 경우는 성립하지만 그 반대는 성립 안 함

데코수학/ 순서수 합 – 1

개념

  • 정렬전순서 <A, ≤>, <B, ≤> : proper lower set of <A, ≤> ⇒ <A, ≤> ≉ <B, ≤>
    • 정렬전순서 <A, ≤>와 그 proper lower set <B, ≤>는 순서 동형이 아니다.
  • Ord<A, ≤> < Ord<B, ≤•> ⇔ <A, ≤> ≈ <B0, ≤•> (<B0, ≤•> : proper lower set of <B, ≤•>)
    • 순서수 <A, ≤>가 순서수 <B, ≤•> 보다 작다면 정렬전순서 <A, ≤>는 정렬전순서 <B, ≤•>의 proper lower set과 동형이다.
  • 무한 정렬전순서 집합의 순서들 중에서 가장 작은 순서수가 존재하지 않는다.
    • 위의 조건에 맞는 순서수는 유한집합이 되기 때문에 위 조건에 맞는 존재하지 않음.
    • Ord<ℕ, ≤대소>가 초한순서수 중 가장 작은 집합
  • Ord A < Ord B, Ord B < Ord C ⇒ Ord A < Ord C
  • Ord<A, ≤> + Ord<B, ≤•> = Ord<A∪B, ≤*>
    • 두 순서수의 합은 A, B의 합집합과 ≤*로 이루어진 순서수로 만든다.
    • A∩B = ∅ 일 때 ≤*의 정의는
      • a ∈ A, b ∈ B ⇒ a ≤* b
        • a가 A에 속하고 b가 B에 속하면 ≤*를 따른다.
      • a, b ∈ A ⇒ (a ≤* b ⇔ a ≤ b)
        • a와 b가 모두 A에 속하면 ≤를 따른다.
      • a, b ∈ B ⇒ (a ≤* b ⇔ a ≤• b)
        • a와 b가 모두 A에 속하면 ≤•를 따른다.
    • A와 B가 서로소가 아니면 그 둘을 카테시안으로 만들어서 서로소로 만든다.
  • 자연수에 대한 순서수 Ord<ℕ, ≤*>에서 관계를 다음과 같이 정의할 때
    • ≤*
      • n ≤* m ⇔ n < m (n ≠ 3)
      • m ≤* 3 (n = 3)
      • (모든 자연수에 대하여 3보다 작은 관계)
    • Ord<ℕ, ≤*> = Ord<ℕ, ≤> + 1
      • Ord<ℕ, ≤*>은 자연수에 대한 순서수 보다 1만큼 더 크다.
  • Ord<A1, ≤> = Ord<A2, ≤*>, Ord<B1, ≤> = Ord<B2, ≤*> (A1∩A2=∅, B1∩B2=∅) ⇒ Ord<A1, ≤> + Ord<B1, ≤> = Ord<A2, ≤*> + Ord<B2, ≤*>
    • 순서수 Ord<A1, ≤>과 Ord<A2, ≤*>가 같고, Ord<B1, ≤>과 Ord<B2, ≤*> 같으면 Ord<A1, ≤>과 Ord<B1, ≤>의 합과 Ord<A2, ≤*>과 Ord<B2, ≤*>의 합은 같다. (단, A1과 A2, B1과 B2 는 서로소)
  • 순서수 덧셈에 대하여는 교환법칙이 성립하지 않는다.
    • Ord A + Ord B ≠ Ord B + Ord A
    • 1 + ℕ = ℕ < ℕ + 1
      • 1 + 자연수 순서수는 자연수 순서수와 같지만 자연수 순서수 + 1은 자연수 순서수보다 크다.

데코수학/ 순서수

개념

  • 기수란 집합의 전단사 함수 성질을 나타냄
    • 집합 내의 대등한 것들을 같은 수로 결부시키는 것
  • 순서수란 정렬전순서 집합 중에 구조로서 같은 것들을 같은 수로 결부 시키는 것
  • 수학에서 매우 중요한 개념이 구조가 같다는 것. 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개의 조건으로 성립
      • 임의의 두 원소에 대하여 작은 원소에 대해 성립하면 그 다음 원소에 대해 성립한다.