Отношение порядка

Определение:

Бинарное отношение $\rho$ на множестве $X$ называется отношением порядка, если оно транзитивно и антисимметрично. Множество, на котором введено отношение порядка, называют упорядоченным.

Множество всех пар $(x,y)$ людей, для которых $x$ старше $y$, является отношением порядка.

Определение:

Отношение порядка $\preceq$ называется отношением нестрогого (частичного) порядка на множестве X, если оно рефлексивно.

Определение:

Отношение порядка $\prec$ называется отношением строгого порядка на множестве $X$, если оно иррефлексивно.

Определение:

Отношение порядка $\rho$ на множестве $X$ называется отношением линейного порядка, если любые $x,y\in X$, \mbox{$x\neq y$}, сравнимы в смысле отношения $\rho$ (либо $x\rho y$, либо $y\rho x$ обязательно выполняется).

1) Отношение родитель-ребенок не является отношением порядка. Очевидно, что у такого отношения отсутствует транзитивность: дед не является родителем своего внука. С другой стороны, отношение предок-потомок является отношением порядка. Например, фамильное дерево с указанием всех связей от дедов к внукам. Отношение предок-потомок является отношением строгого порядка и не является линейным порядком.

2) $\rho_{>} = \{(x,y) | x,y\in\mathbb{R}, x > y\}$ — является отношением строгого линейного порядка.

3) $\rho_\geq = \{(x,y) | x,y\in\mathbb{R}, x\geq y\}$ — является отношением нестрогого линейного порядка.

4) Отношение $\subseteq$, состоящее из всех таких пар подмножеств $(A,B)$ заданного универсального множества $U$, что $A$ является подмножеством множества $B$, называют отношением включения. Отношение включения является отношением нестрогого порядка и не является отношением линейного порядка.

Определение:

Пусть на множестве $X$ введено отношение порядка. Пусть элемент $x\in X$ таков, что не существует такого $y\in X$, $y\neq x$, что $y\prec x$. Тогда $x$ называют минимальным элементом.

Определение:

Пусть на множестве $X$ введено отношение порядка.

Пусть элемент $x\in X$ таков, что для любых $y\in X$, $y\neq x$, выполняется $x\prec y$.

Тогда $x$ называют наименьшим элементом.

Замечание

Может существовать несколько минимальных элементов и только один наименьший.

Рис. 1. Слева частичный порядок: [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math] минимальны, но не сравнимы, поэтому наименьшего нет. Справа линейный порядок [math]\displaystyle{ x_1\prec x_2\prec x_3 }[/math]: у него есть наименьший элемент [math]\displaystyle{ x_1 }[/math].

Лемма:

Если на конечном непустом множестве $X$ задан линейный порядок, то существует наименьший элемент, и он единственен.

Для нахождения наименьшего элемента выберем произвольный элемент $x$ из $X$ и будем сравнивать его поочередно с остальными элементами из $X$. В силу линейности порядка, любой элемент из $X$ сравним с $x$. Если найдется какой-нибудь элемент $y\in X$, для которого $y\prec x$, то по свойству транзитивности окажется, что $y$ предшествует всем уже просмотренным нами ранее элементам множества $X$ (то есть является для всех просмотренных наименьшим). Продолжим перебор элементов, сравнивая теперь оставшиеся элементы из $X$ с элементом $y$, пока не найдем такой $z\in X$, что $z\prec y$. И так далее. Будем повторять процесс, пока не переберем все элементы из $X$. Элемент, выбранный для сравнения с остальными на тот момент и будет наименьшим элементом множества $X$.

Единственность следует из определения наименьшего элемента и антисимметричности отношения порядка. Действительно, если бы существовало два наименьших элемента $x$ и $y$ ($x\neq y$), то по определению наименьшего элемента $x\prec y$ и $y\prec x$. Из этого по свойству антисимметричности отношения порядка следовало бы $x=y$.

Теорема:

Пусть на конечном непустом множестве $X$ задан линейный порядок.

Тогда на $X$ можно выбрать такую нумерацию элементов $x_1, x_2, ..., x_n$ $(X=\{x_1,x_2,...,x_n\})$,

что соотношение $x_i\prec x_j$ $(x_i\preceq x_j\textrm{ и }x_i\neq x_j)$ будет выполняться в том и только в том случае, когда $i < j$.

Согласно лемме о существовании наименьшего элемента, для множества $X$ существует наименьший элемент, то есть такой $x_1\in X$, что $x_1\prec y$ для любых $y\in X$. Удалим элемент $x_1$ из множества $X$.

Множество $X\setminus\{x_1\}$ также удовлетворяет условиям леммы и, значит, в нем тоже существует наименьший элемент — $x_2$.

Мы можем повторять этот процесс до тех пор, пока в множестве $X$ не закончатся элементы. По способу выбора элементов $x_i$ очевидно, что $x_1, x_2, ..., x_n$ и есть искомая нумерация.

Следствие:

Пусть на конечном непустом множестве $X$ задано отношение нестрогого линейного порядка $\preceq$.

Тогда на $X$ можно выбрать такую нумерацию элементов $x_1, x_2, ..., x_n$ ($X=\{x_1,x_2,...,x_n\}$),

что соотношение $x_i\preceq x_j$ будет выполняться в том и только в том случае, когда $i \leq j$.

Если убрать из отношения $\preceq$ все пары $(x,x)$, для $x\in X$, получим отношение строгого линейного порядка $\preceq'$. На отношении $\preceq'$ по теореме можно ввести нумерацию $x_1, x_2, ..., x_n$. Проверим, что эта нумерация удовлетворяет нашим требованиям для исходного отношения $\preceq$.

Пусть $x_i\preceq x_j$. Тогда либо $x_i=x_j$, либо $x_i\preceq' x_j$. В первом случае $i=j$ и, следовательно, $i\leq j$. Во-втором случае по теореме из $x_i\preceq' x_j$ следует $i<j$ и, следовательно, $j\leq j$.

Пусть теперь $i\leq j$. Тогда, если $i=j$, то по свойству рефлексивности отношения частичного порядка выполняется $x_i\preceq x_j$. А если $i < j$, то по построению нумерации элементов выполняется $x_i \preceq' x_j$ и, следовательно, $x_i\preceq x_j$.

Следствие:

Пусть на конечном непустом множестве $X$ задано отношение линейного порядка $\rho$.

Тогда на $X$ можно выбрать такую нумерацию элементов $x_1, x_2, ..., x_n$ ($X=\{x_1,x_2,...,x_n\}$), что:

1) из $x_i \rho x_j$ следует $i\leq j$;

2) из $i < j$ следует $x_i\rho x_j$.

Доказательство аналогично доказательству следствия.

Определение:

Два нестрого упорядоченных множества $X$ и $Y$ называются изоморфными, если существует биекция $\varphi: X\rightarrow Y$, сохраняющая отношение нестрогого порядка.

Иными словами, если $\preceq_x$ и $\preceq_y$ отношения нестрогого порядка соответственно множеств $X$ и $Y$, то

[math]\displaystyle{ x_1 \preceq_x x_2 \quad \Longleftrightarrow \quad\varphi(x_1) \preceq_y \varphi(x_2). }[/math]

Теорема:

Всякое нестрого упорядоченное множество $X$ изоморфно некоторой системе подмножеств множества $X$, нестрого упорядоченной отношением включения.

Доказательство:

Пусть $\preceq$ — отношение нестрогого порядка на множестве $X$. Для каждого элемента $a\in X$ рассмотрим множество $S_a=\{x\in X

[math]\displaystyle{ \blacksquare }[/math]

Конспект: Дискретная математика