Skip to content

[Merged by Bors] - feat: subsingleton tactic#12525

Closed
kmill wants to merge 30 commits intomasterfrom
kmill_subsingleton
Closed

[Merged by Bors] - feat: subsingleton tactic#12525
kmill wants to merge 30 commits intomasterfrom
kmill_subsingleton

Conversation

@kmill
Copy link
Copy Markdown
Contributor

@kmill kmill commented Apr 29, 2024

The subsingleton tactic tries to close equality goals by arguing that the underlying type is a subsingleton type. It might be via a Subsingleton instance (via Subsingleton.elim), but it also handles some cases where morally the types are subsingletons; for example, it can prove that two BEq instances are equal if they both have LawfulBEq instances. For heterogeneous equality, it tries the HEq version of proof irrelevance.

This tactic avoids the issue where

example (α : Sort _) (x y : α) : x = y := by apply Subsingleton.elim

is a "proof" that every type is trivial. Changing this to by subsingleton prevents it from assigning the universe level metavariable in Sort _ to 0.

This tactic can accept a list of instances subsingleton [inst1, inst2, ...] to do something like have := inst1; have := inst2; ...; subsingleton, but it elaborates them in a lenient way (like simp arguments), and they can even be universe polymorphic. For example, subsingleton [CharP.CharOne.subsingleton] is allowed even though the type of CharP.CharOne.subsingleton is Subsingleton ?R with a number of pending instance problems.

This PR also eliminates a number of uses of Subsingleton.elim, either by switching a congr to congr! or by using this new tactic.


Open in Gitpod

kmill added 2 commits April 29, 2024 14:20
The `subsingleton` tactic tries to close equality goals by arguing that the underlying type is a subsingleton type, usually because there is a `Subsingleton` instance. It also handles some cases where morally the types are subsingletons; for example, it can prove that two `BEq` instances are equal if they both have `LawfulBEq` instances.

For heterogeneous equality, it tries the `HEq` version of proof irrelevance, but it can also transform a `@HEq α x β y` goal into a `α = β` goal using `Subsingleton.helim`.

The tactic avoids the issue where
```lean
example (α : Sort _) (x y : α) : x = y := by apply Subsingleton.elim
```
is a "proof" that every type is trivial. Changing this to `by subsingleton` prevents it from assigning the universe level metavariable in `Sort _` to `0`.

This PR also eliminates some uses of `Subsingleton.elim`, either by switching a `congr` to `congr!` or by using this new tactic.
@kmill kmill added awaiting-review t-meta Tactics, attributes or user commands labels Apr 29, 2024
@ghost ghost added the merge-conflict The PR has a merge conflict with master, and needs manual merging. (this label is managed by a bot) label Apr 30, 2024
@ghost ghost removed the merge-conflict The PR has a merge conflict with master, and needs manual merging. (this label is managed by a bot) label Apr 30, 2024
@kmill
Copy link
Copy Markdown
Contributor Author

kmill commented Apr 30, 2024

!bench

@leanprover-bot
Copy link
Copy Markdown
Collaborator

Here are the benchmark results for commit 6ac7cfe.
There were no significant changes against commit 335470e.

@ghost ghost added the merge-conflict The PR has a merge conflict with master, and needs manual merging. (this label is managed by a bot) label May 2, 2024
@ghost ghost removed the merge-conflict The PR has a merge conflict with master, and needs manual merging. (this label is managed by a bot) label May 6, 2024
@ghost ghost added the merge-conflict The PR has a merge conflict with master, and needs manual merging. (this label is managed by a bot) label May 18, 2024
@ghost ghost removed the merge-conflict The PR has a merge conflict with master, and needs manual merging. (this label is managed by a bot) label May 22, 2024
@kim-em
Copy link
Copy Markdown
Contributor

kim-em commented Jul 1, 2024

bors merge

