Universen in abhängiger Typentheorie

11

Ich lese über die Theorie der abhängigen Typen im Online-Buch Homotopy Type Theory .

In Abschnitt 1.3 des Kapitels Typentheorie wird der Begriff der Hierarchie der Universen eingeführt : $\mathcal{U}_0 : \mathcal{U}_1 : \mathcal{U}_2 : \cdots$ , wobei

Jedes Universum $\mathcal{U}_i$ ist ein Element des nächsten Universums $\mathcal{U}_{i+1}$ . Darüber hinaus gehen wir davon aus, dass unsere Universen kumulativ sind, dass , dass alle ist die Elemente der $i^{\mathrm{th}}$ Universum sind auch Elemente der $(i+1)^{\mathrm{th}}$ Universum.

Wenn ich mir jedoch die Formationsregeln für die verschiedenen Typen in Anhang A anschaue, erscheint auf den ersten Blick, wenn ein Universum als Prämisse über dem Balken erscheint, dasselbe Universum darunter. Zum Beispiel für die Regel zur Bildung von Nebenprodukttypen:

\frac{Γ ⊢ A : U_{i} Γ ⊢ B : U i}{Γ ⊢ A + B : U_{i}} (+ - F O R M)

$\dfrac{\Gamma \vdash A : \mathcal{U}_i \quad \Gamma \vdash B : \mathcal{U}i}{\Gamma \vdash A + B : \mathcal{U}_i}(+\mbox{-}FORM)$

Meine Frage ist also, warum eine Hierarchie notwendig ist. Unter welchen Umständen müssen Sie von einem Universum zu einem höheren in der Hierarchie springen? Es ist mir wirklich nicht klar, wie man bei einer Kombination von $A_m: \mathcal{U}_i$ zu einem Typ $B$ , der nicht in $\mathcal{U}_i$ . Im Detail: Die Formationsregeln in den Abschnitten des Anhangs A.2.4, A.2.5, A.2.6, A.2.7, A.2.8, A.2.9, A.2.10, A.3.2 erwähnen entweder $\mathcal{U}_i$ in der Prämisse und Urteil, oder nur im Urteil.

Das Buch weist auch darauf hin, dass es einen formalen Weg gibt, Universen zuzuweisen:

Wenn Zweifel daran bestehen, ob ein Argument korrekt ist, können Sie es überprüfen, indem Sie versuchen, allen darin vorkommenden Universen einheitlich Ebenen zuzuweisen.

Wie werden Ebenen konsistent zugewiesen?

$\mathcal{U}:\mathcal{U}$ $\mathcal{U}_j$ $\mathcal{U}_i$ $j > i$

type-theory homotopy-type-theory dependent-types huynhjl
quelle

1

@huynhjl Die Verwendung von Universen ist nicht erforderlich, um Paradoxien zu vermeiden, zum Beispiel weder die ZF-Mengenlehre noch Quines NF, zwei alternative mathematische Grundlagen verwenden sie. Universen sind ein bequemer Weg, um Paradoxien zu vermeiden (oder so hoffen wir) und gleichzeitig die Fähigkeit zu haben, sehr ausdrucksstarke Typen zu konstruieren.

Martin Berger

14

A \to U_{i}

$A \rightarrow \mathcal{U}_i$

A \to U_{i}

$A \rightarrow \mathcal{U}_i$

U_{i}

$\mathcal{U}_i$

U_{i} : U_{i}

$\mathcal{U}_i : \mathcal{U}_i$

U

$\mathcal{U}$

\frac{⊢ Γ : c t x}{Γ ⊢ U_{i} : U_{i + 1}},

$\frac{\vdash \Gamma : ctx}{\Gamma \vdash \mathcal{U}_i : \mathcal{U}_{i+1}},$

Martin Berger
quelle

12

$X : \mathcal{U}_i$ $i \leq j$ $X : \mathcal{U}_j$ $A : \mathcal{U}_{42}$ $A \to \mathcal{U}_{99}$ $\to$

\frac{Γ ⊢ X : U_{i} Γ ⊢ Y : U_{i}}{Γ ⊢ (X \to Y) : U_{i}}

$\frac{\Gamma \vdash X : \mathcal{U}_i \qquad \Gamma \vdash Y : \mathcal{U}_i}{\Gamma \vdash (X \to Y) : \mathcal{U}_i}$

X \to Y

$X \to Y$

Π_{x : X} Y

$\Pi_{x : X} Y$

Π

$\Pi$

A

$A$

U_{42}

$\mathcal{U}_{42}$

U_{99}

$\mathcal{U}_{99}$

U_{100}

$\mathcal{U}_{100}$

A : U_{100}

$A : \mathcal{U}_{100}$ und fahren Sie dann fort, um zu zeigen, dass

den Typ

.

A \to U_{99}

$A \to \mathcal{U}_{99}$

U_{100}

$\mathcal{U}_{100}$

$\to$

\frac{Γ ⊢ X : U_{i} Γ ⊢ Y : U_{j}}{Γ ⊢ (X \to Y) : U_{max (i, j)}}

$\frac{\Gamma \vdash X : \mathcal{U}_i \qquad \Gamma \vdash Y : \mathcal{U}_j}{\Gamma \vdash (X \to Y) : \mathcal{U}_{\max(i,j)}}$

\frac{Γ ⊢ X : U_{i} Γ ⊢ Y : U_{j} i \leq k j \leq k}{Γ ⊢ (X \to Y) : U_{k}}

$\frac{\Gamma \vdash X : \mathcal{U}_i \qquad \Gamma \vdash Y : \mathcal{U}_j \qquad i \leq k \qquad j \leq k}{\Gamma \vdash (X \to Y) : \mathcal{U}_k}$

Andrej Bauer
quelle

Universen in abhängiger Typentheorie

Antworten: