Maximal and minimal elements

수학(mathematics), 특히 순서 이론(order theory)에서, 일부 준순서화된 집합(preordered set)의 부분집합(subset) $S$ 의 최대한의 원소(maximal element)는 $S$ 에서 임의의 다른 원소보다 작지 않은 $S$ 의 원소입니다. 일부 준순서화된 집합의 부분집합 $S$ 의 최소한의 원소(minimal element)는 $S$ 에서 임의의 다른 원소보다 크지 않은 $S$ 의 원소로 이중적(dually)으로 정의됩니다.

최대한의 원소와 최소한의 원소의 개념은 각각 최댓값과 최솟값으로 알려진 최대 원소와 최소 원소(greatest element and least element)의 개념보다 약합니다. 준순서화된 집합의 부분집합 $S$ 의 최댓값은 $S$ 의 임의의 다른 원소보다 크거나 같은 $S$ 의 원소이고, $S$ 의 최솟값은 다시 이중적으로 정의됩니다. 부분적으로 순서화된 집합(partially ordered set)의 특별한 경우에서, 많아야 하나의 최댓값과 많아야 하나의 최솟값이 있을 수 있지만, 여러 최대한의 원소 또는 최소한의 원소가 있을 수 있습니다.^[1]^[2] 전체적으로 순서화된 집합(totally ordered sets)에 더 전문화하면, 최대한의 원소와 최댓값의 개념이 일치하고 최소한의 원소와 최솟값의 개념이 일치합니다.

예제로서, 포함(containment)에 의해 순서화된 다음 모음에서 $S:=\left\{\{d,o\},\{d,o,g\},\{g,o,a,d\},\{o,a,f\}\right\}$ 원소 {d, o}는 최소한의 것인데 왜냐하면 그것은 모음에서 집합을 포함하지 않기 때문이고, 원소 {g, o, a, d}는 최대한의 것인데 왜냐하면 모음에서 그것을 포함하는 집합이 없기 때문이고, 원소 {d, o, g}는 둘 다 아니고, 원소 {o, a, f}는 최소한의 것과 최대한의 것 둘 다입니다. 대조적으로, $S$ 에 대해 최댓값도 최솟값도 존재하지 않습니다.

조온의 보조정리(Zorn's lemma)는 모든 각 전체적으로 순서화된 부분집합이 위쪽 경계(upper bound)를 가진다는 모든 각 부분적으로 순서화된 집합이 적어도 하나의 최대한의 원소를 포함한다고 말합니다. 이 보조 정리는 바른-순서화 정리(well-ordering theorem)와 선택의 공리(axiom of choice)와^[3] 동등하고 한–바나흐 정리(Hahn–Banach theorem), 체리브라운 정리(Kirszbraun theorem), 티호노프의 정리(Tychonoff's theorem), 모든 각 벡터 공간에 대해 하멜 기저(Hamel basis)의 존재, 모든 각 필드(field)에 대해 대수적 클로저(algebraic closure)의 존재와 같은 다른 수학적 영역에서 주요 결과를 의미합니다.

Definition

$(P,\leq )$ 를 준순서화된 집합(preordered set)으로 놓고 $S\subseteq P$ 라고 놓습니다. $\,\leq \,$ 에 관한 $S$ 의 최대한의 원소(maximal element)는 다음을 만족하는 원소 $m\in S$ 입니다:

만약

s\in S

가

m\leq s

를 만족시키면 반드시

s\leq m

입니다.

유사하게, $\,\leq \,$ 에 관한 $S$ 의 최소한의 원소(minimal element)는 다음을 만족하는 원소 $m\in S$ 입니다:

만약

s\in S

가

s\leq m

를 만족시키면 반드시

m\leq s

입니다.

동등하게, $m\in S$ 가 $\,\leq \,$ 에 관한 $S$ 의 최소한의 원소인 것과 $m$ 이 $\,\geq \,$ 에 관한 $S$ 의 최대한의 원소인 것은 필요충분 조건이며, 여기서 정의에 의해, (모든 $p,q\in P$ 에 대해) $q\geq p$ 인 것과 $p\leq q$ 인 것은 필요충분 조건입니다.