@github-actions github-actions bot added ready-to-merge This PR has been sent to bors. and removed awaiting-review labels Jul 1, 2024
mathlib-bors bot pushed a commit that referenced this pull request Jul 1, 2024
The `subsingleton` tactic tries to close equality goals by arguing that the underlying type is a subsingleton type. It might be via a `Subsingleton` instance (via `Subsingleton.elim`), but it also handles some cases where morally the types are subsingletons; for example, it can prove that two `BEq` instances are equal if they both have `LawfulBEq` instances. For heterogeneous equality, it tries the `HEq` version of proof irrelevance.

This tactic avoids the issue where
```lean
example (α : Sort _) (x y : α) : x = y := by apply Subsingleton.elim
```
is a "proof" that every type is trivial. Changing this to `by subsingleton` prevents it from assigning the universe level metavariable in `Sort _` to `0`.

This tactic can accept a list of instances `subsingleton [inst1, inst2, ...]` to do something like `have := inst1; have := inst2; ...; subsingleton`, but it elaborates them in a lenient way (like `simp` arguments), and they can even be universe polymorphic. For example, `subsingleton [CharP.CharOne.subsingleton]` is allowed even though the type of `CharP.CharOne.subsingleton` is `Subsingleton ?R` with a number of pending instance problems.

This PR also eliminates a number of uses of `Subsingleton.elim`, either by switching a `congr` to `congr!` or by using this new tactic.
@mathlib-bors
Copy link
Copy Markdown
Contributor

mathlib-bors bot commented Jul 1, 2024

Build failed (retrying...):

mathlib-bors bot pushed a commit that referenced this pull request Jul 1, 2024
The `subsingleton` tactic tries to close equality goals by arguing that the underlying type is a subsingleton type. It might be via a `Subsingleton` instance (via `Subsingleton.elim`), but it also handles some cases where morally the types are subsingletons; for example, it can prove that two `BEq` instances are equal if they both have `LawfulBEq` instances. For heterogeneous equality, it tries the `HEq` version of proof irrelevance.

This tactic avoids the issue where
```lean
example (α : Sort _) (x y : α) : x = y := by apply Subsingleton.elim
```
is a "proof" that every type is trivial. Changing this to `by subsingleton` prevents it from assigning the universe level metavariable in `Sort _` to `0`.

This tactic can accept a list of instances `subsingleton [inst1, inst2, ...]` to do something like `have := inst1; have := inst2; ...; subsingleton`, but it elaborates them in a lenient way (like `simp` arguments), and they can even be universe polymorphic. For example, `subsingleton [CharP.CharOne.subsingleton]` is allowed even though the type of `CharP.CharOne.subsingleton` is `Subsingleton ?R` with a number of pending instance problems.

This PR also eliminates a number of uses of `Subsingleton.elim`, either by switching a `congr` to `congr!` or by using this new tactic.
@mathlib-bors
Copy link
Copy Markdown
Contributor

mathlib-bors bot commented Jul 1, 2024

Build failed (retrying...):

@sgouezel
Copy link
Copy Markdown
Contributor

sgouezel commented Jul 1, 2024

bors r-

@mathlib-bors
Copy link
Copy Markdown
Contributor

mathlib-bors bot commented Jul 1, 2024

Canceled.

@sgouezel
Copy link
Copy Markdown
Contributor

sgouezel commented Jul 1, 2024

Can you merge master, fix the build, and send it back to bors?
bors d+

@mathlib-bors
Copy link
Copy Markdown
Contributor

mathlib-bors bot commented Jul 1, 2024

✌️ kmill can now approve this pull request. To approve and merge a pull request, simply reply with bors r+. More detailed instructions are available here.

@github-actions github-actions bot added the delegated This pull request has been delegated to the PR author (or occasionally another non-maintainer). label Jul 1, 2024
@kmill
Copy link
Copy Markdown
Contributor Author

kmill commented Jul 1, 2024

bors r+

