(번역) Greatest element and least element

Original article: w:Greatest element and least element

 

수학(mathematic), 특히 순서 이론(order theory)에서, 부분적으로 순서화된 집합(partially ordered set, 포셋(poset))의 부분집합 $S$의 최대 원소(greatest element)는 $S$의 모든 각 다른 원소보다 큰 $S$의 원소입니다. 용어 최소 원소(least element)는 이중적(dually)으로 정의됩니다. 즉, 그것은 $S$의 모든 각 다른 원소보다 작은 $S.$의 원소입니다.

Definitions

$(P,\le )$를 준순서화된 집합(preordered set)이라고 놓고 $S\subseteq P$라고 놓습니다. 원소 $g\in P$는 만약 $g\in S$이고 다음을 만족시키면 $S$의 최대 원소(greatest element of $S$)라고 말합니다: 

$s\le g$ for all $s\in S.$

위의 정의에서 $\le$ 대신 $\ge$를 사용함으로써, $S$의 최소 원소의 정의가 얻어집니다. 명시적으로, 원소 $l\in P$는 만약 $l\in S$이고 그것이 다음을 만족시키면  $S$의 최소 원소(least element of $S$)라고 말합니다: 

$l\le s$ for all $s\in S.$

만약 $(P,\le )$는 심지어 부분적으로 순서화된 집합(partially ordered set)이면, $S$는 많아야 하나의 최대 원소를 가질 수 있고 많아야 하나의 최소 원소를 가질 수 있습니다. $S$의 최대 원소가 존재하고 고유할 때마다, 이 원소는 $S$의 그 최대 원소라고 불립니다. 용어 $S$의 그 최소 원소는 유사하게 정의됩니다. 

만약 $(P,\le )$가 최대 원소 (각각, 최소 원소)를 가지면 이 원소는 $(P,\le )$의 꼭대기(top) (각각, 밑바닥(bottom))이라고도 불립니다. 

Relationship to upper/lower bounds

심지어 부분적으로 순서화된 집합(partially ordered set)이면

$(P,\le )$를 준순서화된 집합(preordered set)이라고 놓고 $S\subseteq P$라고 놓습니다. $(P,\le )$에서 $S$의 위쪽 경계(upper bounds)는 $u\in P$이고 모든 $s\in S$에 대해 $s\le u$임을 만족하는 원소 $u$입니다. 중요하게, $P$에서 $S$의 위쪽 경계는 $S$의 원소일 필요는 없다는 것입니다.

만약 $g\in P$이면 $g$가 $S$의 최대 원소인 것과 $g$가$(P,\le )$에서 $S$의 위쪽 경계이고 $g\in S$인 것은 필요충분 조건입니다. 특히, $S$의 임의의 최대 원소는 ($P$에서) $S$의 위쪽 경계이기도 하지만 $P$에서 $S$의 위쪽 경계는 $S$의 최대 원소인 것과 그것이 $S$에 속하는 것은 필요충분 조건입니다. $P=S$인 특별한 경우에서, "$u$는 $S$에서 $S$의 위쪽 경계이다"라는 정의는 다음과 같이 됩니다: $u$는 $u\in S$이고 모든 $s\in S$에 대해 $s\in S,$임을 만족하는 원소이며, 이는 이전에 주어진 최대 원소의 정의와 완전하게 동일합니다. 따라서 $g$가 $S$의 최대 원소인 것과 $g$가 $S$에서 $S$의 위쪽 경계인 것은 필요충분 조건입니다. 

만약 $u$가 $S$에서' $S$의 위쪽 경계가 아닌 $P$에서 $S$의 위쪽 경계이면 (이것이 발생하는 것과 $u\notin S$인 것은 필요충분 조건), $u$는 $S$의 최대 원소가 될 수 없습니다 (어쨌든, 어떤 다른 원소가 $S$의 최대 원소일 가능성이 있습니다). 특히, $S$가 동시에 최대 원소를 가지지 않고 $P$에서 $S$의 위쪽 경계가 존재하는 것이 가능합니다. 

