Chapter 1: "recursor" or "eliminator"?

[awodey]

both terms occur often -- the former more often. shall we even try to be consistent?

[cangiuli]

As far as I know, the chapter is consistent about using "recursor" for non-dependent elimination and "eliminator"/"induction" for dependent elimination.

[mikeshulman]

At some point, it was proposed that "eliminator" sounds more like technical type-theoretic terminology and "induction" and "recursion" are more familiar words.

On Wed, Apr 17, 2013 at 9:16 PM, Carlo Angiuli notifications@github.comwrote:

As far as I know, the chapter is consistent about using "recursor" for non-dependent elimination and "eliminator"/"induction" for dependent elimination.

— Reply to this email directly or view it on GitHubhttps://github.com/HoTT/book/issues/145#issuecomment-16546350 .

[dlicata335]

yeah, I thought avoiding "eliminator" was in a style guide at some point. I've tried to use "induction" instead of "elimination" in the homotopy chapter.

[mikeshulman]

One problem is that we have recursion/recursor, elimination/eliminator, but induction/??

On Wed, Apr 17, 2013 at 9:39 PM, Dan Licata notifications@github.comwrote:

yeah, I thought avoiding "eliminator" was in a style guide at some point. I've tried to use "induction" instead of "elimination" in the homotopy chapter.

— Reply to this email directly or view it on GitHubhttps://github.com/HoTT/book/issues/145#issuecomment-16547540 .

[awodey]

induction term?

On Apr 17, 2013, at 9:44 PM, Mike Shulman notifications@github.com wrote:

One problem is that we have recursion/recursor, elimination/eliminator, but induction/??

On Wed, Apr 17, 2013 at 9:39 PM, Dan Licata notifications@github.comwrote:

yeah, I thought avoiding "eliminator" was in a style guide at some point. I've tried to use "induction" instead of "elimination" in the homotopy chapter.

— Reply to this email directly or view it on GitHubhttps://github.com/HoTT/book/issues/145#issuecomment-16547540 .

— Reply to this email directly or view it on GitHub.

[awodey]

er, "element"

On Apr 17, 2013, at 9:48 PM, steve awodey steveawodey@icloud.com wrote:

induction term?

On Apr 17, 2013, at 9:44 PM, Mike Shulman notifications@github.com wrote:

One problem is that we have recursion/recursor, elimination/eliminator, but induction/??

On Wed, Apr 17, 2013 at 9:39 PM, Dan Licata notifications@github.comwrote:

yeah, I thought avoiding "eliminator" was in a style guide at some point. I've tried to use "induction" instead of "elimination" in the homotopy chapter.

— Reply to this email directly or view it on GitHubhttps://github.com/HoTT/book/issues/145#issuecomment-16547540 .

— Reply to this email directly or view it on GitHub.

[mikeshulman]

We also talked about avoiding "term" for "element"...

On Wed, Apr 17, 2013 at 9:48 PM, Steve Awodey notifications@github.comwrote:

induction term?

On Apr 17, 2013, at 9:44 PM, Mike Shulman notifications@github.com wrote:

One problem is that we have recursion/recursor, elimination/eliminator, but induction/??

On Wed, Apr 17, 2013 at 9:39 PM, Dan Licata notifications@github.comwrote:

yeah, I thought avoiding "eliminator" was in a style guide at some point. I've tried to use "induction" instead of "elimination" in the homotopy chapter.

— Reply to this email directly or view it on GitHub< https://github.com/HoTT/book/issues/145#issuecomment-16547540> .

— Reply to this email directly or view it on GitHub.

— Reply to this email directly or view it on GitHubhttps://github.com/HoTT/book/issues/145#issuecomment-16548038 .

[dlicata335]

induction principle?

"by the eliminator for truncation, it suffices to show..." "by the induction principle for truncation, it suffices to show..."

[mikeshulman]

But can "induction principle" refer to the particular term

ind_N : forall (P : N -> Type) (d0 : P 0) (ds : forall n, P n -> P (S n)) (n : N), P n

?

On Wed, Apr 17, 2013 at 10:27 PM, Dan Licata notifications@github.comwrote:

induction principle?

"by the eliminator for truncation, it suffices to show..." "by the induction principle for truncation, it suffices to show..."

— Reply to this email directly or view it on GitHubhttps://github.com/HoTT/book/issues/145#issuecomment-16550149 .

[dlicata335]

I call that term "the induction principle for nat", yes. It's a bit of an abuse, because it's more precise to use "the induction principle" to refer to the type of that term. But it has a unique proof...

[mikeshulman]

I feel like we're also using the phrase "induction principle" to refer to the "rule" that allows us to define functions by a certain sort of pattern matching. But maybe it is okay to conflate the two, since the "rule" is equivalently an application of the term.

On Wed, Apr 17, 2013 at 10:34 PM, Dan Licata notifications@github.comwrote:

I call that term "the induction principle for nat", yes. It's a bit of an abuse, because it's more precise to use "the induction principle" to refer to the type of that term. But it has a unique proof...

— Reply to this email directly or view it on GitHubhttps://github.com/HoTT/book/issues/145#issuecomment-16550516 .

[dlicata335]

yeah, that's true. are there places where we care about the distinction? It seemed like we were pretty loose about pattern matching vs applying the elimination term. I think of the "rule" as being implemented by the elimination term.

What about coining "inductor"? It's no worse than "recursor".

[mikeshulman]

On Wed, Apr 17, 2013 at 10:47 PM, Dan Licata notifications@github.comwrote:

yeah, that's true. are there places where we care about the distinction? It seemed like we were pretty loose about pattern matching vs applying the elimination term. I think of the "rule" as being implemented by the elimination term.

I don't think there are. Maybe it would be simpler to do it this way. It would involve a little bit of rewriting here and there in chapters 1, 5, and 7.

What about coining "inductor"? It's no worse than "recursor".

