Not signed in (Sign In)

Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

  • Sign in using OpenID

Site Tag Cloud

2-category 2-category-theory abelian-categories adjoint algebra algebraic algebraic-geometry algebraic-topology analysis analytic-geometry arithmetic arithmetic-geometry book bundles calculus categorical categories category category-theory chern-weil-theory cohesion cohesive-homotopy-type-theory cohomology colimits combinatorics complex complex-geometry computable-mathematics computer-science constructive cosmology definitions deformation-theory descent diagrams differential differential-cohomology differential-equations differential-geometry digraphs duality elliptic-cohomology enriched fibration foundation foundations functional-analysis functor gauge-theory gebra geometric-quantization geometry graph graphs gravity grothendieck group group-theory harmonic-analysis higher higher-algebra higher-category-theory higher-differential-geometry higher-geometry higher-lie-theory higher-topos-theory homological homological-algebra homotopy homotopy-theory homotopy-type-theory index-theory integration integration-theory k-theory lie-theory limits linear linear-algebra locale localization logic mathematics measure-theory modal modal-logic model model-category-theory monad monads monoidal monoidal-category-theory morphism motives motivic-cohomology nforum nlab noncommutative noncommutative-geometry number-theory of operads operator operator-algebra order-theory pages pasting philosophy physics pro-object probability probability-theory quantization quantum quantum-field quantum-field-theory quantum-mechanics quantum-physics quantum-theory question representation representation-theory riemannian-geometry scheme schemes set set-theory sheaf simplicial space spin-geometry stable-homotopy-theory stack string string-theory superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topology topos topos-theory tqft type type-theory universal variational-calculus

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).

nLab > Latest Changes: natural numbers object

Bottom of Page

