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

редактировать

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

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

Невозможно, чтобы два элемента были меньше другого. То есть $∀ x, y: ¬ (x < y ∧ y < x) {\displaystyle \forall x,y:\neg \;(x$ ${\ displaystyle \ forall x, y: \ neg \; (x <y \; \ wedge \; y <x)}$ .
Для всех x, y и z, если x < y then either x < z or z < y. That is, $∀ x, y, z: x < y → ( x < z ∨ z < y) {\displaystyle \forall x,y,z:x$ ${\ Displaystyle \ forall x, y, z: x <y \; \ to \; (x <z \; \ vee \; z <y)}$ .
Каждые два элемента, для которых ни один из них не является меньше другого должно быть равно. То есть $∀ x, y: ¬ (x < y ∨ y < x) → x = y {\displaystyle \forall x,y:\neg \;(x$ ${\ displaystyle \ forall x, y: \ neg \; (x <y \; \ vee \; y <x) \; \ to \; x = y}$

Это первое условие просто асимметрия. Из первых двух условий следует, что псевдопорядок является транзитивным. Второе условие часто называется ко-транзитивностью или сравнением и является конструктивным заменителем трихотомии. Как правило, для двух элементов псевдоупорядоченного множества это не всегда бывает, что один из них меньше другого или они равны, но при любом нетривиальном интервале любой элемент находится либо выше нижней границы, либо ниже верхней границы.

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

x # y ↔ x < y ∨ y < x {\displaystyle x\#y\;\leftrightarrow \;x

{\ displaystyle x \ #y \; \ leftrightarrow \; Икс <Y \; \ Vee \; Y <X}

, а равенство определяется отрицанием отделенности.

Отрицание псевдопорядка - это частичный порядок, который близко к общему порядку : если x ≤ y определяется как отрицание y < x, then we have

¬ (¬ (x ≤ y) ∧ ¬ (y ≤ x)). {\ displaystyle \ neg \; (\ neg \; (x \ leq y) \; \ wedge \; \ neg \; (y \ leq x)).}

{\ displaystyle \ neg \; (\ neg \; (x \ leq y) \; \ клин \; \ neg \; (y \ leq x)).}

Используя классическую логику один затем пришел бы к выводу, что x ≤ y или y ≤ x, так что это будет полный порядок. Однако этот вывод неверен в конструктивном случае.

Типичный псевдопорядок - это псевдопорядок действительных чисел: одно действительное число меньше другого, если существует (можно построить) рациональное число, большее, чем первое, и меньшее, чем последнее. Другими словами, x < y if there exists a rational number z such that x < z < y.

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

Второе условие само по себе заслуживает рассмотрения. Это называется ко-транзитивностью, поскольку отношение транзитивно , если его дополнение удовлетворяет условию 2. Более того, его следующие свойства могут быть доказаны с помощью классической логики.

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

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

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

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

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

Примечания

Ссылки

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