CODEWITHSUNDEEP
coq
tomjerry7
tomjerry7

Reputation: 101

How to build a function implicitly in Coq?

I am trying to prove that every group has an inverse function.

I have defined a group as follows:

Record Group:Type := {
G:Set;
mult:G->G->G;
e:G;
assoc:forall x y z:G, mult x (mult y z)=mult (mult x y) z;
neut:forall x:G, mult e x=x /\ mult x e=x;
inverse:forall x:G,exists y:G, mult x y = e
}.

I am aware that it is better to just replace the inverse axiom by inverse:forall x:G, {y: mult x y = e}., or even inverse:G->G. is_inverse:forall x:G, mult x (inverse x)=e., but I prefer my definition, mainly because I want the definition to be identical to the one given in a classroom.

So I have included a suitable version of the axiom of choice:

Axiom indefinite_description : forall (A : Type) (P: A->Prop), ex P -> sig P.
Axiom functional_choice : forall A B (R:A->B->Prop), (forall x, exists y, R x y) -> (exists f, forall x, R x (f x)).

Now I can prove my claim:

Lemma inv_func_exists(H:Group):exists inv_func:G H->G H, (forall x:G H, mult H x (inv_func(x))=e H).
generalize (inverse H).
apply functional_choice.
Qed.

Now that I have proved the existence, I would like to define an actual function. Here I feel that things start to go messy. The following definition creates an actual function, but seems to ugly and complicated:

Definition inv_func(H:Group):G H->G H.
pose (inv_func_exists H).
pose indefinite_description.
generalize e0 s.
trivial.
Qed.

Lastly, I would like to prove that inv_func is actually an inverse function:

Lemma inv_func_is_inverse:forall (H:Group), forall x:(G H), mult H x (inv_func H x)=e H.

I can see that Coq knows how inv_func was defined (e.g. Print inv_func), but I have no idea how to formally prove the lemma.

To conclude, I would appreciate suggestions as to how to prove the last lemma, and of better ways to define inv_func (but under my definition of group, without including the existence of such a function in the group definition. I believe the question could be relevant in many other situations when one can prove some correspondence for each element and needs to build this correspondence as a function).

Upvotes: 2

Views: 223

Answers (1)

ejgallego
ejgallego

Reputation: 6852

There are quite a few questions inside your question. I'll try to address all of them:

  • First, there is no reason to prefer exists x, P + description over {x | P}, indeed, it seems weird you do so. {x | P} is perfectly valid as "there exists a x that can be computed" and I would rather use that definition with your groups.

  • Secondly, when creating definitions using tactics, you should end the proof with the command Defined. Using Qed will declare the definition "Opaque", which means it cannot be expanded, then preventing you proof.

  • The way to extract the witness from your definition is by using a projection. In this case, proj1_sig.

Using all the above we arrive at:

Definition inv_func' (H:Group) (x : G H) : G H.
Proof.
destruct (inverse H x) as [y _].
exact y.
Defined.

Definition inv_func (H:Group) (x : G H) : G H := proj1_sig (inverse H x).

Lemma inv_func_is_inverse (H:Group) (x: G H) : mult H x (inv_func H x) = e H.
Proof. now unfold inv_func; destruct (inverse H x). Qed.

Upvotes: 4

Related Questions