एक मोनिक और महाकाव्य फ़ंक्शन एक आइसोमोर्फिज्म है, इसलिए इसका एक उलटा है। मुझे Coq में इसका एक प्रमाण चाहिए।

  Axiom functional_extensionality: forall A B (f g : A->B),  (forall a, f a = g a) -> f = g.
  Definition compose {A B C} (f : B->C) (g: A->B) a := f (g a).
  Notation "f ∘ g" := (compose f g) (at level 40).
  Definition id {A} (a:A) := a.
  Definition monic {A B} (f:A->B) := forall C {h k:C->A}, f ∘ h = f ∘ k -> h = k.
  Definition epic  {A B} (f:A->B) := forall C {h k:B->C}, h ∘ f = k ∘ f -> h = k.
  Definition iso {A B} (f:A->B) := monic f /\ epic f.

  Goal forall {A B} (f:A->B), iso f -> exists f', f∘f' = id /\ f'∘f = id.

मुझे ऑनलाइन मिले सबूत (1 , 2) कोई कंस्ट्रक्शन नहीं देते का f' (उलटा)। क्या इसे कोक में दिखाना संभव है? (यह मेरे लिए स्पष्ट नहीं है कि व्युत्क्रम गणना योग्य है ...)

coq
4
larsr 13 जिंदा 2020, 17:31

1 उत्तर

सबसे बढ़िया उत्तर

सबसे पहले, शब्दावली का सवाल। श्रेणी सिद्धांत में, एक समरूपता एक आकृतिवाद है जिसमें एक बाएँ और दाएँ उलटा होता है, इसलिए मैं आपकी परिभाषाओं को थोड़ा बदल रहा हूँ:

Definition compose {A B C} (f : B->C) (g: A->B) a := f (g a).
Notation "f ∘ g" := (compose f g) (at level 40).
Definition id {A} (a:A) := a.
Definition monic {A B} (f:A->B) := forall C {h k:C->A}, f ∘ h = f ∘ k -> h = k.
Definition epic  {A B} (f:A->B) := forall C {h k:B->C}, h ∘ f = k ∘ f -> h = k.
Definition iso {A B} (f:A->B) :=
  exists g : B -> A, f ∘ g = id /\ g ∘ f = id.

कुछ मानक स्वयंसिद्धों को मानकर इस परिणाम को सिद्ध करना संभव है, अर्थात् प्रस्तावात्मक विस्तार और रचनात्मक निश्चित विवरण (अद्वितीय पसंद का स्वयंसिद्ध):

Require Import Coq.Logic.FunctionalExtensionality.
Require Import Coq.Logic.PropExtensionality.
Require Import Coq.Logic.Description.

Section MonoEpiIso.

Context (A B : Type).

Implicit Types (f : A -> B) (x : A) (y : B).

Definition surjective f := forall y, exists x, f x = y.

Lemma epic_surjective f : epic f -> surjective f.
Proof.
intros epic_f y.
assert (H : (fun y => exists x, f x = y) = (fun y => True)).
{ apply epic_f.
  apply functional_extensionality.
  intros x; apply propositional_extensionality; split.
  - intros _; exact I.
  - now intros _; exists x. }
now pattern y; rewrite H.
Qed.

Definition injective f := forall x1 x2, f x1 = f x2 -> x1 = x2.

Lemma monic_injective f : monic f -> injective f.
Proof.
intros monic_f x1 x2 e.
assert (H : f ∘ (fun a : unit => x1) = f ∘ (fun a : unit => x2)).
{ now unfold compose; simpl; rewrite e. }
assert (e' := monic_f _ _ _ H).
exact (f_equal (fun g => g tt) e').
Qed.

Lemma monic_epic_iso f : monic f /\ epic f -> iso f.
Proof.
intros [monic_f epic_f].
assert (Hf : forall y, exists! x, f x = y).
{ intros y.
  assert (sur_f := epic_surjective _ epic_f).
  destruct (sur_f y) as [x xP].
  exists x; split; trivial.
  intros x' x'P.
  now apply (monic_injective _ monic_f); rewrite xP, x'P. }
exists (fun a => proj1_sig (constructive_definite_description _ (Hf a))).
split; apply functional_extensionality; unfold compose, id.
- intros y.
  now destruct (constructive_definite_description _ (Hf y)).
- intros x.
  destruct (constructive_definite_description _ (Hf (f x))); simpl.
  now apply (monic_injective _ monic_f).
Qed.

End MonoEpiIso.

मेरा मानना ​​​​है कि इस परिणाम को कम से कम किसी प्रकार की अनूठी पसंद के बिना साबित करना संभव नहीं है। प्रपोजल और फंक्शनल एक्सटेंलिटी मान लें। ध्यान दें कि, यदि exists! x : A, P x धारण करता है, तो अद्वितीय कार्य

{x | P x} -> unit

इंजेक्शन और विशेषण दोनों है। (विशिष्टता भाग से अंतःक्षेपण होता है, और अस्तित्व के भाग से प्रक्षेप्यता आती है।) यदि इस फ़ंक्शन में प्रत्येक P : A -> Type के लिए एक व्युत्क्रम होता है, तो हम इस व्युत्क्रम का उपयोग अद्वितीय पसंद के स्वयंसिद्ध को लागू करने के लिए कर सकते हैं। चूंकि यह स्वयंसिद्ध Coq में नहीं है, इसलिए इस व्युत्क्रम को मूल सिद्धांत में बनाना संभव नहीं होना चाहिए।

7
Arthur Azevedo De Amorim 13 जिंदा 2020, 15:55