Login
You're viewing the discuss.systems public feed.
  • Aug 21, 2024, 6:56 PM

    We work constructively in HoTT/UF.

    Let ℕ∞ be the type of conatural numbers, which extends ℕ with a point at infinity.

    The type ℕ∞ has decidable equality iff WLPO holds.

    However, for every n : ℕ and x : ℕ∞, it is decidable whether n = x. We say that the finite elements of ℕ∞ are "isolated".

    An intuition for a general element of ℕ∞ is as the behaviour of a stopwatch that either ticks finitely many times and then stops, or else ticks forever if nobody bothers to stop it.

    With this intuition, define x =ₘ y, for x y : ℕ∞, to mean that we can't distinguish x and y after only m ticks. I am sure you can make this formal if you want to.

    I will abuse language and regard any n : ℕ as an element of ℕ∞ by ticking n times and then stopping.

    Let f : ℕ∞ → ℕ be any function.

    There are (at least) six senses in which f can be considered to be continuous.

    (1) ∃ m ꞉ ℕ , (Π n : ℕ , f (max m n) = f ∞).

    (1') Σ m ꞉ ℕ , (Π n : ℕ , f (max m n) = f ∞).

    (2) Π x : ℕ∞ , ∃ m ꞉ ℕ , (Π y : ℕ∞ , x =ₘ y → f x = f y).

    (2') Π x : ℕ∞ , Σ m ꞉ ℕ , (Π y : ℕ∞ , x =ₘ y → f x = f y).

    (3) ∃ m ꞉ ℕ , (Π x y : ℕ∞ , x =ₘ y → f x = f y).

    (3') Σ m ꞉ ℕ , (Π x y : ℕ∞ , x =ₘ y → f x = f y).

    Perhaps surprisingly, they are all logically equivalent, constructively, without the need for Brouwerian intuitionistic axioms.

    (1) continuity property at ∞.

    (1') continuity data at ∞.

    (2) continuity property at all points

    (2') continuity data at all points.

    (3) uniform continuity property at all points.

    (3') uniform continuity data all points.

    If you want to see formal definitions, statements and proofs, here they are:
    cs.bham.ac.uk/~mhe/TypeTopolog

    1/

    💬 3🔄 2⭐ 0

Replies

  • Aug 22, 2024, 5:43 PM

    The proofs of the above claims use the following ingredients.

    (i) If A is a type family indexed by natural numbers such that the type A n is decidable for every n : ℕ, then ∃ n ꞉ ℕ , A n implies Σ n' ꞉ ℕ , A n'.

    This means that from a "secret" n : ℕ with A n, we can find an explicit n' : ℕ with A n' (it isn't necessarily the same as n, but we have n' ≤ n).

    You see, propositional truncation doesn't erase information. It just keeps it secret, and sometimes secrets leak.

    (ii) If B is a type family indexed by extended natural numbers such that the type B x is decidable for every x : ℕ∞, then the statement "B x for all x : ℕ∞" is decidable.

    If B were indexed by non-extended natural numbers, this wouldn't be possible, because this would amount to WLPO.

    (iii) If g : ℕ∞ → 𝟚 is any function, then the statement "g n = 0 for all n : ℕ" is decidable.

    So notice that g is defined on ℕ∞, but for the decidability statement we quantify over its subtype ℕ.

    This is amazing, in my view, because in general the decidability of quantifications over ℕ with decidable types amount to WLPO, which is not provable (or disprovable) in our flavour of constructive mathematics.

    (iv) If we have two functions g h : ℕ∞ → 𝟚 that agree at all n : ℕ and at ∞, then they agree at all x : ℕ∞.

    This is amazing because we can't tell whether the given x : ℕ∞ is in ℕ or is ∞, as this amounts to LPO, a statement stronger than WLPO. So the proof can't be by cases on x.

    We say that the subtype of ℕ∞ consisting of the elements of ℕ and also ∞ is "dense".

    2/

    💬 1🔄 1⭐ 0
  • Aug 22, 2024, 7:05 PM

    Is ℕ∞ an oddity among the zoo of types, by having these outrageously nice constructive properties?

    Perhaps.

    But there are as many such outrageously nice types as there are ordinals for which you can define "codes".

    (I) Given any such ordinal α, we can find a well-ordered type X(α) whose order type is ≥ α and X(α) has such outrageously nice constructive properties.

    This is in TypeTopology, but, unfortunately, I didn't get to write a paper about this yet, although I've given many talks with different angles about this situation.

    (II) And what are the ordinals α for which we can define codes in type theory in practice?

    They e.g. go well above the Feferman–Schütte ordinal

    en.wikipedia.org/wiki/Feferman

    as shown by Anton Setzer.

    So we have an outrageously large zoo of outrageously nice types, by combining (I) and (II).

    3/

    💬 1🔄 0⭐ 0
  • Aug 22, 2024, 7:37 PM

    Why invoke ordinals to explain that?

    Actually we don't need to.

    What I did, in practice, was to show that such outrageously nice types are closed under a number of type-theoretic constructions, so that we can get more and more of them.

    Then I saw, after the fact, that these constructions preserve not only outrageous-nicety but also well-orderedness (constructively).

    So we can use ordinals to measure how far we can get with outrageous nicety.

    4/

    💬 2🔄 0⭐ 0
  • Aug 23, 2024, 6:06 PM

    Let me add that the use of HoTT/UF is not essential for the above claims.

    We could equally work in the setoid model, to get the same results, where everything invoked above is also available, including propositional truncations and function extensionality.

    5/

    💬 0🔄 0⭐ 0
  • Aug 22, 2024, 4:59 AM

    @MartinEscardo Oh no! I'm still trying to catch up with the wonderful facts about ℕ∞ which you have already posted!

    More seriously, having a lot of mathematics around to absorb is a good problem to have and I have written up two of the more basic facts from this post as issues at github.com/metamath/set.mm/iss and github.com/metamath/set.mm/iss

    iset.mm issues don't always get resolved quickly, but I posed github.com/metamath/set.mm/iss in 2019 and just last week finished the proof - at us.metamath.org/ileuni/exmidon

    💬 0🔄 0⭐ 0
  • 💬 0🔄 0⭐ 0
  • 💬 0🔄 0⭐ 0