La canonicità implica una debole normalizzazione?

Question

Contesto: Tipo teoria.

La mia comprensione di:

.
• wn: ogni termine può riscrivere a NF.
• Canonicità: ogni termine riscrive in forma canonica.

Poi porta a un'intuizione in cui se la canonica detiene, quindi otteniamo NF= forma canonica e quindi WN tiene.Tuttavia, non vedo persone lo affermano spesso, come Questa domanda parla di canonicità ma non menziona mai NF o normalizzazione.Su NLab , si dice che la forma canonica sia una forma normale, che giustifica il mio "NF=La forma canonica "Indovina ma non dice quindi che WN tiene.Pertanto sto dubitando della mia intuizione.

Allora, mi chiedo se è giusto (c'è una prova?), o se è sbagliato (c'è un controesempio?).

Answer 1

La canalonicità non implica una debole normalizzazione. Innanzitutto, fammi a esprimere le definizioni coinvolte più precisamente:

.
• wn: ogni termine aperto è riducibile a un termine normale
• canonicità: ogni termine chiuso è riducibile a un termine canonico

(Nota: nella moderna metatopooria della teoria del tipo, è più comune parlare della conversione invece di riduzione, e allo stesso modo di parlare dell'esistenza unica di forme normali invece della normalizzazione debole / forte. Questa risposta rimane valida se sostituiamo " Riducibile "sopra con" convertibile ").

I termini normali e canonici non sono gli stessi. Ad esempio, la variabile x nel contesto x : Bool è normale ma non canonico. Inoltre, il termine chiuso λ(b : Bool). if true then b else b è canonico ma non normale.

La teoria del tipo di estensione ha la proprietà delle canonicità ma non è un'esistenza SN, o unica di forme normali. Questo perché in ETT è possibile aggiungere un'uguaglianza definitiva incoerente al contesto o aggiungere una teoria equazionale di un sistema completo di Turing. Ad esempio, nel contesto ETT n : Nat, p : n = suc n La variabile n non ha un modulo normale univoco, poiché n può essere espanso arbitrariamente utilizzando p.

Tuttavia, se abbiamo un termine ETT chiuso, non possiamo avere nulla di Dvvio nel contesto, quindi un termine chiuso può essere ancora valutato a una forma canonica.