How to define my own (recursive) Coq notations?

Question

I've started working a lot with Ensembles now, because they are more flexible. To help me with that, I'm trying to define some convenient notations. The following is relatively easy, for example:

Notation "a ∈ S" := (@In _ S a)  (at level 80).

And I can add a similar bunch for the other binary set operators.

But I'm having a lot of trouble with notations like this:

Notation "∀ x ∈ S , P" := (forall x, (x ∈ S) -> P)  (at level 90).

It is accepted, but whenever I try to use it I get this error:

Syntax error: "∈" expected after [constr:operconstr level 200] (in [constr:operconstr]).

Question 1: What am I doing wrong?

For bonus points, can you tell me how to define a recursive notation for it? I've tried, but it seems to give me a whole new set of problems. Here's my attempt, a straightforward edit of the library definition:

Notation "∀ x .. y ∈ S , P" :=
  (forall x, (x ∈ S) -> .. (forall y, (y ∈ S) -> P) ..)
  (at level 200, x binder, y binder, right associativity).

I don't see why the library version in Coq.Unicode.Utf8_core should parse and mine shouldn't, but:

Error: Cannot find where the recursive pattern starts.

Question 2: See question 1.

mhelvens mhelvens · Accepted Answer · 2013-06-05T22:59:58

The reason that the recursive notation above didn't work is that binders (in this case x and y) can only be used in one of two specific locations in the right hand side [see manual]:

at the binder location in a fun [ ] => ... term, or
at the binder location in a forall [ ], ... term.

So, I could not use them again as terms. This seems somewhat arbitrary to me, since binders are terms within their binding context. However, you can do pretty much anything you want with the fun route:

Definition all_in_E `(E: Ensemble T, P: T → Prop) : T → Prop :=
  (λ x: T, (x ∈ E) → (P x)).

Notation "∀ x .. y ∈ S , P" :=
  ( all ( all_in_E S ( fun x => .. ( all ( all_in_E S ( fun y => P ))) .. )))
  (at level 200, x closed binder, y closed binder, right associativity).

Definition ex_in_E `(E: Ensemble T, P: T → Prop) : T → Prop :=
  (λ x: T, (x ∈ E) ∧ (P x)).

Notation "∃ x .. y ∈ S , P" :=
  ( ex ( ex_in_E S ( fun x => .. ( ex ( ex_in_E S ( fun y => P ))) .. )))
  (at level 200, x closed binder, y closed binder, right associativity).

The functions all_in_E and ex_in_E take a predicate (a fun) and augment it with a condition for membership in a given ensemble E. It's taking the long way around, but it works.

Here's a fully working block of code with examples:

Require Export Coq.Unicode.Utf8.
Require Export Coq.Sets.Ensembles.

Generalizable All Variables.

Notation "a ∈ S" := (@In _ S a)            (at level 70, no   associativity).
Notation "A ∪ B" := (@Union _ A B)         (at level 50, left associativity).
Notation "A ∩ B" := (@Intersection _ A B)  (at level 40, left associativity).

Definition all_in_E `(E: Ensemble T, P: T → Prop) : T → Prop :=
  (λ x: T, (x ∈ E) → (P x)).

Notation "∀ x .. y ∈ S , P" :=
  ( all ( all_in_E S ( fun x => .. ( all ( all_in_E S ( fun y => P ))) .. )))
  (at level 200, x closed binder, y closed binder, right associativity).

Definition ex_in_E `(E: Ensemble T, P: T → Prop) : T → Prop :=
  (λ x: T, (x ∈ E) ∧ (P x)).

Notation "∃ x .. y ∈ S , P" :=
  ( ex ( ex_in_E S ( fun x => .. ( ex ( ex_in_E S ( fun y => P ))) .. )))
  (at level 200, x closed binder, y closed binder, right associativity).

Section TestingEnsembleQuantifiers.
  Definition A_nat := Full_set nat.
  Definition E_nat := Empty_set nat.
  Definition F_nat := Singleton _ 5.

  Require Import Coq.Arith.Gt.

  Example exists_in_intersection: ∃ x ∈ A_nat ∩ F_nat , x = 5.
    unfold ex_in_E.
    exists 5.
    split ; trivial.
    split.
    apply Full_intro.
    apply In_singleton.
  Qed.

  Example forall_in_union: ∀ x ∈ F_nat ∪ E_nat, x ≥ 5.
    unfold all_in_E, all.
    intros.
    destruct H ; destruct H.
    auto with arith.
  Qed.
End TestingEnsembleQuantifiers.

Please note also the new precedence levels for the set operators, which make more sense in relation to the existing precedence levels [see manual].

How to define my own (recursive) Coq notations?

1 Answers