만약 부분집합 $S$ 가 지정되지 않으면 그것은 $S:=P$ 로 가정되어야 합니다. 명시적으로, $(P,\leq )$ 의 최대한의 원소 (각각, 최소한의 원소)는 $\,\leq \,$ 에 관해 $S:=P$ 의 최대한의 (각각 최소한의) 원소입니다.

만약 준순서화된 집합 $(P,\leq )$ 이 역시 부분적으로 순서화된 집합(partially ordered set)으로 발생하면 (또는 보다 일반적으로, 제한 $(S,\leq )$ 이 부분적으로 순서화된 집합이면), $m\in S$ 이 $S$ 의 최대한의 원소인 것과 $S$ 가 $m$ 보다 엄격하게 큰 원소를 포함하지 않는 것은 필요충분 조건입니다; 명시적으로, 이것은 $m\leq s$ 와 $m\neq s$ 임을 만족하는 임의의 원소 $s\in S$ 가 존재하지 않음을 의미합니다. 최소한의 원소에 대해 특성화는 $\,\leq$ 대신 $\,\geq \,$ 를 사용함으로써 얻습니다.

Existence and uniqueness

최대한의 원소는 존재할 필요가 없습니다.

Example 1: $S=[1,\infty )\subseteq \mathbb {R}$ 라고 놓습니다, 여기서 $\mathbb {R}$ 은 실수(real numbers)를 나타냅니다. 모든 $m\in S$ 에 대해, $s=m+1\in S$ 이지만 $m<s$ 입니다 (즉, $m\leq s$ 이지만 $m=s$ 이 아닙니다).
Example 2: $S=\{s\in \mathbb {Q} ~:~1\leq s^{2}\leq 2\}$ 라고 놓습니다, 여기서 $\mathbb {Q}$ 는 유리수(rational numbers)를 나타내고 여기서 ${\sqrt {2}}$ 는 무리수입니다..

일반적으로 $\,\leq \,$ 는 $S$ 위에 오직 부분 순서입니다. 만약 $m$ 가 최대한의 원소이고 $s\in S$ 이면, $s\leq m$ 도 아니고 $m\leq s$ 도 아닌 가능성이 남습니다. 이것은 둘 이상의 최대한의 원소가 존재할 가능성을 열어 둡니다.

Example 3: 펜스(fence) $a_{1}<b_{1}>a_{2}<b_{2}>a_{3}<b_{3}>\ldots$ 에서, 이미지에서 보이는 것처럼 모든 $a_{i}$ 는 최소한의 것이고 $b_{i}$ 는 최대한의 것입니다.
Example 4: A를 적어도 두 개의 원소를 갖는 집합으로 놓고 $S=\{\{a\}~:~a\in A\}$ 를 $\,\subseteq$ 에 의해 부분적으로 순서화된 한원소 부분집합(singleton subsets)으로 구성된 거듭제곱 집합(power set) $\wp (A)$ 의 부분집합으로 놓습니다. 이것은 어떤 두 원소도 비교-가능이 아니고 모든 각 원소 $\{a\}\in S$ 가 최대한의 것 (및 최소한의 것)인 이산 포셋입니다; 더욱이, 임의의 구별되는 $a,b\in A$ 에 대해, $\{a\}\subseteq \{b\}$ 도 아니고 $\{b\}\subseteq \{a\}$ 도 아닙니다.

Greatest elements

부분적으로 순서화된 집합 $(P,\leq )$ 에 대해, $\,\leq \,$ 의 비-반사적 커널(irreflexive kernel)은 $\,<\,$ 로 표시되고 $x\leq y$ 이고 $x\neq y$ 이면 $x<y$ 에 의해 정의됩니다. 임의적인 구성원 $x,y\in P$ 에 대해, 다음 경우 중 정확하게 하나가 적용됩니다:

$x<y$ ;
$x=y$ ;
$y<x$ ;
$x$ 와 $y$ 는 비-비교가능입니다.

부분집합 $S\subseteq P$ 와 일부 $x\in S$ 가 주어지면,

