Відношення часткового порядку

Бінарне відношення R, задане на множині А, називається відношенням часткового порядку (частковим порядком на А), якщо R рефлексивне, антисиметричне, транзитивне. Множина А, на якій задано відношення часткового порядку, називається частково упорядкованою. Множину А, частково упорядковану відношенням R, позначатимемо <A,R>. Часто відношення часткового порядку позначається символом £.

Наприклад, відношення R={<1,2>,<2,2>,<1,3>,<3,3>,<1,1>,<4,4>}, задане на множині А={1,2,3,4}, є рефлексивним, антисиметричним та транзитивним, отже, є частковим порядком на А. Прикладами відношень часткового порядку є відношення ³ та £ на множині R. Відношення {<1,2>,<1,1>,<2,1>} на множині А={1,2} не рефлексивне (й не транзитивне), отже, воно не є частковим порядком на А. Відношення А² на будь-якій множині А, що має понад один елемент, не антисимет-ричне (містить пари виду <x,y> та <y,x>, де x¹y), тому не є частковим порядком на А. Відношення і_А на будь-якій множині А є частковим порядком на А. Відношення включення Í на булеані деякої множини А є частковим порядком, оскільки воно рефлексивне (ХÍХ для будь-якої підмножини Х множини А), антисиметричне (якщо Х та Y – підмножини множини А й XÍY та YÍX, то X=Y), транзитивне (якщо X, Y – підмножини множини А й XÍY та YÍZ, то XÍZ).

Теорема 9. Нехай R та R₁ – часткові порядки на А. Довести, що:

а) RÇR₁ – частковий порядок на А;

б) R^-1 – частковий порядок на А.

Доведення. Покажемо, що відношення RÇR₁ рефлексивне, антисиметричне, транзитивне. Оскільки R та R₁ – часткові порядки на А, то відношення R та R₁ рефлексивні, а тоді й відношення RÇR₁ рефлексивне. Нехай <x,y>ÎRÇR₁ та <y,x>ÎRÇR₁. Тоді <х,у>ÎR й <у,х>ÎR, звідки х=у в силу антисиметричності R. Нехай <x,y>ÎRÇR₁ та <y,z>ÎRÇR₁. Тоді <x,y>ÎR, <y,z>ÎR, <x,y>ÎR₁, <y,z>ÎR₁, звідки <x,z>ÎR та <x,z>ÎR₁ в силу транзитивності R та R₁. Отже, <x,z>ÎRÇR₁. Таким чином, RÇR₁ є частковим порядком на А.

Як відомо (див. задачі XXXI, XXXIV, XXXVI до попереднього розділу), відношення R^-1 рефлексивне, антисиметричне та транзитивне, якщо таким є відношення R, отже, відношення, обернене до часткового порядку, є частковим порядком.

Бінарне відношення R, задане на множині А, називається відношенням строгого порядку на А (строгим порядком на А), якщо R антирефлексивне та транзитивне. Часто відношення строгого порядку позначається символом <.

Наприклад, відношення {<1,2>,<1,3>,<1,4>} є строгим порядком на множині {1,2,3,4,5}. Прикладами відношень строгого порядку на множині N є відношення < та >. Відношення Р на множині людей, задане умовою хРу Û х є предком у, є антирефлексивним та транзитивним, отже, є відношенням строгого порядку. Відношення М на множині людей, задане умовою хМу Û х – мати у, є антирефлексивним, але не є транзитивним, отже, й не є відношенням строгого порядку.

Бінарне відношення R, задане на множині А, називається відношенням передпорядку на А (передпорядком на А), або відношенням квазіпорядку на А (квазіпорядком на А), якщо R рефлексивне та транзитивне.

Зрозуміло, що будь-який частковий порядок на множині А є також передпорядком на А.

Наприклад, відношення R={<1,1>,<2,3>,<2,2>,<3,2>,<3,3>} та S={<2,2>, <2,3>,<3,3>,<1,1>} є передпорядками на множині А={1,2,3}; S є частковим порядком на А, а R – ні. Відношення строгого порядку не є передпорядком. Відношення {<1,1>,<2,2>,<3,3>,<2,1>,<3,2>} на множині А={1,2,3} не транзитивне, отже, не є передпорядком на А.

Нехай R – частковий порядок на А. Елементи х та у множини А називаються такими, що порівнюються відносно часткового порядку R, якщо <x,y>ÎR або <y,x>ÎR.

Розглянемо, наприклад, частковий порядок R={<1,1>,<1,2>,<2,2>, <3,3>} на множині A={1,2,3}. Оскільки хRх для кожного елемента х з множини А, то 1 та 1, 2 та 2, 3 та 3 порівнюються відносно R. Елементи 1 та 2 також порівнюються відносно R. 1 та 3, а також 2 та 3 не порівнюються відносно R. Розглянемо відношення включення на булеані множини {a,b,c}. Оскільки {a}Ë{b} й {b}Ë{a}, то {a} та {b} не порівнюються відносно Í.