I find that more of an argument against "recursor" than for "inductor"... (-:

[dlicata335]

Wait, I wasn't proposing changing the story to "the rule is implemented by the inductor"---I think "functions defined by cases" are clearer than "apply this eliminator/universal mapping property term". I meant that using "induction principle" to refer to either/both is OK, since we're being loose anyway.

[mikeshulman]

On Wed, Apr 17, 2013 at 11:06 PM, Dan Licata notifications@github.comwrote:

Wait, I wasn't proposing changing the story to "the rule is implemented by the inductor"

I wasn't really either. But I do find it kind of confusing to be told both that "we can define functions by cases in such-and-such a way" and "there is this operator which allows us to define functions". Does our type theory include both as basic notions? It seems cleaner to me to define one of them in terms of the other.

[dlicata335]

I thought the story for Chapter 1 and the first part of the appendix was "we can define functions by cases in such and such a way" is the basic notion (and then we observe that in particular we can define a universal such function), and that the story for the second part of the appendix was "there is this operator" is the basic notion.

[mikeshulman]

On Wed, Apr 17, 2013 at 11:21 PM, Dan Licata notifications@github.comwrote:

I thought the story for Chapter 1 and the first part of the appendix was "we can define functions by cases in such and such a way" is the basic notion (and then we observe that in particular we can define a universal such function),

That's a consistent story and one that I would support, but if that's the intent, it's not clear to me in chapter 1 at least. The phrase "we can package this principle into a constant" doesn't really convey a precise meaning to me. You seem to be suggesting that we should say instead something like the following.

"Rather than invoking the induction principle every time we want to define a function, we could instead invoke it once, in a universal case, and then simply apply the resulting function in all other cases. That is, we could define a function of type

ind_N : \prd{C:N->\UU}{c0 :C(0)}{cs : \prd{n:N} C(n) -> C(s(n))}{n:N} C(n)

with the defining equations:

ind_N(C,c0,cs,0) := c0 ind_N(C,c0,cs,s(n)) := cs(n,ind_N(C,c0,cs,n)).

Then instead of defining a function using the induction principle directly, such as

double(0) := 0 double(s(n)) := s(s(double(n)))

we could instead define it with an explicit definition in terms of ind_N:

double(n) := ind_N(N,0,\lam{k}{x} s(s(x)),n).

By abuse of language, we may also refer to ind_N as the 'induction principle' for N."

Does that sound right?

[dlicata335]

sounds right to me! I don't particularly care (or think it really matters) which is primitive, though I am in favor of picking one story rather than being ambiguous about it. Carlo and I asked Thorsten what he intended for Chapter 1 (when we were discussing the appendix) and my understanding is that this (functions defined by cases as primitive) was the intended story.

[mikeshulman]

Okay, I'll try to clarify chapter 1 then. And shall we try to eliminate "eliminator" in favor of "induction principle"?

On Wed, Apr 17, 2013 at 11:42 PM, Dan Licata notifications@github.comwrote:

sounds right to me! I don't particularly care (or think it really matters) which is primitive, though I am in favor of picking one story rather than being ambiguous about it. Carlo and I asked Thorsten what he intended for Chapter 1 (when we were discussing the appendix) and my understanding is that this (functions defined by cases as primitive) was the intended story.

— Reply to this email directly or view it on GitHubhttps://github.com/HoTT/book/issues/145#issuecomment-16554095 .

[awodey]

I would prefer to avoid the word "eliminator" anyway. If we're going to use induction principle, shouldn't we also use "recursion principle" in a parallel way? the word "recursor" could then just be slang.

On Apr 17, 2013, at 11:49 PM, Mike Shulman notifications@github.com wrote:

Okay, I'll try to clarify chapter 1 then. And shall we try to eliminate "eliminator" in favor of "induction principle"?

On Wed, Apr 17, 2013 at 11:42 PM, Dan Licata notifications@github.comwrote:

sounds right to me! I don't particularly care (or think it really matters) which is primitive, though I am in favor of picking one story rather than being ambiguous about it. Carlo and I asked Thorsten what he intended for Chapter 1 (when we were discussing the appendix) and my understanding is that this (functions defined by cases as primitive) was the intended story.

— Reply to this email directly or view it on GitHubhttps://github.com/HoTT/book/issues/145#issuecomment-16554095 .

— Reply to this email directly or view it on GitHub.

[mikeshulman]

On Wed, Apr 17, 2013 at 11:53 PM, Steve Awodey notifications@github.comwrote:

If we're going to use induction principle, shouldn't we also use "recursion principle" in a parallel way? the word "recursor" could then just be slang.

Okay by me.

[txa]

I am not happy with the current wording either. I would like to say recursor/eliminator and use induction principle for proofs using induction or equivalently structural recursive functions and pattern matching. My understanding is that the explanation that we can define function by (a restricted form of) pattern matching is primitive but can be captured by am elimination principle which is in a sense a universal function which captures this principle. Maybe this should be expressed more clearly.

Thorsten

Sent from my iPhone

On 18 Apr 2013, at 01:39, "Steve Awodey" notifications@github.com<mailto:notifications@github.com> wrote:

both terms occur often -- the former more often. shall we even try to be consistent?

— Reply to this email directly or view it on GitHubhttps://github.com/HoTT/book/issues/145.

[RobertHarper]

I'm with Thorsten here. This terminology is very familiar on the CS side, and I would prefer not to try to avoid it.

Bob

(sent from handheld)

On Apr 18, 2013, at 6:04, Thorsten Altenkirch notifications@github.com wrote:

I am not happy with the current wording either. I would like to say recursor/eliminator and use induction principle for proofs using induction or equivalently structural recursive functions and pattern matching. My understanding is that the explanation that we can define function by (a restricted form of) pattern matching is primitive but can be captured by am elimination principle which is in a sense a universal function which captures this principle. Maybe this should be expressed more clearly.

Thorsten

Sent from my iPhone

On 18 Apr 2013, at 01:39, "Steve Awodey" notifications@github.com<mailto:notifications@github.com> wrote:

both terms occur often -- the former more often. shall we even try to be consistent?

— Reply to this email directly or view it on GitHubhttps://github.com/HoTT/book/issues/145. — Reply to this email directly or view it on GitHub.

[mikeshulman]

Thorsten and Bob, I don't understand what you're saying. What is it in particular you would like to change about the wording I suggested? On Apr 18, 2013 7:56 AM, "Robert Harper" notifications@github.com wrote:

I'm with Thorsten here. This terminology is very familiar on the CS side, and I would prefer not to try to avoid it.

Bob

(sent from handheld)

On Apr 18, 2013, at 6:04, Thorsten Altenkirch notifications@github.com wrote:

I am not happy with the current wording either. I would like to say recursor/eliminator and use induction principle for proofs using induction or equivalently structural recursive functions and pattern matching. My understanding is that the explanation that we can define function by (a restricted form of) pattern matching is primitive but can be captured by am elimination principle which is in a sense a universal function which captures this principle. Maybe this should be expressed more clearly.

Thorsten

Sent from my iPhone

On 18 Apr 2013, at 01:39, "Steve Awodey" <notifications@github.com mailto:notifications@github.com> wrote:

both terms occur often -- the former more often. shall we even try to be consistent?

— Reply to this email directly or view it on GitHub< https://github.com/HoTT/book/issues/145>. — Reply to this email directly or view it on GitHub.

— Reply to this email directly or view it on GitHubhttps://github.com/HoTT/book/issues/145#issuecomment-16572236 .

[txa]

I was suggesting to revert to use the words eliminator and recursor and Bob seems to support this.

Rationale: induction principle should refer to the principle that allows us to define functions/proofs by induction. Induction term seems wrong, induction constant would be ok but isn't familiar to anybody. Hence why not adopt the standard terminology from type theory.

T.

From: Mike Shulman notifications@github.com<mailto:notifications@github.com> Reply-To: HoTT/book reply@reply.github.com<mailto:reply@reply.github.com> Date: Thu, 18 Apr 2013 13:03:05 +0100 To: HoTT/book book@noreply.github.com<mailto:book@noreply.github.com> Cc: Thorsten Altenkirch txa@Cs.Nott.AC.UK<mailto:txa@Cs.Nott.AC.UK> Subject: Re: [book] Chapter 1: "recursor" or "eliminator"? (#145)

Thorsten and Bob, I don't understand what you're saying. What is it in particular you would like to change about the wording I suggested? On Apr 18, 2013 7:56 AM, "Robert Harper" notifications@github.com<mailto:notifications@github.com> wrote:

I'm with Thorsten here. This terminology is very familiar on the CS side, and I would prefer not to try to avoid it.

Bob

(sent from handheld)

On Apr 18, 2013, at 6:04, Thorsten Altenkirch notifications@github.com<mailto:notifications@github.com> wrote:

I am not happy with the current wording either. I would like to say recursor/eliminator and use induction principle for proofs using induction or equivalently structural recursive functions and pattern matching. My understanding is that the explanation that we can define function by (a restricted form of) pattern matching is primitive but can be captured by am elimination principle which is in a sense a universal function which captures this principle. Maybe this should be expressed more clearly.

Thorsten

Sent from my iPhone

On 18 Apr 2013, at 01:39, "Steve Awodey" notifications@github.com<mailto:notifications@github.com mailto:notifications@github.com> wrote:

both terms occur often -- the former more often. shall we even try to be consistent?

— Reply to this email directly or view it on GitHub< https://github.com/HoTT/book/issues/145>. — Reply to this email directly or view it on GitHub.

— Reply to this email directly or view it on GitHubhttps://github.com/HoTT/book/issues/145#issuecomment-16572236 .

— Reply to this email directly or view it on GitHubhttps://github.com/HoTT/book/issues/145#issuecomment-16572494.

This message and any attachment are intended solely for the addressee and may contain confidential information. If you have received this message in error, please send it back to me, and immediately delete it. Please do not use, copy or disclose the information contained in this message or in any attachment. Any views or opinions expressed by the author of this email do not necessarily reflect the views of the University of Nottingham.

This message has been checked for viruses but the contents of an attachment

may still contain software viruses which could damage your computer system:

you are advised to perform your own checks. Email communications with the

University of Nottingham may be monitored as permitted by UK legislation.

[txa]

Very good!

From: Mike Shulman notifications@github.com<mailto:notifications@github.com> Reply-To: HoTT/book reply@reply.github.com<mailto:reply@reply.github.com> Date: Thu, 18 Apr 2013 04:33:12 +0100 To: HoTT/book book@noreply.github.com<mailto:book@noreply.github.com> Subject: Re: [book] Chapter 1: "recursor" or "eliminator"? (#145)

On Wed, Apr 17, 2013 at 11:21 PM, Dan Licata notifications@github.com<mailto:notifications@github.com>wrote:

I thought the story for Chapter 1 and the first part of the appendix was "we can define functions by cases in such and such a way" is the basic notion (and then we observe that in particular we can define a universal such function),

That's a consistent story and one that I would support, but if that's the intent, it's not clear to me in chapter 1 at least. The phrase "we can package this principle into a constant" doesn't really convey a precise meaning to me. You seem to be suggesting that we should say instead something like the following.

"Rather than invoking the induction principle every time we want to define a function, we could instead invoke it once, in a universal case, and then simply apply the resulting function in all other cases. That is, we could define a function of type

ind_N : \prd{C:N->\UU}{c0 :C(0)}{cs : \prd{n:N} C(n) -> C(s(n))}{n:N} C(n)

with the defining equations:

ind_N(C,c0,cs,0) := c0 ind_N(C,c0,cs,s(n)) := cs(n,ind_N(C,c0,cs,n)).

Then instead of defining a function using the induction principle directly, such as

double(0) := 0 double(s(n)) := s(s(double(n)))

we could instead define it with an explicit definition in terms of ind_N:

double(n) := ind_N(N,0,\lam{k}{x} s(s(x)),n).

By abuse of language, we may also refer to ind_N as the 'induction principle' for N."

Does that sound right?

— Reply to this email directly or view it on GitHubhttps://github.com/HoTT/book/issues/145#issuecomment-16553642.

This message and any attachment are intended solely for the addressee and may contain confidential information. If you have received this message in error, please send it back to me, and immediately delete it. Please do not use, copy or disclose the information contained in this message or in any attachment. Any views or opinions expressed by the author of this email do not necessarily reflect the views of the University of Nottingham.

This message has been checked for viruses but the contents of an attachment

may still contain software viruses which could damage your computer system:

you are advised to perform your own checks. Email communications with the

University of Nottingham may be monitored as permitted by UK legislation.

[awodey]

sorry, this doesn't answer the original question (look at the thread, guys!):

are we using the word "eliminator" OR "recursor" OR both (and then when)?

On Apr 18, 2013, at 11:24 AM, Thorsten Altenkirch notifications@github.com wrote:

I was suggesting to revert to use the words eliminator and recursor and Bob seems to support this.

Rationale: induction principle should refer to the principle that allows us to define functions/proofs by induction. Induction term seems wrong, induction constant would be ok but isn't familiar to anybody. Hence why not adopt the standard terminology from type theory.

T.

From: Mike Shulman notifications@github.com<mailto:notifications@github.com> Reply-To: HoTT/book reply@reply.github.com<mailto:reply@reply.github.com> Date: Thu, 18 Apr 2013 13:03:05 +0100 To: HoTT/book book@noreply.github.com<mailto:book@noreply.github.com> Cc: Thorsten Altenkirch txa@Cs.Nott.AC.UK<mailto:txa@Cs.Nott.AC.UK> Subject: Re: [book] Chapter 1: "recursor" or "eliminator"? (#145)

Thorsten and Bob, I don't understand what you're saying. What is it in particular you would like to change about the wording I suggested? On Apr 18, 2013 7:56 AM, "Robert Harper" notifications@github.com<mailto:notifications@github.com> wrote:

I'm with Thorsten here. This terminology is very familiar on the CS side, and I would prefer not to try to avoid it.

Bob

(sent from handheld)

On Apr 18, 2013, at 6:04, Thorsten Altenkirch notifications@github.com<mailto:notifications@github.com> wrote:

I am not happy with the current wording either. I would like to say recursor/eliminator and use induction principle for proofs using induction or equivalently structural recursive functions and pattern matching. My understanding is that the explanation that we can define function by (a restricted form of) pattern matching is primitive but can be captured by am elimination principle which is in a sense a universal function which captures this principle. Maybe this should be expressed more clearly.

Thorsten

Sent from my iPhone

On 18 Apr 2013, at 01:39, "Steve Awodey" notifications@github.com<mailto:notifications@github.com mailto:notifications@github.com> wrote:

both terms occur often -- the former more often. shall we even try to be consistent?

— Reply to this email directly or view it on GitHub< https://github.com/HoTT/book/issues/145>. — Reply to this email directly or view it on GitHub.

— Reply to this email directly or view it on GitHubhttps://github.com/HoTT/book/issues/145#issuecomment-16572236 .

— Reply to this email directly or view it on GitHubhttps://github.com/HoTT/book/issues/145#issuecomment-16572494.

This message and any attachment are intended solely for the addressee and may contain confidential information. If you have received this message in error, please send it back to me, and immediately delete it. Please do not use, copy or disclose the information contained in this message or in any attachment. Any views or opinions expressed by the author of this email do not necessarily reflect the views of the University of Nottingham.

This message has been checked for viruses but the contents of an attachment

may still contain software viruses which could damage your computer system:

you are advised to perform your own checks. Email communications with the

University of Nottingham may be monitored as permitted by UK legislation. — Reply to this email directly or view it on GitHub.

[mikeshulman]

Well, the argument was that "eliminator" sounds weird and technical to a mathematician. But I agree that aligning with standard terminology is also a good thing, unless there are strong reasons to change it. And we aren't really using the eliminator very much anyway; mostly in the book we talk about the induction principle. So I think I'm okay with calling it the eliminator where we mention it, but pointing out that we won't use it much.

By the way, I've been assuming that "recursor" applies only to the non-dependent eliminator, since in some contexts at least it is the non-dependent form of induction that's called "recursion". Is that correct or not?

On Thu, Apr 18, 2013 at 11:24 AM, Thorsten Altenkirch < notifications@github.com> wrote:

I was suggesting to revert to use the words eliminator and recursor and Bob seems to support this.

Rationale: induction principle should refer to the principle that allows us to define functions/proofs by induction. Induction term seems wrong, induction constant would be ok but isn't familiar to anybody. Hence why not adopt the standard terminology from type theory.

T.

From: Mike Shulman <notifications@github.com<mailto: notifications@github.com>> Reply-To: HoTT/book reply@reply.github.com<mailto:reply@reply.github.com>

Date: Thu, 18 Apr 2013 13:03:05 +0100 To: HoTT/book book@noreply.github.com<mailto:book@noreply.github.com> Cc: Thorsten Altenkirch txa@Cs.Nott.AC.UK<mailto:txa@Cs.Nott.AC.UK> Subject: Re: [book] Chapter 1: "recursor" or "eliminator"? (#145)

Thorsten and Bob, I don't understand what you're saying. What is it in particular you would like to change about the wording I suggested? On Apr 18, 2013 7:56 AM, "Robert Harper" <notifications@github.com<mailto: notifications@github.com>> wrote:

I'm with Thorsten here. This terminology is very familiar on the CS side, and I would prefer not to try to avoid it.

Bob

(sent from handheld)

On Apr 18, 2013, at 6:04, Thorsten Altenkirch <notifications@github.com mailto:notifications@github.com> wrote:

I am not happy with the current wording either. I would like to say recursor/eliminator and use induction principle for proofs using induction or equivalently structural recursive functions and pattern matching. My understanding is that the explanation that we can define function by (a restricted form of) pattern matching is primitive but can be captured by am elimination principle which is in a sense a universal function which captures this principle. Maybe this should be expressed more clearly.

Thorsten

Sent from my iPhone

On 18 Apr 2013, at 01:39, "Steve Awodey" <notifications@github.com mailto:notifications@github.com mailto:notifications@github.com> wrote:

both terms occur often -- the former more often. shall we even try to be consistent?

— Reply to this email directly or view it on GitHub< https://github.com/HoTT/book/issues/145>. — Reply to this email directly or view it on GitHub.

— Reply to this email directly or view it on GitHub< https://github.com/HoTT/book/issues/145#issuecomment-16572236> .

— Reply to this email directly or view it on GitHub< https://github.com/HoTT/book/issues/145#issuecomment-16572494>.

This message and any attachment are intended solely for the addressee and may contain confidential information. If you have received this message in error, please send it back to me, and immediately delete it. Please do not use, copy or disclose the information contained in this message or in any attachment. Any views or opinions expressed by the author of this email do not necessarily reflect the views of the University of Nottingham.

This message has been checked for viruses but the contents of an attachment

may still contain software viruses which could damage your computer system:

you are advised to perform your own checks. Email communications with the

University of Nottingham may be monitored as permitted by UK legislation.

— Reply to this email directly or view it on GitHubhttps://github.com/HoTT/book/issues/145#issuecomment-16583200 .

[txa]

Answer: we should be using eliminator for the dependent elimination constant recursor for the special non-dependent However, in the moment we are using "induction principle" for "eliminator". I think we should change that.

Thorsten

From: Steve Awodey notifications@github.com<mailto:notifications@github.com> Reply-To: HoTT/book reply@reply.github.com<mailto:reply@reply.github.com> Date: Thu, 18 Apr 2013 16:29:09 +0100 To: HoTT/book book@noreply.github.com<mailto:book@noreply.github.com> Cc: Thorsten Altenkirch txa@Cs.Nott.AC.UK<mailto:txa@Cs.Nott.AC.UK> Subject: Re: [book] Chapter 1: "recursor" or "eliminator"? (#145)

sorry, this doesn't answer the original question (look at the thread, guys!):

are we using the word "eliminator" OR "recursor" OR both (and then when)?

On Apr 18, 2013, at 11:24 AM, Thorsten Altenkirch notifications@github.com<mailto:notifications@github.com> wrote:

I was suggesting to revert to use the words eliminator and recursor and Bob seems to support this.

Rationale: induction principle should refer to the principle that allows us to define functions/proofs by induction. Induction term seems wrong, induction constant would be ok but isn't familiar to anybody. Hence why not adopt the standard terminology from type theory.

T.

From: Mike Shulman notifications@github.com<mailto:notifications@github.commailto:notifications@github.com> Reply-To: HoTT/book reply@reply.github.com<mailto:reply@reply.github.commailto:reply@reply.github.com> Date: Thu, 18 Apr 2013 13:03:05 +0100 To: HoTT/book book@noreply.github.com<mailto:book@noreply.github.commailto:book@noreply.github.com> Cc: Thorsten Altenkirch txa@Cs.Nott.AC.UK<mailto:txa@Cs.Nott.AC.UKmailto:txa@Cs.Nott.AC.UK> Subject: Re: [book] Chapter 1: "recursor" or "eliminator"? (#145)

Thorsten and Bob, I don't understand what you're saying. What is it in particular you would like to change about the wording I suggested? On Apr 18, 2013 7:56 AM, "Robert Harper" notifications@github.com<mailto:notifications@github.commailto:notifications@github.com> wrote:

I'm with Thorsten here. This terminology is very familiar on the CS side, and I would prefer not to try to avoid it.

Bob

(sent from handheld)

On Apr 18, 2013, at 6:04, Thorsten Altenkirch notifications@github.com<mailto:notifications@github.commailto:notifications@github.com> wrote:

I am not happy with the current wording either. I would like to say recursor/eliminator and use induction principle for proofs using induction or equivalently structural recursive functions and pattern matching. My understanding is that the explanation that we can define function by (a restricted form of) pattern matching is primitive but can be captured by am elimination principle which is in a sense a universal function which captures this principle. Maybe this should be expressed more clearly.

Thorsten

Sent from my iPhone

On 18 Apr 2013, at 01:39, "Steve Awodey" notifications@github.com<mailto:notifications@github.commailto:notifications@github.com mailto:notifications@github.com> wrote:

both terms occur often -- the former more often. shall we even try to be consistent?

— Reply to this email directly or view it on GitHub< https://github.com/HoTT/book/issues/145>. — Reply to this email directly or view it on GitHub.

— Reply to this email directly or view it on GitHubhttps://github.com/HoTT/book/issues/145#issuecomment-16572236 .

— Reply to this email directly or view it on GitHubhttps://github.com/HoTT/book/issues/145#issuecomment-16572494.

This message and any attachment are intended solely for the addressee and may contain confidential information. If you have received this message in error, please send it back to me, and immediately delete it. Please do not use, copy or disclose the information contained in this message or in any attachment. Any views or opinions expressed by the author of this email do not necessarily reflect the views of the University of Nottingham.

This message has been checked for viruses but the contents of an attachment

may still contain software viruses which could damage your computer system:

you are advised to perform your own checks. Email communications with the

University of Nottingham may be monitored as permitted by UK legislation. — Reply to this email directly or view it on GitHub.

— Reply to this email directly or view it on GitHubhttps://github.com/HoTT/book/issues/145#issuecomment-16583504.

This message and any attachment are intended solely for the addressee and may contain confidential information. If you have received this message in error, please send it back to me, and immediately delete it. Please do not use, copy or disclose the information contained in this message or in any attachment. Any views or opinions expressed by the author of this email do not necessarily reflect the views of the University of Nottingham.

This message has been checked for viruses but the contents of an attachment

may still contain software viruses which could damage your computer system:

you are advised to perform your own checks. Email communications with the

University of Nottingham may be monitored as permitted by UK legislation.

[txa]

That's correct – however one may say "structural recursion" to make clear that we don't mean "general recursion" (this may confuse the potential CS reader).

T.

From: Mike Shulman notifications@github.com<mailto:notifications@github.com> Reply-To: HoTT/book reply@reply.github.com<mailto:reply@reply.github.com> Date: Thu, 18 Apr 2013 16:31:28 +0100 To: HoTT/book book@noreply.github.com<mailto:book@noreply.github.com> Cc: Thorsten Altenkirch txa@Cs.Nott.AC.UK<mailto:txa@Cs.Nott.AC.UK> Subject: Re: [book] Chapter 1: "recursor" or "eliminator"? (#145)

Well, the argument was that "eliminator" sounds weird and technical to a mathematician. But I agree that aligning with standard terminology is also a good thing, unless there are strong reasons to change it. And we aren't really using the eliminator very much anyway; mostly in the book we talk about the induction principle. So I think I'm okay with calling it the eliminator where we mention it, but pointing out that we won't use it much.

By the way, I've been assuming that "recursor" applies only to the non-dependent eliminator, since in some contexts at least it is the non-dependent form of induction that's called "recursion". Is that correct or not?

On Thu, Apr 18, 2013 at 11:24 AM, Thorsten Altenkirch < notifications@github.commailto:notifications@github.com> wrote:

I was suggesting to revert to use the words eliminator and recursor and Bob seems to support this.

Rationale: induction principle should refer to the principle that allows us to define functions/proofs by induction. Induction term seems wrong, induction constant would be ok but isn't familiar to anybody. Hence why not adopt the standard terminology from type theory.

T.

From: Mike Shulman notifications@github.com<mailto:notifications@github.com<mailto: notifications@github.commailto:notifications@github.com>> Reply-To: HoTT/book reply@reply.github.com<mailto:reply@reply.github.commailto:reply@reply.github.com>

Date: Thu, 18 Apr 2013 13:03:05 +0100 To: HoTT/book book@noreply.github.com<mailto:book@noreply.github.commailto:book@noreply.github.com> Cc: Thorsten Altenkirch txa@Cs.Nott.AC.UK<mailto:txa@Cs.Nott.AC.UKmailto:txa@Cs.Nott.AC.UK> Subject: Re: [book] Chapter 1: "recursor" or "eliminator"? (#145)

Thorsten and Bob, I don't understand what you're saying. What is it in particular you would like to change about the wording I suggested? On Apr 18, 2013 7:56 AM, "Robert Harper" notifications@github.com<mailto:notifications@github.com<mailto: notifications@github.commailto:notifications@github.com>> wrote:

I'm with Thorsten here. This terminology is very familiar on the CS side, and I would prefer not to try to avoid it.

Bob

(sent from handheld)

On Apr 18, 2013, at 6:04, Thorsten Altenkirch notifications@github.com<mailto:notifications@github.com mailto:notifications@github.com> wrote:

I am not happy with the current wording either. I would like to say recursor/eliminator and use induction principle for proofs using induction or equivalently structural recursive functions and pattern matching. My understanding is that the explanation that we can define function by (a restricted form of) pattern matching is primitive but can be captured by am elimination principle which is in a sense a universal function which captures this principle. Maybe this should be expressed more clearly.

Thorsten

Sent from my iPhone

On 18 Apr 2013, at 01:39, "Steve Awodey" notifications@github.com<mailto:notifications@github.com mailto:notifications@github.com mailto:notifications@github.com> wrote:

both terms occur often -- the former more often. shall we even try to be consistent?

— Reply to this email directly or view it on GitHub< https://github.com/HoTT/book/issues/145>. — Reply to this email directly or view it on GitHub.

— Reply to this email directly or view it on GitHub< https://github.com/HoTT/book/issues/145#issuecomment-16572236> .

— Reply to this email directly or view it on GitHub< https://github.com/HoTT/book/issues/145#issuecomment-16572494>.

This message and any attachment are intended solely for the addressee and may contain confidential information. If you have received this message in error, please send it back to me, and immediately delete it. Please do not use, copy or disclose the information contained in this message or in any attachment. Any views or opinions expressed by the author of this email do not necessarily reflect the views of the University of Nottingham.

This message has been checked for viruses but the contents of an attachment

may still contain software viruses which could damage your computer system:

you are advised to perform your own checks. Email communications with the

University of Nottingham may be monitored as permitted by UK legislation.

— Reply to this email directly or view it on GitHubhttps://github.com/HoTT/book/issues/145#issuecomment-16583200 .

— Reply to this email directly or view it on GitHubhttps://github.com/HoTT/book/issues/145#issuecomment-16583633.

This message and any attachment are intended solely for the addressee and may contain confidential information. If you have received this message in error, please send it back to me, and immediately delete it. Please do not use, copy or disclose the information contained in this message or in any attachment. Any views or opinions expressed by the author of this email do not necessarily reflect the views of the University of Nottingham.

This message has been checked for viruses but the contents of an attachment

may still contain software viruses which could damage your computer system:

you are advised to perform your own checks. Email communications with the

University of Nottingham may be monitored as permitted by UK legislation.

[awodey]

thanks! will you please check it for consistency and revise as needed?

On Apr 18, 2013, at 11:38 AM, Thorsten Altenkirch notifications@github.com wrote:

Answer: we should be using eliminator for the dependent elimination constant recursor for the special non-dependent However, in the moment we are using "induction principle" for "eliminator". I think we should change that.

Thorsten

From: Steve Awodey notifications@github.com<mailto:notifications@github.com> Reply-To: HoTT/book reply@reply.github.com<mailto:reply@reply.github.com> Date: Thu, 18 Apr 2013 16:29:09 +0100 To: HoTT/book book@noreply.github.com<mailto:book@noreply.github.com> Cc: Thorsten Altenkirch txa@Cs.Nott.AC.UK<mailto:txa@Cs.Nott.AC.UK> Subject: Re: [book] Chapter 1: "recursor" or "eliminator"? (#145)

sorry, this doesn't answer the original question (look at the thread, guys!):

are we using the word "eliminator" OR "recursor" OR both (and then when)?

On Apr 18, 2013, at 11:24 AM, Thorsten Altenkirch notifications@github.com<mailto:notifications@github.com> wrote:

I was suggesting to revert to use the words eliminator and recursor and Bob seems to support this.

Rationale: induction principle should refer to the principle that allows us to define functions/proofs by induction. Induction term seems wrong, induction constant would be ok but isn't familiar to anybody. Hence why not adopt the standard terminology from type theory.

T.

From: Mike Shulman notifications@github.com<mailto:notifications@github.commailto:notifications@github.com> Reply-To: HoTT/book reply@reply.github.com<mailto:reply@reply.github.commailto:reply@reply.github.com> Date: Thu, 18 Apr 2013 13:03:05 +0100 To: HoTT/book book@noreply.github.com<mailto:book@noreply.github.commailto:book@noreply.github.com> Cc: Thorsten Altenkirch txa@Cs.Nott.AC.UK<mailto:txa@Cs.Nott.AC.UKmailto:txa@Cs.Nott.AC.UK> Subject: Re: [book] Chapter 1: "recursor" or "eliminator"? (#145)

Thorsten and Bob, I don't understand what you're saying. What is it in particular you would like to change about the wording I suggested? On Apr 18, 2013 7:56 AM, "Robert Harper" notifications@github.com<mailto:notifications@github.commailto:notifications@github.com> wrote:

I'm with Thorsten here. This terminology is very familiar on the CS side, and I would prefer not to try to avoid it.

Bob

(sent from handheld)

On Apr 18, 2013, at 6:04, Thorsten Altenkirch notifications@github.com<mailto:notifications@github.commailto:notifications@github.com> wrote:

I am not happy with the current wording either. I would like to say recursor/eliminator and use induction principle for proofs using induction or equivalently structural recursive functions and pattern matching. My understanding is that the explanation that we can define function by (a restricted form of) pattern matching is primitive but can be captured by am elimination principle which is in a sense a universal function which captures this principle. Maybe this should be expressed more clearly.

Thorsten

Sent from my iPhone

On 18 Apr 2013, at 01:39, "Steve Awodey" notifications@github.com<mailto:notifications@github.commailto:notifications@github.com mailto:notifications@github.com> wrote:

both terms occur often -- the former more often. shall we even try to be consistent?

— Reply to this email directly or view it on GitHub< https://github.com/HoTT/book/issues/145>. — Reply to this email directly or view it on GitHub.

— Reply to this email directly or view it on GitHubhttps://github.com/HoTT/book/issues/145#issuecomment-16572236 .

— Reply to this email directly or view it on GitHubhttps://github.com/HoTT/book/issues/145#issuecomment-16572494.

This message and any attachment are intended solely for the addressee and may contain confidential information. If you have received this message in error, please send it back to me, and immediately delete it. Please do not use, copy or disclose the information contained in this message or in any attachment. Any views or opinions expressed by the author of this email do not necessarily reflect the views of the University of Nottingham.

This message has been checked for viruses but the contents of an attachment

may still contain software viruses which could damage your computer system:

you are advised to perform your own checks. Email communications with the

University of Nottingham may be monitored as permitted by UK legislation. — Reply to this email directly or view it on GitHub.

— Reply to this email directly or view it on GitHubhttps://github.com/HoTT/book/issues/145#issuecomment-16583504.

This message and any attachment are intended solely for the addressee and may contain confidential information. If you have received this message in error, please send it back to me, and immediately delete it. Please do not use, copy or disclose the information contained in this message or in any attachment. Any views or opinions expressed by the author of this email do not necessarily reflect the views of the University of Nottingham.

This message has been checked for viruses but the contents of an attachment

may still contain software viruses which could damage your computer system:

you are advised to perform your own checks. Email communications with the

University of Nottingham may be monitored as permitted by UK legislation. — Reply to this email directly or view it on GitHub.

[txa]

ok I will do it.

[RobertHarper]

What he said.

(sent from handheld)

On Apr 18, 2013, at 11:24, Thorsten Altenkirch notifications@github.com wrote:

I was suggesting to revert to use the words eliminator and recursor and Bob seems to support this.

Rationale: induction principle should refer to the principle that allows us to define functions/proofs by induction. Induction term seems wrong, induction constant would be ok but isn't familiar to anybody. Hence why not adopt the standard terminology from type theory.

T.

From: Mike Shulman notifications@github.com<mailto:notifications@github.com> Reply-To: HoTT/book reply@reply.github.com<mailto:reply@reply.github.com> Date: Thu, 18 Apr 2013 13:03:05 +0100 To: HoTT/book book@noreply.github.com<mailto:book@noreply.github.com> Cc: Thorsten Altenkirch txa@Cs.Nott.AC.UK<mailto:txa@Cs.Nott.AC.UK> Subject: Re: [book] Chapter 1: "recursor" or "eliminator"? (#145)

Thorsten and Bob, I don't understand what you're saying. What is it in particular you would like to change about the wording I suggested? On Apr 18, 2013 7:56 AM, "Robert Harper" notifications@github.com<mailto:notifications@github.com> wrote:

I'm with Thorsten here. This terminology is very familiar on the CS side, and I would prefer not to try to avoid it.

Bob

(sent from handheld)

On Apr 18, 2013, at 6:04, Thorsten Altenkirch notifications@github.com<mailto:notifications@github.com> wrote:

I am not happy with the current wording either. I would like to say recursor/eliminator and use induction principle for proofs using induction or equivalently structural recursive functions and pattern matching. My understanding is that the explanation that we can define function by (a restricted form of) pattern matching is primitive but can be captured by am elimination principle which is in a sense a universal function which captures this principle. Maybe this should be expressed more clearly.

Thorsten

Sent from my iPhone

On 18 Apr 2013, at 01:39, "Steve Awodey" notifications@github.com<mailto:notifications@github.com mailto:notifications@github.com> wrote:

both terms occur often -- the former more often. shall we even try to be consistent?

— Reply to this email directly or view it on GitHub< https://github.com/HoTT/book/issues/145>. — Reply to this email directly or view it on GitHub.

— Reply to this email directly or view it on GitHubhttps://github.com/HoTT/book/issues/145#issuecomment-16572236 .

— Reply to this email directly or view it on GitHubhttps://github.com/HoTT/book/issues/145#issuecomment-16572494.

This message and any attachment are intended solely for the addressee and may contain confidential information. If you have received this message in error, please send it back to me, and immediately delete it. Please do not use, copy or disclose the information contained in this message or in any attachment. Any views or opinions expressed by the author of this email do not necessarily reflect the views of the University of Nottingham.

This message has been checked for viruses but the contents of an attachment

may still contain software viruses which could damage your computer system:

you are advised to perform your own checks. Email communications with the

University of Nottingham may be monitored as permitted by UK legislation. — Reply to this email directly or view it on GitHub.

[RobertHarper]

Typically "recursor" is used only for the eliminator of an inductive type; application is an eliminator, not a recursor. Coinductive eliminators are corecursors, btw.

(sent from handheld)

On Apr 18, 2013, at 11:31, Mike Shulman notifications@github.com wrote:

Well, the argument was that "eliminator" sounds weird and technical to a mathematician. But I agree that aligning with standard terminology is also a good thing, unless there are strong reasons to change it. And we aren't really using the eliminator very much anyway; mostly in the book we talk about the induction principle. So I think I'm okay with calling it the eliminator where we mention it, but pointing out that we won't use it much.

By the way, I've been assuming that "recursor" applies only to the non-dependent eliminator, since in some contexts at least it is the non-dependent form of induction that's called "recursion". Is that correct or not?

On Thu, Apr 18, 2013 at 11:24 AM, Thorsten Altenkirch < notifications@github.com> wrote:

I was suggesting to revert to use the words eliminator and recursor and Bob seems to support this.

Rationale: induction principle should refer to the principle that allows us to define functions/proofs by induction. Induction term seems wrong, induction constant would be ok but isn't familiar to anybody. Hence why not adopt the standard terminology from type theory.

T.

From: Mike Shulman <notifications@github.com<mailto: notifications@github.com>> Reply-To: HoTT/book reply@reply.github.com<mailto:reply@reply.github.com>

Date: Thu, 18 Apr 2013 13:03:05 +0100 To: HoTT/book book@noreply.github.com<mailto:book@noreply.github.com> Cc: Thorsten Altenkirch txa@Cs.Nott.AC.UK<mailto:txa@Cs.Nott.AC.UK> Subject: Re: [book] Chapter 1: "recursor" or "eliminator"? (#145)

Thorsten and Bob, I don't understand what you're saying. What is it in particular you would like to change about the wording I suggested? On Apr 18, 2013 7:56 AM, "Robert Harper" <notifications@github.com<mailto: notifications@github.com>> wrote:

I'm with Thorsten here. This terminology is very familiar on the CS side, and I would prefer not to try to avoid it.

Bob

(sent from handheld)

On Apr 18, 2013, at 6:04, Thorsten Altenkirch <notifications@github.com mailto:notifications@github.com> wrote:

I am not happy with the current wording either. I would like to say recursor/eliminator and use induction principle for proofs using induction or equivalently structural recursive functions and pattern matching. My understanding is that the explanation that we can define function by (a restricted form of) pattern matching is primitive but can be captured by am elimination principle which is in a sense a universal function which captures this principle. Maybe this should be expressed more clearly.

Thorsten

Sent from my iPhone

On 18 Apr 2013, at 01:39, "Steve Awodey" <notifications@github.com mailto:notifications@github.com mailto:notifications@github.com> wrote:

both terms occur often -- the former more often. shall we even try to be consistent?

— Reply to this email directly or view it on GitHub< https://github.com/HoTT/book/issues/145>. — Reply to this email directly or view it on GitHub.

— Reply to this email directly or view it on GitHub< https://github.com/HoTT/book/issues/145#issuecomment-16572236> .

— Reply to this email directly or view it on GitHub< https://github.com/HoTT/book/issues/145#issuecomment-16572494>.

This message and any attachment are intended solely for the addressee and may contain confidential information. If you have received this message in error, please send it back to me, and immediately delete it. Please do not use, copy or disclose the information contained in this message or in any attachment. Any views or opinions expressed by the author of this email do not necessarily reflect the views of the University of Nottingham.

This message has been checked for viruses but the contents of an attachment

may still contain software viruses which could damage your computer system:

you are advised to perform your own checks. Email communications with the

University of Nottingham may be monitored as permitted by UK legislation.

— Reply to this email directly or view it on GitHubhttps://github.com/HoTT/book/issues/145#issuecomment-16583200 .

— Reply to this email directly or view it on GitHub.

[tac-tics]

Speaking of coinductive types, are there no plans to mention coalgebraic data types in the text?

It seems like it would be a shame not to at least give a brief mention, since they are the backbone of functional programming, and a bridge between theory and application.

[awodey]

we don't have anything to say about them -- no one has investigated them yet.

On Apr 18, 2013, at 12:13 PM, tac-tics notifications@github.com wrote:

Speaking of coinductive types, are there no plans to mention coalgebraic data types in the text?

It seems like it would be a shame not to at least give a brief mention, since they are the backbone of functional programming, and a bridge between theory and application.

— Reply to this email directly or view it on GitHub.

[andrejbauer]

Who are thou, rabbit?

[awodey]

Oh wait, Thorsten -- maybe Mike is already on it?

[txa]

Since we are not using coinductive types there is no need to introduce them. However, we should mention this in the notes to chapter 1.

[tac-tics]

@andrejbauer I'm just an eager spectator. And one who has gotten hung up on coinductive proofs in Agda more times than he can count.

[txa]

Eager spectators are ok but shouldn't be anonymous. Or keep quiet. Btw what is wrong with coinduction in Agda?

[tac-tics]

Well, my name is Michael Maloney. I'm a big fan of everyone's work here. I am interested in type theory as a tool for teaching mathematics in a computer-aided fashion.

There's nothing wrong with coinduction with Agda. But there's definitely a broken symmetry between inductive types and coinductive types in type theory, and I am hoping to learn more about it as more people study it.

But I don't mean to derail this thread. I just thought it would be worthwhile to at least mention (to use the new terminology in the text) 'the mere existence of coinductive types' :)

[RobertHarper]

I'm not sure what the decision was here. I use eliminator as a general term for any type, and restrict recursor to inductive types. Since the NuPRL days we made no distinction between a dependent and a non-dependent eliminator for an inductive type; a recursor is a recursor no matter whether the typing is dependent or not. For this reason I find it odd to say things like "the recursor or for the unit type is not useful, but the induction principle is". I have no objection to using the two terms interchangeably (recursor and induction principle or possibly inductor), but I don't consider it standard to be distinguishing the dependent from the non-dependent case. We never did this in NuPRL, nor did Martin-Loef in the earliest papers afaicr.

Are we all ok with that?

[dlicata335]

It's helpful to distinguish the two for higher inductives, because the path cases have simpler types for the "recursion principle" than for the "induction principle" instantiated with a constant fibration. It's good to have different names for the two, and to set up this distinction in chapter 1. I think I got the convention of D-rec (recursion = simply typed) vs. D-elim/D-ind (induction = dependently typed) from Epigram.

[mikeshulman]

Can this be closed?

[dlicata335]

it looks to me like the current version is consistent ("eliminator" is general, "recursor" gets used only for simply-typed elim, "induction" only for dependent elim), so i vote close

[mikeshulman]

I say two votes to close make a quorum; anyone who objects can reopen it.

[awodey]

so we're using both eliminator and recursor -- that was my original question: why do we need the term "eliminator" at all?

[mikeshulman]

I think the answer is because it's standard in type theory. We may not want to use it a lot, but we should at least mention it to expose the reader to it.

[RobertHarper]

recursors are the eliminators for inductive types. application is not a recursor, its an eliminator, for example. were we to have coinductive types, their intro's would be corecursors.

bob

On Apr 26, 2013, at 5:14 PM, Steve Awodey wrote:

so we're using both eliminator and recursor -- that was my original question: why do we need the term "eliminator" at all?

— Reply to this email directly or view it on GitHub.