만약 경우 1이 결코 임의의 $y\in S$ 에 대해 적용되지 않으면, $x$ 는 위에서 정의된 것처럼 $S$ 의 최대한의 원소입니다;
만약 경우 1과 4가 결코 임의의 $y\in S$ 에 대해 적용되지 않으면, $x$ 는 $S$ 의 최대 원소(greatest element)라고 불립니다.

따라서 최대 원소의 정의는 최대한의 원소의 정의보다 더 강합니다.

동등하게, 부분집합 $S$ 의 최대 원소는 $S$ 의 모든 각 다른 원소보다 큰 $S$ 의 원소로 정의될 수 있습니다. 부분집합은 많아야 하나의 최대 원소를 가질 수 있습니다.^{[proof 1]}

$S$ 의 최대 원소는, 만약 존재하면, $S$ 의 최대한의 원소이고,^{[proof 2]} 유일한 원소입니다.^{[proof 3]} 대우(contraposition)에 의해, 만약 $S$ 가 여러 개의 최대한의 원소를 가지면, 그것은 최대 원소를 가질 수 없습니다; 예제 3을 참조하십시오. 만약 $P$ 가 오름 체인 조건(ascending chain condition)을 만족시키면, $P$ 의 부분집합 $S$ 가 최대 원소를 가지는 것과 그것이 하나의 최대한의 원소를 가지는 것은 필요충분 조건입니다.^{[proof 4]}

$S$ 에 대한 $S$ 의 제한이 전체 순서일 때 (맨 위 그림에서 $S=\{1,2,4\}$ 가 예제임), 최대한의 원소와 최대 원소의 개념은 일치합니다.^{[proof 5]} 이것은 필요 조건이 아닙니다: $S$ 가 최대 원소를 가질 때마다, 위에서 언급한 것처럼 그 개념도 일치합니다. 만약 최대한의 원소와 최대 원소의 개념이 $P$ 의 모든 각 2-원소 부분집합 $S$ 에서 일치하면, $\,\leq \,$ 는 $P$ 위에 전체 순서입니다.^{[proof 6]}

Directed sets

전체적으로 순서화된 집합(totally ordered set)에서, 최대한의 원소와 최대 원소라는 용어가 일치하며, 이는 오직 전체 순서가 고려되는 해석학(analysis)과 같은 분야에서 두 용어가 서로 바꿔서 사용됩니다. 이 관찰은 임의의 부분적으로 순서화된 집합의 전체적으로 순서화된 부분집합뿐만 아니라, 방향화된 집합(directed sets)을 통한 순서 이론적 일반화에도 적용됩니다. 방향화된 집합에서, 원소의 모든 각 쌍 (특히 비-비교가능 원소의 쌍)은 집합 내에서 공통적인 위쪽 경계를 가집니다. 만약 방향화된 집합이 최대한의 원소를 가지면, 그것은 역시 최대 원소이고,^{[proof 7]} 따라서 유일한 최대한의 원소입니다. 최대한의 또는 최대 원소가 없는 방향화된 집합에 대해, 위의 예제 1과 2를 참조하십시오.

최소한의 원소에 대해서도 유사한 결론이 참입니다.

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

Properties

각각의 유한하고 비-빈 부분집합 $S$ 는 최대한의 원소와 최소한의 원소를 모두 가집니다. 무한 부분집합은 예를 들어 보통의 순서를 갖는 정수(integers) $\mathbb {Z}$ 와 같이 그것들 중 어느 것도 가질 필요가 없습니다.
부분집합 $S$ 의 최대한의 원소의 집합은 항상 역체인(antichain)입니다. 즉, $S$ 의 서로 다른 두 최대한의 원소는 비교-가능이 아닙니다. 최소한의 원소에도 동일하게 적용됩니다.

Examples

파레토 효율(Pareto efficiency)에서, 파레토 최적은 파레토 개선의 부분 순서에 관한 최대한의 원소이고, 최대한의 원소의 집합은 파레토 국경(Pareto frontier)이라고 불립니다.
결정 이론(decision theory)에서, 허용-가능한 결정 규칙(admissible decision rule)은 지배적 결정 규칙(dominating decision rule)의 부분 순서에 관한 최대한의 원소이다.
현대 포트폴리오 이론(modern portfolio theory)에서, 위험과 수익에 대한 곱 순서(product order)에 관한 최대한의 원소의 집합은 그 효율적 국경(efficient frontier)이라고 불립니다.
집합 이론(set theory)에서, 집합이 유한한 것과 부분집합의 모든 각 비-빈 가족이 포함 관계(inclusion relation)에 의해 순서화될 때 최소한의 원소를 가지는 것은 필요충분 조건입니다.
추상 대수(abstract algebra)에서, 최대한의 공통 약수(maximal common divisor)의 개념은 원소의 집합의 공통 약수가 둘 이상의 최대한의 원소를 가질 수 있는 숫자 시스템으로 최대 공통 약수(greatest common divisors)를 일반화하는 데 필요합니다.
계산적 기하학(computational geometry)에서, 점 집합의 최댓값(maxima of a point set)은 좌표-별 지배의 부분 순서에 관한 최대한의 것입니다.

Consumer theory

경제학에서, 부분 순서 대신 준순서 (일반적으로 전체 준순서)를 사용하여 반-대칭의 공리를 완화할 수 있습니다; 최대한의 원소와 유사한 개념은 매우 유사하지만, 아래에 자세히 설명된 것처럼 다른 용어가 사용됩니다.

소비자 이론(consumer theory)에서, 소비 공간은 어떤 집합 $X$ , 각 $x\in X$ 가 그 경제에서 각 기존 상품에 대해 지정된 소비의 량을 나타내도록 일반적으로 어떤 벡터 공간의 양수 직교입니다. 소비자의 선호도(preferences)는 보통 $x,y\in X$ 와 $x\preceq y$ 이도록 전체 준순서 $\preceq$ 에 의해 표시됩니다: $x$ 는 많아야 $y$ 만큼 선호된다라고 읽습니다. $x\preceq y$ 와 $y\preceq x$ 일 때 소비자는 $x$ 와 $y$ 사이에 무관심하다고 해석되지만 $x=y$ 라고 결론을 내릴 이유는 없습니다. 선호 관계는 반-대칭으로 가정되지 않습니다. 이 맥락에서, 임의의 $x=y$ 에 대해, 원소 $x\in B$ 는 다음이 $y\preceq x$ 를 의미하면 최대한의 원소(maximal element)라고 말합니다: $y\in B$ 여기서 $x\prec y,$ 즉 $y\preceq x$ 가 아닌 $x\preceq y$ 라는 의미에서 다른 묶음에 의해 지배되지 않는 소비 묶음으로 해석됩니다.

형식적 정의는 순서화된 집합에 대해 최대 원소의 정의와 매우 유사하다는 점에 유의해야 합니다. 어쨌든, $\preceq$ 가 단지 준순서일 때, 위의 속성을 갖는 원소 $x$ 는 순서화에서 최대한의 원소와 매우 유사하게 동작합니다. 예를 들어, 최대한의 원소 $x\in B$ 가 $y\preceq x$ 에 대해 고유하지 않다는 것은 $x\preceq y$ 일 가능성을 배제하지 않습니다 (반면 $y\preceq x$ 와 $x\preceq y$ 는 $x=y$ 를 의미하지 않고 단순히 무관심 $x\sim y$ 를 의미합니다). 선호도 준순서에 대해 최대 원소의 개념은 가장 선호되는(most preferred) 선택의 개념입니다. 즉, 다음이 $y\prec x$ 를 의미하는 일부 $x\in B$ 가 있습니다. $y\in B$ 명백한 적용은 수요 대응의 정의에 대한 것입니다. $P$ 를 $X$ 의 함수형의 클래스라고 놓습니다. 원소 $p\in P$ 는 가격 함수형(price functional) 또는 가격 시스템(price system)이라고 불리고 모든 각 소비 묶음 $x\in X$ 를 시장 가치 $p(x)\in \mathbb {R} _{+}$ 로 매핑합니다. 예산 대응(budget correspondence)은 임의의 가격 시스템과 임의의 소득의 수준을 다음 부분집합으로 매핑하는 대응 $\Gamma \colon P\times \mathbb {R} _{+}\rightarrow X$ 입니다: $\Gamma (p,m)=\{x\in X~:~p(x)\leq m\}.$

