Search
Duplicate

이상엽/ 집합론/ 집합의 순서

부분순서집합

정의

부분순서관계

반사적, 반대칭적, 추이적인 관계
•
ex 1) 두 집합 A,BA, B 에 대하여 A⊆BA \subseteq B
•
ex 2) 두 실수 x,yx, y 에 대하여 x≤yx \leq y
•
ex 3) 두 자연수 n,mn, m 에 대하여 nn이 mm의 배수인 관계

부분순서집합

집합 AA 상에 부분순서관계 ≤\leq 가 주어진 경우 AA를 부분순서집합이라 하고 이를 (A,≤)(A, \leq) 로 나타내기도 한다.
•
집합 AA에 ≤\leq 관계가 부여 됐을 뿐이지, 집합 AA의 모든 원소들이 순서 관계를 가져야 하는 것은 아니다.
•
ex) A={∅,{1},{2},{1,2}}A = \{ \emptyset, \{ 1 \}, \{ 2 \}, \{ 1, 2 \} \} 일 때,
◦
다음의 관계는 성립하지만
▪
∅→{1}\emptyset \to \{ 1 \}
▪
∅→{2}\emptyset \to \{ 2 \}
▪
∅→{1,2}\emptyset \to \{ 1, 2 \}
▪
{1}→{1,2}\{ 1 \} \to \{ 1, 2 \}
▪
{2}→{1,2}\{ 2 \} \to \{ 1, 2 \}
◦
다음의 관계는 성립하지 않는다.
▪
{1}→{2}\{ 1 \} \to \{ 2 \}
▪
{2}→{1}\{ 2 \} \to \{ 1 \}
◦
즉 모든 원소들이 부분순서 관계를 갖지는 않는다는 것.

극대원소와 극소원소

AA가 부분순서집합이라 할 때,
•
∀x∈A,x≥a⇒x=a\forall x \in A, x \geq a \Rightarrow x = a를 만족하는 AA의 원소 aa를 극대원소,
•
∀x∈A,x≤b⇒x=b\forall x \in A, x \leq b \Rightarrow x = b 를 만족하는 AA의 원소 bb를 극소원소라 한다.
•
ex) 멱집합 P(X)P(X) 에서 ∅,X\emptyset, X
•
극대, 극소 원소는 유일하지 않다. 극대, 극소는 최대, 최소와는 다르다.
•
ex) 집합 A={a,b,c,d,e}A = \{ a, b, c, d, e \} 의 관계가 다음과 같다면
◦
a→ca \to c
◦
b→cb \to c
◦
b→db \to d
◦
d→ed \to e
◦
c, e는 극대원소가 되고
◦
a, b는 극소원소가 된다.

최대원소와 최소원소

AA가 부분순서집합이라 할 때,
•
∀x∈A,x≤a\forall x \in A, x \leq a 를 만족하는 AA의 원소 aa를 최대원소,
•
∀x∈A,x≥b\forall x \in A, x \geq b 를 만족하는 AA의 원소 bb를 최소원소라 한다.
•
극대, 극소와 달리 최대, 최소는 유일하다.

상한과 하한

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

상계와 하계

BB가 부분순서집합 AA의 부분집합이라 할 때,
•
∀x∈B,x≤a\forall x \in B, x \leq a 인 a∈Aa \in A를 AA에서 BB의 상계,
•
∀x∈B,x≥b\forall x \in B, x \geq b 인 b∈Ab \in A를 AA에서 BB의 하계라 한다.
•
상계-하계는 항상 존재하지 않음.

상한과 하한

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

절편과 절단

절편

부분순서집합 AA의 원소 aa에 대하여
•
Sa={x∈A∣x<a}S_{a} = \{ x \in A | x < a \}
◦
집합 아래에 표시된 숫자보다 작은 숫자들을 모은 집합이라고 생각하면 된다.
•
ex 1) R\mathbb{R}의 절편 S0=(−∞,0)S_{0} = (- \infty, 0)
•
ex 2) N\mathbb{N}의 절편 S3={1,2}S_{3} = \{ 1, 2 \}

절단

