Was ist Induktion-Induktion?

Was ist Induktion-Induktion ?

Die Ressourcen, die ich gefunden habe, sind:

das HoTT-Buch am Ende von Kapitel 5.7.
Artikel von nLab
ein Artikel namens Induktiv-Induktive Definitionen
In diesem Blogbeitrag werden auch induktiv-induktive Typen erwähnt

Die ersten beiden Referenzen sind mir zu kurz und die beiden letzteren zu technisch. Kann es jemand in Laienform erklären? Es wäre besser, wenn es Agda-Code gäbe.

type-theory induction inductive-datatypes 盛安安
quelle

Es gibt Agda-Code in Ihrem vierten Zitat.

Gilles 'SO - hör auf böse zu sein'

Sicher, aber es wäre super schwer, diese riesige Menge an Code durchzulesen. Und (ich denke) super einfach, wenn man nur 1 oder 2 Beispiele sieht.

Supplemental 2016-10-03: Ich habe Induktion-Induktion und Induktions-Rekursion gemischt (nicht das erste Mal, dass ich das gemacht habe!). Ich entschuldige mich für das Durcheinander. Ich habe die Antwort aktualisiert, um beide abzudecken.

Ich finde die Erklärungen in der Arbeit von Forsberg & Setzer Eine endliche Axiomatisierung induktiv-induktiver Definitionen aufschlussreich.

Induktionsrekursion

Eine induktiv-rekursive Definition ist eine Definition, bei der wir auf besondere Weise gleichzeitig einen Typ $A$ und eine Typfamilie $B : A \to \mathsf{Type}$ :

$A$ ist als induktiver Typ definiert.
$B$ wird durch Rekursion auf $A$ .
Entscheidend ist , dass die Definition von $A$ kann verwendet werden $B$ .

Ohne die dritte Anforderung könnten wir zuerst $A$ und dann separat $B$ .

Hier ist ein Babybeispiel. Definieren Sie $A$ induktiv, um die folgenden Konstruktoren zu haben:

$a : A$
$\ell : \big(\sum_{x : A} B(x)\big) \to A$

Die Typfamilie $B$ ist definiert durch

$B(a) = \mathtt{bool}$
$B(\ell(x, f)) = \mathtt{nat}$ .

$A$

a : A .

$a : A.$

B (a)

$B(a)$

b o o l

$\mathtt{bool}$

ℓ (a, f a l s e)

$\ell(a, \mathtt{false})$

ℓ (a, t r u e)

$\ell(a, \mathtt{true})$

A

$A$

B (ℓ (a, f a l s e)) = B (ℓ (a, t r u e)) = n a t

$B(\ell(a, \mathtt{false})) = B(\ell(a, \mathtt{true})) = \mathtt{nat}$

n : n a t

$n : \mathtt{nat}$

ℓ (ℓ (a, f a l s e), n) : A

$\ell(\ell(a, \mathtt{false}), n) : A$

ℓ (ℓ (a, t r u e), n) : A

$\ell(\ell(a, \mathtt{true}), n) : A$

B (ℓ (ℓ (a, t r u e), n)) = n a t

$B(\ell(\ell(a, \mathtt{true}), n)) = \mathtt{nat}$

m : n a t

$m : \mathtt{nat}$

ℓ (ℓ (ℓ (a, t r u e), n), m) : A

$\ell(\ell(\ell(a, \mathtt{true}), n), m) : A$

ℓ (ℓ (ℓ (a, f a l s e), n), m) : A

$\ell(\ell(\ell(a, \mathtt{false}), n), m) : A$

A

$A$

Induktion-Induktion

$A$ $B : A \to \mathsf{Type}$

$A$
$B$ $A$
$A$ $B$

$B$

B (c (\dots)) = \dots

$B(\mathsf{c}(\ldots)) = \cdots$

c (\dots)

$\mathsf{c}(\ldots)$

A

$A$

B

$B$

B

$B$

$A$

$a : A$
$\ell : \big(\sum_{x : A} B(x)\big) \to A$

$B$

$\mathsf{Tru} : B(a)$
$\mathsf{Fal} : B(a)$
$x : A$ $y : B(x)$ $\mathsf{Zer} : B(\ell(x,y))$
$x : A$ $y : B(x)$ $z : B(\ell(x,y))$ $\mathsf{Suc}(z) : B(\ell(x,y))$

$B$ $B(a)$ $B(\ell(x,y))$

Andrej Bauer
quelle

Warum zum Teufel sollte jemand solche Datentypen definieren

Um zu lehren, was ein induktiv-induktiver Typ ist. Ich könnte Ihnen ein reales Beispiel geben, nämlich ein Typuniversum, aber das wäre verwirrend.

Andrej Bauer

@AndrejBauer Das sieht für mich eher nach Induktionsrekursion aus. Induktion-Induktion ist, wenn die Typenfamilie als induktiver Typ definiert ist .

Gallais

Ups, du hast absolut recht. Ich werde es reparieren.

Andrej Bauer

ℓ

$\ell$

Was ist Induktion-Induktion?

Antworten:

Induktionsrekursion

Induktion-Induktion