수요 대응(demand correspondence)은 임의의 가격 $p$ 와 임의의 소득의 수준 $m$ 을 $\Gamma (p,m)$ 의 $\preceq$ -최대한의 원소의 집합에 매핑합니다. $D(p,m)=\left\{x\in X~:~x{\text{ is a maximal element of }}\Gamma (p,m)\right\}.$

그것은 수요 대응이라고 불리는데, 왜냐하면 주어진 $p$ 와 $m$ 에 대해, 소비자 $x^{*}$ 의 합리적인 선택(rational choice)은 어떤 원소 $x^{*}\in D(p,m)$ 일 것이라고 그 이론이 예측하기 때문입니다.

Related notions

부분적으로 순서화된 집합 $P$ 의 부분집합 $Q$ 는 만약 모든 각 $x\in P$ 에 대해 $x\leq y$ 를 만족하는 일부 $y\in Q$ 가 존재하면 공끝(cofinal)이라고 말합니다. 최대한의 원소를 갖는 부분적으로 순서화된 집합의 모든 각 공끝 부분집합은 모든 최대한의 원소를 포함해야 합니다.

부분적으로 순서화된 집합 $P$ 의 부분집합 $L$ 은 만약 그것이 아래로 닫혀 있으면 $P$ 의 아래쪽 집합(lower set)이라고 말합니다: 만약 $y\in L$ 이고 $x\leq y$ 이면 $x\in L$ 입니다. 유한 순서화된 집합 $P$ 의 모든 각 부분집합 $L$ 은 $L$ 의 모든 최대한의 원소를 포함하는 가장 작은 아래쪽 집합과 같습니다.

Notes

Proofs

^ If $g_{1}$ and $g_{2}$ are both greatest, then $g_{1}\leq g_{2}$ and $g_{2}\leq g_{1},$ and hence $g_{1}=g_{2}$ by antisymmetry. $\blacksquare$
^ If $g$ is the greatest element of $S$ and $s\in S,$ then $s\leq g.$ By antisymmetry, this renders ( $g\leq s$ and $g\neq s$ ) impossible. $\blacksquare$
^ If $m$ is a maximal element then $m\leq g$ (because $g$ is greatest) and thus $m=g$ since $m$ is maximal. $\blacksquare$
^ Only if: see above. — If: Assume for contradiction that $S$ has just one maximal element, $m,$ but no greatest element. Since $m$ is not greatest, some $s_{1}\in S$ must exist that is incomparable to $m.$ Hence $s_{1}\in S$ cannot be maximal, that is, $s_{1}<s_{2}$ must hold for some $s_{2}\in S.$ The latter must be incomparable to $m,$ too, since $m<s_{2}$ contradicts $m$ 's maximality while $s_{2}\leq m$ contradicts the incomparability of $m$ and $s_{1}.$ Repeating this argument, an infinite ascending chain $s_{1}<s_{2}<\ldots <s_{n}<\cdots$ can be found (such that each $s_{i}$ is incomparable to $m$ and not maximal). This contradicts the ascending chain condition. $\blacksquare$
^ Let $m\in S$ be a maximal element, for any $s\in S$ either $s\leq m$ or $m\leq s.$ In the second case, the definition of maximal element requires that $s=m,$ so it follows that $s\leq m.$ In other words, $m$ is a greatest element. $\blacksquare$
^ If $a,b\in P$ were incomparable, then $S=\{a,b\}$ would have two maximal, but no greatest element, contradicting the coincidence. $\blacksquare$
^ Let $m\in D$ be maximal. Let $x\in D$ be arbitrary. Then the common upper bound $u$ of $m$ and $x$ satisfies $u\geq m$ , so $u=m$ by maximality. Since $x\leq u$ holds by definition of $u$ , we have $x\leq m$ . Hence $m$ is the greatest element. $\blacksquare$