mathlib-bors bot pushed a commit that referenced this pull request Jul 1, 2024
The `subsingleton` tactic tries to close equality goals by arguing that the underlying type is a subsingleton type. It might be via a `Subsingleton` instance (via `Subsingleton.elim`), but it also handles some cases where morally the types are subsingletons; for example, it can prove that two `BEq` instances are equal if they both have `LawfulBEq` instances. For heterogeneous equality, it tries the `HEq` version of proof irrelevance.

This tactic avoids the issue where
```lean
example (α : Sort _) (x y : α) : x = y := by apply Subsingleton.elim
```
is a "proof" that every type is trivial. Changing this to `by subsingleton` prevents it from assigning the universe level metavariable in `Sort _` to `0`.

This tactic can accept a list of instances `subsingleton [inst1, inst2, ...]` to do something like `have := inst1; have := inst2; ...; subsingleton`, but it elaborates them in a lenient way (like `simp` arguments), and they can even be universe polymorphic. For example, `subsingleton [CharP.CharOne.subsingleton]` is allowed even though the type of `CharP.CharOne.subsingleton` is `Subsingleton ?R` with a number of pending instance problems.

This PR also eliminates a number of uses of `Subsingleton.elim`, either by switching a `congr` to `congr!` or by using this new tactic.
@kmill
Copy link
Copy Markdown
Contributor Author

kmill commented Jul 1, 2024

bors r-

@mathlib-bors
Copy link
Copy Markdown
Contributor

mathlib-bors bot commented Jul 1, 2024

Canceled.

@kmill
Copy link
Copy Markdown
Contributor Author

kmill commented Jul 1, 2024

bors r+

mathlib-bors bot pushed a commit that referenced this pull request Jul 1, 2024
The `subsingleton` tactic tries to close equality goals by arguing that the underlying type is a subsingleton type. It might be via a `Subsingleton` instance (via `Subsingleton.elim`), but it also handles some cases where morally the types are subsingletons; for example, it can prove that two `BEq` instances are equal if they both have `LawfulBEq` instances. For heterogeneous equality, it tries the `HEq` version of proof irrelevance.

This tactic avoids the issue where
```lean
example (α : Sort _) (x y : α) : x = y := by apply Subsingleton.elim
```
is a "proof" that every type is trivial. Changing this to `by subsingleton` prevents it from assigning the universe level metavariable in `Sort _` to `0`.

This tactic can accept a list of instances `subsingleton [inst1, inst2, ...]` to do something like `have := inst1; have := inst2; ...; subsingleton`, but it elaborates them in a lenient way (like `simp` arguments), and they can even be universe polymorphic. For example, `subsingleton [CharP.CharOne.subsingleton]` is allowed even though the type of `CharP.CharOne.subsingleton` is `Subsingleton ?R` with a number of pending instance problems.

This PR also eliminates a number of uses of `Subsingleton.elim`, either by switching a `congr` to `congr!` or by using this new tactic.
@mathlib-bors
Copy link
Copy Markdown
Contributor

mathlib-bors bot commented Jul 1, 2024

This PR was included in a batch that was canceled, it will be automatically retried

mathlib-bors bot pushed a commit that referenced this pull request Jul 1, 2024
The `subsingleton` tactic tries to close equality goals by arguing that the underlying type is a subsingleton type. It might be via a `Subsingleton` instance (via `Subsingleton.elim`), but it also handles some cases where morally the types are subsingletons; for example, it can prove that two `BEq` instances are equal if they both have `LawfulBEq` instances. For heterogeneous equality, it tries the `HEq` version of proof irrelevance.

This tactic avoids the issue where
```lean
example (α : Sort _) (x y : α) : x = y := by apply Subsingleton.elim
```
is a "proof" that every type is trivial. Changing this to `by subsingleton` prevents it from assigning the universe level metavariable in `Sort _` to `0`.