심지어 집합이 일부 위쪽 경계를 가지더라도, 음의 실수의 예제에서 볼 수 있듯이 최대 원소를 가질 필요는 없습니다. 이 예제는 역시 최소 위쪽 경계 (이 경우 숫자 0)의 존재가 최대 원소의 존재를 의미하지 않는다는 것을 보여줍니다.

Contrast to maximal elements and local/absolute maximums

준순서화된 집합의 부분집합의 최대 원소는 집합에서 임의의 다른 원소보다 엄격하게 작지 않은 원소인 집합의 최대한의 원소(maximal element)와 혼동해서는 안 됩니다.

$(P,\le )$를 준순서화된 집합(preordered set)이라고 놓고 $S\subseteq P$라고 놓습니다. 원소 $m\in S$은 만약 다음 조건이 만족되면 $S$의 최대한의 원소(maximal element of $S$)라고 말합니다: 

• $s\in S$가 $m\le s$를 만족시킬 때마다, 반드시 $s\le m$이다.

만약 $(P,\le )$가 부분적으로 순서화된 집합(partially ordered set)이면, $m\in S$은 $S$의 최대한의 원소인 것과 $m\le s$이고 $s\ne m$임을 만족하는 임의의 $s\in S$가 존재하지 않는 것은 필요충분 조건입니다. $(P,\le )$의 최대한의 원소(maximal element of $(P,\le )$)는 부분집합 $S:=P$의 최대한의 원소를 의미하는 것으로 정의됩니다.

집합은 최대 원소 없이 여러 개의 최대한의 원소를 가질 수 있습니다. 위쪽 경계 및 최대한의 원소와 마찬가지로, 최대 원소가 존재하지 않을 수 있습니다. 

전체적으로 순서화된 집합(totally ordered set)에서, 최대한의 원소와 최대 원소는 일치합니다; 그리고 그것은 역시 최댓값(maximum)이라고도 불립니다; 함수 값의 경우에서, 그것은 역시 지역적 최댓값(local maximum)과의 혼동을 피하기 위해 절대 최댓값(absolute maximum)이라고도 불립니다. 이중 용어는 최솟값(minimum)과 절대 최솟값(absolute minimum)입니다. 함께 그것들은 절대 극단값(absolute extrema)이라고 불립니다. 유사한 결론이 최소 원소에 대해 유지됩니다.

 

Role of (in)comparability in distinguishing greatest vs. maximal elements

준순서화된 집합 $(P,\le )$의 최대 원소 $g$와 최대한의 원소 $m$ 사이의 가장 중요한 차이점 중 하나는 비교할 수 있는 원소와 관련이 있습니다. 두 원소 $x,y\in P$는 $x\le y$ 또는 $y\le x$이면 비교-가능(comparable)이라고  말합니다; 그것들은 만약 비교-가능이 아니면 비-비교가능(incomparable)이라고 불립니다. 준순서가 반사적(reflexive)이기 때문에 (이는 $x\le x$가 모든 원소 $x$에 대해 참임을 의미함), 모든 각 원소 $x$는 항상 자신과 비교-가능입니다. 결과적으로, 비-비교가능이 될 수 있는 유일한 원소의 쌍은 구별되는(distinct) 쌍입니다. 일반적으로, 어쨌든, 준순서화된 집합 (및 심지어 방향화된 부분적으로 순서화된 집합)은 비-비교가능인 원소를 가질 수 있습니다.

정의에 의해, 원소 $g\in P$는 만약 모든 각 $s\in P$에 대해 $s\le g$이면 $(P,\le )$의 최대 원소입니다; 따라서 그 정의에 따라, $(P,\le )$의 최대 원소는, 특히, $P$에서 ''모든 각'' 원소와 비교-가능이 되어야 합니다. 이것은 최대한의 원소에 요구되지 않습니다. $(P,\le )$의 최대한의 원소는 $P$에서 모든 각 원소와 비교-가능이 됨을 요구하지 ''않습니다''. 이것은 "최대 원소"의 정의와 달리, "최대한의 원소"의 정의는 중요한 ''if'' 문을 포함하고 있기 때문입니다. $m\in P$에 대해 $(P,\le )$의 최대한의 원소가 되어야 하는 정의하는 조건은 다음과 같이 다시 바꿀 수 있습니다: 

