Как определять максимальные и минимальные элементы в отношении порядка
Кратко: если \(R\) — отношение порядка, то
- \(a\) — минимальный элемент, если не существует \(x\ne a\), для которого \(xRa\);
- \(a\) — максимальный элемент, если не существует \(x\ne a\), для которого \(aRx\).
То есть при стрелке \(x\to y\), если \(xRy\):
- минимальный элемент не имеет входящих стрелок;
- максимальный элемент не имеет исходящих стрелок.
Алгоритм
Сначала убедись, что \(R\) — отношение порядка:
- \(xRx\) для всех \(x\in A\) — рефлексивность;
- \(xRy\) и \(yRx\) влекут \(x=y\) — антисимметричность;
- из \(xRy\) и \(yRz\) следует \(xRz\) — транзитивность.
Для каждого элемента \(a\) проверь: \[ \{x\in A:xRa\}. \] Если там только сам \(a\), то \(a\) минимальный.
Затем проверь: \[ \{x\in A:aRx\}. \] Если там только сам \(a\), то \(a\) максимальный.
Важно: минимальных и максимальных элементов может быть несколько.
- Наименьший элемент \(a\): \(aRx\) для всех \(x\in A\). Он всегда единственный.
- Наибольший элемент \(a\): \(xRa\) для всех \(x\in A\). Он также единственный.
Пример из задания: пункт 1б
\[ A=\{3,4,5,6,7\}, \qquad xRy\Longleftrightarrow |x-y|(x-3)(y-8)\ge 0. \]
Если \(x\ne y\), то \(|x-y|>0\), а \(y-8<0\). Поэтому неравенство выполняется только при \(x=3\).
Значит:
\[ 3R4,\;3R5,\;3R6,\;3R7, \]
а среди элементов \(4,5,6,7\) есть только отношения вида \(xRx\).
Следовательно:
- минимальный элемент: \(\boxed{3}\);
- максимальные элементы: \(\boxed{4,5,6,7}\);
- наименьший элемент: \(\boxed{3}\);
- наибольшего элемента нет.
Обсуждение
6 сообщенийРазбери пункт 6б по этому алгоритму
Пришли условие или фото пункта 6б — в переписке его не видно. Разберу по тому же алгоритму.
В пункте 6б: \[ A=\{1,2,4,5,7,8,9\},\qquad xRy\Longleftrightarrow x\mid 3y. \]
Перечислим пары \(xRy\), где \(x\ne y\): \[ (1,2),(1,4),(1,5),(1,7),(1,8),(1,9),(2,4),(2,8),(4,8). \] Кроме них, есть все пары \((x,x)\), так как \(x\mid 3x\).
- Не симметрично: \(1R2\), но \(2\not R1\).
- Антисимметрично: среди перечисленных пар нет таких, чтобы вместе с \((x,y)\) была пара \((y,x)\).
- Транзитивно: цепочки нетривиальных отношений \(2R4\) и \(4R8\) дают \(2R8\); цепочки, начинающиеся с \(1\), также транзитивны, поскольку \(1\) находится в отношении со всеми элементами.
- Значит, \(R\) — отношение порядка, но не отношение эквивалентности.
Теперь определим минимальные и максимальные элементы:
- У \(1\) нет входящих отношений от других элементов, поэтому минимальный элемент — \(\boxed{1}\).
- У \(5,7,8,9\) нет исходящих отношений к другим элементам, поэтому максимальные элементы — \(\boxed{5,7,8,9}\).
Наибольшего элемента нет: ни один элемент не находится в отношении со всеми элементами как второй элемент.
почему у 1 нет входящих отношений? например 2R1, получается, что в 1 входят стрелочки
Здесь \(2R1\) означает, что \(2\mid 3\cdot1\), то есть \(2\mid3\). Это неверно: \(3\) не делится на \(2\).
Чтобы в \(1\) входила стрелка от другого элемента \(x\), должно выполняться \(xR1\), то есть \(x\mid3\). Среди элементов \(A=\{1,2,4,5,7,8,9\}\) только \(1\) делит \(3\). Поэтому от других элементов стрелок в \(1\) нет; петля \(1R1\) не учитывается при определении минимального элемента.
