Псевдо-порядок

В конструктивной математике псевдопорядок — это имя, данное определенным бинарным отношениям, подходящим для моделирования непрерывного порядка.

В классической математике ее аксиомы представляют собой формулировку строгого полного порядка (также называемого линейным порядком), который в этом контексте также может быть определен другими, эквивалентными способами.

Примеры

Конструктивная теория действительных чисел является типичным примером, в котором формулировка псевдопорядка становится решающей. Действительное число меньше другого, если существует (можно построить) рациональное число, большее первого и меньше второго. Другими словами, здесь x < y имеет место, если существует такое рациональное число z, что x < z < y .Примечательно, что для континуума в конструктивном контексте обычный закон трихотомии не выполняется, т.е. он не доказуем автоматически. Таким образом, аксиомы при описании подобных порядков слабее (при работе с использованием только конструктивной логики), чем альтернативные аксиомы строгого тотального порядка, которые часто используются в классическом контексте.

Определение

Псевдопорядок — это бинарное отношение, удовлетворяющее трем условиям:

• Невозможно, чтобы каждый из двух элементов был меньше другого. То есть для всех $x$ и $y$,

$\neg (x<y\land y<x)$

• Каждые два элемента, для которых ни один из них не меньше другого, должны быть равны. То есть для всех $x$ и $y$,

$\neg (x<y\lor y<x)\to x=y$

• Для всех x , y и z , если x < y, то либо x < z, либо z < y . То есть для всех $x$, $y$ и $z$,

$x<y\to (x<z\lor z<y)$

Вспомогательные обозначения

Существуют общие конструктивные переформулировки, использующие противопоставления и действительные эквиваленты. $\neg (\phi \land \psi )\leftrightarrow (\phi \to \neg \psi )$ а также $\neg (\phi \lor \psi )\leftrightarrow (\neg \phi \land \neg \psi )$. Отрицание псевдопорядка $x<y$ двух элементов определяет рефлексивный частичный порядок $y\leq x$. В этих терминах первое условие гласит:

$x<y\to x\leq y$

и это на самом деле просто асимметрию выражает $x<y$. Это подразумевает иррефлексивность , знакомую из классической теории.

Классические

Второе условие в точности выражает антисимметрию ассоциированного частичного порядка:

$(x\leq y\land y\leq x)\to x=y$

При двух приведенных выше переформулировках знаки отрицания могут быть скрыты в определении псевдопорядка.

Естественное отношение отделенности на псевдоупорядоченном множестве задается формулой $x\#y:=(x<y\lor y<x)$. При этом второе условие точно утверждает, что это соотношение является тесным,

$\neg (x\#y)\to x=y$

Вместе с первой аксиомой это означает, что равенство можно выразить как отрицание обособленности. Обратите внимание, что отрицание равенства, как правило, представляет собой просто двойное отрицание обособленности.

Теперь дизъюнктивный силлогизм может быть выражен как $(\phi \lor \psi )\to (\neg \phi \to \psi )$. Такое логическое следствие классически можно обратить, и тогда это условие в точности выражает трихотомию. По сути, это также формулировка связности .

Обсуждение

Асимметрия

Принцип непротиворечия для частичного порядка гласит, что $\neg {\big (}x\leq y\land \neg (x\leq y))$ или эквивалентно $\neg \neg {\big (}x\leq y\lor y<x)$, для всех элементов. Конструктивно обоснованность двойного отрицания в точности означает, что не может быть опровержений ни одного из дизъюнкций в классическом утверждении. $\forall x.\forall y.\neg (y<x)\lor (y<x)$независимо от того, представляет ли это предложение разрешимую проблему .

Используя условие асимметрии, из вышеизложенного также следует $\neg \neg (x\leq y\lor y\leq x)$, дважды отрицательная сильная связность . В контексте классической логики « $\leq$«таким образом, представляет собой (нестрогий) тотальный порядок .

Котранзитивность

Противоположность третьего условия в точности выражает, что ассоциированное отношение $x\leq y$ (частичный порядок) транзитивен. Это свойство называется котранзитивностью . Используя условие асимметрии, можно быстро вывести теорему о том, что псевдопорядок на самом деле транзитивен также . Транзитивность — общая аксиома классического определения линейного порядка.

Условие, также называемое сравнением (а также слабой линейностью ): для любого нетривиального интервала, заданного некоторым $x$ и некоторые $y$ над ним любой третий элемент $z$ находится либо выше нижней границы , либо ниже верхней границы. Поскольку это следствие дизъюнкции, оно также связано с законом трихотомии. И действительно, наличие псевдопорядка в ЧУМ, полном по Дедекинду-МакНилу, подразумевает принцип исключенного третьего. Это влияет на обсуждение полноты конструктивной теории действительных чисел.

Связь с другими объектами недвижимости

В этом разделе предполагается классическая логика. По крайней мере, тогда можно доказать следующие свойства:

Если R — котранзитивное отношение, то

• R также квазитранзитивен ;
• R удовлетворяет аксиоме 3 полупорядков ;
• несравнимость относительно R — транзитивное отношение; и
• R связно тогда и только тогда, когда оно рефлексивно .

Достаточными условиями для того, чтобы котранзитивное отношение R было транзитивным, также являются:

• R — левоевклидово ;
• R — правоевклидово;
• R антисимметричен ​ .

Полусвязное отношение R также является котранзитивным, если оно симметрично , лево- или право-евклидово, транзитивно или квазитранзитивно. Если несравнимость относительно R является транзитивным отношением, то R является котранзитивным, если оно симметрично, лево- или правоевклидово или транзитивно.

См. также

• Конструктивный анализ
• Неразложимость (интуиционистская логика)
• Линейный порядок

Ссылки

• Хейтинг, Аренд (1966). Интуиционизм: введение (2-е изд.). Амстердам: Паб Северной Голландии. Компания р. 106 .