• $s\in P$에 대해, 만약 $m\le s$ (따라서 $m$과 비-비교가능인 원소는 무시됨)이면 $s\le m$입니다.

Example where all elements are maximal but none are greatest

$S$가 적어도 두 개의 (구별되는) 원소를 포함하는 집합이고 $i\le j$인 것과 $i=j$인 것이 필요충분 조건이라고 선언함으로써 $S$ 위의 부분 순서 $\le$를 정의한다고 가정합니다. 만약 $i\ne j$가 $S$에 속하면 $i\le j$도 $j\le i$도 유지되지 않으며, 이는 $S$에서 모든 구별되는 (즉, 같지 않은) 원소의 쌍이 비-비교가능임을 보여줍니다. 결과적으로, $(S,\le )$는 최대 원소를 가질 수 없습니다 (왜냐하면 $S$의 최대 원소가, 특히, $S$의 모든 각 원소와 비교-가능이어야 하지만 $S$는 그러한 원소를 가지지 않기 때문입니다). 어쨌든, 모든 각 원소 $m\in S$는 $(S,\le )$의 최대한의 원소인데 왜냐하면 $S$에서 $m$ 및 $\ge m$과 비교-가능 둘 다인 정확하게 하나의 원소가 있고, 해당 원소는 $m$ 자체 (물론 $\le m$임)이기 때문입니다.

대조적으로, 만약 준순서화된 집합(preordered set) $(P,\le )$이 우연히 최대 원소 $g$를 가지게 되면 $g$는 반드시 $(P,\le )$의 최대한의 원소가 될 것이고 더욱이, 최대 원소 $g$의 결론이 $P$의 모든 각 원소와 비교-가능이라는 것이기 때문에, 만약 $(P,\le )$도 부분적으로 순서화되면 $g$가 $(P,\le )$의 유일한 최대한의 원소라는 결론을 내릴 수 있습니다. 어쨌든, 고유성의 결론은 만약 준순서화된 집합 $(P,\le )$도 부분적으로 순서화되지 않으면 더 이상 보장되지 않습니다. 예를 들어, $R$이 비-빈 집합이고 $i\le j$가 항상 모든 $i,j\in R$에 대해 성립한다고 선언함으로써 $R$ 위에 준순서 $\le$를 정의한다고 가정합니다. 방향화된 준순서화된 집합 $(R,\le )$이 부분적으로 순서화된 것과 $R$이 정확하게 하나의 원소를 가지는 것은 필요충분 조건입니다. $R$로부터 모든 원소의 쌍은 비교-가능이고 $R$의 모든 각 원소는 $(R,\le )$의 최대 원소 (및 따라서 역시 최대한의 원소)입니다. 따라서 특히, 만약 $R$이 적어도 두 개의 원소를 가지면 $(R,\le )$은 여러 개의 구별되는 최대 원소를 가집니다.

Properties

전체에 걸쳐, $(P,\le )$를 부분적으로 순서화된 집합(partially ordered set)으로 놓고 $S\subseteq P$라고 놓습니다. 

• 집합 $S$는 많아야 하나의 최대 원소를 가질 수 있습니다. 따라서 만약 집합이 최대 원소를 가지면 그것은 반드시 고유합니다.
• 만약 그것이 존재하면, $S$의 최대 원소는 $S$에도 포함된 $S$의 위쪽 경계(upper bound)입니다.
• * 만약 $g$가 $S$의 최대 원소이면 $g$는 역시 $S$의 최대한의 원소이고 게다가, $S$의 임의의 다른 최대한의 원소는 반드시 $g.$와 같을 것입니다.
  
  • 따라서 집합 $S$가 여러 개의 최대한의 원소를 가지면 그것은 최대 원소를 가질 수 없습니다.