This tactic can accept a list of instances `subsingleton [inst1, inst2, ...]` to do something like `have := inst1; have := inst2; ...; subsingleton`, but it elaborates them in a lenient way (like `simp` arguments), and they can even be universe polymorphic. For example, `subsingleton [CharP.CharOne.subsingleton]` is allowed even though the type of `CharP.CharOne.subsingleton` is `Subsingleton ?R` with a number of pending instance problems.

This PR also eliminates a number of uses of `Subsingleton.elim`, either by switching a `congr` to `congr!` or by using this new tactic.
@mathlib-bors
Copy link
Copy Markdown
Contributor

mathlib-bors bot commented Jul 1, 2024

Build failed (retrying...):

mathlib-bors bot pushed a commit that referenced this pull request Jul 1, 2024
The `subsingleton` tactic tries to close equality goals by arguing that the underlying type is a subsingleton type. It might be via a `Subsingleton` instance (via `Subsingleton.elim`), but it also handles some cases where morally the types are subsingletons; for example, it can prove that two `BEq` instances are equal if they both have `LawfulBEq` instances. For heterogeneous equality, it tries the `HEq` version of proof irrelevance.

This tactic avoids the issue where
```lean
example (α : Sort _) (x y : α) : x = y := by apply Subsingleton.elim
```
is a "proof" that every type is trivial. Changing this to `by subsingleton` prevents it from assigning the universe level metavariable in `Sort _` to `0`.

This tactic can accept a list of instances `subsingleton [inst1, inst2, ...]` to do something like `have := inst1; have := inst2; ...; subsingleton`, but it elaborates them in a lenient way (like `simp` arguments), and they can even be universe polymorphic. For example, `subsingleton [CharP.CharOne.subsingleton]` is allowed even though the type of `CharP.CharOne.subsingleton` is `Subsingleton ?R` with a number of pending instance problems.

This PR also eliminates a number of uses of `Subsingleton.elim`, either by switching a `congr` to `congr!` or by using this new tactic.
@mathlib-bors
Copy link
Copy Markdown
Contributor

mathlib-bors bot commented Jul 1, 2024

Pull request successfully merged into master.

Build succeeded:

@mathlib-bors mathlib-bors bot changed the title feat: subsingleton tactic [Merged by Bors] - feat: subsingleton tactic Jul 1, 2024
@mathlib-bors mathlib-bors bot closed this Jul 1, 2024
@mathlib-bors mathlib-bors bot deleted the kmill_subsingleton branch July 1, 2024 21:15
dagurtomas pushed a commit that referenced this pull request Jul 2, 2024
The `subsingleton` tactic tries to close equality goals by arguing that the underlying type is a subsingleton type. It might be via a `Subsingleton` instance (via `Subsingleton.elim`), but it also handles some cases where morally the types are subsingletons; for example, it can prove that two `BEq` instances are equal if they both have `LawfulBEq` instances. For heterogeneous equality, it tries the `HEq` version of proof irrelevance.

This tactic avoids the issue where
```lean
example (α : Sort _) (x y : α) : x = y := by apply Subsingleton.elim
```
is a "proof" that every type is trivial. Changing this to `by subsingleton` prevents it from assigning the universe level metavariable in `Sort _` to `0`.

This tactic can accept a list of instances `subsingleton [inst1, inst2, ...]` to do something like `have := inst1; have := inst2; ...; subsingleton`, but it elaborates them in a lenient way (like `simp` arguments), and they can even be universe polymorphic. For example, `subsingleton [CharP.CharOne.subsingleton]` is allowed even though the type of `CharP.CharOne.subsingleton` is `Subsingleton ?R` with a number of pending instance problems.

This PR also eliminates a number of uses of `Subsingleton.elim`, either by switching a `congr` to `congr!` or by using this new tactic.
@adomani adomani mentioned this pull request Aug 1, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

delegated This pull request has been delegated to the PR author (or occasionally another non-maintainer). ready-to-merge This PR has been sent to bors. t-meta Tactics, attributes or user commands

Projects

None yet

Development

Successfully merging this pull request may close these issues.

6 participants