Алгебра. Ткач Л.И. - 29 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

BA
<< и
были полными. Чтобы получить полный порядок, определим его так:
()( )
2121212211
иилиесли,;; bbaaaababa
BA
<<< = .
5. Бинарное отношение равенства является частичным порядком на любом непустом множестве
A:
baba
=
⇔
<
. Для
такого частичного порядка никакие два различных элемента не сравнимы.
Понятие отношения порядка (полного или частичного) на множестве
A можно уточнить. Пусть A − непустое множество.
Определение 5.3.3. Бинарное отношение
<
на множестве A называется отношением строгого порядка на множестве
A
(или строгим порядком на множестве A), если оно обладает следующими свойствами:
1) транзитивность;
2) антисимметричность;
3) антирефлексивность.
Определение 5.3.4. Бинарное отношение < на множестве A называется отношением нестрогого порядка на множест-
ве A
(или нестрогим порядком на множестве A), если оно обладает следующими свойствами:
1) транзитивность;
2) антисимметричность;
3) рефлексивность.
Конечно, бинарное отношение
< на множестве A является отношением строгого (нестрогого) порядка на множестве A,
если оно является отношением частичного порядка на множестве
A и антирефлексивно (рефлексивно).
Отношение строгого (нестрогого) порядка на множестве
A обозначается, как правило, символом
p
(×), что является,
очевидно, отражением символа
< (≤). Используя эти символы можно записать: x ×y ⇔
x
yp
или x = y, т.е. если к бинарному
отношению
p
добавить все элементы вида (x; x), то получим бинарное отношение × и, наоборот, если из бинарного отношения ×
удалить элементы вида (
x; x), то получим бинарное отношение
p
.
Примеры.
1. Бинарное отношение
< (≤) на любом непустом подмножестве R является отношением полного строгого (нестрогого)
порядка.
2. На множестве функций с действительными аргументами и значениями можно ввести частичный строгий (нестрогий)
порядок, считая, что
fgp
( f × g), если
() ()
f
xgx<
(
(
)
(
)
f
xgx≤
).
3. На буквах русского алфавита традиционно определяется некоторый порядок (а
p
б
p
в
p
…
p
я). Этот порядок яв-
ляется полным строгим.
4. На словах русского алфавита определен
лексикографический порядок (как в словарях). Этот порядок можно опреде-
лить так: если слово
x является началом слова y, то x
p
y (например, маг
p
магистр). Если ни одно из слов не является нача-
лом другого, смотрим на первую по порядку букву, в которой слова отличаются: то слово, где эта буква меньше в алфавит-
ном порядке, и будет меньше. Этот порядок также полный (что иначе бы делали составители словарей?) и строгий.
Пусть
A − частично упорядоченное множество.
Определение 5.3.5. Элемент a ∈ A называется наименьшим (наибольшим) в множестве A, если для любого x ∈ A, x ≠ a
верно
a < x (x < a).
Определение 5.3.4. Полностью упорядоченное множество называется вполне упорядоченным, если каждое его непустое
подмножество имеет наименьший элемент.
Очевидно, что любое частично упорядоченное множество имеет только один наименьший (наибольший) элемент.
Примеры.
1. Любое конечное полностью упорядоченное множество является вполне упорядоченным.
2. Множество
N, очевидно, вполне упорядоченное.
3. Множество
Z, взятое в естественном порядке: …, –3,–2,–1, 0, 1, 2, 3, … не является вполне упорядоченным.
Теорема 5.3.1. (Теорема Цермело) Всякое множество путем введения некоторого отношения порядка можно сделать вполне
упорядоченным.
Пример. Как мы уже знаем, множество Z, взятое в естественном порядке, не является вполне упорядоченным. Но, рас-
положив его элементы в специальном порядке, например 0, –1, 1, –2, 2, …, мы можем сделать его вполне упорядоченным.
5.4. ТРАНСФИНИТНАЯ ИНДУКЦИЯ
Очень часто при доказательстве математических утверждений используется метод математической индукции, состоя-
щий в следующем.
Пусть имеется некоторое утверждение
P(n), которое формулируется для каждого натурального числа n. Если:
1) утверждение
P(1) верно,
2) из того, что
P(k) верно для всех k ≤ n следует, что P(n + 1) верно,
то утверждение
P(n) верно для любого n ∈ N.
Аналогичный метод доказательств может быть использован с заменой натуральных чисел на любое вполне упорядо-
ченное множество. В этом случае он носит название
трансфинитной индукции. Итак, метод трансфинитной индукции со-
стоит в следующем.
Пусть дано некоторое утверждение
P(a), формулируемое для каждого a ∈ A, где A − вполне упорядоченное множество.
Если:
1) верно утверждение
P(a
1
), где a
1
– наименьший элемент множества A;
2) из того, что утверждение
P(a) верно для всех a × b (a ≠ b) следует, что P(b) верно,
тогда
P(a) верно для всех a ∈ A.
Действительно, если бы существовали элементы в
A, для которых P(a) не имеет места, то в множестве таких элементов
нашелся бы наименьший, обозначим его
a′ (очевидно a
1
× a′), и мы пришли бы к противоречию, так как для всех a
× a′ (a ≠ a)
утверждение
P(a) было бы верно и в силу 2) P(a′) тоже должно быть верно.

Страницы