{-# OPTIONS --cubical-compatible #-}
module Padova2025.Explorations.Uncountability.Impossible.Toy where
open import Padova2025.ProgrammingBasics.Booleans
open import Padova2025.ProgrammingBasics.Naturals.Base
open import Padova2025.ProgrammingBasics.Lists
open import Padova2025.ProgrammingBasics.HigherOrder
open import Padova2025.ProvingBasics.Termination.Gas
open import Padova2025.Explorations.Uncountability.Applications
_β_ : Bool β Cantor β Cantor
x β xs = Ξ» { zero β x ; (succ n) β xs n }
{-# NON_TERMINATING #-}
Ξ΅ : (Cantor β Bool) β Cantor
Ξ΅ P = x β Ξ΅ (P β (x β_))
where
x : Bool
x = P (false β Ξ΅ (P β (false β_)))
has-root? : (Cantor β Bool) β Bool
has-root? P = not (P (Ξ΅ P))
root : (Cantor β Bool) β Maybe (List Bool)
root P with P (Ξ΅ P)
... | false = just (map (Ξ΅ P) (zero β· one β· two β· three β· four β· []))
... | true = nothing
_β‘?_ : (Cantor β Bool) β (Cantor β Bool) β Bool
P β‘? Q = not (has-root? (Ξ» xs β not (xor (P xs) (Q xs))))
where
xor : Bool β Bool β Bool
xor false false = false
xor false true = true
xor true false = true
xor true true = false