Gleich indizierte induktive Typen implizieren gleiche Indizes

9

Lassen Sie uns einen induktiven Typ durch fooindizieren x : X.

Parameter X : Type.

Inductive foo : X -> Type :=
| constr : forall (x : X), foo x.

Ich bin neugierig, wenn foo x = foo yimpliziert x = y. Ich habe keine Ideen, wie ich das beweisen kann.

Lemma type_equality_implies_index_equality : forall (x y : X), foo x = foo y -> x = y.

Wenn dies nicht bewiesen werden kann, warum?

Tom
quelle

Antworten:

8

Es kann nicht bewiesen werden. Betrachten Sie den folgenden Sonderfall des Satzes, wenn wir setzen X := bool:

foo true = foo false -> true = false

Angesichts dessen trueund falseanders, wenn der Satz beweisbar wäre, sollte es möglich sein, dies zu zeigen foo trueund foo falseanders zu sein. Das Problem ist, dass diese beiden Typen isomorph sind :

Inductive foo : bool -> Type :=
| constr : forall (x : bool), foo x.

(* An isomorphism between foo true and foo false *)
Definition foo_t_f (x : foo true) : foo false := constr false.
Definition foo_f_t (x : foo false) : foo true := constr true.

(* Proofs that the functions are inverses of each other *)
Lemma foo_t_fK x : foo_f_t (foo_t_f x) = x.
Proof. unfold foo_f_t, foo_t_f. now destruct x. Qed.

Lemma foo_f_tK x : foo_t_f (foo_f_t x) = x.
Proof. unfold foo_f_t, foo_t_f. now destruct x. Qed.

In Coqs Theorie ist es nicht möglich zu zeigen, dass zwei isomorphe Typen unterschiedlich sind, ohne zusätzliche Axiome anzunehmen. Aus diesem Grund ist eine Erweiterung der Coq-Theorie wie die Homotopietypentheorie sinnvoll. In HoTT kann gezeigt werden, dass isomorphe Typen gleich sind, und wenn es möglich wäre, Ihren Satz zu beweisen, wäre HoTT inkonsistent.

Arthur Azevedo De Amorim
quelle
Mein Kopf tut weh, aber ich glaube, ich verstehe. Hätten Sie eine Referenz für die Aussage "In Coqs Theorie ist es nicht möglich zu zeigen, dass zwei isomorphe Typen unterschiedlich sind, ohne zusätzliche Axiome anzunehmen." ?
Tom
Und ist es möglich zu zeigen (x <> y) -> (foo x <> foo y)? Ich bin wirklich verwirrt in dieser Welt ohne das Prinzip der ausgeschlossenen Mitte.
Tom
Die beste Referenz, die ich kenne (obwohl vielleicht nicht die zugänglichste), ist Hofmanns und Streichers Artikel "The Groupoid Interpretation of Type Theory". Wie Hofmann es ausdrückt ( ncatlab.org/homotopytypetheory/files/HofmannDMV.pdf ), können wir eine solide Erweiterung der Martin-Löf-Typentheorie haben, bei der isomorphe Typen gleich sind. Dieses Ergebnis gilt auch für die Theorie von Coq.
Arthur Azevedo De Amorim
Und nein, es ist nicht möglich, das Kontrapositive zu zeigen. Das Gegenbeispiel, das ich mit wahr und falsch gegeben habe, würde dieser Aussage ebenfalls widersprechen.
Arthur Azevedo De Amorim