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

Бінарне відношення 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 } не порівнюються відносно Í.