Not signed in (Sign In)

Start a new discussion

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-categories 2-category 2-category-theory abelian-categories adjoint algebra algebraic algebraic-geometry algebraic-topology analysis analytic-geometry arithmetic arithmetic-geometry bundles calculus categories category category-theory chern-weil-theory cohesion cohesive-homotopy-theory cohesive-homotopy-type-theory cohomology colimits combinatorics comma complex-geometry computable-mathematics computer-science constructive cosmology definitions deformation-theory descent diagrams differential differential-cohomology differential-equations differential-geometry differential-topology digraphs duality education elliptic-cohomology enriched fibration finite foundations functional-analysis functor galois-theory gauge-theory gebra geometric-quantization geometry graph graphs gravity grothendieck 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 infinity integration integration-theory k-theory lie-theory limit limits linear linear-algebra locale localization logic manifolds mathematics measure-theory modal-logic model model-category-theory monads monoidal monoidal-category-theory morphism motives motivic-cohomology newpage noncommutative noncommutative-geometry number-theory of operads operator operator-algebra order-theory 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 string string-theory subobject superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topology topos topos-theory 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).
    • CommentRowNumber1.
    • CommentAuthorDavid_Corfield
    • CommentTimeOct 20th 2011

    I thought it better to use pred(n)pred(n) rather than n1n -1 in the addition, since it’s supposed to apply to \infty.

    • CommentRowNumber2.
    • CommentAuthorTobyBartels
    • CommentTimeOct 21st 2011

    Is this the page corecursion? Well, 1=pred\infty - 1 = \pred \infty too (both are \infty in the extended natural numbers), but (regardless of \infty) one probably shouldn’t use subtraction in addition.

    • CommentRowNumber3.
    • CommentAuthorDavid_Corfield
    • CommentTimeOct 21st 2011

    Yes, that page.

    • CommentRowNumber4.
    • CommentAuthorDavid_Corfield
    • CommentTimeOct 21st 2011

    It’s a little confusing of Adamek to call that binary function ’add’, when it’s really the morphism of a coalgebra which gives rise to the addition function.

    • CommentRowNumber5.
    • CommentAuthorTobyBartels
    • CommentTimeOct 21st 2011

    Yeah; I may have clarified this a bit in the page.

    • CommentRowNumber6.
    • CommentAuthorUrs
    • CommentTimeSep 28th 2012
    • (edited Sep 28th 2012)

    I have a dumb and naive question about corecursion.

    May I say that the following is a corecursive definition of “smooth function”:

    A function \mathbb{R} \to \mathbb{R} is smooth if 1. it is continuous and 2. its derivative exists and is itself a smooth function.

    ?

    • CommentRowNumber7.
    • CommentAuthorDavid_Corfield
    • CommentTimeSep 28th 2012

    You can look at the stream terminal coalgebra (functions analytic at 0) for the functor F:X×XF: X \to \mathbb{R} \times X.

    F(f)=f(0),f. F(f) = \langle f(0), f' \rangle.

    See, e.g., Calculus in coinductive form.

    • CommentRowNumber8.
    • CommentAuthorUrs
    • CommentTimeSep 28th 2012

    I just want a natural-language statement. Not a stream. If I write

    A function \mathbb{R} \to \mathbb{R} is smooth if 1. it is continuous and 2. its derivative exists and is itself a smooth function.

    do you all nod and say “sure, that’s a valid corecursive definition” or do you object?

    • CommentRowNumber9.
    • CommentAuthorDavid_Corfield
    • CommentTimeSep 28th 2012

    So what’s an example of a comparable natural-language recursive definition? Don’t those always work via initial algebras?

    • CommentRowNumber10.
    • CommentAuthorUrs
    • CommentTimeSep 28th 2012
    • (edited Sep 28th 2012)

    When you say “A natural number is either 0 or the succesor of a natural number.” then you haven’t said the word “initial algebra”.

    All I am after is a sanity check on that blue boxed statement! :-)

    • CommentRowNumber11.
    • CommentAuthorTodd_Trimble
    • CommentTimeSep 28th 2012

    I think the blue box statement is correct, but that doesn’t mean I understand quite how to formalize it as a terminal coalgebra construction. “Derivative exists” currently puzzles me.

    • CommentRowNumber12.
    • CommentAuthorUrs
    • CommentTimeSep 28th 2012
    • (edited Sep 28th 2012)

    Thanks, Todd.

    This just occurred to me when thinking about how to write, as you will have guessed, an expositional account of Cartesian spaces and smooth functions.

    • CommentRowNumber13.
    • CommentAuthorDavid_Corfield
    • CommentTimeSep 28th 2012

    I’d like to know how this works. Can I say

    An extended natural number is either 0 or has a predecessor which is an extended natural number?

    • CommentRowNumber14.
    • CommentAuthorMike Shulman
    • CommentTimeSep 28th 2012

    I agree with this definition (and I like it a lot!). I also think you can omit clause 1, since differentiability implies continuity.

    However, I would say this is not a corecursive definition but rather a coinductive definition. And in reply to Todd, I would regard it as a corecursive definition of a predicate rather than a type, so that the corresponding terminal coalgebra lives on a poset. In this case, the poset is the power set of the set of functions \mathbb{R}\to\mathbb{R}, and the endofunctor takes a set FF of functions to the set of functions whose derivative exists and is in FF. The terminal coalgebra of this endofunctor (i.e. greatest fixed point) is the set of smooth functions.

    If you want to use this as a definition of “smooth function” without having a prior notion of “function” in hand, then I guess things would be trickier.

    • CommentRowNumber15.
    • CommentAuthorTodd_Trimble
    • CommentTimeSep 28th 2012

    Ah, thank you Mike! I vaguely had in mind something similar, but didn’t quite have the wherewithal to say it.

    • CommentRowNumber16.
    • CommentAuthorTodd_Trimble
    • CommentTimeSep 28th 2012

    @David 13: yes, that’s exactly right.

    • CommentRowNumber17.
    • CommentAuthorTobyBartels
    • CommentTimeOct 1st 2012

    Yes, C nC^n (for finite nn) is defined by induction on nn, while C C^\infty is defined by coinduction all at once.

    We similarly have inductive definitions of nn-category for finite nn and also coinductive definitions for \infty-category all at once (although in this case it's also possible to define an nn-category as an \infty-category with an extra property, so we usually don't mix these).

    • CommentRowNumber18.
    • CommentAuthorColin Tan
    • CommentTimeNov 27th 2018
    • (edited Nov 27th 2018)
    Regarding @David 13 and @Todd 16, it seems that what David wrote, "An extended natural number is either 0 or has a predecessor which is an extended natural number" doesn't quite serve to define the extended natural numbers. For that statement doesn't preclude the extended natural numbers to be {0, 1, 2, ...}, right? Indeed if n is an element of {0, 1, 2,...}, then it is also true that n is either 0 or n - 1 is an element of {0, 1, 2, ...}.

    Although it does seem to be true that the natural numbers is the smallest pointed set with basepoint called 0 equipped with an endomap called successor that satisfises Urs statement, "A natural number is either 0 or the sucessor of a natural number", but it doesn't seem to be true that the extended natural numbers it the largest set equiped with a partial endomap called predecessor whose domain of definition is the complement of {0} that satisfies David's statement.
    • CommentRowNumber19.
    • CommentAuthorMike Shulman
    • CommentTimeNov 28th 2018

    “The largest set” doesn’t really make much sense. In fact “the smallest set” doesn’t really make much sense either, structurally. What we mean is that the natural numbers are the initial such set, and the conatural numbers are the terminal such set.

    • CommentRowNumber20.
    • CommentAuthorColin Tan
    • CommentTimeNov 29th 2018

    I think it is not sufficient to say that the conatural numbers are the terminal set such that a conatural number is either 0 or has a predecessor that is a conatural number. This would mean only the existence of a unique morphism from those partial functions with the same set as its source and target whose domain of definition is the complement of a singleton.

    More correctly, it should be

    The predecessor of a conatural number is either undefined or a conatural number.

    Then this allows the existence of a morphism from those partial functions p from a set X to itself which is undefined on more than one element of X.

    In this sense, corecursion still seems to me not quite to define exactly what an object is, but is more a definition in the old sense, the Aristotle sense of pointing the essence of something. I feel that the above phrasing in the blue box is more correct than the linguistically equivalence manner of speech: A conatural number either does not have a predecessor or has a predecessor that is a conatural number. In the sense, we are not really naming conatural numbers per se, but rather describing the effect of taking the predecessor of a conatural number.

    • CommentRowNumber21.
    • CommentAuthorTodd_Trimble
    • CommentTimeNov 29th 2018

    “Conatural numbers” is the terminal object in the category of coalgebras of the endofunctor F:SetSetF: Set \to Set defined by F(X)=X+1F(X) = X + 1 (thus, a coalgebra is a set XX equipped with a morphism XX+1X \to X + 1). That defines it uniquely up to isomorphism.

    • CommentRowNumber22.
    • CommentAuthorColin Tan
    • CommentTimeNov 29th 2018
    • (edited Nov 29th 2018)

    Yes. I was trying to point that that it is insufficient to say that the conatural numbers is the terminal set equipped with a partial endo-function such that each element of this set is either some distinguished element or it sent via this partial endo-function to some element of this set, for that is not enough to identify all coalgebras, only those coalgebras where the morphism f:XX+1f : X \to X + 1 sends a unique element of X to *1\ast \in 1.

    As a general coalgebra is equivalent to a set equipped with a partial endo-function, thus the image of the partial endo-function on each element of this set is either undefined or is some element of this set. The partial endo-function could be undefined on more than on element. Which informally becomes: “the predecessor of a conatural number is either undefined or a conatural number”. If we were to say informally “a conatural number is either 0 or has a predecessor that is a conatural number”, we are implicitly specifically that the predecessor partial function is undefined only at 0.

    • CommentRowNumber23.
    • CommentAuthorTodd_Trimble
    • CommentTimeNov 29th 2018
    • (edited Nov 29th 2018)

    There may be multiple ways of characterizing the sought-after conatural numbers. The (second-order) Peano definition for the natural numbers can be succinctly stated as an FF-algebra (X,θ:X+1X)(X, \theta: X + 1 \to X) such that θ\theta is monic and the algebra has only itself as subalgebra. I haven’t checked this works, but it might be that a straighforward dualization (a coalgebra whose structure map is epic and has only itself as quotient coalgebra) also provides a correct characterization of conatural numbers. This might be a precise way to capture the informal intuitions described earlier.

    • CommentRowNumber24.
    • CommentAuthorMike Shulman
    • CommentTimeNov 29th 2018

    Well, the terminal object in the category of all XX+1X\mapsto X+1 coalgebras is also the terminal object in any full subcategory thereof that contains it. The latter universal property is weaker, but still defines the same object.

Add your comments
  • Please log in or leave your comment as a "guest post". If commenting as a "guest", please include your name in the message as a courtesy. Note: only certain categories allow guest posts.
  • To produce a hyperlink to an nLab entry, simply put double square brackets around its name, e.g. [[category]]. To use (La)TeX mathematics in your post, make sure Markdown+Itex is selected below and put your mathematics between dollar signs as usual. Only a subset of the usual TeX math commands are accepted: see here for a list.

  • (Help)