From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/2215 Path: news.gmane.org!not-for-mail From: Alex Simpson Newsgroups: gmane.science.mathematics.categories Subject: Re: Inductive datatypes in toposes Date: Tue, 04 Mar 2003 01:49:36 +0000 (GMT) Message-ID: <1046742576.3e640630a95fb@mail.inf.ed.ac.uk> References: <200303031730.SAA17354@fb04209.mathematik.tu-darmstadt.de> NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Trace: ger.gmane.org 1241018501 3076 80.91.229.2 (29 Apr 2009 15:21:41 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 29 Apr 2009 15:21:41 +0000 (UTC) To: categories@mta.ca Original-X-From: rrosebru@mta.ca Tue Mar 4 07:58:12 2003 -0400 Return-path: Envelope-to: categories-list@mta.ca Delivery-date: Tue, 04 Mar 2003 07:58:12 -0400 Original-Received: from Majordom by mailserv.mta.ca with local (Exim 4.10) id 18qAx3-0001hQ-00 for categories-list@mta.ca; Tue, 04 Mar 2003 07:51:17 -0400 X-Authentication-Warning: topper.inf.ed.ac.uk: apache set sender to als@localhost using -f In-Reply-To: <200303031730.SAA17354@fb04209.mathematik.tu-darmstadt.de> User-Agent: IMP/PHP IMAP webmail program 2.2.8 X-Originating-IP: 130.54.16.90 Original-Sender: cat-dist@mta.ca Precedence: bulk X-Keywords: X-UID: 5 Original-Lines: 38 Xref: news.gmane.org gmane.science.mathematics.categories:2215 Archived-At: Lutz Schroeder asked: > > is there a good reference for the construction of inductive > datatypes > > (lists, trees etc.) in a topos with nno (assuming that my guess that > > such a construction is indeed possible is correct)? Thomas Streicher replied: > It is not clear to me to which extent one can characterise those > inductive > types that can be reduced to inductively defined predicates in HAH. > However, one knows that assuming W-types (`a la Martin-Loef) one can > reduce > most inductive types to W-types in extensional type theory. As far as > I > understand that's the reason why Moerdijk and Palmgren introduced lccc's > with > W-types as sort of ``predicative toposes''. Just to point out that "assuming W-types" here is no extra assumption. Moerdijk and Palmgren observe that every elementary topos with nno has W-types. This observation more than answers Schroeder's original question affirmatively. See Moerdijk and Palmgren, "Well-founded trees in categories", APAL 104, 2000, for the observation. I'm not sure whether they include the details (I don't have the paper to hand), but it's not a hard exercise. Alex Simpson Alex Simpson, LFCS, Division of Informatics, Univ. of Edinburgh Email: Alex.Simpson@ed.ac.uk Tel: +44 (0)131 650 5113 Web: http://www.dcs.ed.ac.uk/home/als Fax: +44 (0)131 667 7209