-
Notifications
You must be signed in to change notification settings - Fork 297
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
[Merged by Bors] - feat(topology/connected): Connectedness of unions of sets #10005
Conversation
Add a theorem that unions of preconnected sets indexed by integers such that each of them meets the next one is preconnected In a separate file (src/data/set/increasing_union.lean), add a series of possibly lemma on increasing unions It is possible that these lemmas have a neater proof.
src/data/set/increasing_union.lean
Outdated
|
||
Given a sequence of sets s : ℕ → set α, | ||
we construct its increasing Union by | ||
λ n:ℕ, Union (set restrict s { j : ℕ | j ≤ n}) -/ |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Are you sure you don't want
λ n:ℕ, Union (set restrict s { j : ℕ | j ≤ n}) -/ | |
λ n:ℕ, Union (subtype.restrict s (≤ n)) -/ |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This also looks a lot like partial_sups
, cc @YaelDillies
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
And accumulate
.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Yeah it is partial_sups
. I'm sorry you wrote it all, Antoine, because this is duplicate 😕
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I was almost certain something like that would exist, and I am truly glad that it already exists.
I'll try to understand how it works tomorrow and to adjust the other file accordingly.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
@YaelDillies , OK, it was nice and easy to use partial_sups
.
At first, I thought that the assertion that partial_sups s
is monotone was missing, but it seems to be included in the galois connection…
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
partial_sups
is defined as a monotone function. That's what the little m
to the right of the arrow stands for. You can look at the API for preorder_hom
for how to use this.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Unfortunately, I can't read that little symbol on the right of the arrow, it is printed as a box in both vim and VisualStudio, all I know is that it has Unicode code 8344…
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
@AntoineChambert-Loir In that case I think you are in dire need of a font with more unicode support 😉
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
That I could guess, but I think I use the standard VisualStudioCode (on Mac OS)…
I left unfortunate bugs in the commit (bad interaction between my two branches). A new commit will appear soon. |
Finally, I left the two theorems |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Some initial style comments
Co-authored-by: Eric Wieser <wieser.eric@gmail.com>
Co-authored-by: Eric Wieser <wieser.eric@gmail.com>
…thlib into ad-connectedness
@AntoineChambert-Loir , I worked on the first two lemmas to show you some tricks and answer some questions. My advice is to study the diff at 1a1bb97 and see whether you can learn something and clean up this PR. Unfortunately git is a bit confused when displaying the diff (because it can't figure out which of my blank lines match yours) so you may have to create a new version of the file on your computer and compare them by putting them side by side. |
Thanks for the review! It is indeed much nicer to do this for |
Yeah, this is all fairly new. Nothing in mathlib uses it yet, so I'm very happy to see people needing it! |
This PR/issue depends on: |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Thanks 🎉 It took a while, but this looks really great now!
bors merge
* Add multiple results about when unions of sets are (pre)connected. In particular, the union of connected sets indexed by `ℕ` such that each set intersects the next is connected. * Remove some `set.` prefixes in the file * There are two minor fixes in other files, presumably caused by the fact that they now import `order.succ_pred` * Co-authored by Floris van Doorn fpvdoorn@gmail.com Co-authored-by: Antoine Chambert-Loir <antoine.chambert-loir@math.univ-paris-diderot.fr> Co-authored-by: Patrick Massot <patrickmassot@free.fr> Co-authored-by: Floris van Doorn <fpvdoorn@gmail.com>
theorem is_connected.Union_nat_of_chain {s : ℕ → set α} | ||
(H : ∀ n : ℕ, is_connected (s n)) | ||
(K : ∀ n : ℕ, (s n ∩ s n.succ).nonempty) : | ||
/-- The Union of connected sets indexed by a type with an archimedian successor (like `ℕ` or `ℤ`) |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
/-- The Union of connected sets indexed by a type with an archimedian successor (like `ℕ` or `ℤ`) | |
/-- The Union of connected sets indexed by a type with an archimedean successor (like `ℕ` or `ℤ`) |
|
||
/-- The Union of connected sets indexed by a type with an archimedian successor (like `ℕ` or `ℤ`) | ||
such that any two neighboring sets meet is preconnected. -/ | ||
theorem is_preconnected.Union_of_chain {s : β → set α} |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I would get rid of dot notation here and below because you can't actually use it.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I agree you cannot actually use it (though I kinda hope we can change the way projection notation works in Lean 4 so that H.Union_of_chain K
works in this case).
However, I'm not sure if that means we should change the .
to a _
: it might be more predictable to guess the name if we consistently keep using .
even when projection notation doesn't apply.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
At least, there's precedent for not using it when the condition is in a forall. For example, star_convex_Union
.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I believe there is a bunch of precedent for both options. We have not decided on a rule here. (measurable_set.pi
to pick one)
Pull request successfully merged into master. Build succeeded: |
ℕ
such that each set intersects the next is connected.set.
prefixes in the fileorder.succ_pred
succ
/pred
inductions on relations #11518