subsequences and asymptotical properties

[malarbol]

This pull request introduces the concept of subsequence of a sequence and asymptotical behavior of sequences. In addition, we introduce a few illustrative results using these concepts on sequences in partially ordered sets and monotonic sequences of natural numbers.

More precisely, we introduce the following concepts:

• elementary-number-theory.strictly-increasing-sequences-natural-numbers:
  • sequences f : ℕ → ℕ that preserve strict inequality of natural numbers
  • basic properties
  • strictly increasing sequences of natural numbers take arbitrarily large values
• elementary-number-theory.strictly-decreasing-sequences-natural-numbers:
  • sequences f : ℕ → ℕ that reverse strict inequality of natural numbers
  • they do not exist
• foundation.asymptotical-dependent-sequences:
  • dependent sequences A : ℕ → UU l such that A n is pointed for sufficiently large natural numbers n
  • basic properties
  • asymptotical (binary) functoriality
• foundation.asymptotical-value-sequences
  • sequences that asymptotically take the same value
  • basic properties
• foundation.asymptotically-constant-sequences:
  • sequences u such that u p ＝ u q for sufficiently large p and q
  • a sequence is asymptotically constant if and only if it is asymptotically equal to a constant sequence
  • a sequence is asymptotically constant if and only if all its subsequences are asymptotically constant
  • a sequence asymptotically equal to an asymptotically constant sequence is asymptotically constant
  • characterization as asymptotically stationary sequences
  • a sequence is asymptotically constant if and only if it is asymptotically equal to all its subsequences
• foundation.asymptotically-equal-sequences:
  • sequences u and v such that u n ＝ v n for any sufficiently large natural number n
  • reflexivity, symmetry, transitivity
• foundation.constant-sequences:
  • sequences for which all terms are equal
  • basic properties
• foundation.subsequences:
  • sequences u ∘ f for some sequence u and strictly increasing map f : ℕ → ℕ
  • properties
  • any sequence is a subsequence of itself
  • a subsequence of a subsequence is a subsequence if the original sequence
  • subsequences are functorial
  • a dependent sequence is asymptotical if and only if all its subsequences are asymptotical

These concepts are used in the following modules to serve as illustrative examples

• elementary-number-theory.decreasing-sequences-natural-numbers:
  • sequences of natural numbers that reverse inequality
  • a few conditions under which a decreasing sequence of natural numbers is asymptotically constant
• elementary-number-theory.increasing-sequences-natural-numbers:
  • sequences of natural numbers that preserve inequality
• order-theory.constant-sequences-posets:
  • characterization as increasing and decreasing sequences
• order-theory.decreasing-sequences-posets:
  • sequences in partially ordered sets that reverse the ordering
  • properties
  • sub-sequential properties
  • a few conditions under which a decreasing sequence is asymptotically constant
• order-theory.increasing-sequences-posets:
  • sequences in partially ordered sets that preserve the ordering
  • properties
  • sub-sequential properties
  • a few conditions under which an increasing sequence is asymptotically constant
• order-theory.monotonic-sequences-posets:
  • a decreasing/increasing sequence is asymptotically constant if it has an increasing/decreasing subsequence
• order-theory.sequences-posets
  • sequences in the underlying type of a partially ordered set
  • comparison of sequences in a partially ordered set
  • asymptotical comparison of sequences in a partially ordered set
  • a sequence asymptotically between to asymptotical sequences is asymptotically equal to them

Finally, we also introduce a few helpful properties on existing concepts, e.g. "the maximum of two natural numbers is greater than each of them", "two equal elements in a poset are comparable", etc.

[malarbol]

Hello again. I've been playing around with metric structures and things like that. On the way I ended up needing/wanting these few new properties on sequences. They result interesting to prove things like ("asymptotical equality of sequences preserves limits", or "a sequence has a limit if and only of all its subsequence have this limit"). I think maybe these concepts could also prove themselves interesting in other contexts (e.g. polynomials on ring as asymptotically vanishing sequences, etc.).

[fredrik-bakke]

Hey @malarbol, I'm just having a quick look at your changes for now, but why not have separate files for increasing and decreasing sequences? I would similarly expect us to have separate files for order-preserving and order-reversing maps

[malarbol]

Hey @malarbol, I'm just having a quick look at your changes for now, but why not have separate files for increasing and decreasing sequences? I would similarly expect us to have separate files for order-preserving and order-reversing maps

Hey @fredrik-bakke, thanks for the feedback. I'm sorry, this PR got a bit bigger than anticipated (again 😅) and I still have a lot of cleanup to do. I'll do my best to address your concern; we may still need a module importing both of them, for properties like "a sequence is constant iff it is both increasing and decreasing".

[fredrik-bakke]

That's okay. The property you mentioned should go in a file abour constant sequences :)

[malarbol]

Hey again @fredrik-bakke. I refactored a few concepts and cleaned things up a bit. I also updated the title/description of the PR to reflect better its content. If you prefer, maybe we could split this PR into two, with "new concepts" on one hand, and the "illustrative modules" on the other. Some of these modules could also be more interesting, like maybe proving that "decreasing sequences of natural numbers are asymptotically constant" is equivalent to the LPO, or study behavior of bounded increasing sequences of natural numbers but I'm not sure how to handle these right now.

I already have a few follow-up ideas that motivated this PR:

• metric structures (with sequential limits, etc.)
• series, polynomials, convolution products, etc. (using asymptotically vanishing sequence in monoids, rings, etc.)

[fredrik-bakke]

Hey Malarbol! I'm back. Sorry for the terribly long wait; I'll try to review your PR in one of the coming days :)