11. Отношение предпорядка, упорядоченности, строгой упорядоченности. Отношение частичного порядка.

Отношения порядка

• Отношения частичного порядка

• Отношения полного или линейного порядка

• Отношения строгого порядка

• Отношения нестрогого порядка

Отношение частичного и полного порядка.

Подмножество называется местным ( мерным) отношением на множестве А. Говорят, что элементы находятся в отношении , если .

Наиболее часто встречающимися и хорошо изученными являются двухместные или бинарные отношения.

Бинарное отношение R в множестве М, обладающее следующими свойствами:

• рефлексивности: (a M) ((a,a)R);

• антисимметричности: (a,b M) (((a,b)R) и (b,a)R)╚ a=b);

• транзитивности: (a,b,c M) (((a,b)R) и (b,c)R) (a,c)R)

называется отношением упорядоченности и может быть обозначено: . Бинарное отношение R в множестве М, обладающее следующими свойствами:

• антирефлексивности: (a M) ((a,a) R);

• антисимметричности: (a,b M) (((a,b)R) и (b,a)R)╚ a=b);

• транзитивности: (a,b,c M) (((a,b)R) и (b,c)R) (a,c)R)

называется отношением строгой упорядоченности и может быть обозначено: . Бинарное отношение R в множестве М, обладающее следующими свойствами:

• рефлексивности: (a M) ((a,a)R);

• транзитивности: (a,b,c M) (((a,b)R) и (b,c)R) (a,c)R)

называется отношением предпорядка.

Отношение r называется отношением полного порядка (полным порядком), если оно транзитивно, антисимметрично и антирефлексивно (либо транзитивно и ассиметрично).

Отношения частичного порядка, то есть рефлексивные, антисимметричные и транзитивные.

Примеры:

а) Отношения “ ” и “ ” являются отношениями нестрогого порядка, отношения “<” и “>” – отношениями строгого порядка (на всех основных числовых множествах). Оба отношения полностью упорядочивают множества и .

б) Отношение подчинённости в трудовом коллективе создаёт строгий частичный порядок. В нём, например, несравнимыми являются сотрудники различных структурных подразделений (отделов и т. п.).

в) На системе подмножеств множества отношение включения “ ” задаёт нестрогий частичный порядок, а отношение строгого включения “ ” задаёт строгий частичный порядок. Например, , а и не сравнимы.

Отношение R называется:

a) эквивалентностью, если оно рефлексивно, симметрично и транзитивно

b) толерантностью, если оно рефлексивно и симметрично;

c) предпорядком, если оно рефлексивно и транзитивно;

d) порядком, если оно транзитивно и антисимметрично.