1 to 27 of 27

  1.  
    • CommentRowNumber1.
    • CommentAuthorUrs
    • CommentTimeJan 12th 2010

    started an Examples-section at natural numbers object

    btw, the natural numbers objects of a topos is unique, up to isomorphism, right? if so, we should say that

    • CommentRowNumber2.
    • CommentAuthorMike Shulman
    • CommentTimeJan 12th 2010

    Yes, of course, since it has a universal property.

    • CommentRowNumber3.
    • CommentAuthorUrs
    • CommentTimeApr 27th 2012

    I have expanded a little at Transfer of NNOs along inverse images.

    • CommentRowNumber4.
    • CommentAuthorTodd_Trimble
    • CommentTimeAug 14th 2013

    I added an explicit definition of parametrized NNO to natural numbers object.

    I have a question: there is mention in that article of a categories with finite products and a parametrized NNO, and the initial such structure FF, and it is written that the canonical maps

    hom F(N k,N)→hom Set(ℕ k,ℕ)\hom_F(N^k, N) \to \hom_{Set}(\mathbb{N}^k, \mathbb{N})

    surject onto the primitive recursive maps. Why couldn’t “surject” be replaced by “biject”?

    • CommentRowNumber5.
    • CommentAuthorZhen Lin
    • CommentTimeAug 14th 2013

    Perhaps it’s a question of extensionality? The morphisms N k→NN^k \to N are surely constructed by syntactic means, and it’s conceivable that two such morphisms describe the same primitive recursive function in the standard model of arithmetic while not being provably equal (in whatever system of arithmetic corresponds to FF).

    • CommentRowNumber6.
    • CommentAuthorTodd_Trimble
    • CommentTimeAug 14th 2013

    Maybe, but I’d really like to see a specific example of that.

    • CommentRowNumber7.
    • CommentAuthorZhen Lin
    • CommentTimeAug 14th 2013

    Hmmm. Well, consider the primitive recursive “function” GG defined by G(n)=1G(n) = 1 if nn codes the proof of a contradiction in Peano arithmetic, and G(n)=0G(n) = 0 otherwise. (This is primitive recursive because no unbounded searches are required to verify the validity of a proof.) In the standard model of arithmetic, GG is the constant 00 function, but we could equally consider the elementary topos corresponding to a model of ZFC+¬Con(PA)ZFC + \neg Con(PA), in which GG is not the constant 00 function. Thus GG and the constant 00 function must be distinct in the category FF.

    • CommentRowNumber8.
    • CommentAuthorTodd_Trimble
    • CommentTimeAug 14th 2013

    Ah yes, that certainly seems to work. Nice!

    • CommentRowNumber9.
    • CommentAuthorTodd_Trimble
    • CommentTimeAug 14th 2013
    • (edited Aug 14th 2013)

    But wait: ZFC proves that PA is consistent (since one can establish ordinal induction up to ε 0\epsilon_0 in ZFC).

    Edit: Well, I think the conclusion must still hold anyway: in the initial structure, it cannot be established that G=0G = 0, since that would amount to provability of that statement within primitive recursive arithmetic. So GG and 00 are distinct there.

    • CommentRowNumber10.
    • CommentAuthorZhen Lin
    • CommentTimeAug 14th 2013

    Oops, quite right. I suppose ZFC+¬Con(ZFC)ZFC + \neg Con(ZFC), with the “function” that verifies proofs of inconsistency of ZFC, is what I meant.

    • CommentRowNumber11.
    • CommentAuthorDavidRoberts
    • CommentTimeDec 28th 2015

    Why is it that a parameterized NNO is the same as being preserved by all the functors to the coKelisli categories for the comonad A×−A\times -? I’m trying to see how this works as I’d like to think of an NNO as being an initial algebra for a polynomial endofunctor (arising from 1←1→1+1→1) and these two pictures aren’t meshing.

    • CommentRowNumber12.
    • CommentAuthorziggurism
    • CommentTimeMay 21st 2020

    please doublecheck my correction. but it seems like the second pair is backwards. if we identify (\pi_1 \circ a, \pi_2 \circ b) and (\pi_2 \circ a, \pi_1 \circ b), that means we’re declaring i-l = j-k for i+j = k+l, whereas we actually want i-l = k-j. So we want to identify (\pi_1 \circ b, \pi_2 \circ a)

    diff, v51, current

    • CommentRowNumber13.
    • CommentAuthorTodd_Trimble
    • CommentTimeMay 21st 2020

    Yes, you seem to be correct. Good catch.

    • CommentRowNumber14.
    • CommentAuthorUrs
    • CommentTimeJun 27th 2020

    added pointer to:

    diff, v52, current

    • CommentRowNumber15.
    • CommentAuthorMike Shulman
    • CommentTimeAug 28th 2020

    Added proof that the “simpler” notion of parametrized NNO is equivalent to the more obviously correct one.

    diff, v53, current

    • CommentRowNumber16.
    • CommentAuthorGuest
    • CommentTimeMar 25th 2023
    Looking all over for the meaning of the endofunctor X -> 1 + X, but not finding it on maybe monad or endofunctor pages.
    • CommentRowNumber17.
    • CommentAuthorDavidRoberts
    • CommentTimeMar 25th 2023
    • (edited Mar 25th 2023)

    @Guest

    F(x):=x⊔1F(x) := x \sqcup 1, where 1 is terminal (the coproduct is sometimes written as ++, especially in a disjunctive or extensive category). It’s a special case of the List monad, if that helps.

    But perhaps you meant something else by your question?

  18. Considering that pointed object in a monoidal category got created a few days ago, I wonder if it makes sense to talk about natural numbers objects in an arbitrary monoidal category as the initial object 𝒩\mathcal{N} with an endomorphism 𝒩→𝒩\mathcal{N} \to \mathcal{N} and a morphism out of the tensor unit I→𝒩I \to \mathcal{N}?

    I think that in Vect K\mathrm{Vect}_K for a field KK the natural numbers object as defined in the previous sentence would be the infinite-dimensional vector space with denumerable basis - or equivalently the underlying vector space of the sequence space K ℕK^\mathbb{N}.

    • CommentRowNumber19.
    • CommentAuthorBryceClarke
    • CommentTimeJun 6th 2023

    Added references to two papers by Robert Paré on natural numbers, one of which discusses natural number objects in monoidal categories.

    diff, v66, current

    • CommentRowNumber20.
    • CommentAuthorTodd_Trimble
    • CommentTimeJun 6th 2023
    • (edited Jun 6th 2023)

    In the ordinary version where the monoidal product is cartesian, there are two standard tacks: (1) use this definition if the category is cartesian closed, or (2) use instead parametrized natural number objects (because without extra infrastructure like cartesian closure, it will be hard to get a satisfactory theory up and running with just the vanilla definition).

    Your idea could be interesting. I’d want to review a little recursion theory before opining on whether I think it would fly.

    (Small nit: K ℕK^\mathbb{N} will have basis of cardinality equal to the cardinality of the underlying set. MO post)

  21. In the ordinary version where the monoidal product is cartesian, there are two standard tacks: (1) use this definition if the category is cartesian closed, or (2) use instead parametrized natural number objects (because without extra infrastructure like cartesian closure, it will be hard to get a satisfactory theory up and running with just the vanilla definition).

    So I’d imagine in my proposed definition (1) would have to be in a closed monoidal category and (2) would use the tensor product in the definition of parametrised NNO.

    • CommentRowNumber22.
    • CommentAuthorTodd_Trimble
    • CommentTimeJun 6th 2023

    That’s what I was thinking, Madeleine. Meanwhile, Bryce added a reference which is worth looking over.

  23. I said earlier that

    I think that in Vect K\mathrm{Vect}_K for a field KK the natural numbers object as defined in the previous sentence would be the infinite-dimensional vector space with denumerable basis - or equivalently the underlying vector space of the sequence space K ℕK^\mathbb{N}.

    and Todd Trimble said

    (Small nit: K ℕK^\mathbb{N} will have basis of cardinality equal to the cardinality of the underlying set. MO post)

    I just realised where Todd is coming from. It is rather the polynomial ring K[X]K[X] whose underlying vector space is the free vector space K[ℕ]K[\mathbb{N}]. K ℕK^\mathbb{N} is equivalent to the power series ring K[[X]]K[[X]], and the underlying vector space of K[[X]]K[[X]] is not freely generated by the natural numbers ℕ\mathbb{N}.

    • CommentRowNumber24.
    • CommentAuthorMadeleine Birchfield
    • CommentTimeJul 25th 2023
    • (edited Jul 25th 2023)

    Other similarities between the natural numbers ℕ\mathbb{N} in SetSet and the polynomial ring K[X]K[X] in Vect K\mathrm{Vect}_K: ℕ\mathbb{N} is the free commutative monoid object on one generator in SetSet, while K[X]K[X] is the free commutative monoid object on one generator in Vect K\mathrm{Vect}_K.

    • CommentRowNumber25.
    • CommentAuthorTodd_Trimble
    • CommentTimeJul 25th 2023

    Yes, and the strong symmetric monoidal functor X↦K⋅XX \mapsto K \cdot X that carries a set XX to the free KK-vector space on XX carries the commutative monoid object ℕ\mathbb{N} in SetSet to the commutative monoid objects K⋅ℕ≅K[x]K \cdot \mathbb{N} \cong K[x] in Vect KVect_K.

  26. I wonder if (the underlying vector space of) the power series ring K[[X]]K[[X]] or the sequence algebra K ℕK^\mathbb{N} plays the role in Vect K\mathrm{Vect}_K that the extended natural numbers does in Set\mathrm{Set}, as the terminal coalgebra of the endofunctor V↦K⊕VV \mapsto K \oplus V.

    • CommentRowNumber27.
    • CommentAuthorTodd_Trimble
    • CommentTimeJul 25th 2023

    This happens to be true, and follows from Adamek’s theorem, or its dual, which gives a criterion for constructing terminal coalgebras. In detail, the endofunctor K⊕−K \oplus - coincides with K×−K \times - (biproducts), and K×−K \times - preserves connected limits, in particular inverse limits of ω\omega-chains, which is the crucial hypothesis in Adamek’s theorem. An easy way to verify this preservation property is to view K×−K \times - as a composite

    Vect→ΔVect×Vect→c K×1Vect×Vect→prodVectVect \stackrel{\Delta}{\to} Vect \times Vect \stackrel{c_K \times 1}{\to} Vect \times Vect \stackrel{prod}{\to} Vect

    where the right adjoints Δ,prod\Delta, prod obviously preserve connected limits, and the constant functor c Kc_K also preserves connected limits. (Actually, diagonal functors Δ:C 1→C 1+1\Delta: C^1 \to C^{1 + 1} always preserve limits, regardless of whether it’s a right adjoint, because limits in functor categories are computed pointwise.)

1 to 27 of 27

  1.