Skip to content

feat(Data/List/Chain): generalize WellFounded.asymmetric₃ to chains#36922

Open
SnirBroshi wants to merge 2 commits intoleanprover-community:masterfrom
SnirBroshi:feature/well-founded-asymmetric-n
Open

feat(Data/List/Chain): generalize WellFounded.asymmetric₃ to chains#36922
SnirBroshi wants to merge 2 commits intoleanprover-community:masterfrom
SnirBroshi:feature/well-founded-asymmetric-n

Conversation

@SnirBroshi
Copy link
Copy Markdown
Collaborator

@SnirBroshi SnirBroshi commented Mar 20, 2026

The existing WellFounded.asymmetric shows r a b → ¬r b a,
and WellFounded.asymmetric₃ shows r a b → r b c → ¬r c a.
This adds WellFounded.asymmetricₙ which shows l.IsChain r → ¬r l.getLast l.head.

Also adds a couple of IsChain lemmas which might be useful.

Open in Gitpod

@github-actions
Copy link
Copy Markdown

github-actions bot commented Mar 20, 2026 •
edited
Loading

PR summary 0879935299

Import changes for modified files

No significant changes to the import graph

Import changes for all files
Files Import difference

Declarations diff

+ IsChain.rel_getLast_dropLast
+ IsChain.rel_getLast_head_of_append
+ WellFounded.asymmetricₙ
+ WellFoundedRelation.asymmetricₙ

You can run this locally as follows 
## summary with just the declaration names:
./scripts/pr_summary/declarations_diff.sh <optional_commit>

## more verbose report:
./scripts/pr_summary/declarations_diff.sh long <optional_commit>

The doc-module for scripts/pr_summary/declarations_diff.sh contains some details about this script.

No changes to technical debt.

You can run this locally as

./scripts/reporting/technical-debt-metrics.sh pr_summary
  • The relative value is the weighted sum of the differences with weight given by the inverse of the current value of the statistic.
  • The absolute value is the relative value divided by the total sum of the inverses of the current values (i.e. the weighted average of the differences).

@github-actions github-actions bot added the t-data Data (lists, quotients, numbers, etc) label Mar 20, 2026
vihdzp
vihdzp reviewed Mar 21, 2026
View reviewed changes
Mathlib/Data/List/Chain.lean

end List

theorem WellFoundedRelation.asymmetricₙ [WellFoundedRelation α] {l : List α} (hne : l ≠ [])
Copy link
Copy Markdown
Collaborator

@vihdzp vihdzp Mar 21, 2026

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I don't think we should be writing theorems about WellFoundedRelation. Yeah, I know WellFounded.asymmetric does the same, but that's a core idiosyncracy we should probably fix at some point.

Copy link
Copy Markdown
Collaborator Author

@SnirBroshi SnirBroshi Mar 21, 2026

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I couldn't manage to get termination_by working without this intermediate step

@mathlib-merge-conflicts mathlib-merge-conflicts bot added the merge-conflict The PR has a merge conflict with master, and needs manual merging. (this label is managed by a bot) label Mar 25, 2026
@mathlib-merge-conflicts
Copy link
Copy Markdown

mathlib-merge-conflicts bot commented Mar 25, 2026

This pull request has conflicts, please merge master and resolve them.

@github-actions github-actions bot removed the merge-conflict The PR has a merge conflict with master, and needs manual merging. (this label is managed by a bot) label Mar 25, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

1 more reviewer

@vihdzp vihdzp vihdzp left review comments

Reviewers whose approvals may not affect merge requirements

Assignees

@joneugster joneugster

Labels

t-data Data (lists, quotients, numbers, etc)

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

3 participants

@SnirBroshi @vihdzp @joneugster