Skip to content

[Merged by Bors] - refactor: ungeneralize LinearIndependent#18426

Closed
eric-wieser wants to merge 10 commits intomasterfrom
eric-wieser/ungeneralize-linear-independent
Closed

[Merged by Bors] - refactor: ungeneralize LinearIndependent#18426
eric-wieser wants to merge 10 commits intomasterfrom
eric-wieser/ungeneralize-linear-independent

Conversation

@eric-wieser
Copy link
Copy Markdown
Member

@eric-wieser eric-wieser commented Oct 30, 2024

The existing definition is nonsense over semirings; this replaces it with a more plausible one, such that:

example : ¬ LinearIndependent ℕ Nat.succ := by
  intro h
  have := @h (.single 3 1) (.single 1 2)
  simp [Finsupp.single_eq_single_iff] at this

which was previously true without the ¬.
Some of the nonsense semiring results following the definition must then be ungeneralized to rings.

I've been conservative here and only generalized the ones that generalizer trivially, and are used by important downstream
applications such as Basis on semirings. Unimportant downstream applications have instead been ungeneralized to Ring.
Many more results can likely be generalized in future.

Some context at https://leanprover.zulipchat.com/#narrow/channel/217875-Is-there-code-for-X.3F/topic/.E2.9C.94.20.60E.2FL.2FF.60.20and.20.60K.2FL'.2FF.60.20isomorphic.20.3D.3E.20.60.5BE.3AL.5D.3D.5BK.3AL'.5D.60/near/408999160.


Open in Gitpod

The existing definition is nonsense over semirings; this replaces it with a more plausible one, and ungeneralizes all the results that follow to rings.

Many of the results still hold in semirings, but re-generalizing them is left to future work.

Some context at https://leanprover.zulipchat.com/#narrow/channel/217875-Is-there-code-for-X.3F/topic/.E2.9C.94.20.60E.2FL.2FF.60.20and.20.60K.2FL'.2FF.60.20isomorphic.20.3D.3E.20.60.5BE.3AL.5D.3D.5BK.3AL'.5D.60/near/408999160.
@github-actions github-actions bot added the t-algebra Algebra (groups, rings, fields, etc) label Oct 30, 2024
@github-actions
Copy link
Copy Markdown

github-actions bot commented Oct 30, 2024

PR summary 6b819c58d6

Import changes for modified files

No significant changes to the import graph

Import changes for all files
Files Import difference

Declarations diff

+ Basis.eq_bot_of_rank_eq_zero
+ linearIndependent_iff_ker
- eq_bot_of_rank_eq_zero

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.

@eric-wieser eric-wieser marked this pull request as ready for review October 30, 2024 02:51
theorem linearIndependent_iff_injective_linearCombination :
LinearIndependent R v ↔ Function.Injective (Finsupp.linearCombination R v) := Iff.rfl

alias ⟨LinearIndependent.injective_linearCombination, _⟩ :=
Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

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

Don't we usually put "injective" at the end as an exception to the naming convention?

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

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

Because LinearIndependent.injective_linearCombination is an existing result in mathlib, as well as linearIndependent_iff_injective_linearCombination.

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

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

Yes, all these declarations are just moved.

@smul_eq_zero _ _ _ _ _ b.noZeroSMulDivisors _ _


variable {R M : Type*} [Ring R] [AddCommGroup M] [Module R M]
Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

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

Probably it would be good to have a section here

@acmepjz
Copy link
Copy Markdown
Collaborator

acmepjz commented Oct 30, 2024

Looks good! I think it's OK as long as it does not break major results in mathlib.

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.

I tend to agree with https://github.com/leanprover-community/mathlib4/pull/18426/files#r1821964810. Otherwise it looks like a good change, thanks!

maintainer merge

@github-actions
Copy link
Copy Markdown

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

@github-actions github-actions bot added the maintainer-merge A reviewer has approved the changed; awaiting maintainer approval. label Oct 30, 2024
@riccardobrasca
Copy link
Copy Markdown
Member

Taking into account the last comment LGTM, thanks.

bors d+

@mathlib-bors
Copy link
Copy Markdown
Contributor

mathlib-bors bot commented Oct 30, 2024

✌️ eric-wieser 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 Oct 30, 2024
@eric-wieser
Copy link
Copy Markdown
Member Author

bors merge

@github-actions github-actions bot added the ready-to-merge This PR has been sent to bors. label Oct 30, 2024
mathlib-bors bot pushed a commit that referenced this pull request Oct 30, 2024
The existing definition is nonsense over semirings; this replaces it with a more plausible one, such that:
```lean
example : ¬ LinearIndependent ℕ Nat.succ := by
  intro h
  have := @h (.single 3 1) (.single 1 2)
  simp [Finsupp.single_eq_single_iff] at this
```
which was previously true without the `¬`.
Some of the nonsense semiring results following the definition must then be ungeneralized to rings.

