Order - 편집 역사

Ahn9807: /* Complete partial order */

2023-11-08T07:01:38Z

Complete partial order

← 이전 판		2023년 11월 8일 (수) 07:01 판
41번째 줄:		41번째 줄:

	Lemma: 만약 poset이 CPO면 poset은 least element를 가지며, 만약 공집합이 least element을 가지고 있다면, CPO의 least element는 공집합의 least element와 같다.		Lemma: 만약 poset이 CPO면 poset은 least element를 가지며, 만약 공집합이 least element을 가지고 있다면, CPO의 least element는 공집합의 least element와 같다.
			예를 들어서, N을 100 이하의 자연수의 집합으로 정의하고 <를 보통의 비교 연산자로 정의하자. 이 집합 N은 CPO인데, 왜냐하면 모든 N의 부분 집합 X는 least upper bound를 가지고 있기 때문이다. 예를 들어서 {2, 4, 6}은 6을 Least upper bound를 가지고 있다. 제시된 Lemma는 공집합이 되며, 공집합의 Least element는 반드시 모든 자연수 집합의 부분집합의 least element이기 때문에 이 CPO는 또한 반드시 Lemma를 만족시킨다. 그러나 N을 자연수의 집합으로 간주하면 CPO가 아닌데, 짝수의 집합은 N의 부분집합으로 Partial order이지만, Upper bound가 없기 때문에, 집합 N은 CPO가 이경우 아니다.

	=== Continuous Function ===		=== Continuous Function ===

2023년 11월 8일 (수) 06:19에 Ahn9807님의 편집

2023-11-08T06:19:07Z

← 이전 판		2023년 11월 8일 (수) 06:19 판
17번째 줄:		17번째 줄:

	== Partial Order ==		== Partial Order ==
	~~어떤것이~~ 순서를 ~~정의하는 가~~.		어떻게 순서를 정의할 것인가.
	Partial Order에서는 약한 부분 순서(weak partial order)와, 강한 부분 순서(strict partial order)가 있다. 둘다 Anti-Symmetric과 Transitive를 만족하지만, Reflexive의 정의에서 다른데, 약한 부분 순서는 반사(Reflexive)를 허용하지만 강한 부분 순서는 비반사(Anti-Reflexive)를 허용한다. 즉 부분 순서 집합은		Partial Order에서는 약한 부분 순서(weak partial order)와, 강한 부분 순서(strict partial order)가 있다. 둘다 Anti-Symmetric과 Transitive를 만족하지만, Reflexive의 정의에서 다른데, 약한 부분 순서는 반사(Reflexive)를 허용하지만 강한 부분 순서는 비반사(Anti-Reflexive)를 허용한다. 즉 부분 순서 집합은 (Anti)Relexive, Anti-Symmetric, 그리고 Transitive를 만족하는 집합이다.

			=== Poset ===
			집합 D가 Partial order이면 partial order set (D, <)라고 하거나 단순히 poset이라고 한다.

			=== Least Upper Bound ===
			Partial order set D 그리고 D의 부분집합 X에 대해서, 만약 d <math>\in</math>가 모든 X의 원소 x에 대해서 x < d이면 d를 upperbound라고 하며, Least upper bound는 모든 Upper bound중에서 제일 작은 원소를 말한다. 즉 자연수의 집합 [1, 10]에서 Upper bound는 11, 12 ...가 될 수 있지만, Least upper bound는 11하나 뿐이다.

	== Total Order ==		== Total Order ==
25번째 줄:		31번째 줄:
	예를 들어서 {0, 1}의 subset인 공집합, {0}, {1}, 그리고 {0, 1}을 생각 해보자. Order을 원소의 개수라고 작은 순서라고 해보자.		예를 들어서 {0, 1}의 subset인 공집합, {0}, {1}, 그리고 {0, 1}을 생각 해보자. Order을 원소의 개수라고 작은 순서라고 해보자.
	공집합 < {0} 그리고 {1} < {0, 1}처럼 <라는 명령어를 정의할 수 있다. 이 명령어 "<"는 Partial Order이지만 Total Order는 아닌데, 이는 {0} < {1}이 정의되지 않기 때문이다.		공집합 < {0} 그리고 {1} < {0, 1}처럼 <라는 명령어를 정의할 수 있다. 이 명령어 "<"는 Partial Order이지만 Total Order는 아닌데, 이는 {0} < {1}이 정의되지 않기 때문이다.

			=== Chain ===
			Partial ordered set D에 대해서 D의 부분집합 X가 Total order set이면 X를 Chain이라고 한다.

			예를 들어서 0->1->2->3->4->5 ...인 0을 포함한 양의 정수 집합이 있다고 하자. 이떄 (0) (0,1) (0,1,3)과 같은 집합들은 이 poset의 chain이다.

			=== Complete partial order ===
			poset D에 대해서 D의 모든 chain X가 least upper bound를 가지고 있으면 D를 Complete partial order집합이라고 한다.

			Lemma: 만약 poset이 CPO면 poset은 least element를 가지며, 만약 공집합이 least element을 가지고 있다면, CPO의 least element는 공집합의 least element와 같다.

			=== Continuous Function ===
			연속 함수에 대한 많은 정의가 있을 수 있지만, Partial order로도 Continouous를 정의할 수 있다. 두 poset D1 D2에 대해서 F: D1 -> D2가 모든 체인들에 대해서 least upper bound가 보존되면 이 함수를 연속이다 라고 한다.

	== 참고 ==		== 참고 ==
	# https://math.stackexchange.com/questions/367583/example-of-partial-order-thats-not-a-total-order-and-why		# https://math.stackexchange.com/questions/367583/example-of-partial-order-thats-not-a-total-order-and-why

