Бінарне відношення 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} не рефлексивне (й не транзитивне), отже, воно не є частковим порядком на А. Відношення А2 на будь-якій множині А, що має понад один елемент, не антисимет-ричне (містить пари виду <x,y> та <y,x>, де x¹y), тому не є частковим порядком на А. Відношення іА на будь-якій множині А є частковим порядком на А. Відношення включення Í на булеані деякої множини А є частковим порядком, оскільки воно рефлексивне (ХÍХ для будь-якої підмножини Х множини А), антисиметричне (якщо Х та Y – підмножини множини А й XÍY та YÍX, то X=Y), транзитивне (якщо X, Y – підмножини множини А й XÍY та YÍZ, то XÍZ).
Теорема 9. Нехай R та R1 – часткові порядки на А. Довести, що:
а) RÇR1 – частковий порядок на А;
б) R-1 – частковий порядок на А.
Доведення. Покажемо, що відношення RÇR1 рефлексивне, антисиметричне, транзитивне. Оскільки R та R1 – часткові порядки на А, то відношення R та R1 рефлексивні, а тоді й відношення RÇR1 рефлексивне. Нехай <x,y>ÎRÇR1 та <y,x>ÎRÇR1. Тоді <х,у>ÎR й <у,х>ÎR, звідки х=у в силу антисиметричності R. Нехай <x,y>ÎRÇR1 та <y,z>ÎRÇR1. Тоді <x,y>ÎR, <y,z>ÎR, <x,y>ÎR1, <y,z>ÎR1, звідки <x,z>ÎR та <x,z>ÎR1 в силу транзитивності R та R1. Отже, <x,z>ÎRÇR1. Таким чином, RÇR1 є частковим порядком на А.
Як відомо (див. задачі 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} не порівнюються відносно Í.