I've been conservative here and only generalized the ones that generalizer trivially, and are used by important downstream
applications such as `Basis` on semirings. Unimportant downstream applications have instead been ungeneralized to `Ring`.
Many more results can likely be generalized in future.

Some context at https://leanprover.zulipchat.com/#narrow/channel/217875-Is-there-code-for-X.3F/topic/.E2.9C.94.20.60E.2FL.2FF.60.20and.20.60K.2FL'.2FF.60.20isomorphic.20.3D.3E.20.60.5BE.3AL.5D.3D.5BK.3AL'.5D.60/near/408999160.
@mathlib-bors
Copy link
Copy Markdown
Contributor

mathlib-bors bot commented Oct 30, 2024

Pull request successfully merged into master.

Build succeeded:

@mathlib-bors mathlib-bors bot changed the title refactor: ungeneralize LinearIndependent [Merged by Bors] - refactor: ungeneralize LinearIndependent Oct 30, 2024
@mathlib-bors mathlib-bors bot closed this Oct 30, 2024
@mathlib-bors mathlib-bors bot deleted the eric-wieser/ungeneralize-linear-independent branch October 30, 2024 12:13
grunweg pushed a commit that referenced this pull request Nov 2, 2024
The existing definition is nonsense over semirings; this replaces it with a more plausible one, such that:
```lean
example : ¬ LinearIndependent ℕ Nat.succ := by
  intro h
  have := @h (.single 3 1) (.single 1 2)
  simp [Finsupp.single_eq_single_iff] at this
```
which was previously true without the `¬`.
Some of the nonsense semiring results following the definition must then be ungeneralized to rings.

I've been conservative here and only generalized the ones that generalizer trivially, and are used by important downstream
applications such as `Basis` on semirings. Unimportant downstream applications have instead been ungeneralized to `Ring`.
Many more results can likely be generalized in future.

Some context at https://leanprover.zulipchat.com/#narrow/channel/217875-Is-there-code-for-X.3F/topic/.E2.9C.94.20.60E.2FL.2FF.60.20and.20.60K.2FL'.2FF.60.20isomorphic.20.3D.3E.20.60.5BE.3AL.5D.3D.5BK.3AL'.5D.60/near/408999160.
mathlib-bors bot pushed a commit that referenced this pull request Jan 6, 2025
After the definition is changed in #18426, many results can now be generalized to semirings.

Co-authored-by: Eric Wieser <wieser.eric@gmail.com>
mathlib-bors bot pushed a commit that referenced this pull request Jan 17, 2025
A module over a ring is said to be flat if tensoring with it preserves injective linear maps. The same definition remains reasonable over a semiring, because (1) injective linear maps still coincides with monomorphisms over a semiring*; (2) projective modules (in particular, free modules) and localizations are still examples of flat modules over a semiring; (3) we recently fixed the definition of linear independence over semirings (#18426), and flatness of S/R means `(1:S) ⊗[R] ·` preserves linear independence. In fact (2) is the main motivation for this PR: it allows us to unify results about free modules (e.g. polynomial algebras) and localizations over a semiring.

There is a caveat in the definition: injective linear maps need to come from a particular universe, as we can't quantify over all universes. Over a ring, using Baer's criterion and character modules, we may restrict to inclusion maps of (f.g.) ideals, and that was the definition adopted in Mathlib. However, the proof doesn't work over a semiring due to three difficulties: (1) Baer's criterion for injective modules doesn't work over a semiring; (2) Q/Z isn't an injective object in the category of AddCommMonoids, in fact this category [doesn't have enough injectives](https://mathoverflow.net/questions/277284/which-semirings-have-enough-injectives-in-their-category-of-modules); (3) homs into Q/Z does not distinguish points in an AddCommMonoid.

However, we can still show that it suffices to consider injective linear maps between modules in the same universe as the semiring, using the fact that every module is the direct limit of its f.g. submodules, and that taking tensor products commutes with taking direct limits: of course, f.g. modules fit in the same universe as the semiring. We therefore change the definition of flatness to state preservation of injectivity of inclusion of f.g. submodules into f.g. modules in the same universe as the semiring.

As we reorder the lemmas in Flat/Basic.lean, We also change all the iff lemmas to use implicit arguments; several other files need to be fixed for this reason, and as we fix them, we also generalize them to CommSemirings and in some cases golf the proofs.


(*) There are more epimorphisms than surjective homs, e.g. the inclusion of N in Z.
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). maintainer-merge A reviewer has approved the changed; awaiting maintainer approval. ready-to-merge This PR has been sent to bors. t-algebra Algebra (groups, rings, fields, etc)

Projects

None yet

Development

Successfully merging this pull request may close these issues.

5 participants