La canonicità implica una debole normalizzazione?
-
29-09-2020 - |
Domanda
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?).
Soluzione
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.