СВ в 08:41, 28 октября 2026

2026-10-28T08:41:53Z

← Предыдущая		Версия 08:41, 28 октября 2026
Строка 43:		Строка 43:
	\|content=Может существовать несколько минимальных элементов и только один наименьший.		\|content=Может существовать несколько минимальных элементов и только один наименьший.
	}}		}}
			[[Файл:p12-01-partial-vs-linear.svg\|мини\|800px\|alt=Частичный порядок с двумя минимальными элементами без наименьшего и линейный порядок с наименьшим элементом x1\|Рис. 1. Слева частичный порядок: <math>a</math> и <math>b</math> минимальны, но не сравнимы, поэтому наименьшего нет. Справа линейный порядок <math>x_1\prec x_2\prec x_3</math>: у него есть наименьший элемент <math>x_1</math>.]]

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

СВ в 19:14, 9 октября 2026

2026-10-09T19:14:06Z

← Предыдущая		Версия 19:14, 9 октября 2026
Строка 125:		Строка 125:
	Таким образом, биекция $\varphi$ сохраняет отношение нестрогого порядка.		Таким образом, биекция $\varphi$ сохраняет отношение нестрогого порядка.
	}}		}}

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

СВ: Новая страница: «{{Определение |definition= Бинарное отношение $\rho$ на множестве $X$ называется отношением поряд...»

2026-10-09T18:58:01Z

Новая страница: «{{Определение |definition= Бинарное отношение $\rho$ на множестве $X$ называется отношением поряд...»

Новая страница

{{Определение
|definition=
Бинарное отношение $\rho$ на множестве $X$ называется отношением порядка, если оно транзитивно и антисимметрично. Множество, на котором введено отношение порядка, называют упорядоченным.
}}
Множество всех пар $(x,y)$ людей, для которых $x$ старше $y$, является отношением порядка.
{{Определение
|definition=
Отношение порядка $\preceq$ называется отношением нестрогого (частичного) порядка на множестве X, если оно рефлексивно.
}}
{{Определение
|definition=
Отношение порядка $\prec$ называется отношением строгого порядка на множестве $X$, если оно иррефлексивно.
}}
{{Определение
|definition=
Отношение порядка $\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$,
называют ''отношением включения''.
Отношение включения является отношением нестрогого порядка и не является отношением линейного порядка.
{{Определение
|definition=
Пусть на множестве $X$ введено отношение порядка. Пусть элемент $x\in X$ таков, что не существует такого $y\in X$, $y\neq x$, что $y\prec x$.
Тогда $x$ называют минимальным элементом.
}}
{{Определение
|definition=
Пусть на множестве $X$ введено отношение порядка.
Пусть элемент $x\in X$ таков, что для любых $y\in X$, $y\neq x$, выполняется $x\prec y$.
Тогда $x$ называют наименьшим элементом.
}}
{{Замечание
|content=Может существовать несколько минимальных элементов и только один наименьший.
}}
{{Лемма
|statement=Если на конечном непустом множестве $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$.

{{Теорема
|statement=Пусть на конечном непустом множестве $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$ и есть искомая нумерация.

{{Следствие
|statement=Пусть на конечном непустом множестве $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$.

{{Следствие
|statement=Пусть на конечном непустом множестве $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$.
}}

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

{{Определение
|definition=
Два нестрого упорядоченных множества $X$ и $Y$ называются изоморфными, если существует биекция $\varphi: X\rightarrow Y$, сохраняющая отношение нестрогого порядка.
Иными словами, если $\preceq_x$ и $\preceq_y$ отношения нестрогого порядка соответственно множеств $X$ и $Y$, то
<math>
x_1 \preceq_x x_2 \quad \Longleftrightarrow \quad\varphi(x_1) \preceq_y \varphi(x_2).
</math>
}}
{{Теорема
|statement=Всякое нестрого упорядоченное множество $X$ изоморфно некоторой системе подмножеств множества $X$, нестрого упорядоченной отношением включения.
|proof=
Пусть $\preceq$ {{---}} отношение нестрогого порядка на множестве $X$.
Для каждого элемента $a\in X$ рассмотрим множество $S_a=\{x\in X | x\preceq a\}$.
Ясно, что $S_a \subseteq X$ для любого $a\in X$.

Покажем, что система подмножеств $\{S_a | a\in X\}$, упорядоченная отношением включения, есть искомая система подмножеств.
Рассмотрим отображение $\varphi: X \rightarrow \{S_a | a\in X\}$ такое, что $\varphi(a) = S_a$.

Если $S_a=S_b$, то, поскольку $a\in S_a$, то $b\in S_a$ и, следовательно, $b\preceq a$.
Аналогично, $a\preceq b$. Таким образом, в силу антисимметричности отношения $\preceq$, $a=b$. Значит, отображение $\varphi$ инъективно.

С другой стороны, у любого множества $S_a$ есть прообраз $a$. Значит, $\varphi$ сюръективно. Следовательно, $\varphi$ {{---}} биекция.

Пусть $a\preceq b$. Тогда из $x\preceq a$ в силу транзитивности отношения следует $x\preceq b$, а значит $S_a\subseteq S_b$.
Пусть $S_a\subseteq S_b$. Тогда, поскольку $a\in S_a$, то $a\in S_b$ и, следовательно, $a\preceq b$.
Таким образом, биекция $\varphi$ сохраняет отношение нестрогого порядка.
}}

Отношение порядка - История изменений

СВ в 08:41, 28 октября 2026

СВ в 19:14, 9 октября 2026

СВ: Новая страница: «{{Определение |definition= Бинарное отношение $\rho$ на множестве $X$ называется отношением поряд...»