Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

HoTT without cuts (wild speculations)

Homotopical Type Theory in its current formulation has a way too huge proof theoretical ordinal strength for a metatheory. It would be practical to have a gradual control over its proof theoretical ordinal by means of adding or removing particular wellfoundness axioms. It seems, it can be easily done: first we have to remove all constructors for product types except linear lambda abstraction (so, no value duplication, no splits, no natrec). We will be able to emulate all this techniques with some help of interaction nets.

In HoTT we can define types with additional equality, for example the circle skeleton and the type of unordered pairs:
Family CircleSkeleton
  GenericPoint (CircleSkeleton)
  Loop (GenericPoint = GenericPoint)
Family Couple (TypeType)
  Couple (T (Type), a (T), b (T) ⇒ Couple[T])
  Mirror (T (Type), a (T), b (T) ⇒ [Couple[T, a, b] = Couple[T, b, a]])

HoTT types form (∞,0)-categories, but we probably could allow nonreflexive arrows on the first H-Level to represent incomplete (or nonterminating) computations. Let's define a type of Natural numbers together with possibly incomplete addition:
Family Nat (Type)
  Zero (Nat)
  Succ (NatNat)
Directed-Family Nat-Plus-Addition extending Nat
  Add (Nat, NatNat-Plus-Addition)
  ZeroReduction (x (Nat) ⇒ [Add [Zero, x] = x])
  SuccReduction (a (Nat), b (Nat) ⇒ [Add[Succ[a], b] = Succ[Add[a, b]]])

Nat-Plus-Addition is now the type of expressions involving natural numbers and addition, and we can, step-by-step, by applying reductions, convert it to a Nat, preserving equality. ZeroReduction and SuccReduction are the computation rules in sense of Interaction Nets. Assuming univalence, ‖Nat-Plus-Addition‖ = Nat means precisely that Nat-Plus-Addition can always be reduced to Nat.

How can we prove that some ‖Type-Plus-Computation‖ = Type?
We certainly can do it only relatively to some wellfoundness postulate. Optimally, we have to represent ordinals α as universal interaction nets Cα of complexity up to α, than map interaction net Type-Plus-Computation in question onto Cα in such a way that elements of type Type are mapped onto Zero. The postulate that o is wellfounded should then have the form Cα = Unit we should be able to conclude that Type-Plus-Computation = Type.
Probably, we could use Takeuti Diagrams (encoded as Directed-Families) as universal interaction nets of corresponding complexities.
Tags: fprog
Subscribe

  • (no subject)

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

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

    Как известно, питьевая вода во многих странах дефицитный ресурс. И даже в дождливой Германии летом иногда случаются засухи, в результате которых она…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments