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

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

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

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

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

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

${\displaystyle \neg (x<y\land y<x)}$

• Любые два элемента, ни один из которых не меньше другого, должны быть равны. То есть, для всех и ,${\displaystyle x}$${\displaystyle у}$

${\displaystyle \neg (x<y\lor y<x)\to x=y}$

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

${\displaystyle x<y\to (x<z\or z<y)}$

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

${\displaystyle x<y\to x\leq y}$

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

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

${\displaystyle (x\leq y\land y\leq x)\to x=y}$

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

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

${\displaystyle \neg (x\#y)\to x=y}$

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

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

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

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

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

Условие также называется сравнением (а также слабой линейностью ): для любого нетривиального интервала, заданного some и some выше него, любой третий элемент находится либо выше нижней границы , либо ниже верхней границы. Поскольку это следствие дизъюнкции, оно также связано с законом трихотомии. И действительно, наличие псевдопорядка на Dedekind-MacNeille-полном частично упорядоченном множестве подразумевает принцип исключенного третьего. Это влияет на обсуждение полноты в конструктивной теории действительных чисел.${\displaystyle x}$${\displaystyle у}$${\displaystyle z}$

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

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

• R также квазитранзитивен ;
• R удовлетворяет аксиоме 3 полупорядков ; ^{[примечание 1]}
• несравнимость относительно R является транзитивным отношением; ^{[примечание 2]} и
• R является связным тогда и только тогда, когда оно рефлексивно . ^{[примечание 3]}

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

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

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

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

• Гейтинг, Аренд (1966). Интуиционизм: введение (2-е изд.). Амстердам: North-Holland Pub. Co. стр. 106.