Want to take part in these discussions? Sign in if you have an account, or apply for one below
Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.
I thought it better to use $pred(n)$ rather than $n -1$ in the addition, since it’s supposed to apply to $\infty$.
Is this the page corecursion? Well, $\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.
Yes, that page.
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.
Yeah; I may have clarified this a bit in the page.
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.
?
You can look at the stream terminal coalgebra (functions analytic at 0) for the functor $F: X \to \mathbb{R} \times X$.
$F(f) = \langle f(0), f' \rangle.$See, e.g., Calculus in coinductive form.
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?
So what’s an example of a comparable natural-language recursive definition? Don’t those always work via initial algebras?
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! :-)
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.
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.
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?
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 $F$ of functions to the set of functions whose derivative exists and is in $F$. 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.
Ah, thank you Mike! I vaguely had in mind something similar, but didn’t quite have the wherewithal to say it.
@David 13: yes, that’s exactly right.
Yes, $C^n$ (for finite $n$) is defined by induction on $n$, while $C^\infty$ is defined by coinduction all at once.
We similarly have inductive definitions of $n$-category for finite $n$ and also coinductive definitions for $\infty$-category all at once (although in this case it's also possible to define an $n$-category as an $\infty$-category with an extra property, so we usually don't mix these).
“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.
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.
“Conatural numbers” is the terminal object in the category of coalgebras of the endofunctor $F: Set \to Set$ defined by $F(X) = X + 1$ (thus, a coalgebra is a set $X$ equipped with a morphism $X \to X + 1$). That defines it uniquely up to isomorphism.
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 : X \to X + 1$ sends a unique element of X to $\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.
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 $F$-algebra $(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.
Well, the terminal object in the category of all $X\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.
Whoops. Clickable link:
1 to 27 of 27