Теория множеств

[Kemmerix]

Элемент $m$ из подмножества $A$ частично упорядоченного множества $P$ называется максимальным(минимальным), если для каждого $x$ из $A$, для которого $m \le x (m \ge x)$
будет $m = x$.
Другими словами, элемент $m$ из подмножества $A$ частично упорядоченного множества $P$ является максимальным(минимальным), если для всякого $x$ из $A$ имеет место $m \ge x (m\le x)$.
Есть для примера частично упорядоченное множество $ \left( \begin{array}{ccc} 1 &0 & 0 \\ 1& 1 & 0 \\ 1 & 1 & 1 \end{array} \right)$.
Объясните пожалуйста, какие элементы здесь максимальные и минимальные.

[Mysterious Light]

Пусть меня поправят, если я не прав.

$m\in A \textrm{ максимален }\Leftrightarrow \forall x\in A.\; (m\leq x \Rightarrow m=x)$
не то же самое, что
$m\in A \textrm{ максимален }\Leftrightarrow \forall x\in A.\; (m\geq x)$

Всякий максимум во втором значении будет максимумом в первом, но порой бывают множества, в которых есть элемент $m$, который не сравним с некоторыми элементами $A$, но нет такого элемента $x\in A$, который был бы сравним с $m$ и больше него.

Ваш пример прост: элементы $\{a,b,c\}$ упорядочены линейно $a<b<c$. $\max(a,b)=b,\;\max(a,c)=c,\;\max(b,c)=c$, максимум всего множества $c$. Неинтересно.

Лучше рассмотрите $\{a,b,c,d\}$ с таким порядком: $a<b<d,\;a<c<d$.

$$\left( \begin{array}{cccc} 1&0&0&0\\ 1&1&0&0\\ 1&0&1&0\\ 1&1&1&1 \end{array} \right)$$

Какой максимум множества $\{a,b,c\}$? И существует ли он вообще в смысле первого и второго определений?

[Joker_vD]

У максимального элемента ровно одно определение: нету такого элемента, чтобы был больше максимального. Есть еще "наибольший" элемент: это тот, который больше любого другого.

[Kemmerix]

Mysterious Light в сообщении #645834 писал(а):

Пусть меня поправят, если я не прав.

$m\in A \textrm{ максимален }\Leftrightarrow \forall x\in A.\; (m\leq x \Rightarrow m=x)$
не то же самое, что
$m\in A \textrm{ максимален }\Leftrightarrow \forall x\in A.\; (m\geq x)$

Всякий максимум во втором значении будет максимумом в первом, но порой бывают множества, в которых есть элемент $m$, который не сравним с некоторыми элементами $A$, но нет такого элемента $x\in A$, который был бы сравним с $m$ и больше него.

Ваш пример прост: элементы $\{a,b,c\}$ упорядочены линейно $a<b<c$. $\max(a,b)=b,\;\max(a,c)=c,\;\max(b,c)=c$, максимум всего множества $c$. Неинтересно.

Лучше рассмотрите $\{a,b,c,d\}$ с таким порядком: $a<b<d,\;a<c<d$.

$$\left( \begin{array}{cccc} 1&0&0&0\\ 1&1&0&0\\ 1&0&1&0\\ 1&1&1&1 \end{array} \right)$$

Какой максимум множества $\{a,b,c\}$? И существует ли он вообще в смысле первого и второго определений?

Mysterious Light спасибо за объяснение, я взял такой простой пример, что бы мне по пальцах объяснили как находится максимальный и минимальный элемент, этот пример не задание, задание - написать программу которая будет искать $ \max $ и $ \min$ в частично упорядоченном множестве. Как определить рефлективность, антисимметричность и транзитивность не вызвало такого труда, как с определением $ \max $ и $ \min$.
А в множестве

$$\left( \begin{array}{ccc} 1&0&0\\ 0&1&0\\ 1&0&1\\ \end{array} \right)$$

Максимальный элемент
$a<c$. $\max(a,b)=b,\;\max(a,c)=c,\;\max(b,c)=b$, $\max = b?$
Минимальный элемент
$c>a$. $\min(a,b)=a,\;\min(a,c)=a,\;\min(b,c)=c$, $\min = a?$

[Mysterious Light]

$a$ и $b$ не сравнимы, в множестве $\{a,b\}$ нет наибольшего элемента и неоднозначен максимальный элемент:
$\forall x\in\{a,b\}\;(x\geq a\;\Leftrightarrow\;x=a)$
$\forall x\in\{a,b\}\;(x\geq b\;\Leftrightarrow\;x=b)$

P.S. будешь полным перебором истакь? Сложность $O(n^2)$.