ТЕМА 12 / 55 · ПУНКТ 12 10–15 минут

Частичный и линейный порядок

Сначала пойми идею. Затем попробуй рассказать доказательство своими словами и закрепи результат задачей.

Что означают буквы и значки8 обозначений

Здесь — обозначения, которые встретятся в этой теме. Точный смысл буквы уточняй по формуле рядом с ней.

$x$: Произвольный элемент множества или число, с которым работаем.
$y$: Другое число или результат функции: часто пишут y = f(x).
$z$: Третий элемент или третья точка, помимо x и y.
$X$: Множество исходных элементов; для функции — её область определения.
$\R$: Множество вещественных чисел: все точки числовой прямой.
$\Rightarrow$: «Следует»: если верно условие слева, то верно утверждение справа.
$\subseteq$: «Содержится»: каждый элемент первого множества лежит и во втором.
$\preceq$: Знак порядка: x ≼ y означает, что x не превосходит y в заданном отношении.

ШАГ 01

Разбираемся в теме

Определение и обозначения

Отношение $\preceq$ на $X$ — частичный порядок, если $x\preceq x$ .
$x\preceq y$ и $y\preceq x\Rightarrow x=y$ .
$x\preceq y$ и $y\preceq z\Rightarrow x\preceq z$ .
Линейный порядок дополнительно требует сравнимости любых $x,y$ : $x\preceq y$ или $y\preceq x$ .

Пример

Включение $\subseteq$ на множествах — частичный порядок: $\{1\}$ и $\{2\}$ несравнимы.

Обычное $\le$ на $\R$ — линейный.

НАГЛЯДНАЯ СХЕМА · Частичный и линейный порядок

В частичном порядке элементы могут быть несравнимы; в линейном любые два сравнимы.

Понял идею?Проверь себя на задаче или устном вопросе.