latihan baz_num_elts dari Yayasan Perangkat Lunak

9

Saya mengikuti latihan berikut dalam Yayasan Perangkat Lunak :

(** **** 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 *)
[] *)

Semua jawaban yang saya lihat di Internet mengatakan bahwa jawabannya adalah 2, dan unsur-unsurnya adalah x dan y. Jika itu masalahnya, maka bagi saya tidak jelas apa yang dimaksud dengan elemen . Tentunya ada dua konstruktor, tetapi tidak mungkin untuk benar-benar membuat nilai tipe baz .

Tidak mungkin membuat nilai tipe bazkarena xmemiliki tipe baz -> baz. ymemiliki tipe baz -> bool -> baz. Untuk mendapatkan nilai tipe, bazkita harus meneruskan nilai tipe bazke salah satu xatau y. Kami tidak bisa mendapatkan nilai tipe baztanpa memiliki nilai tipe baz.

Sejauh ini saya telah menafsirkan elemen dengan nilai rata-rata . Jadi (cons nat 1 nil)dan (cons nat 1 (cons nat 2 nil))keduanya akan menjadi elemen tipe list natdan akan ada jumlah elemen tipe yang tak terbatas list nat. Akan ada dua elemen tipe bool, yaitu truedan false. Di bawah penafsiran ini, saya berpendapat bahwa tidak ada unsur elemen baz.

Apakah saya benar, atau bisakah seseorang menjelaskan apa yang saya salah pahami?

Twernmilt
sumber
1
Tentu. Saya telah menambahkan sebuah paragraf yang menjelaskan mengapa saya pikir tidak mungkin untuk membuat nilai tipe baz.
Twernmilt
Bagus. Itulah yang saya pikir Anda pikirkan. Terima kasih, Twernmilt. Untuk apa nilainya, saya memiliki reaksi yang sama dengan yang Anda lakukan: Saya juga akan mengharapkan jawabannya adalah bahwa tidak ada unsur elemen baz.
DW

Jawaban:

8

Saya setuju dengan kamu. Ada sebuah ikatan antara bazdan 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
sumber