Skip to content

[Merged by Bors] - feat: filtering lists and bounded quantifiers are primitive recursive#26295

Closed
DavidJWebb wants to merge 63 commits intoleanprover-community:masterfrom
DavidJWebb:PrimRec-Filter
Closed

[Merged by Bors] - feat: filtering lists and bounded quantifiers are primitive recursive#26295
DavidJWebb wants to merge 63 commits intoleanprover-community:masterfrom
DavidJWebb:PrimRec-Filter

Conversation

@DavidJWebb
Copy link
Copy Markdown
Contributor

@DavidJWebb DavidJWebb commented Jun 23, 2025

A few useful lemmas not explicitly in Primrec.lean :

  • Filtering for elements from a list that meet a primrec criterion is primrec
  • Checking whether a list has some element meeting a primrec criterion is primrec
  • Checking whether every element of a list meets a primrec criterion is primrec
  • Primitive recursive functions are closed under bounded existential and universal quantifiers

Open in Gitpod

@github-actions github-actions bot added new-contributor This PR was made by a contributor with at most 5 merged PRs. Welcome to the community! t-computability Computability theory (TMs, DFAs, languages, grammars, etc) labels Jun 23, 2025
@github-actions
Copy link
Copy Markdown

github-actions bot commented Jun 23, 2025 •
edited
Loading

PR summary ebe81ab238

Import changes for modified files

No significant changes to the import graph

Import changes for all files
Files Import difference

Declarations diff

+ listFilter_listRange
+ not
++ exists_lt
++ exists_mem_list
++ forall_lt
++ forall_mem_list
++ listFilter

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

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

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

Increase in tech debt: (relative, absolute) = (1.00, 0.33)
Current number Change Type
3 1 large files

Current commit fc9a6571fa
Reference commit ebe81ab238

You can run this locally as

./scripts/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).

@grunweg grunweg changed the title Filtering lists and bounded quantifiers are primitive recursive feat: filtering lists and bounded quantifiers are primitive recursive Jun 23, 2025
grunweg
grunweg reviewed Jun 23, 2025
View reviewed changes
@grunweg grunweg added the awaiting-author A reviewer has asked the author a question or requested changes. label Jun 23, 2025
@grunweg grunweg removed the awaiting-author A reviewer has asked the author a question or requested changes. label Jun 24, 2025
grunweg
grunweg reviewed Jul 22, 2025
View reviewed changes
Copy link
Copy Markdown
Contributor

@grunweg grunweg left a comment

Choose a reason for hiding this comment

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

Your code looks good, but can be compressed a bit.
I left some comments in this direction; I'll look again when have had time to address these ones.

@grunweg grunweg added the awaiting-author A reviewer has asked the author a question or requested changes. label Jul 22, 2025
@DavidJWebb
Copy link
Copy Markdown
Contributor Author

DavidJWebb commented Jul 24, 2025 •
edited
Loading

Your code looks good, but can be compressed a bit. I left some comments in this direction

I appreciate the tips - they helped me golf my next file down by 100 lines, or ~20%!

@DavidJWebb
Copy link
Copy Markdown
Contributor Author

DavidJWebb commented Aug 14, 2025

-awaiting-author

@github-actions github-actions bot removed the awaiting-author A reviewer has asked the author a question or requested changes. label Aug 14, 2025
YaelDillies
YaelDillies approved these changes Aug 15, 2025
View reviewed changes
Copy link
Copy Markdown
Contributor

@YaelDillies YaelDillies left a comment

Choose a reason for hiding this comment

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

Thanks!

maintainer delegate

@github-actions
Copy link
Copy Markdown

github-actions bot commented Aug 15, 2025

🚀 Pull request has been placed on the maintainer queue by YaelDillies.

@ghost ghost added the maintainer-merge A reviewer has approved the changed; awaiting maintainer approval. label Aug 15, 2025
@DavidJWebb
Copy link
Copy Markdown
Contributor Author

DavidJWebb commented Aug 15, 2025 •
edited
Loading

Made as many of those changes as I could. A few of the shortenings threw errors if executed all the way, but most of the .comps and .eqs went through okay.

YaelDillies
YaelDillies reviewed Aug 15, 2025
View reviewed changes
@bryangingechen
Copy link
Copy Markdown
Contributor

bryangingechen commented Aug 15, 2025

Thanks!
bors d+

@mathlib-bors
Copy link
Copy Markdown
Contributor

mathlib-bors bot commented Aug 15, 2025

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

@ghost ghost added delegated This pull request has been delegated to the PR author (or occasionally another non-maintainer). and removed maintainer-merge A reviewer has approved the changed; awaiting maintainer approval. labels Aug 15, 2025
@DavidJWebb
Copy link
Copy Markdown
Contributor Author