• 만약 $P$가 오름 체인 조건(ascending chain condition)을 만족시키면, $P$의 부분집합 $S$가 최대 원소를 가지는 것과 그것이 하나의 최대한의 원소를 가지는 것은 필요충분 조건입니다.
• $S$에 대한 $\le$의 제한이 전체 순서일 때 (맨 위 그림에서 $S=\{1,2,4\}$가 예제임), 최대한의 원소와 최대 원소의 개념이 일치합니다.
  
  • 어쨌든, 이것은 $S$가 최대 원소를 가질 때마다 위에서 언급한 것처럼 개념도 일치하기 때문에 필요 조건이 아닙니다.
• 만약 최대한의 원소와 최대 원소의 개념이 $P$의 모든 각 2-원소 부분집합 $S$에서 일치하면, $\le$는 $P$의 전체 순서입니다.

Sufficient conditions

• 유한 체인(chain)에는 항상 가장 큰 원소와 가장 작은 원소가 있습니다.

Top and bottom

부분적으로 순서화된 전체 집합의 최소 원소와 최대 원소는 특별한 역할을 하고 각각 맨바닥(bottom, ⊥)과 꼭대기(top, ⊤), 또는 영(zero, 0)과 단위(unit, 1)라고도 불립니다. 만약 둘 다 존재하면, 그 포셋은 경계진 포셋(bounded poset)이라고 불립니다. 0과 1의 표기법은 포셋이 여집합된 격자(complemented lattice)일 때, 그리고 혼동이 없을 때, 즉 맨바닥과 꼭대기와 다른 원소 0과 1을 이미 포함하고 있는 숫자의 부분 순서에 대해 이야기하지 않을 때 바람직하게 사용됩니다. 최소 원소와 최대 원소의 존재는 부분 질서의 특별한 완비성 속성(completeness property)입니다.

추가 입문 정보는 순서 이론(order theory)에 대한 기사에서 찾을 수 있습니다.

Examples

• 정수(integers)의 부분집합은 실수(real numbers)의 집합 $\mathbb{R}$에서 위쪽 경계를 가지지 않습니다.
• $\{a,b,c,d\}$ 위에 관계 $\le$를 $a\le c,$ $a\le d,$ $b\le c,$ $b\le d$에 의해 주어졌다고 놓습니다. 집합 $\{a,b\}$는 위쪽 경계 $c$와 $d$를 가지지만, 최소 위쪽 경계를 가지지 않고, 최대 원소를 가지지 않습니다 (참조. 그림).
• 유리수(rational numbers)에서, 제곱이 2보다 작은 숫자의 집합은 위쪽 경계를 가지지만 최대 원소와 최소 위쪽 경계를 가지지 않습니다.
• $\mathbb{R}$에서, 1보다 작은 숫자의 집합은 최소 위쪽 경계, 즉, 1을 가지지만, 최대 원소를 가지지 않습니다.
• $\mathbb{R}$에서, 1보다 작거나 같은 숫자의 집합은 최대 원소, 즉, 1을 가지며, 이는 역시 최소 위쪽 경계입니다.
• 곱 순서(product order)를 갖는 ${\mathbb{R}}^2$에서, $0<x<1$을 갖는 쌍 $(x,y)$의 집합은  위쪽 경계를 가지지 않습니다.
• 사전식 순서(lexicographical order)를 갖는 ${\mathbb{R}}^2$에서, 이 집합은 위쪽 경계, 예를 들어, $(1,0)$을 가집니다. 그것은 최소 위쪽 경계를 가지지 않습니다.

See also

• Maximal and minimal elements
• Limit superior and limit inferior (infimum limit)
• Upper and lower bounds

References

• The notion of locality requires the function's domain to be at least a topological space.
• Davey, B. A.; Priestley, H. A. (2002). Introduction to Lattices and Order (2nd ed.). Cambridge University Press. ISBN 978-0-521-78451-1.