Ahn9807: 새 문서: 분류: 프로그래밍 언어 == 개요 == 순서쌍 (a,b)에 대해서 관계를 정의하고, 그 관계를 통해서 나온 == 관계 == 집합 $X$ 위의 이항 관계 $\le$ 가 다음 관계가 있다. * Reflexive: 임의의 $x\in X$ 에 대하여, $x\le x$ * Anit-Reflexive: 임의의 $x\in X$ 에 대하여, $x\not< x$ * Transitive: 임의의 $x,y,z\in X$ 에 대하여, $x\le y\le z$
2023-11-08T04:26:51Z

새 문서: 분류: 프로그래밍 언어 == 개요 == 순서쌍 (a,b)에 대해서 관계를 정의하고, 그 관계를 통해서 나온 == 관계 == 집합 <math>X</math> 위의 이항 관계 <math>\le</math>가 다음 관계가 있다. * Reflexive: 임의의 <math>x\in X</math>에 대하여, <math>x\le x</math> * Anit-Reflexive: 임의의 <math>x\in X</math>에 대하여, <math>x\not< x</math> * Transitive: 임의의 <math>x,y,z\in X</math>에 대하여, <math>x\le y\le z</m...

새 문서
[[분류: 프로그래밍 언어]]

== 개요 ==
순서쌍 (a,b)에 대해서 관계를 정의하고, 그 관계를 통해서 나온

== 관계 ==
집합 <math>X</math> 위의 [[이항 관계]] <math>\le</math>가 다음 관계가 있다.
* Reflexive: 임의의 <math>x\in X</math>에 대하여, <math>x\le x</math>
* Anit-Reflexive: 임의의 <math>x\in X</math>에 대하여, <math>x\not< x</math>
* Transitive: 임의의 <math>x,y,z\in X</math>에 대하여, <math>x\le y\le z</math>라면 <math>x\le z</math>
* Symmetric: 임의의 <math>x,y\in X</math>에 대하여, <math>x\le y</math>라면 <math>y\le x</math>
* Anti-Symmetric: 임의의 <math>x,y\in X</math>에 대하여, <math>x\le y\le x</math>라면 <math>x=y</math>

== Equivalence (동치) ==
어떤것이 같다고 정의하는 가.
동치에서는 Reflexive, Trasitive, 그리고 Sysmmetric이 성립된다. 예를 들어서 a==b mod(10)관계는 동치이다. 이 경우 Anti-Symmetric은 만족하지 못한다. 예) mod 12 <= mod 22 <= mod 12 이지만, 12 == 22가 아니다.

== Partial Order ==
어떤것이 순서를 정의하는 가.
Partial Order에서는 약한 부분 순서(weak partial order)와, 강한 부분 순서(strict partial order)가 있다. 둘다 Anti-Symmetric과 Transitive를 만족하지만, Reflexive의 정의에서 다른데, 약한 부분 순서는 반사(Reflexive)를 허용하지만 강한 부분 순서는 비반사(Anti-Reflexive)를 허용한다. 즉 부분 순서 집합은

== Total Order ==
Total order는 Partial order에 모든 원소는 서로 비교 가능하다는 조건인 Connectivity가 추가된 Order를 의미한다.

예를 들어서 {0, 1}의 subset인 공집합, {0}, {1}, 그리고 {0, 1}을 생각 해보자. Order을 원소의 개수라고 작은 순서라고 해보자.
공집합 < {0} 그리고 {1} < {0, 1}처럼 <라는 명령어를 정의할 수 있다. 이 명령어 "<"는 Partial Order이지만 Total Order는 아닌데, 이는 {0} < {1}이 정의되지 않기 때문이다.

== 참고 ==
# https://math.stackexchange.com/questions/367583/example-of-partial-order-thats-not-a-total-order-and-why