Еще больше мяулога

Задача 82

Нам дан какой-то порядок (R_𝑖), в котором ∃a,b∈A:¬(a≼b)∧¬(b≼a)

Построим порядок (R_i+1), в котором мы делаем эти эти элементы сравнимыми. Пусть (R_i+1)=(R_i)∪{[(x,y),x≼a∧b≼y]}. Это добавит в отношение пару (a,b) и еще набор пар, нужный для сохранения свойств порядка. Проверим, что это тоже порядок:

• Рефлексивность: очевидно из рефлексивности (R_i)

• Транзитивность: ∀x,y,z:(x≼y)∧(y≼z)→x≼z.

  • Для y∈{a,b} это следует из пар, которые мы добавили:

    • Если y=a: x→a→b→z

    • Если y=b:y→b→z

  • Для всех остальных элементов это выполняется из транзитивности (R_i)

• Антисимметричность: если (x≼y)∧(y≼x), то это не может быть (a,b), так как ¬(b≼a), и не могут быть элементы из добавленных пар (потому что между ними есть a и b в порядке). Остальные элементы (не равные) тоже не могут иметь такое свойство из антисимметричности (R_i)

Значит, (R_i+1) - частичный порядок. Но несравнимых элементов там стало меньше. Значит, что когда-нибудь пары несравнимых элементов закончатся, и мы получим Q. ЧТД