DavidJWebb commented Aug 15, 2025

bors r+

mathlib-bors bot pushed a commit that referenced this pull request Aug 15, 2025
@DavidJWebb
feat: filtering lists and bounded quantifiers are primitive recursive (…
a13fa16 
…#26295)

A few useful lemmas not explicitly in Primrec.lean :

- Filtering for elements from a list that meet a primrec criterion is primrec
- Checking whether a list has some element meeting a primrec criterion is primrec
- Checking whether every element of a list meets a primrec criterion is primrec
- Primitive recursive functions are closed under bounded existential and universal quantifiers
@mathlib-bors
Copy link
Copy Markdown
Contributor

mathlib-bors bot commented Aug 15, 2025

Build failed (retrying...):

mathlib-bors bot pushed a commit that referenced this pull request Aug 15, 2025
@DavidJWebb
feat: filtering lists and bounded quantifiers are primitive recursive (…
7747617 
…#26295)

A few useful lemmas not explicitly in Primrec.lean :

- Filtering for elements from a list that meet a primrec criterion is primrec
- Checking whether a list has some element meeting a primrec criterion is primrec
- Checking whether every element of a list meets a primrec criterion is primrec
- Primitive recursive functions are closed under bounded existential and universal quantifiers
@mathlib-bors
Copy link
Copy Markdown
Contributor

mathlib-bors bot commented Aug 15, 2025

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 Aug 16, 2025
@DavidJWebb
feat: filtering lists and bounded quantifiers are primitive recursive (…
b2b88d7 
…#26295)

A few useful lemmas not explicitly in Primrec.lean :

- Filtering for elements from a list that meet a primrec criterion is primrec
- Checking whether a list has some element meeting a primrec criterion is primrec
- Checking whether every element of a list meets a primrec criterion is primrec
- Primitive recursive functions are closed under bounded existential and universal quantifiers
@mathlib-bors
Copy link
Copy Markdown
Contributor

mathlib-bors bot commented Aug 16, 2025

Pull request successfully merged into master.

Build succeeded:

@mathlib-bors mathlib-bors bot changed the title feat: filtering lists and bounded quantifiers are primitive recursive [Merged by Bors] - feat: filtering lists and bounded quantifiers are primitive recursive Aug 16, 2025
@mathlib-bors mathlib-bors bot closed this Aug 16, 2025
@DavidJWebb DavidJWebb deleted the PrimRec-Filter branch August 16, 2025 00:51
Julian added a commit to Aaron1011/mathlib4 that referenced this pull request Aug 16, 2025
@Julian
Merge remote-tracking branch 'origin/master' into gromov-growth
74c41e2 
* origin/master: (508 commits)
  feat(Logic/Basic): forall_and_index (leanprover-community#27737)
  feat(Algebra/intNorm): `x` divides `intNorm x` (leanprover-community#28021)
  feat(RingTheory/MvPolynomial/MonomialOrder): some lemmas about degree (leanprover-community#26000)
  chore: more elementary Motzkin polynomial proof (leanprover-community#28482)
  feat: e-seminormed monoid (leanprover-community#27385)
  feat(RingTheory): ` (⊥ : Ideal R) ^ n = ⊥` (leanprover-community#28171)
  fix(LinearAlgebra/Dimension/ErdosKaplansky): authorship (leanprover-community#28513)
  chore: golf entire `X_pow_eq_monomial` (leanprover-community#28504)
  feat(RingTheory): invertible modules and Picard group (leanprover-community#25337)
  chore: use delta `deriving` for leanprover-community#380 (leanprover-community#28498)
  feat: add bilinear maps for vector/matrix products (leanprover-community#28130)
  feat(Counterexamples): topologists' sine curve (leanprover-community#25833)
  feat(Analysis/Convex): doubly stochastic matrices have operator norm at most one (leanprover-community#28453)
  chore(Topology/Compactification): deprecate duplicate `ultrafilter_pure_injective` (leanprover-community#28436)
  feat: add `@[simp]` to `Multiset.cons_le_cons` and `Finset.insert_subset_insert` (leanprover-community#28285)
  feat: make `ring` work for semifields (leanprover-community#28494)
  feat: filtering lists and bounded quantifiers are primitive recursive (leanprover-community#26295)
  chore(Analysis/Analytic): split `Analytic.Basic` (leanprover-community#26270)
  refactor: tidy `mulVec` and `vecMul` lemmas about `•` (leanprover-community#28450)
  feat(Order/WellFounded): Acc and infinite descending chain (leanprover-community#28120)
  feat(NumberTheory/Padics): {Int,Rat}.padicValuation (leanprover-community#27667)
  chore(*): address a few timeout-related porting notes (leanprover-community#28483)
  feat(Algebra): toAlgebra_algebraMap (leanprover-community#28238)
  feat(Shrink): `IsCancelMul` instance (leanprover-community#28407)
  chore(Geometry): golf entire `chart_eq'` and `orthogonalProjection_orthogonalProjection` (leanprover-community#28485)
  feat: shifted geometric series and a `ProbabilityMeasure` version of `measure_iUnion_le` (leanprover-community#28087)
  chore(LinearAlgebra/PiTensorProduct): `rw` away use of `erw` in `lifts_zero` (leanprover-community#27554)
  feat(RingTheory): faithfully flat ring maps (leanprover-community#24530)
  chore(Geometry/RingedSpace): remove use of `erw` in `stalkSpecializes_stalkMap` (leanprover-community#27656)
  chore: add the Brownian motion project to downstream_repos.yml (leanprover-community#28459)
  feat(CategoryTheory/Sites/SheafOfTypes): composition of a sheaf with uliftFunctor is still a sheaf (leanprover-community#27816)
  feat(Valuation/DiscreteValuationRel): val relations with compatible valuations to Zm0 are IsDiscrete (leanprover-community#27213)
  chore(*): process a bunch of `aesop`-related porting notes (leanprover-community#28402)
  feat(CategoryTheory): abstract argument for the stability under transfinite compositions (leanprover-community#26030)
  chore: bump toolchain to v4.23.0-rc2 (leanprover-community#28454)
  chore(FieldTheory/Finite): fermat's little theorem in Nat form (leanprover-community#27962)
  feat(Combinatorics/SimpleGraph/Paths): add theorem `SimpleGraph.Walk.IsPath.concat` (leanprover-community#27582)
  feat(Slope): slope_pos_iff_of_le and related lemmas (leanprover-community#28039)
  feat: tactic analysis framework (leanprover-community#26683)
  chore(Data/EReal): deprecate `add_pos_of_nonneg_of_pos` and `add_ne_top_iff_of_ne_bot` (duplicates) (leanprover-community#28424)
  feat(MathlibTest/FieldSimp): add a few more tests (leanprover-community#28413)
  chore(RingTheory/HahnSeries): deprecate duplicate `orderTop_add_orderTop_le_orderTop_mul` (leanprover-community#28231)
  chore(AlgebraicGeometry/IdealSheaf): deprecate duplicate `AlgebraicGeometry.Scheme.IdealSheafData.Scheme.zeroLocus_radical` (leanprover-community#28202)
  feat(Algebra/Order): ArchimedeanClass ball (leanprover-community#27885)
  chore(Geometry/RingedSpace): remove use of `erw` in `isUnit_of_isUnit_germ` (leanprover-community#27660)
  feat(SkewMonoidAlgebra): coeff_mul lemmas (leanprover-community#27255)
  chore(LinearAlgebra): golf entire `isUnit_det` (leanprover-community#28438)
  chore(FieldTheory/IntermediateField): golf entire `coe_sum` and `coe_prod` (leanprover-community#28431)
  feat: separate linter error message for empty doc-strings (leanprover-community#27895)
  feat(RingTheory/PowerSeries/Binomial): add basic lemmas, golf (leanprover-community#27497)
  ...
Paul-Lez pushed a commit to Paul-Lez/mathlib4 that referenced this pull request Aug 23, 2025
@DavidJWebb @Paul-Lez
feat: filtering lists and bounded quantifiers are primitive recursive (…
798cee4 
…leanprover-community#26295)

A few useful lemmas not explicitly in Primrec.lean :

- Filtering for elements from a list that meet a primrec criterion is primrec
- Checking whether a list has some element meeting a primrec criterion is primrec
- Checking whether every element of a list meets a primrec criterion is primrec
- Primitive recursive functions are closed under bounded existential and universal quantifiers
pechersky pushed a commit to pechersky/mathlib4 that referenced this pull request Aug 25, 2025
@DavidJWebb @pechersky
feat: filtering lists and bounded quantifiers are primitive recursive (…
97178ce 
…leanprover-community#26295)

A few useful lemmas not explicitly in Primrec.lean :

- Filtering for elements from a list that meet a primrec criterion is primrec
- Checking whether a list has some element meeting a primrec criterion is primrec
- Checking whether every element of a list meets a primrec criterion is primrec
- Primitive recursive functions are closed under bounded existential and universal quantifiers
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@grunweg grunweg grunweg left review comments

@YaelDillies YaelDillies YaelDillies approved these changes

Assignees

No one assigned

Labels

delegated This pull request has been delegated to the PR author (or occasionally another non-maintainer). new-contributor This PR was made by a contributor with at most 5 merged PRs. Welcome to the community! t-computability Computability theory (TMs, DFAs, languages, grammars, etc)

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

4 participants

@DavidJWebb @grunweg @YaelDillies @bryangingechen