baz_num_elts Übung von Software Foundations

9

Ich bin bei der folgenden Übung in Software Foundations :

(** **** Exercise: 2 stars (baz_num_elts) *)
(** Consider the following inductive definition: *)

Inductive baz : Type :=
   | x : baz -> baz
   | y : baz -> bool -> baz.

(** How _many_ elements does the type [baz] have? 
(* FILL IN HERE *)
[] *)

Alle Antworten, die ich im Internet gesehen habe, besagen, dass die Antwort 2 ist und dass die Elemente x und y sind. Wenn das der Fall ist, ist mir nicht klar, was unter Elementen zu verstehen ist . Es gibt sicherlich zwei Konstruktoren, aber es ist unmöglich, tatsächlich einen Wert vom Typ baz zu erstellen .

Es ist unmöglich, einen Wert vom Typ Typ zu erstellen, bazda xdieser Typ hat baz -> baz. yhat Typ baz -> bool -> baz. Um einen Wert vom Typ zu erhalten baz, müssen wir einen Wert vom Typ bazentweder an xoder übergeben y. Wir können keinen Wert vom Typ erhalten, bazohne bereits einen Wert vom Typ zu haben baz.

Bisher habe ich bisher Interpretation Elemente , um Mittelwerte . Also (cons nat 1 nil)und (cons nat 1 (cons nat 2 nil))wären beide Elemente vom Typ list natund es würde unendlich viele Elemente vom Typ geben list nat. Es würde zwei Elemente des Typs geben bool, nämlich trueund false. Unter dieser Interpretation würde ich argumentieren, dass es keine Elemente des Typs gibt baz.

Bin ich richtig oder kann jemand erklären, was ich falsch verstehe?

coq Twernmilt
quelle
1
Sicher. Ich habe einen Absatz hinzugefügt, in dem erklärt wird, warum es meiner Meinung nach unmöglich ist, einen Typwert zu erstellen baz.
Twernmilt
Nett. Das habe ich mir gedacht. Danke, Twernmilt. Für das, was es wert ist, habe ich die gleiche Reaktion wie Sie: Auch ich hätte erwartet, dass die Antwort lautet, dass es keine Typelemente gibt baz.
DW

Antworten:

8

Ich stimme mit Ihnen ein. Es gibt eine Bijektion zwischen bazund False.

Definition injective : forall {t1 t2}, (t1 -> t2) -> Prop := fun t1 t2 f1 => forall x1 x2, f1 x1 = f1 x2 -> x1 = x2.

Definition surjective : forall {t1 t2}, (t1 -> t2) -> Prop := fun t1 t2 f1 => forall x1, exists x2, f1 x2 = x1.

Definition bijective : forall {t1 t2}, (t1 -> t2) -> Prop := fun t1 t2 f1 => injective f1 /\ surjective f1.

Inductive baz : Type :=
   | x : baz -> baz
   | y : baz -> bool -> baz.

Theorem baz_False : baz -> False. Proof. induction 1; firstorder. Qed.

Goal exists f1 : baz -> False, bijective f1.
Proof.
exists baz_False. unfold bijective, injective, surjective. firstorder.
assert (H2 := baz_False x1). firstorder.
assert (H2 := x1). firstorder.
Qed.
Rui Baptista
quelle