rocq-prover / rocq-prover/stdlib

Order tactic fails when `eq` is defined in terms of `le`

Open
#51 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Rocq Prover
Stars
42
Forks
38
Avg merge
14h 6m
Merged PRs (30d)
3

Description

Version

The Coq Proof Assistant, version 8.6.1 (November 2017)
compiled on Nov 5 2017 23:16:40 with OCaml 4.02.3

Operating system

Linux x86_64, NixOS 17.09

Description of the problem

Given an OrderTac module for T, I want to use the order tactic to prove

x, y : T
H : y < x -> False
______________________________________(1/1)
x <= y

But after order_prepare it ends up with

x, y : T
H : x <= y
H0 : ~ y == x
______________________________________(1/1)
False

which is not provable.

The trouble lies in my definition of eq x y as le x y /\ le y x and in the application of not_neg_eq at https://github.com/coq/coq/blob/a4043608f704f026de7eb5167a109ca48e00c221/theories/Structures/OrdersTac.v#L214. This application shouldn't succeed, but it does, because when apply is given a function of type A -> B /\ C, it'll "helpfully" add the necessary projection to unify with a goal of B. So in this case, not_neq_eq has type ~~y==x -> y==x, which unfolds to ~~y==x -> y <= x /\ x <= y, which undesirably unifies with the goal of x <= y.

This can be fixed by using simple apply rather than apply.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Inspect theories/Structures/OrdersTac.v around line 214 and follow the order_prepare path. Reproduce the supplied OrderTac example, then verify that the application no longer accepts the unintended projection and that the example proves the intended goal.

Written by the indexing model from the issue text.

Assessment

Domain
tooling
Issue type
Bug
Difficulty
1/5
Estimated time
Under an hour
Activity status
Stale
Clarity
Clearly specified
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.