From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/1670 Path: news.gmane.org!not-for-mail From: jesse@andrew.cmu.edu (Jesse F. Hughes) Newsgroups: gmane.science.mathematics.categories Subject: Re: coinduction: definable equationally? Date: 28 Oct 2000 16:54:59 -0400 Message-ID: <87bsw4wusc.fsf@phiwumbda.dyndns.org> References: <200010280923.CAA10190@coraki.Stanford.EDU> NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII X-Trace: ger.gmane.org 1241018009 32346 80.91.229.2 (29 Apr 2009 15:13:29 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 29 Apr 2009 15:13:29 +0000 (UTC) To: "Categories@Mta. Ca" Original-X-From: rrosebru@mta.ca Sun Oct 29 20:04:16 2000 -0400 Return-Path: Original-Received: (from Majordom@localhost) by mailserv.mta.ca (8.11.1/8.11.1) id e9TNKwN24211 for categories-list; Sun, 29 Oct 2000 19:20:58 -0400 (AST) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f X-Authentication-Warning: phiwumbda.dyndns.org: jesse set sender to jesse@andrew.cmu.edu using -f Mail-Copies-To: poster In-Reply-To: Vaughan Pratt's message of "Sat, 28 Oct 2000 02:23:02 -0700" User-Agent: Gnus/5.0807 (Gnus v5.8.7) XEmacs/21.1 (Carlsbad Caverns) Original-Sender: cat-dist@mta.ca Precedence: bulk X-Keywords: X-UID: 28 Original-Lines: 37 Xref: news.gmane.org gmane.science.mathematics.categories:1670 Archived-At: Vaughan Pratt writes: > 1. Is there a variety embedding coinduction? > > Jesse Hughes distinguishes induction from recursion in terms of natural > numbers. For him induction is Peano's mathematical induction, while > recursion is the uniqueness of the map from the (unique up to a unique > isomorphism) initial algebra to an arbitrary algebra. > This doesn't look like what I had in mind, exactly. Peano's mathematical induction was meant as an example of induction, not the whole meaning of induction. I stated induction in terms of natural numbers only to continue Dusko's example. I'm afraid that I was a bit vague in what exactly induction is in my previous post. I say that a G-algebra A satisfies the principle of induction just in case every mono G-homomorphism into A is an isomorphism. If our base category has equalizers, then A satisfies the principle of induction just in case, for every algebra B, there is at most one homomorphism A -> B. So induction is the uniqueness part of initiality. What's recursion, then? As far as I'm concerned, recursion is just initiality. I.e., an algebra A satisfies the principle of definition by recursion just in case it is the initial algebra. (Why not take recursion to be just the existence part? I haven't seen much use for just the existence part and it also doesn't fit well with conventional usage.) Clearly, on this view, the principle of recursion implies the principle of induction, but the converse is not the case. I hope that my idea of induction is a bit clearer. I really must learn to write more precisely. -- Jesse Hughes "Such behaviour is exclusively confined to functions invented by mathematicians for the sake of causing trouble." -Albert Eagle's _A Practical Treatise on Fourier's Theorem_