1.
B∩C=∅,B∪C=AB \cap C = \emptyset, B \cup C = A
2.
x∈B∧y≤x⇒y∈Bx \in B \wedge y \leq x \Rightarrow y \in B
3.
x∈C∧x≤y⇒y∈Cx \in C \wedge x \leq y \Rightarrow y \in C
를 만족하는 부분순서집합 AA의 공집합이 아닌 부분집합들의 쌍 AA$latex (B, C) &s=2$
•
ex) R\mathbb{R}의 두 부분집합 M=(−∞,0),N=[0,∞)M = (- \infty, 0), N = [0, \infty) 에 대하여 (M,N)(M, N)
•
일종의 분할과 비슷하다.

순서동형

순서보존함수

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

순서동형

부분순서집합 A,BA, B에 대하여
•
함수 f:A→Bf : A \to B 가 전단사이고 ∀x,y∈A,x≤y⇒f(x)≤f(y)\forall x, y \in A, x \leq y \Rightarrow f(x) \leq f(y) 이면 ff를 순서동형사상이라 한다.
•
이때 A,BA, B는 순서동형이라 하고 A≃BA \simeq B로 나타낸다.
•
ex) 항등함수 IA:A→AI_{A} : A \to A

전순서집합

전순서집합

비교가능

부분순서집합 AA의 두 원소 x,yx, y가 x≤y∨y≤xx \leq y \vee y \leq x이면 x,yx, y는 비교가능하다고 한다.
•
ex) 집합 A={a,b,c,d}A = \{ a, b, c, d \}의 관계가 다음과 같을 때
◦
a→ca \to c
◦
b→cb \to c
◦
c→dc \to d
◦
다른 원소들 간에는 비교가 가능하지만 a와 b는 비교가 불가능하다.

전순서집합

부분순서집합 AA의 임의의 두 원소가 비교가능하면 AA를 전순서집합이라고 한다.
•
집합 내의 모든 원소가 비교 가능한 상태이면 전순서집합이 된다.

쇄

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

정렬집합

부분순서집합 AA의 공집합이 아닌 모든 부분집합 BB가 최소원소를 가지면, 그리고 그 때에만 집합  AA를 정렬집합이라 한다.
•
ex)
◦
((0,1),≤)((0, 1), \leq)는 전순서집합이긴 하지만, 최소 원소를 갖고 있지 않기 때문에 정렬집합은 아니다.
◦
(N,≤)(\mathbb{N}, \leq)는 전순서집합이기도 하고 정렬집합이기도 하다.
•
따라서 정렬집합이면 전순서집합이다. 그 역은 성립하지 않는다.

서수

서수의 개념

서수

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

유한서수와 초한서수

유한서수란 유한정렬집합의 기수이고, 초한서수란 무한정렬집합의 서수이다.
•
<대표적인 초한서수>
◦
ω=o(N)\omega = o(\mathbb{N})

서수의 순서

정렬집합 A,BA, B에 대하여 o(A)=α,o(B)=βo(A) = \alpha, o(B) = \beta 일 때,
•
AA가 BB의 절편과 순서동형이면 α\alpha는 β\beta 보다 작거나 같다고 하며 α⩽β\alpha \leqslant \beta 로 나타낸다.
•
이때 특히 α≠β\alpha \neq \beta 이면 α<β\alpha < \beta 로 나타낸다.

서수의 연산

서수 합

서로소인 두 집합 A,BA, B의 서수를 각각 α,β\alpha, \beta 라고 할 때 α+β=o(A∪B)\alpha + \beta = o(A \cup B)
•
ex) A={1},B={a,b}A = \{ 1 \}, B = \{ a, b \} 라면
◦
BB 를 B1={2,3}B_{1} = \{ 2, 3 \} 로 변환한 후에
◦
그 둘을 합하여 A∪B={1,2,3}A \cup B = \{ 1, 2, 3 \} 을 만든다.

서수 곱

서로소인 두 집합 A,BA, B 의 서수를 각각 α,β\alpha, \beta 라고 할 때 αβ=o(B×A)\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⋅(ω+1)=2⋅ω+22 \cdot (\omega + 1) = 2 \cdot \omega + 2
▪
(ω+1)⋅2≠ω⋅2+2(\omega + 1) \cdot 2 \neq \omega \cdot 2 + 2
•
일반적으로 서수는 합과 곱에 대하여 교환법칙이 성립하지 않는다.
◦
1+ω≠ω+11 + \omega \neq \omega + 1
◦
2⋅ω≠ω⋅22 \cdot \omega \neq \omega \cdot 2
Made with