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

Отношение порядкабинарное отношение (далее обозначаемое или ) между элементами данного множества, по своим свойствам сходное со свойствами отношения неравенства[⇨].

Множество, все элементы которого сравнимы заданным отношением порядка (то есть для любых либо , либо ), называется линейно упорядоченным, а отношение порядка называется линейным порядком. Если же сравнимы не все неравные элементы, порядок называется частичным, а множество — частично упорядоченным. Различают также строгий порядок , при котором невозможно, и нестрогий в противном случае[1].

Примеры[1].

  • Отношение для вещественных чисел определяет для них нестрогий линейный порядок..
  • Отношение для вещественных чисел определяет для них строгий линейный порядок..
  • Отношение делимости на множестве натуральных чисел: если является делителем Это нестрогий частичный порядок, так как не всякие натуральные числа делятся друг на друга без остатка.
  • Отношение включения на множестве подмножеств заданного множества также определяет нестрогий частичный порядок.
  • Отношение (предок, потомок) на популяции животных является строгим частичным порядком.

ОпределенияПравить

Отношение нестрогого (рефлексивного) частичного порядка ( ) на множестве   — это бинарное отношение, для которого при любых   из   выполнены следующие условия[2]:

  1. Рефлексивность:  .
  2. Антисимметричность: если   и  , то  .
  3. Транзитивность: если   и  , то  .

Удобно также дополнительно определить для отношения   отношение строгого (антирефлексивного) порядка ( ) на том же множестве[1]:

 , если   и при этом  

Свойства строгого отношения отличаются от свойств нестрогого:

  1. Антирефлексивность:  ;
  2. Асимметричность: если  , то  ;
  3. Транзитивность: если   и  , то  .

2-е свойство не является независимым, оно следует из антирефлексивности и транзитивности. Поэтому отношение является отношением строгого порядка тогда и только тогда, когда оно антирефлексивно и транзитивно.

Множество  , на котором введено отношение строгого или нестрогого порядка, называется частично упорядоченным. Если к тому же для любых элементов   дополнительно выполняется одно из условий:   или   то порядок называется линейным, а множество — линейно упорядоченным[2].

ИсторияПравить

Знаки   и   предложил английский учёный Томас Хэрриот в своём сочинении, изданном посмертно в 1631 году[3].

Определение частично упорядоченного множества впервые явно сформулировал Ф. Хаусдорф [4], хотя аналогичные аксиомы порядка рассматривались еще Г. Лейбницем около 1690 года. Определение линейно упорядоченного и вполне упорядоченного множеств впервые дано Г. Кантором[5].

Вариации и обобщенияПравить

Если упорядоченное множество образует какую-либо алгебраическую структуру, то обычно требуется, чтобы порядок в этой структуре был согласован с алгебраическими операциями. См. об этом статьи:

Иногда полезно рассматривать отношения, для которых выполняются только первая и третья аксиомы (рефлексивность и антисимметричность); такие отношения называются предпорядком или квазипорядком. Если   — квазипорядок, то отношение, заданное формулой[6].

  если   и  

будет отношением эквивалентности. На фактормножестве по этой эквивалентности можно определить нестрогий порядок следующим образом[6]:

  если  

где   — класс эквивалентности, содержащий элемент  

См. такжеПравить

ПримечанияПравить

  1. 1 2 3 Курош, 1973, с. 16, 20—22.
  2. 1 2 Нечаев, 1975, с. 78.
  3. Александрова Н. В. История математических терминов, понятий, обозначений: Словарь-справочник. — 3-е изд. — СПб.: ЛКИ, 2008. — С. 111—112. — 248 с. — ISBN 978-5-382-00839-4.
  4. Hausdorff F. Grundzuge der Mengenlehre, Lpz., 1914.
  5. Частично упорядоченное множество // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1985. — Т. 5. — С. 833—836. — 1248 с.
  6. 1 2 Порядок // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1984. — Т. 4. — С. 505. — 1216 с.

ЛитератураПравить