Леми про най... елементи
Лема 2
В частково впорядкованій множині найменший (найбільший) елемент є єдиним мінімальним (максимальним)
Припустимо x1 – найменьш., а x2 – мінімальн.
x1 – найменш. x1≤x2 |
} |
x2 – мінімальн. |
x |
= x |
|
||||
x2 – мінімальн. |
|
1 |
2 |
|
|
|
|
21
Відношення лінійного порядку
Відношенням лінійного порядку
на множині A будемо називати рефлексивне, антисиметричне, транзитивне та порівняльне бінарне відношення на множині A.
1. |
Рефлексивне |
3. Транзитивне |
|
x A xRx |
xRy, yRz xRz |
2. Антисиметричне |
4. Порівняльне |
|
|
xRy yRx x=y |
x,y A xRy yRx |
22
Означення
Множина називається лінійно впорядкованою, якщо на ній задано відношення лінійного порядку
23
Лема 3
В лінійно впорядкованій множині мінімальний (максимальний) елемент є найменшим (найбільшим)
x0 – мінімальний, x A |
в силу порівняльності |
x≤x0 |
оскільки x0 мінімальний x0=x |
x0≤x |
x0≤x
В обох випадках x0≤x
24