Martin Escardo, April 2013.
Adapted to this development June 2018, with further additions.
Ordinals like in the HoTT book and variations.
\begin{code}
{-# OPTIONS --safe --without-K #-}
open import MLTT.Plus-Properties using (+-commutative)
open import MLTT.Spartan
open import UF.Base
open import UF.DiscreteAndSeparated
open import UF.ClassicalLogic
open import UF.FunExt
open import UF.Hedberg
open import UF.PropTrunc
open import UF.Sets
open import UF.Subsingletons
open import UF.Subsingletons-FunExt
module Ordinals.Notions
{π€ π₯ : Universe}
{X : π€ Μ }
(_<_ : X β X β π₯ Μ )
where
is-prop-valued : π€ β π₯ Μ
is-prop-valued = (x y : X) β is-prop (x < y)
data is-accessible : X β π€ β π₯ Μ where
acc : {x : X} β ((y : X) β y < x β is-accessible y) β is-accessible x
accessible-induction : (P : (x : X) β is-accessible x β π¦ Μ )
β ((x : X) (Ο : (y : X) β y < x β is-accessible y)
β ((y : X) (l : y < x) β P y (Ο y l))
β P x (acc Ο))
β (x : X) (a : is-accessible x) β P x a
accessible-induction P f = h
where
h : (x : X) (a : is-accessible x) β P x a
h x (acc Ο) = f x Ο (Ξ» y l β h y (Ο y l))
prev : {x : X}
β is-accessible x
β (y : X) β y < x β is-accessible y
prev (acc a) = a
prev-behaviour : (x : X) (a : is-accessible x)
β acc (prev a) οΌ a
prev-behaviour = accessible-induction _ (Ξ» _ _ _ β refl)
transfinite-induction' : (P : X β π¦ Μ )
β ((x : X) β ((y : X) β y < x β P y) β P x)
β (x : X) β is-accessible x β P x
transfinite-induction' P f = accessible-induction
(Ξ» x _ β P x)
(Ξ» x _ β f x)
\end{code}
Added 31 October 2022 by Tom de Jong.
We record the (computational) behaviour of transfinite induction for use in
other constructions.
\begin{code}
transfinite-induction'-behaviour :
(P : X β π¦ Μ ) (f : (x : X) β ((y : X) β y < x β P y) β P x)
(x : X) (a : is-accessible x)
β transfinite-induction' P f x a
οΌ f x (Ξ» y l β transfinite-induction' P f y (prev a y l))
transfinite-induction'-behaviour P f x (acc Ο) = refl
\end{code}
End of addition.
\begin{code}
is-well-founded : π€ β π₯ Μ
is-well-founded = (x : X) β is-accessible x
is-Well-founded : π€ β π₯ β π¦ βΊ Μ
is-Well-founded {π¦} = (P : X β π¦ Μ )
β ((x : X) β ((x' : X) β x' < x β P x') β P x)
β (x : X) β P x
transfinite-induction : is-well-founded β β {π¦} β is-Well-founded {π¦}
transfinite-induction w P f x = transfinite-induction' P f x (w x)
transfinite-induction-converse : is-Well-founded {π€ β π₯} β is-well-founded
transfinite-induction-converse Ο = Ο is-accessible (Ξ» _ β acc)
transfinite-recursion : is-well-founded
β β {π¦} {Y : π¦ Μ }
β ((x : X) β ((x' : X) β x' < x β Y) β Y)
β X β Y
transfinite-recursion w {π¦} {Y} = transfinite-induction w (Ξ» x β Y)
accessibility-is-prop : FunExt
β (x : X) β is-prop (is-accessible x)
accessibility-is-prop fe = accessible-induction P Ο
where
P : (x : X) β is-accessible x β π€ β π₯ Μ
P x a = (b : is-accessible x) β a οΌ b
Ο : (x : X) (Ο : (y : X) β y < x β is-accessible y)
β ((y : X) (l : y < x) (a : is-accessible y) β Ο y l οΌ a)
β (b : is-accessible x) β acc Ο οΌ b
Ο x Ο IH b = acc Ο οΌβ¨ i β©
acc Ο οΌβ¨ prev-behaviour x b β©
b β
where
Ο : (y : X) β y < x β is-accessible y
Ο = prev b
h : (y : X) (l : y < x) β Ο y l οΌ Ο y l
h y l = IH y l (Ο y l)
i = ap acc
(dfunext (fe π€ (π€ β π₯)) (Ξ» y β dfunext (fe π₯ (π€ β π₯)) (h y)))
\end{code}
Added 31 October 2022 by Tom de Jong.
We record the (computational) behaviour of transfinite induction/recursion for
use in other constructions.
\begin{code}
transfinite-induction-behaviour : FunExt β (w : is-well-founded)
{π¦ : Universe} (P : X β π¦ Μ )
(f : (x : X) β ((y : X) β y < x β P y) β P x)
(x : X)
β transfinite-induction w P f x
οΌ f x (Ξ» y l β transfinite-induction w P f y)
transfinite-induction-behaviour fe w {π¦} P f x =
transfinite-induction w P f x οΌβ¨ I β©
f x (Ξ» y l β transfinite-induction' P f y (prev (w x) y l)) οΌβ¨ II β©
f x (Ξ» y l β transfinite-induction' P f y (w y)) οΌβ¨ refl β©
f x (Ξ» y l β transfinite-induction w P f y) β
where
I = transfinite-induction'-behaviour P f x (w x)
II = ap (f x) (dfunext (fe π€ (π₯ β π¦))
(Ξ» y β dfunext (fe π₯ π¦)
(Ξ» l β ap (transfinite-induction' P f y) (e y l))))
where
e : (y : X) (l : y < x) β prev (w x) y l οΌ w y
e y l = accessibility-is-prop fe y (prev (w x) y l) (w y)
transfinite-recursion-behaviour : FunExt
β (w : is-well-founded)
{π¦ : Universe} {Y : π¦ Μ }
(f : (x : X) β ((y : X) β y < x β Y) β Y)
(x : X)
β transfinite-recursion w f x
οΌ f x (Ξ» y _ β transfinite-recursion w f y)
transfinite-recursion-behaviour fe w {π¦} {Y} =
transfinite-induction-behaviour fe w (Ξ» _ β Y)
\end{code}
End of addition.
\begin{code}
is-transitive : π€ β π₯ Μ
is-transitive = (x y z : X) β x < y β y < z β x < z
private
_βΌ_ : X β X β π€ β π₯ Μ
x βΌ y = β u β u < x β u < y
extensional-po = _βΌ_
extensional-po-is-prop-valued : FunExt
β is-prop-valued
β (x y : X) β is-prop (x βΌ y)
extensional-po-is-prop-valued fe isp x y =
Ξ β-is-prop (Ξ» {π€} {π₯} β fe π€ π₯) (Ξ» u l β isp u y)
βΌ-refl : {x : X} β x βΌ x
βΌ-refl u l = l
βΌ-refl-οΌ : {x y : X} β x οΌ y β x βΌ y
βΌ-refl-οΌ refl = βΌ-refl
βΌ-trans : {x y z : X} β x βΌ y β y βΌ z β x βΌ z
βΌ-trans f g u l = g u (f u l)
is-extensional : π€ β π₯ Μ
is-extensional = (x y : X) β x βΌ y β y βΌ x β x οΌ y
is-extensional' : π€ β π₯ Μ
is-extensional' = (x y : X) β ((u : X) β (u < x) β (u < y)) β x οΌ y
extensional-gives-extensional' : is-extensional β is-extensional'
extensional-gives-extensional' e x y f = e x y
(Ξ» u l β prβ (f u) l)
(Ξ» u l β prβ (f u) l)
extensional'-gives-extensional : is-extensional' β is-extensional
extensional'-gives-extensional e' x y g h = e' x y (Ξ» u β (g u , h u))
\end{code}
The HoTT Book additionally requires that the underlying type is a set
in the following definition, but this actually follows from the
extensionality condition (see below):
\begin{code}
is-well-order : π€ β π₯ Μ
is-well-order = is-prop-valued
Γ is-well-founded
Γ is-extensional
Γ is-transitive
prop-valuedness : is-well-order β is-prop-valued
prop-valuedness (p , w , e , t) = p
well-foundedness : is-well-order β is-well-founded
well-foundedness (p , w , e , t) = w
extensionality : is-well-order β is-extensional
extensionality (p , w , e , t) = e
transitivity : is-well-order β is-transitive
transitivity (p , w , e , t) = t
well-foundedness-is-prop : FunExt β is-prop is-well-founded
well-foundedness-is-prop fe = Ξ -is-prop (fe π€ (π€ β π₯))
(accessibility-is-prop fe)
extensionally-ordered-types-are-sets : FunExt
β is-prop-valued
β is-extensional
β is-set X
extensionally-ordered-types-are-sets fe isp e = Ξ³
where
f : {x y : X} β x οΌ y β x οΌ y
f {x} {y} p = e x y (transport (x βΌ_) p (βΌ-refl {x}))
(transport (_βΌ x) p (βΌ-refl {x}))
ec : {x y : X} {l l' : x βΌ y} {m m' : y βΌ x} β e x y l m οΌ e x y l' m'
ec {x} {y} {l} {l'} {m} {m'} = apβ (e x y)
(extensional-po-is-prop-valued fe isp x y l l')
(extensional-po-is-prop-valued fe isp y x m m')
ΞΊ : {x y : X} β wconstant (f {x} {y})
ΞΊ p q = ec
Ξ³ : is-set X
Ξ³ = Id-collapsibles-are-sets (f , ΞΊ)
well-ordered-types-are-sets : FunExt β is-well-order β is-set X
well-ordered-types-are-sets fe (p , w , e , t) =
extensionally-ordered-types-are-sets fe p e
extensionality-is-prop : FunExt β is-prop-valued β is-prop is-extensional
extensionality-is-prop fe isp e e' =
dfunext (fe π€ (π€ β π₯))
(Ξ» x β dfunext (fe π€ (π€ β π₯))
(Ξ» y β Ξ β-is-prop (Ξ» {π€} {π₯} β fe π€ π₯)
(Ξ» l m β extensionally-ordered-types-are-sets fe isp e)
(e x y)
(e' x y)))
transitivity-is-prop : FunExt β is-prop-valued β is-prop is-transitive
transitivity-is-prop fe isp = Ξ β
-is-prop (Ξ» {π€} {π₯} β fe π€ π₯)
(Ξ» x y z l m β isp x z)
being-well-order-is-prop : FunExt β is-prop is-well-order
being-well-order-is-prop fe = prop-criterion Ξ³
where
Ξ³ : is-well-order β is-prop is-well-order
Ξ³ o = Γβ-is-prop (Ξ β-is-prop ((Ξ» {π€} {π₯} β fe π€ π₯))
(Ξ» x y β being-prop-is-prop (fe π₯ π₯)))
(well-foundedness-is-prop fe)
(extensionality-is-prop fe (prop-valuedness o))
(transitivity-is-prop fe (prop-valuedness o))
private
_βΎ_ : X β X β π₯ Μ
x βΎ y = Β¬ (y < x)
βΎ-is-prop-valued : funext π₯ π€β β is-prop-valued β (x y : X) β is-prop (x βΎ y)
βΎ-is-prop-valued fe p x y = negations-are-props fe
<-gives-βΎ : (x : X)
β is-accessible x
β (y : X) β y < x β y βΎ x
<-gives-βΎ = transfinite-induction'
(Ξ» x β (y : X) β y < x β y βΎ x)
(Ξ» x f y l m β f y l x m l)
βΎ-refl : (x : X) β is-accessible x β x βΎ x
βΎ-refl x a l = <-gives-βΎ x a x l l
irreflexive : (x : X) β is-accessible x β Β¬ (x < x)
irreflexive = βΎ-refl
<-gives-β : is-well-founded
β (x y : X) β x < y β x β y
<-gives-β w x y l p = irreflexive y (w y) (transport (_< y) p l)
<-gives-βΌ : is-transitive β {x y : X} β x < y β x βΌ y
<-gives-βΌ t {x} {y} l u m = t u x y m l
βΌ-coarser-than-βΎ : (y : X) β is-accessible y β (x : X) β x βΌ y β x βΎ y
βΌ-coarser-than-βΎ y a x f l = βΎ-refl y a (f y l)
is-bot : X β π€ β π₯ Μ
is-bot x = (y : X) β x βΎ y
is-bot' : X β π€ β π₯ Μ
is-bot' x = (y : X) β x βΌ y
is-bot'-gives-is-bot : is-well-founded β (x : X) β is-bot' x β is-bot x
is-bot'-gives-is-bot w x i y = βΌ-coarser-than-βΎ y (w y) x (i y)
is-bot-gives-is-bot' : (x : X) β is-bot x β is-bot' x
is-bot-gives-is-bot' x i y z l = π-elim (i z l)
is-top : X β π€ β π₯ Μ
is-top x = (y : X) β y βΎ x
is-top' : X β π€ β π₯ Μ
is-top' x = (y : X) β y βΌ x
is-top'-gives-is-top : is-well-founded β (x : X) β is-top' x β is-top x
is-top'-gives-is-top w x i y = βΌ-coarser-than-βΎ x (w x) y (i y)
\end{code}
There is no hope of proving the converse constructively, because in
the ordinal of truth values any ¬¬-dense truth-value p satisfies
is-top p, and the only truth-value that satisfies is-top is β€. See the
module OrdinalOfTruthValues.
\begin{code}
has-top : π€ β π₯ Μ
has-top = Ξ£ x κ X , is-top x
no-minimal-is-empty : is-well-founded
β β {π¦} (A : X β π¦ Μ )
β ((x : X) β A x β is-nonempty (Ξ£ y κ X , (y < x) Γ A y))
β is-empty (Ξ£ A)
no-minimal-is-empty w A s (x , aβ) = Ξ³
where
g : (x : X) β is-accessible x β Β¬ (A x)
g x (acc Ο) Ξ½ = Ξ΄
where
h : ¬¬ (Ξ£ y κ X , (y < x) Γ A y)
h = s x Ξ½
IH : (y : X) β y < x β Β¬ (A y)
IH y l = g y (Ο y l)
k : Β¬ (Ξ£ y κ X , (y < x) Γ A y)
k (y , l , a) = IH y l a
Ξ΄ : π
Ξ΄ = h k
f : ((x : X) β A x β ¬¬ (Ξ£ y κ X , (y < x) Γ A y))
β (x : X) β Β¬ (A x)
f s x = g x (w x)
Ξ³ : π
Ξ³ = f s x aβ
no-minimal-is-empty' : is-well-founded
β β {π¦} (A : X β π¦ Μ )
β ((x : X) β A x β Ξ£ y κ X , (y < x) Γ A y)
β is-empty (Ξ£ A)
no-minimal-is-empty' w A s = no-minimal-is-empty w A (Ξ» x a β ¬¬-intro (s x a))
\end{code}
The emptiness of the empty set doesn't play any special role in the
above argument, and can be replaced by any type - would that be
useful?
\begin{code}
in-trichotomy : (x y : X) β π€ β π₯ Μ
in-trichotomy x y = (x < y) + (x οΌ y) + (y < x)
is-trichotomous-element : X β π€ β π₯ Μ
is-trichotomous-element x = (y : X) β in-trichotomy x y
is-trichotomous-order : π€ β π₯ Μ
is-trichotomous-order = (x : X) β is-trichotomous-element x
>-implies-in-trichotomy : {x y : X} β (x < y) β in-trichotomy x y
>-implies-in-trichotomy = inl
οΌ-implies-in-trichotomy : {x y : X} β (x οΌ y) β in-trichotomy x y
οΌ-implies-in-trichotomy = inr β inl
<-implies-in-trichotomy : {x y : X} β (y < x) β in-trichotomy x y
<-implies-in-trichotomy = inr β inr
in-trichotomy-symm : {x y : X} β in-trichotomy x y β in-trichotomy y x
in-trichotomy-symm (inl x-lt-y) = inr (inr x-lt-y)
in-trichotomy-symm (inr (inl x-equiv-y)) = inr (inl (x-equiv-y β»ΒΉ))
in-trichotomy-symm (inr (inr y-lt-x)) = inl y-lt-x
_>_ : (x y : X) β π₯ Μ
x > y = y < x
_β¦_ : (x y : X) β π€ β π₯ Μ
x β¦ y = (x < y) + (y οΌ x)
_β§_ : (x y : X) β π€ β π₯ Μ
x β§ y = (x οΌ y) + (y < x)
β§-implies-β¦ : {x y : X} β x β§ y β y β¦ x
β§-implies-β¦ x-geq-y = +-commutative x-geq-y
β¦-implies-β§ : {x y : X} β x β¦ y β y β§ x
β¦-implies-β§ x-leq-y = +-commutative x-leq-y
β§-implies-in-trichotomy : {x y : X} β x β§ y β in-trichotomy x y
β§-implies-in-trichotomy = inr
β¦-implies-in-trichotomy : {x y : X} β x β¦ y β in-trichotomy x y
β¦-implies-in-trichotomy = cases inl (οΌ-implies-in-trichotomy β _β»ΒΉ)
in-trichotomy-not->-implies-β¦ : {x y : X} β in-trichotomy x y β Β¬ (y < x) β x β¦ y
in-trichotomy-not->-implies-β¦ (inl x-lt-y) y-not-lt-x = inl x-lt-y
in-trichotomy-not->-implies-β¦ (inr (inl x-equals-y)) y-not-lt-x = inr (x-equals-y β»ΒΉ)
in-trichotomy-not->-implies-β¦ (inr (inr y-lt-x)) y-not-lt-x = π-elim (y-not-lt-x y-lt-x)
in-trichotomy-not->-implies-β§ : {x y : X} β in-trichotomy x y β Β¬ (x < y) β x β§ y
in-trichotomy-not->-implies-β§ x-in-trichotomy-y y-not-lt-x =
β¦-implies-β§ (in-trichotomy-not->-implies-β¦
(in-trichotomy-symm x-in-trichotomy-y)
y-not-lt-x)
β§->-transitive : is-well-order β {x y z : X} β (x β§ y) β (z < y) β z < x
β§->-transitive wo {x} {y} {z} (inl refl) y-gt-z = y-gt-z
β§->-transitive wo@(p , w , e , t) {x} {y} {z} (inr x-gt-y) y-gt-z = t z y x y-gt-z x-gt-y
>-β§-transitive : is-well-order β {x y z : X} β (y < x) β (y β§ z) β z < x
>-β§-transitive wo {x} {y} {.y} x-gt-y (inl refl) = x-gt-y
>-β§-transitive wo@(p , w , e , t) {x} {y} {z} x-gt-y (inr y-gt-z) = t z y x y-gt-z x-gt-y
module _ (fe : FunExt) (wo : is-well-order) where
private
X-is-set : is-set X
X-is-set = well-ordered-types-are-sets fe wo
β¦-is-prop : (x y : X) β is-prop (x β¦ y)
β¦-is-prop x y = sum-of-contradictory-props (prop-valuedness wo x y)
X-is-set
Ξ» x-lt-y x-equals-y β irreflexive y (well-foundedness wo y)
(transport (_< y) (x-equals-y β»ΒΉ) x-lt-y)
β§-is-prop : (x y : X) β is-prop (x β§ y)
β§-is-prop x y = sum-of-contradictory-props
(well-ordered-types-are-sets fe wo)
(prop-valuedness wo y x)
Ξ» x-equals-y x-gt-y β irreflexive x (well-foundedness wo x)
(transport (_< x) (x-equals-y β»ΒΉ) x-gt-y)
in-trichotomy-is-prop : (x y : X) β is-prop (in-trichotomy x y)
in-trichotomy-is-prop x y =
sum-of-contradictory-props (prop-valuedness wo x y) (β§-is-prop x y)
Ξ» x-lt-y x-geq-y β irreflexive x (well-foundedness wo x)
(β§->-transitive wo x-geq-y x-lt-y)
being-trichotomous-element-is-prop : (x : X) β is-prop (is-trichotomous-element x)
being-trichotomous-element-is-prop x =
Ξ -is-prop (fe π€ (π€ β π₯))
(Ξ» y β in-trichotomy-is-prop x y)
trichotomy-is-prop : is-prop (is-trichotomous-order)
trichotomy-is-prop = Ξ -is-prop (fe π€ (π€ β π₯))
being-trichotomous-element-is-prop
\end{code}
Not all ordinals are trichotomous, in the absence of excluded middle
or even just LPO, because ββ is not discrete unless LPO holds, but its
natural order is well-founded, and types with well-founded trichotomous
relations are discrete (have decidable equality):
\begin{code}
trichotomous-gives-discrete : is-well-founded
β is-trichotomous-order
β is-discrete X
trichotomous-gives-discrete w t x y = f (t x y)
where
f : (x < y) + (x οΌ y) + (y < x) β (x οΌ y) + (x β y)
f (inl l) = inr (<-gives-β w x y l)
f (inr (inl p)) = inl p
f (inr (inr l)) = inr (β -sym (<-gives-β w y x l))
\end{code}
The following proof that excluded middle gives trichotomy, added 11th
Jan 2021, is the same as that in the HoTT book, except that we use
negation instead of the assumption of existence of propositional
truncations to get a proposition to which we can apply excluded
middle. But notice that, under excluded middle and function
extensionality, double negation is the same thing as propositional
truncation. Notice also we additionally need function extensionality
as an assumption (to know that the negation of a type is a
proposition).
There is also a shorter proof below that uses the existence of
propositional truncations (but seems different to the proof of the
HoTT book).
\begin{code}
trichotomy : funext (π€ β π₯) π€β
β excluded-middle (π€ β π₯)
β is-well-order
β is-trichotomous-order
trichotomy fe em (p , w , e , t) = Ξ³
where
P : X β X β π€ β π₯ Μ
P x y = (x < y) + (x οΌ y) + (y < x)
Ξ³ : (x y : X) β P x y
Ξ³ = transfinite-induction w (Ξ» x β β y β P x y) Ο
where
Ο : (x : X)
β ((x' : X) β x' < x β (y : X) β P x' y)
β (y : X) β P x y
Ο x IH-x = transfinite-induction w (Ξ» y β P x y) Ο
where
Ο : (y : X)
β ((y' : X) β y' < y β P x y')
β P x y
Ο y IH-y = Ξ΄
where
A = Ξ£ x' κ X , (x' < x) Γ ((y < x') + (x' οΌ y))
¬¬A-gives-P : ¬¬ A β P x y
¬¬A-gives-P = b
where
a : A β y < x
a (x' , l , inl m) = t y x' x m l
a (x' , l , inr p) = transport (_< x) p l
b : ¬¬ A β (x < y) + (x οΌ y) + (y < x)
b = inr β inr β EM-gives-DNE (lower-EM π€ em) (y < x) (p y x) β ¬¬-functor a
Β¬A-gives-βΌ : Β¬ A β x βΌ y
Β¬A-gives-βΌ Ξ½ x' l = d
where
a : Β¬ ((y < x') + (x' οΌ y))
a f = Ξ½ (x' , l , f)
b : P x' y
b = IH-x x' l y
c : Β¬ ((y < x') + (x' οΌ y)) β P x' y β x' < y
c g (inl i) = i
c g (inr (inl ii)) = π-elim (g (inr ii))
c g (inr (inr iii)) = π-elim (g (inl iii))
d : x' < y
d = c a b
B = Ξ£ y' κ X , (y' < y) Γ ((x < y') + (x οΌ y'))
¬¬B-gives-P : ¬¬ B β P x y
¬¬B-gives-P = b
where
a : B β x < y
a (y' , l , inl m) = t x y' y m l
a (y' , l , inr p) = transport (_< y) (p β»ΒΉ) l
b : ¬¬ B β (x < y) + (x οΌ y) + (y < x)
b = inl β EM-gives-DNE (lower-EM π€ em) (x < y) (p x y) β ¬¬-functor a
Β¬B-gives-βΌ : Β¬ B β y βΌ x
Β¬B-gives-βΌ Ξ½ y' l = d
where
a : Β¬ ((x < y') + (x οΌ y'))
a f = Ξ½ (y' , l , f)
b : P x y'
b = IH-y y' l
c : Β¬ ((x < y') + (x οΌ y')) β P x y' β y' < x
c g (inl i) = π-elim (g (inl i))
c g (inr (inl ii)) = π-elim (g (inr ii))
c g (inr (inr iii)) = iii
d : y' < x
d = c a b
Β¬A-and-Β¬B-give-P : Β¬ A β Β¬ B β P x y
Β¬A-and-Β¬B-give-P Ξ½ Ξ½' = b
where
a : Β¬ A β Β¬ B β x οΌ y
a Ξ½ Ξ½' = e x y (Β¬A-gives-βΌ Ξ½) (Β¬B-gives-βΌ Ξ½')
b : (x < y) + (x οΌ y) + (y < x)
b = inr (inl (a Ξ½ Ξ½'))
Ξ΄ : P x y
Ξ΄ = Cases (em (Β¬ A) (negations-are-props fe))
(Ξ» (Ξ½ : Β¬ A)
β Cases (em (Β¬ B) (negations-are-props fe))
(Β¬A-and-Β¬B-give-P Ξ½)
¬¬B-gives-P)
¬¬A-gives-P
\end{code}
Added 09-04-2022 -- 04-05-2022 by Ohad Kammar.
We can give a shorter proof using `βΒ¬-gives-β` and LEM, by deducing
that in a well-order, for every u and v, either u βΌ v or there is some
i < u for which Β¬ (i < v).
Like the HoTT proof, we nest two inductions, the outer one that every
element is trichotomous, and the inner one that the currently
considered outer element u is in trichotomy with the currently
considered inner element v.
The crucial observation (`lemma`) is that, under the outer induction
hypothesis for u, the relations (_βΌ u) and (_β¦ u) coincide. We prove
this observation by appealing to LEM to get that either u βΌ x or there
is a witness i < u but Β¬ (i < x). The former means (by extensionality)
that u οΌ x. In the latter case, the witness i satisfies the induction
hypothesis, and so is in trichotomy with x, which by elimination means
i >= x, so u > i >= x.
With this lemma, we can prove the inner induction step by LEM. If v βΌ
u, then by the lemma v <= u and so they are in trichotomy. Otherwise,
there is a witness i < v , Β¬ (i < u). By the induction hypothesis for
v, we have that i is in trichotomy with u, which by elimination means
i >= u, and so v > i >= u, and so u and v are again in trichotomy.
\begin{code}
induction-hypothesis : (P : X β π¦ Μ ) β (x : X) β (π€ β π₯ β π¦) Μ
induction-hypothesis P x = (y : X) β y < x β P y
module _
(f-e : Fun-Ext)
(em : Excluded-Middle)
where
private
pt : propositional-truncations-exist
pt = fe-and-em-give-propositional-truncations (Ξ» π€ π₯ β f-e {π€} {π₯}) em
fe : FunExt
fe π€ π₯ = f-e
open PropositionalTruncation pt
lem-consequence : is-well-order β (u v : X) β (β i κ X , ((i < u) Γ Β¬ (i < v))) + (u βΌ v)
lem-consequence (p , _) u v = Cases
(β-not+Ξ pt em {Ξ£ (Ξ» i β i < u)}
(Ξ» (i , i-lt-u) β i < v)
(Ξ» (i , i-<-u) β p i v))
(Ξ» witness β inl ((β₯β₯-induction (Ξ» s β β-is-prop)
(Ξ» ((i , i-lt-u) , i-not-lt-v) β β£ i , i-lt-u , i-not-lt-v β£) witness)))
Ξ» prf β inr (Ξ» i i-lt-u β prf (i , i-lt-u))
trichotomyβ : is-well-order β is-trichotomous-order
trichotomyβ wo@(p , w , e , t) = transfinite-induction w is-trichotomous-element Ο
where
Ο : (x : X) β induction-hypothesis is-trichotomous-element x β is-trichotomous-element x
Ο u ih =
transfinite-induction w (in-trichotomy u) Ξ» v innerIH β
Cases (lem-consequence wo v u)
(β₯β₯-induction (Ξ» s β in-trichotomy-is-prop fe wo u v)
Ξ» (i , i-lt-v , i-not-lt-u) β inl
let u-leq-i = in-trichotomy-not->-implies-β¦ ((innerIH i i-lt-v)) i-not-lt-u in
>-β§-transitive wo i-lt-v (β¦-implies-β§ u-leq-i))
Ξ» v-below-u β in-trichotomy-symm (β¦-implies-in-trichotomy (lemma v v-below-u))
where
lemma : (x : X) β (x βΌ u) β x β¦ u
lemma x x-below-u = Cases (lem-consequence wo u x)
(β₯β₯-induction (Ξ» s β β¦-is-prop fe wo x u)
Ξ» (i , i-lt-u , i-not-lt-x) β inl
let i-in-trichotomy-x = ih i i-lt-u x in
(>-β§-transitive wo
i-lt-u
(in-trichotomy-not->-implies-β§ i-in-trichotomy-x i-not-lt-x)))
Ξ» u-below-x β inr ((e x u x-below-u u-below-x) β»ΒΉ)
\end{code}
End of proof added by Ohad Kammar.
The following fact and proof were communicated verbally by Paul Blain
Levy to Martin Escardo and Ohad Kammar on 16th November 2022, and it
is written down in Agda by Martin Escardo on the same date:
\begin{code}
is-decidable-order : π€ β π₯ Μ
is-decidable-order = (x y : X) β is-decidable (x < y)
trichotomy-from-decidable-order : is-transitive
β is-extensional
β is-well-founded
β is-decidable-order
β is-trichotomous-order
trichotomy-from-decidable-order t e w d = Ξ³
where
T : X β X β π€ β π₯ Μ
T x y = (x < y) + (x οΌ y) + (y < x)
Ξ³ : (a b : X) β T a b
Ξ³ = transfinite-induction w (Ξ» a β (b : X) β T a b) Ο
where
Ο : (a : X) β ((x : X) β x < a β (b : X) β T x b) β (b : X) β T a b
Ο a IH-a = transfinite-induction w (T a) Ο
where
Ο : (b : X) β ((y : X) β y < b β T a y) β T a b
Ο b IH-b = III
where
I : Β¬ (a < b) β b βΌ a
I Ξ½ y l = f (IH-b y l)
where
f : (a < y) + (a οΌ y) + (y < a) β y < a
f (inl m) = π-elim (Ξ½ (t a y b m l))
f (inr (inl p)) = π-elim (Ξ½ (transport (_< b) (p β»ΒΉ) l))
f (inr (inr m)) = m
II : Β¬ (b < a) β a βΌ b
II Ξ½ x l = g (IH-a x l b)
where
g : (x < b) + (x οΌ b) + (b < x) β x < b
g (inl m) = m
g (inr (inl p)) = π-elim (Ξ½ (transport (_< a) p l))
g (inr (inr m)) = π-elim (Ξ½ (t b x a m l))
III : T a b
III = h (d a b) (d b a)
where
h : (a < b) + Β¬ (a < b)
β (b < a) + Β¬ (b < a)
β (a < b) + (a οΌ b) + (b < a)
h (inl l) _ = inl l
h (inr Ξ±) (inl l) = inr (inr l)
h (inr Ξ±) (inr Ξ²) = inr (inl (e a b (II Ξ²) (I Ξ±)))
trichotomyβ : excluded-middle π₯
β is-well-order
β is-trichotomous-order
trichotomyβ em (p , w , e , t) = trichotomy-from-decidable-order
t e w (Ξ» x y β em (x < y) (p x y))
decidable-order-from-trichotomy : is-transitive
β is-well-founded
β is-trichotomous-order
β is-decidable-order
decidable-order-from-trichotomy t w Ο = Ξ³
where
Ξ³ : (x y : X) β is-decidable (x < y)
Ξ³ x y = f (Ο x y)
where
f : (x < y) + (x οΌ y) + (y < x) β (x < y) + Β¬ (x < y)
f (inl l) = inl l
f (inr (inl p)) = inr (Ξ» (m : x < y) β irreflexive x (w x) (transport (x <_) (p β»ΒΉ) m))
f (inr (inr l)) = inr (Ξ» (m : x < y) β irreflexive x (w x) (t x y x m l))
decidable-order-iff-trichotomy : is-well-order
β is-trichotomous-order β is-decidable-order
decidable-order-iff-trichotomy (_ , w , e , t) =
decidable-order-from-trichotomy t w ,
trichotomy-from-decidable-order t e w
\end{code}
Paul also remarks that the result can be strengthened as follows: A
transitive well-founded relation is trichotomous iff it is both
extensional and decidable. TODO. Write this down in Agda.
End of 16th November 2022 addition.
\begin{code}
not-<-gives-βΌ : funext (π€ β π₯) π€β
β excluded-middle (π€ β π₯)
β is-well-order
β (x y : X) β Β¬ (x < y) β y βΌ x
not-<-gives-βΌ fe em wo@(p , w , e , t) x y = Ξ³ (trichotomy fe em wo x y)
where
Ξ³ : (x < y) + (x οΌ y) + (y < x) β Β¬ (x < y) β y βΌ x
Ξ³ (inl l) Ξ½ = π-elim (Ξ½ l)
Ξ³ (inr (inl e)) Ξ½ = transport (_βΌ x) e βΌ-refl
Ξ³ (inr (inr m)) Ξ½ = <-gives-βΌ t m
βΌ-or-> : funext (π€ β π₯) π€β
β excluded-middle (π€ β π₯)
β is-well-order
β (x y : X) β (x βΌ y) + y < x
βΌ-or-> fe em wo@(p , w , e , t) x y = Ξ³ (trichotomy fe em wo x y)
where
Ξ³ : (x < y) + (x οΌ y) + (y < x) β (x βΌ y) + (y < x)
Ξ³ (inl l) = inl (<-gives-βΌ t l)
Ξ³ (inr (inl e)) = inl (transport (x βΌ_) e βΌ-refl)
Ξ³ (inr (inr m)) = inr m
\end{code}
Because we assume function extensionality and excluded middle in this
annonymous submodule, propositional truncations are available, and it
amounts to double negation.
\begin{code}
βΎ-gives-βΌ-under-trichotomy : is-transitive
β {a b : X}
β ((x : X) β in-trichotomy x b)
β a βΎ b
β a βΌ b
βΎ-gives-βΌ-under-trichotomy t {a} {b} Ο Ξ½ x = Ξ³ (Ο x)
where
Ξ³ : (x < b) + (x οΌ b) + (b < x)
β x < a
β x < b
Ξ³ (inl m) l = m
Ξ³ (inr (inl p)) l = π-elim (Ξ½ (transport (_< a) p l))
Ξ³ (inr (inr m)) l = π-elim (Ξ½ (t b x a m l))
βΎ-gives-βΌ-under-trichotomy' : is-transitive
β is-trichotomous-order
β {a b : X} β a βΎ b β a βΌ b
βΎ-gives-βΌ-under-trichotomy' t Ο {a} {b} = βΎ-gives-βΌ-under-trichotomy t (Ξ» x β Ο x b)
module _ (fe : Fun-Ext)
(em : Excluded-Middle)
where
nonempty-has-minimal' : is-well-order
β (A : X β π¦ Μ )
β ((x : X) β is-prop (A x))
β ¬¬ (Ξ£ x κ X , A x)
β Ξ£ x κ X , A x Γ ((y : X) β A y β x βΌ y)
nonempty-has-minimal' {π¦} W@(p , w , e , t) A A-is-prop-valued f = Ξ³ Ξ΄
where
Ξ : π€ β π₯ β π¦ Μ
Ξ = Ξ£ x κ X , A x Γ ((y : X) β A y β x βΎ y)
g : Β¬ ((x : X) β A x β ¬¬ (Ξ£ y κ X , (y < x) Γ A y))
g = contrapositive (no-minimal-is-empty w A) f
h : ¬¬ (Ξ£ x κ X , Β¬ (A x β ¬¬ (Ξ£ y κ X , (y < x) Γ A y)))
h = not-Ξ -implies-not-not-Ξ£
(Ξ» x β EM-gives-DNE em
(A x β ¬¬ (Ξ£ y κ X , (y < x) Γ A y))
(Ξ β-is-prop fe (Ξ» _ _ β π-is-prop)))
g
Ο : (x : X)
β Β¬ (A x β ¬¬ (Ξ£ y κ X , (y < x) Γ A y))
β A x Γ ((y : X) β A y β x βΎ y)
Ο x Ο = EM-gives-DNE em (A x)
(A-is-prop-valued x)
((Ξ» Ξ½ β Ο (Ξ» a _ β Ξ½ a))) ,
Ξ» y a l β Ο (Ξ» _ Ξ½ β Ξ½ (y , l , a))
Ξ½ : ¬¬ Ξ
Ξ½ = ¬¬-functor (Ξ» (x , f) β x , Ο x f) h
j : (x : X) β is-prop ((y : X) β A y β x βΎ y)
j x = Ξ β-is-prop fe (Ξ» y a l β π-is-prop)
i : (x : X) β is-prop (A x Γ ((y : X) β A y β x βΎ y))
i x = Γ-is-prop (A-is-prop-valued x) (j x)
Ο : is-trichotomous-order
Ο = trichotomyβ em W
Ξ-is-prop : is-prop Ξ
Ξ-is-prop (x , a , f) (x' , a' , f') = to-subtype-οΌ i q
where
q : x οΌ x'
q = k (Ο x x')
where
k : (x < x') + (x οΌ x') + (x' < x) β x οΌ x'
k (inl l) = π-elim (f' x a l)
k (inr (inl p)) = p
k (inr (inr l)) = π-elim (f x' a' l)
Ξ΄ : Ξ
Ξ΄ = EM-gives-DNE em Ξ Ξ-is-prop Ξ½
Ξ³ : Ξ β Ξ£ x κ X , A x Γ ((y : X) β A y β x βΌ y)
Ξ³ (x , a , h) = x , a , (Ξ» y a β βΎ-gives-βΌ-under-trichotomy' t Ο {x} {y} (h y a))
module _ (pt : propositional-truncations-exist) where
open PropositionalTruncation pt
nonempty-has-minimal : is-well-order
β (A : X β π¦ Μ )
β ((x : X) β is-prop (A x))
β β x κ X , A x
β Ξ£ x κ X , A x Γ ((y : X) β A y β x βΌ y)
nonempty-has-minimal w A i e = nonempty-has-minimal' w A i (inhabited-is-nonempty e)
\end{code}
When do we get x βΎ y β x βΌ y (say for ordinals)? When do we get
cotransitivity? Jean S. Josef observed that cotransitivity gives x βΎ y
β x βΌ y if _<_ is an order. But cotransitivity alone is enough.
Or consider the truncated version of the following, if _<_ is
proposition valued.
\begin{code}
cotransitive : π€ β π₯ Μ
cotransitive = (x y z : X) β x < y β (x < z) + (z < y)
cotransitive-βΎ-gives-βΌ : cotransitive β (x y : X) β x βΎ y β x βΌ y
cotransitive-βΎ-gives-βΌ c x y n u l = Ξ³ (c u x y l)
where
Ξ³ : (u < y) + (y < x) β u < y
Ξ³ (inl l) = l
Ξ³ (inr l) = π-elim (n l)
tricho-gives-cotrans : is-transitive β is-trichotomous-order β cotransitive
tricho-gives-cotrans tra tri x y z l = Ξ³ (tri z y)
where
Ξ³ : (z < y) + (z οΌ y) + (y < z) β (x < z) + (z < y)
Ξ³ (inl m) = inr m
Ξ³ (inr (inl refl)) = inl l
Ξ³ (inr (inr m)) = inl (tra x y z l m)
em-gives-cotrans : FunExt β EM (π€ β π₯) β is-well-order β cotransitive
em-gives-cotrans fe em wo@(p , w , e , t) = tricho-gives-cotrans t
(trichotomy (fe (π€ β π₯) π€β) em wo)
\end{code}
This is the end of the submodule with the assumption of excluded
middle.
Originally, in 2011 (see my JSL publication), we needed to work with
the following weakening of well-foundedness (transfinite induction for
detachable subsets), but as of Summer 2018, it is not needed any
longer as we are able to show that our compact ordinals are
well-founded in the standard, stronger, sense.
\begin{code}
is-well-foundedβ : π€ β π₯ Μ
is-well-foundedβ = (p : X β π) β ((x : X) β ((y : X) β y < x β p y οΌ β) β p x οΌ β)
β (x : X) β p x οΌ β
well-founded-Wellfoundedβ : is-well-founded β is-well-foundedβ
well-founded-Wellfoundedβ w p = transfinite-induction w (Ξ» x β p x οΌ β)
being-well-foundedβ-is-prop : FunExt β is-prop is-well-foundedβ
being-well-foundedβ-is-prop fe = Ξ β-is-prop (Ξ» {π€} {π₯} β fe π€ π₯)
(Ξ» p s x β π-is-set)
is-well-orderβ : π€ β π₯ Μ
is-well-orderβ = is-prop-valued Γ is-well-foundedβ Γ is-extensional Γ is-transitive
is-well-order-gives-is-well-orderβ : is-well-order β is-well-orderβ
is-well-order-gives-is-well-orderβ (p , w , e , t) = p , (well-founded-Wellfoundedβ w) , e , t
being-well-orderβ-is-prop : FunExt β is-prop-valued β is-prop is-well-orderβ
being-well-orderβ-is-prop fe isp = Γβ-is-prop
(Ξ β-is-prop (Ξ» {π€} {π₯} β fe π€ π₯)
(Ξ» x y β being-prop-is-prop (fe π₯ π₯)))
(being-well-foundedβ-is-prop fe)
(extensionality-is-prop fe isp)
(transitivity-is-prop fe isp)
\end{code}
Experimental ideas. We don't truncate the Ξ£, at least not for the
moment, so x <β y won't be a proposition (i.e. subsingleton) in
general. However, given π-order-separation, this is logically
equivalent to a proposition (has split support).
\begin{code}
open import MLTT.Two-Properties
_βΊβ_ : X β X β π€ β π₯ Μ
x βΊβ y = Ξ£ p κ (X β π) , (p x <β p y)
Γ ((u v : X) β (u < v β p u β€β p v)
Γ (p u <β p v β u < v))
βΊβ-courser-than-< : (x y : X) β x βΊβ y β x < y
βΊβ-courser-than-< x y (p , l , Ο) = prβ (Ο x y) l
π-order-separated : π€ β π₯ Μ
π-order-separated = (x y : X) β x < y β x βΊβ y
π-order-separated-gives-cotransitive : π-order-separated β cotransitive
π-order-separated-gives-cotransitive s x y z l = g (s x y l)
where
g : (Ξ£ p κ (X β π) , (p x <β p y)
Γ ((u v : X) β (u < v β p u β€β p v)
Γ (p u <β p v β u < v)))
β (x < z) + (z < y)
g (p , m , Ο) = Cases (π-is-discrete (p z) β)
(Ξ» (t : p z οΌ β)
β inr (prβ (Ο z y) (Lemma[aοΌββb<cβa<c] t m)))
(Ξ» (t : Β¬ (p z οΌ β))
β inl (prβ (Ο x z) (Lemma[a<bβcβ ββa<c] m t)))
\end{code}
It seems that this is not going to be useful, because although ββ
satisfies this property, the property doesn't seem to be preserved by
the lexicographic order (think about this).